Графический метод решения задач линейного программирования.

 

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

Этот метод имеет следующие этапы:

1. Строиться область дополнительных решений задачи, если задача была в каноническом виде ее надо привести к стандартному.

2. Графически изобразить решение системы неравенств

1)

решением является одна точка (0; х₂).

 

2)

нет решений

 

3)

 

выпуклый многоугольник

 

 

4)

неограниченная выпуклая многоугольная область

 

f(x) = c₁x₁ + c₂x₂ max (min)

 

 

c₁x₁ + c₂x₂ = L, L - параметр

Целевая функция – семейство параллельных прямых с параметром L , которые называются линиями уровня.

(с₁;с₂) – показывает направление возрастания целевой функции, он перпендикулярен линиям уровня.

Точка максимума – это последняя точка соприкоснове6ния линий уровня с точками решения системы неравенств при выходе линий уровня из заданной области.

I. Задача на максимум и на минимум имеет единственное решение.

II. Задача на минимум имеет единственное решение, задача на максимум имеет множество решений (альтернативный оптимум).

III. Задача имеет единственной решение (т. В), а на максимум – нет решений.

 

 

IV. Задача не имеет решений.