Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Лекція 4. Симплекс-метод вирiшення задач лінiйного програмування. Табличний алгоритм пошуку оптимального рiшення ОЗЛП.






 

 

Одне з рішень (допустимих):

 

 

Якщо знайдено допустиме рішення, то для його покращення необхідно зменшити С. xj зменшити не можна. Тому зменшити С можна тільки в тому випадку, якщо збільшити значення хj з від’ємним коефіцієнтом aj. Тобто якщо всі коефіцієнти С будуть додатні, то отримане рішення буде оптимальним.

Для покращення рішення вільну змінну xj з від’ємним коефіцієнтом у цільовій вункції необхідно зробити базисною (> 0), а ту в свою чергу – вільною (заміна змінних). Міняти вільну змінну треба на ту з базисних, котра раніше за інших обернеться в 0 при даному значенні xj. Вибір залежить від мінімуму {наприклад для збільшення х2 }.

Наприклад, міняємо х2 на у2 (якщо ). Для заміни необхідно вирішити рівняння відносно попередньої вільної змінної х2. Отримаємо:

Потім необхідно підставити значення х2 у всі інші рівняння системи і цільову функцію. Після приведення подібних отримаємо m рівнянь з у2 замість х2.

Для полегшення розрахунків ці перетворення щодо заміни змінних було виконано аналітично в загальному вигляді, а потім з них вивели правило, яке дозволяє автоматично робити заміну.Було отримано табличний алгоритм заміни змінних, в якому всі дії виконуються не з рівняннями, а з таблицями коефіцієнтів рівнянь.

Для того, щоб скласти цю таблицю необхідно всі рівняння та цільову функцію привести до вигляду:

l11 = – a11

b1 = – a1

Вільні змінні

 
 

 


Цільова функція

Вільні члени х1 х2 ... хn
C a0 b1 b2 ... bn
у1 b1 l11 l12 ... l1n
Базисні перемінні
у2

b2 l21 l22 ... l2n
... ... ... ... ... ...
уm bm lm1 lm2 ... lmn

1 етап. Пошук допустимого рішення.

Вільні змінні дорівнюють 0, а базисні дорівнюють відповідним вільним членам. Отже, якщо всі вільні члени ³ 0, то рішення – допустиме.

Якщо один з них < 0, то виконується заміна змінних.

2 етап. Пошук оптимального рішення.

Якщо всі коефіцієнти цільової функції будуть ³ 0, то виконується пошук оптимального рішення за допомогою заміни змінних.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал