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

Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи ЛП (1.1) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соотвествующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.1) ОДР является пустым множеством.

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня ( ), соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

Порядок решения:

1) Строим вектор C. т.к. математическая модель имеет вид

Мы откладываем вектор от 0 до (3; 2)(на рисунке зеленый)

2) Строим L(х) строится перпендикулярно Вектору С (красная линия)

3) Строим ограничения (они на рисунке есть) Неравенство делаем равенством и поочередно находим х1 и х2, подставляя 0 вместо х1 и х2 по очереди.

4) Далее в соответствии с ограничениями заштриховываем те плоскости, которые разрешении ораничением. Для этого подставьте в конкретное неравенство координаты какой-либо точки[например, (0; 0)], и проверьте истинность полученного неравенства

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

5) При поиске max ЦФ передвигайте целевую прямую в направлении вектора C, при поискеmin ЦФ– против направления вектора C. Последняя по ходу движения вершина ОДР будет точкойmax илиmin ЦФ. Если такой точки(точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху(при поискеmax) или снизу(при поискеmin).

6) Определите координаты точкиmax (min) ЦФ вычислите значение ЦФ

Для вычисления координат оптимальной точки решите систему уравнений прямых, на пересечении которых находится Х (на рисунке искомым значением является точка Е следовательно находится на пересечении 1 и 2 ограничения, решаем как систему уравнений и находим) Далее в ЦФ подставляем значения х1 и х2 – это и будет являться максимально возможной прибылью при данных ограничениях)