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

Графічний метод доцільно застосовувати для розв'язування задач лінійного програмування із двома змінними. Обмежене використання даного методу зумовлене складністю побудови багатокутника розв'язків для задач з трьома змінними, а графічне зображення де кількість змінних перевищує число три, взагалі неможливе.

Розглянемо задачу лінійного програмування:

117при обмеженнях:

214

37

Згідно даному методу, кожна нерівність системи (2) визначає півплощину з граничною прямою45 і серед всіх цих півплощин можна вибрати спільну частину, або переріз усіх зазначених півплощин, тобто множину точок, координати яких задовільняють усі обмеження задачі — багатокутник розв'язків.

Звідси випливає, що розв'язати задачу лінійного програмування графічним методом, означає знайти таку вершину багатокутника розв'язків, у результаті підстановки координат якої в (1) функція мети набуває свого максимального або мінімального значення.

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

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

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

1.  Функція мети є необмеженою на множині розв'язків. В такому випадку задача лінійного програмування не має оптимальних планів.

83

2. Система обмежень є несумісною. Функція мети оптимальних планів не має також.

94

4. Цільова функція набуває максимального значення в єжиній точці A багатокутника розв'язків.

104

4. Цільова функція набуває максимального значення в будь-якій точці відрізка AB.

118

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар