lta:=0; z4:=0; z5:=0 ;:=(a [1,1] * x3 + a [2,1] * x4 + a [3,1] * x5) - z1 ;:=(a [1,2] * x3 + a [2,2] * x4 + a [3,2] * x5) - z2 ;:=(g [1,1] * x3 + g [2,1] * x4 + g [3,1] * x5 ) - z3 ;:=(a [1,2] * x3 + a [2,2] * x4 + a [3,2] * x5) - z4 ;:=(g [1,3] * x3 + a [2,3] * x4 + a [3,3] * x5) - z5;
end ; (dl1: 3, dl2: 3, dl3: 3, dl4: 3, dl5: 3);
begin
//макс
if (dl1 lt; 0) and (dl2 lt; 0) and (dl3 lt; 0) and (dl4 lt; 0) and (dl5 lt; 0)
then
if (dl1 gt; dl2) then max:=abs (dl1)
else max:=abs (dl2);
if (dl3 gt; dl4) then max:=abs (dl3)
else max:=abs (dl4)
end ; (max) ;;
end .
4. Інструкція користувачеві по застосуванню програми
Інструкція по застосування програми описана в самій програмі. Користувачеві потрібно всього лише дотримуватися того, що виводиться в діалоговому вікні.
Нехай ЗЛП представлена ??системою обмежень в канонічному вигляді:
.
Кажуть, що обмеження ЗЛП має доцільний вид, якщо при неотрицательной правій частині ліва частина обмежень містить змінну, що входить з коефіцієнтом, рівним одиниці, а в інші обмеження рівності - з коефіцієнтом, рівним нулю.
Нехай система обмежень має вигляд
лінійне програмування симплекс інтерфейс
Зведемо задачу до канонічного вигляду. Для цього додамо до лівим частинам нерівностей додаткові змінні. Отримаємо систему, еквівалентну вихідної:
,
яка має доцільний вид
.
У цільову функцію додаткові змінні вводяться з коефіцієнтами, рівними нулю.
Нехай далі система обмежень має вигляд
Зведемо її до еквівалентної відніманням додаткових змінних з лівих частин нерівностей системи. Отримаємо систему
Однак тепер система обмежень не має переважного вигляду, так як додаткові змінні входять в ліву частину (при) з коефіцієнтами, рівними - 1. Тому, взагалі кажучи, базисний план не є допустимим. У цьому випадку вводиться так званий штучний базис. До лівих частинам обмежень-рівностей, що не мають переважного виду, додають штучні змінні. У цільову функцію змінні, вводять з коефіцієнтом М у разі рішення задачі на мінімум і з коефіцієнтом - М для задачі на максимум, де М - велике позитивне число. Отримана задача називається М-завданням, відповідної вихідної. Вона завжди має доцільний вид.
Нехай вихідна ЗЛП має вигляд
(1)
(2)
(3)
причому жодне з обмежень не має кращою змінної. М-задача запишеться так:
(4)
(5)
,, (6)
Завдання (4) - (6) має переважний план. Її початковий опорний план має вигляд
Якщо деякі з рівнянь (2) мають доцільний вид, то в них не слід вводити штучні змінні.
Теорема. Якщо в оптимальному плані
(7)
М-задачі (4) - (6) всі штучні змінні, то план є оптимальним планом вихідної задачі (1) - (3).
Для того щоб вирішити завдання з обмеженнями, що не мають переважного виду, вводять штучний базис і вирішують розширену М-задачу, яка має початковий опорний план
Рішення вихідної задачі симплексним методом шляхом введення штучних змінних називається симплексним методом зі штучним базисом.
Якщо в результаті застосування симплексного методу до розширеної завданню отриманий оптимальний план, в якому всі штучні змінні, то його перші n компоненти дають оптимальний план вихідної задачі.
Теорема. Якщо в оптимальному плані М-задачі хоча б одна з штучних змінних відмінна від нуля, то вихідна задача не має допустимих планів, тобто її умови несумісні.
Ознаки оптимальності.
Теорема. Нехай вихідна завдання вирішується на максимум. Якщо для деякого опорного плану всі оцінки невід'ємні, то такий план оптимальний.
Теорема. Якщо вихідна завдання вирішується на мініму...
