2.6. Канонічний вигляд злп
У вихідній постановці ЗЛП можуть допускати різні форми запису. Так, в одних задачах потрібно максимізувати цільову функцію, в інших - мінімізувати; деякі лінійні обмеження можуть мати вигляд рівностей, інші - нерівностей і т.д.
Для однаковості запису ЗЛП уводиться так звана канонічна форма запису.
Говорять, що ЗЛП записано в канонічній формі, якщо вона має такий вигляд:
(2.3)
Відзначимо наступні особливості канонічного виду:
1) потрібно мінімізувати цільову функцію;
2) всі лінійні обмеження, крім вимог невід’ємності змінних, мають вигляд рівностей;
на всі змінні накладені вимоги невід’ємності .
Покажемо, що будь-яку ЗЛП можна привести до канонічного виду.
1) Якщо в ЗЛП потрібно максимізувати цільову функцію f, то покладемо g = - f і зажадаємо мінімізувати функцію g. Вийде нова ЗЛП, що еквівалентна вихідній в тому розумінні, що кожне оптимальне рішення вихідної задачі буде оптимальним рішенням нової задачі і навпаки.
2) Припустимо, що в ЗЛП є лінійне обмеження виду
.
Замінимо таке обмеження наступними
двома обмеженнями:
де z - нова змінна, котра в цільову функцію вводиться з коефіцієнтом 0 (інакше кажучи, змінна z не вводиться в цільову функцію). Значення змінної z можна не враховувати після вирішення нової задачі.
Аналогічно,
обмеження виду
заміняється двома обмеженнями:
3)
Припустимо, що в ЗЛП не до всіх змінних
пред'явлена вимога невід’ємності. Тоді
кожну змінну
,
на яку не накладена вимога невід’ємності
, представимо у вигляді різниці двох
невід’ємних змінних:
(2.6)
Кожне
входження змінної
в
цільову функцію або обмеження замінимо
різницею
.
Вирішивши нову задачу за допомогою
(2.6), повернемося до колишніх змінних.
Зазначеними прийомами будь-яка ЗЛП приводиться до канонічного виду.
Приклад. Привести до канонічного виду
Проробимо описані дії.
Тепер одержимо ЗЛП у канонічному виді:
2.7. Поняття опорного плану ЗЛП.
Нехай ЗЛП задана в канонічному вигляді (2.3 - 2.5). Припустимо, що система рівнянь (2.4) приведена до жорданової форми з невід’ємними правими частинами:
(2.6)
де
.
Дорівнявши до нуля вільні змінні, одержимо базисне рішення системи (2.4)
(2.7)
У
силу умови
набір
значень змінних (2.7) задовольняє й
обмеженням (2.5). Тому (2.6) єприпустимим
рішенням ЗЛП.
Припустиме
рішення (2.7) називається базисним
припустимим
рішенням або опорним
планом ЗЛП.
При цьому говорять, що змінні
складають
припустимий базис.
Виявляється, що якщо ОПР зобразити геометрично, то кожний опорний план ЗЛП відповідає вершині багатогранника. Тому справедлива наступна теорема.
Якщо ЗЛП розв'язна, то існує оптимальний опорний план.
3. Симплексний метод вирішення злп
3.1. Загальна характеристика й основні етапи симплекс - методу
Основоположниками симплекс-методу є радянський математик Л.В. Канторович і американський математик Дж. Данциг.
Симплекс-методом можна вирішити будь-яку ЗЛП або виявити її нерозв'язність. Багато спеціальних класів ЗЛП можна вирішити іншими, більш ефективними для цих класів методами. Однак перевага симплекс-методу - його універсальність. Майже для всіх ЕОМ розроблені стандартні програми для вирішення ЗЛП симплекс - методом.
Опишемо загальну ідею симплекса-методу.
Припустимо, що ЗЛП записано в канонічному вигляді й цільовій функції потрібно мінімізувати. Як ми вже знаємо, оптимальний план слід шукати серед опорних планів ЗЛП. Симплекс-метод не перебирає всі опорні плани (що було б часто неможливо через їхню величезну кількість), а, починаючи з деякого вихідного опорного плану, він послідовно переходить до інших опорних планів зі зменшенням цільової функції. Симплекс-метод припиняє свою роботу тоді, коли або буде знайдений оптимальний опорний план, або установлена нерозв'язність задачі.
При вирішенні ЗЛП симплекс-методом можна виділити наступні етапи:
1) приведення ЗЛП до канонічного вигляду;
2) приведення системи лінійних рівнянь до жорданової форми з невід’ємними правими частинами з одночасною перевіркою на нерозв'язність ЗЛП через суперечливість системи лінійних обмежень;
3) дослідження опорного плану на оптимальність;
4) дослідження ЗЛП на нерозв'язність через необмеженість знизу на ОПР цільової функції;
5) перехід до нового, "кращого" опорного плану.