Короткі теоретичні відомості

Геометричний метод розв’язання можна застосовувати тільки для систем обмежень з двома або трьома змінними. Тому геометричний метод має досить вузькі рамки для свого застосування. Проте геометричний метод викликає певний інтерес при виробленні наочних представлень про задачі лінійного програмування.

У випадку двох змінних розв’язок шукається на площині, у випадку трьох змінних – у просторі.

Алгоритм графічного методу розв’язування задач лінійного програмування:

1. Замінити знаки нерівності у системи обмежень на знаки рівності.

2. Будуємо прямі лінії.

2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3. Знаходимо багатокутник розв’язків задачі лінійного програмування.

4. Будуємо вектор нормалі, який має координати , де - коефіцієнти при відповідних змінних у цільовій функції.

5. Будуємо лінію рівнів, яка перпендикулярна до вектора нормалі (с ₁ х ₁ + с ₂ х ₂ = const).

6. Переміщуючи лінію рівнів в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину многокутника розв’язків, де цільова функція досягає екстремального значення.

7. Визначаємо координати точки, в якій цільова функція набуває максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.

Застосовуючи графічний метод до розв’язування задач лінійного програмування можна тримати такі випадки:

- цільова функція набуває максимального значення в єдиній вершині А багатокутника розв’язків (рисунок 2.1);

- цільова функція набуває максимального значення у будь-якій точці відрізка АВ (рисунок 2.2). Тобто задача лінійного програмування має альтернативні оптимальні плани;

- задача лінійного програмування не має оптимальних планів (рисунок 2.4 — система обмежень задачі несумісна);

- задача лінійного програмування не має максимального значення. (рисунок 2.3 — цільова функція не обмежена згори). Тобто .

Рисунок 2.1 – Єдина точка максимуму Рисунок 2.2 – Декілька точок

максимуму

Рисунок 2.3 – Відсутнє значення Рисунок 2.4 – Несумісна система

- задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рисунок 2.5, 2.6 та 2.7).

Рисунок 2.5 - Максимум за умови Рисунок 2.6 – Мінімум за

необмеженої області допустимих умови необмеженої області

розв’язків допустимих розв’язків

Рисунок 2.7 – Мінімум та максимум за умови необмеженої області допустимих розв’язків

Дата добавления: 2017-02-01