я.
Будуємо область допустимих рішень.
Будуємо лінію рівня.
Визначаємо напрямок градієнта.
Визначаємо точку максимуму (мінімуму):
Точка максимуму - точка допустимої області, найбільш віддалена від лінії рівня в напрямку градієнта, точка мінімуму - точка допустимої області, найбільш віддалена від лінії рівня в напрямку антіградіента.
При вирішенні ЗЛП можливі наступні випадки:
Основні властивості ЗЛП (див. рис.).
ЗЛП є опуклою завданням, тому рішення завжди єдино.
Оптимальне рішення досягається принаймні в одній з вершин допустимої області: а) тільки в одній вершині, б) в двох вершинах і має нескінченну безліч планів.
Якщо допустима область не обмежена, то ЗЛП може бути розв'язана або не розв'язна, що залежить від цільової функції: в) завдання на max не розв'язна, а на min - розв'язна; г) ЗЛП залагодити.
Якщо допустима область складається з єдиної точки, то в ній досягається і максимум і мінімум - д).
Якщо допустима область порожня, то ЗЛП не розв'язна - е).
Якщо допустима область обмежена і не порожня, то ЗЛП завжди має рішення.
Лекція 3
Симплекс-метод розв'язання ЗЛП
Запитання:
1. Стандартна форма ЗЛП, правила побудови. p align="justify">. Канонічний вигляд ЗЛП, початкова дозволене базисне рішення (НДБР), метод штучного базису. p align="justify">. Симплекс-метод. br/>
1. Стандартна форма ЗЛП, правила побудови
Графічний метод розв'язання ЗЛП можна використовувати, якщо число невідомих дорівнює 2 або різниця між числом невідомих і числом обмежень, записаних у вигляді рівнянь, дорівнює 2. У загальному випадку ці вимоги не завжди виконуються. Щоб використовувати для вирішення якийсь універсальний метод вирішення, ЗЛП необхідно записати в певній, стандартній формі. p align="justify"> Стандартна форма ЗЛП являє собою такий вид завдання, у якому:
) всі змінні невід'ємні;
) всі обмеження задані у вигляді рівнянь;
) цільова функція сформульована на мінімум.
Вимоги ці виправдані. По-перше, пошук максимуму лінійної функції зводиться до пошуку мінімуму функції з протилежними за знаком коефіцієнтами: оптимальні точки збігаються, а значення цільових функцій рівні за абсолютним значенням. По-друге, лінійна функція не має екстремумів і досягає свого найбільшого або найменшого значення на кордоні допустимої області, тому і вирішувати необхідно не нерівності, а рівняння. Запишемо правила приведення будь ЗЛП до стандартного вигляду. p align="justify"> Правила побудови стандартної форми ЗЛП:
1) Якщо F (x) = C1x1 + C2x2 + ... + Cnxn max, то можна шукати
F (x) = - C1x1 - C2x2 - ... - Cnxn min.
) Обмеження у вигляді нерівностей () можуть бути зведені до рівнянь введенням додаткових, що врівноважують невід'ємних рівнянь.
Наприклад: 2х1 + 3х2 4 2х1 + 3х2 + х3 = 4, х3 - урівноважує змінна. p> x1 + 2x2 5 4x1 + 2x2 - x4 = 5, x4 - урівноважує змінна.
) Якщо деяка змінна х може бути не обмежена знаком, то в стандартному вигляді таку зміну можна представити у вигляді різниці двох невід'ємних змінних: x = x '- x'', x', x''.
При цьому додаткові змінні не входять в цільову функцію. Стандартна форма ЗЛП в матричному вигляді виглядає так: Ax = b, x, F (x) = CTx min. br/>
2. Канонічний вигляд ЗЛП, початкова дозволене базисне рішення (НДБР), метод штучного базису
Щоб ЗЛП мала рішення необхідно, щоб система обмежень була сумісна. Це можливо, якщо ранг m системи (число лінійно незалежних рівнянь) була не більше числа невідомих n. Випадок m> n неможливий. При m = n система має єдине рішення, яке визначається методами звичайної алгебри. Якщо m Базисом називають будь-який набір m змінних такої, що визначник, складений з коефіцієнтів при цих змінних, відмінний від нуля. Відповідне рішення називаю базисним рішенням.
Змінні, що входять в базис, наз...
