Лекція 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, то виконується пошук оптимального рішення за допомогою заміни змінних.

 








Дата добавления: 2015-12-22; просмотров: 736;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

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

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.