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

Если число переменных в ЗЛП равно 2, а ограничениями является система неравенств, то задачу можно решать графическим методом. Он применим для решения ЗЛП следующего вида:

(3)

(4)

Алгоритм решения ЗЛП графическим методом.

1. Записывают уравнения прямых, соответствующих ограничениям (4) и строят их на плоскости X₁OX₂.

2. Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости X₁OX₂ и подставляют ее координаты в левую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; иначе искомая полуплоскость находится с противоположной стороны от прямой.

3. Эти действия выполняются последовательно для всех неравенств (4).

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

5. Определяют направление возрастания (убывания) целевой функции F. Для этого строят вектор-нормаль градиента целевой функции: =grad F= =(c₁;c₂), его направление показывает направление возрастания функции F, в противоположном направлении функция убывает.

6. Определяют граничную точку (точки) ОДР, в которых целевая функция принимает максимальное или минимальное значение.

7. Для этого строят линию уровня целевой функции и передвигают ее в направлении вектора =(c₁;c₂) до тех пор, пока она не пройдет через последнюю её общую точку с многоугольником решений.

8. Вычисляют значения координат найденной точки, решая совместно уравнения, задающие прямые, на пересечении которых находится эта точка, или, выявляя уравнение граничной прямой ОДР, с которой совпадает линия уровня целевой функции.

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

Пример. Фирма выпускает 2 вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы приведены в таблице.

Исходный продукт	Расход исходных продуктов на 1 кг мороженого		Запас, кг
	сливочное	шоколадное
Молоко	0,8	0,5	400
Наполнители	0,4	0,8	365

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более, чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 д. е., шоколадного-14 д. е.

Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

Решение. Обозначим: x – суточный объем выпуска сливочного мороженого, кг; x – суточный объем выпуска шоколадного мороженого, кг. Составим математическую модель задачи.

Целевая функция будет иметь вид:

F=16x +14x max. (5)

Система ограничений:

(6)

Построим в плоскости x₁Ox₂ область допустимых решений, то есть решение системы ограничений (6) (см. рис.20). Для этого, заметим, что каждое неравенство системы ограничений определяет в плоскости x₁Ox₂ полуплоскость, лежащую выше или ниже прямой, определяемой соответствующим уравнением.

Построим прямые: 0,8x +0,5x =400, 0,4x +0,8x =365, x -x =100, x =350, x =0, x =0. Точки пересечения этих прямых обозначим A, B, C, D, E.

Рис. 1. Решение задачи линейного программирования

Рассмотрим первое неравенство системы ограничений (6). Чтобы построить его решение, возьмём, например, точку с координатами x =0, x =0. Подставив их в неравенство, получаем 0 400 – верно, следовательно, искомая полуплоскость (решение) лежит ниже прямой 0,8x +0,5x =400, остальные полуплоскости находятся аналогичным образом. В результате пересечения всех этих областей получаем область OABCDE - ОДР задачи. Для нахождения максимального значения целевой функции F проверим граничные точки из области решений.

Построим линию уровня F целевой функции F: . Переместим её в направлении вектора-нормали =(16;14) градиента целевой функции параллельно самой себе, пока хотя бы одна её точка будет принадлежать ОДР. По рисунку видно, что точкой выхода из ОДР является точка С. Её координаты определяются из системы:

Решая её, найдем координаты точки С: x =312,5 и x =300. В точке С и будет оптимальное решение X*=(312,5; 300). При этом F =16∙312,5+14∙300=9200(д. е.).

Таким образом, фирма должна выпускать в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9200 д.е.