Графічний метод розв'язування задач лінійного програмування - Розв'язання задач математичного програмування

Розглянемо задачу.

Знайти

(2.17)

За умов:

(2.18)

. (2.19)

Припустимо, що система (2.18) за умов (2.19) сумісна і багатокутник її розв'язків обмежений.

Алгоритм графічного методу розв'язування задачі лінійного програмування складається з таких кроків:

    1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.18) знаків нерівностей на знаки рівностей. 2. Визначаємо півплощини, що відповідають кожному обмеженню задачі. 3. Знаходимо багатокутник розв'язків задачі лінійного програмування. 4. Будуємо вектор, що задає напрям зростання значення цільової функції задачі. 5. Будуємо пряму С1Х1 + С2Х2 = const, перпендикулярну до вектора. 6. Рухаючи пряму С1Х1 + С2Х2 = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набирає екстремального значення. 7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.

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

    1. Цільова функція набирає максимального значення в єдиній вершині А багатокутника розв'язків (рис. 2.5). 2. Максимального значення цільова функція досягає в будь-якій точці відрізка АВ (рис. 2.6). Тоді задача лінійного програмування має альтернативні оптимальні плани. 3. Задача лінійного програмування не має оптимальних планів: якщо цільова функція необмежена згори (рис. 2.7) або система обмежень задачі несумісна (рис. 2.8).
рис. 2.6

Рис. 2.5 Рис. 2.6

рис. 2.8

Рис. 2.7 Рис. 2.8

4. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв'язків (рис. 2.9 і 2.10). На рис. 2.9 у точці В маємо максимум, на рис. 2.10 у точці А -- мінімум, на рис. 2.11 зображено, як у разі необмеженої області допустимих планів цільова функція може набирати максимального чи мінімального значення у будь-якій точці променя.

рис. 2.10

Рис. 2.9 Рис. 2.10

Рис. 2.11

Похожие статьи




Графічний метод розв'язування задач лінійного програмування - Розв'язання задач математичного програмування

Предыдущая | Следующая