2. Графічний метод розв’язування задач лп з
Графічний метод розв’язування задачі ЛП можна застосовувати і у випадку, коли система обмежень містить n невідомих і m незалежних рівнянь, але при цьому n-m=2.
Сформулюємо
задачу: серед
усіх невід’ємних
розв’язків
системи
основних обмежень рівнянь – знайти
такий, при якому цільова функція набуває
оптимального значення:
(1)
за умов
(2)
(3)
При цьму припускаємо, що всі рівняння системи (2) лінійно-незалежні та виконується умова n-m=2.
Означення. Будь які m змінних системи лінійних рівнянь з n змінними (n>m) називаються базисними (основними), якщо визначник матриці коефіцієнтів при них не дорівнює нулю. Тоді решта змінних (n-m) називаються вільними (неосновними).
Нехай
в системі (2) змінні
є
базисними змінними, тобто відмінним
від нуля є визначник
(4)
Тоді
- вільні змінні. Систему (2) можна записати
у вигляді:
(5)
Оскільки вільні змінні xm+1,xm+2 можуть приймати довільні значення, то система (5) має нескінченну множину розв’язків.
Проводимо методом Жордана-Гаусса m виключень, тоді система обмежень (5) приймає вигляд:
(6)
Таким чином, базисним змінним після перетворень Жордана-Гаусса відповідають одиничні лінійно незалежні вектори
;
;….
Які утворюють одиничний базис у m – вимірному просторі.
Після підстановки (6) у (1) одержимо цільову функцію
,
яка не містить базисних змінних, тому задачу (1)-(3) можна представити в наступному вигляді:
(7)
за умов
(8)
(9)
Представлена задача, очевидно, може бути розв’язана графічним методом.
3. Приклади розв’язування задач лп графічним методом.
Приклад 2. Розв’язати задачу ЛП графічним методом.
за умов
Питання для самоконтролю.
Дайте геометричну інтерпретацію задачі ЛП.
Чи можна в лінійній моделі замінюючи знаки обмежень ≤ або ≥ на знак = поліпшити значення цільової функції?
В якій точці многогранника розв’язків лінійна цільова функція задачі ЛП досягає оптимального значення?
Чи може у задачі ЛП із двома змінними цільова функція приймати однакові значення у двох різних екстремальних точках?
Запишіть алгоритм розв’язання задачи ЛП графічним методом.