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

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

1) Строим все полуплоскости, соответствующие ограничениям системы.

2) Находим область допустимых решений (ОДР), как множество точек, в котором пересекаются все построенные полуплоскости.

3) Строим вектор , выходящий из начала координат, где и – это коэффициенты при неизвестных в целевой функции . Этот вектор указывает направление возрастания целевой функции.

4) Перпендикулярно вектору проводим так называемую линию уровня (т.е. прямую , проходящую через начало координат).

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

6) Находим координаты этой общей крайней точки, решая систему уравнений прямых, на пересечении которых она находится.

7) Подставляем эти координаты в целевую функцию и находим ее max (или min).

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

max

Решение. Третье и четвертое ограничения системы – двойные неравенства, преобразуем их к более привычному для подобных задач виду , это и , т.о. первое из полученных неравенств (или ) относится к условию неотрицательности, а второе к системе ограничений. Аналогично, это и .

Т.о. задача примет вид

max

,

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

; ; ; (рис.5).

Областью решений неравенств является пятиугольник ABCDE.

Построим вектор .Через начало координат перпендикулярно вектору проведем линию уровня . И затем будем перемещать ее параллельно самой себе в направлении вектора до точки выхода из области допустимых решений. Это будет точка С. Найдем координаты этой точки, решив систему, состоящую из уравнений первой и четвертой прямых:

.

Подставим координаты точки С в целевую функцию и найдем ее максимальное значение Пример. Построить линии уровня и для задачи линейного программирования:

max (min)

Решение. Область допустимых решений – открытая область (рис.6). Линия уровня проходит через точку В. Функция Z имеет минимум в этой точке. Линию уровня построить нельзя, так как нет точки выхода из области допустимых решений, это значит, что .

 

Задания для самостоятельной работы.

1. Найти область решений системы неравенств:

а) б)

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

min

3. Составить экономико-математическую модель и решить графически задачу линейного программирования

Фирма выпускает изделия двух видов А и В. Изделия каждого вида обрабатывают на двух станках (I и II). Время обработки одного изделия каждого вида на станках, время работы станков за рабочую смену, прибыль фирмы от реализации одного изделия вида А и вида В занесены в таблицу:

Станки	Время обработки одного изделия, мин.	Время работы станка за смену, мин.
А	В
I
II
Прибыль от одного изделия, грн.	0,3	0,9

Изучение рынка сбыта показало, что ежедневный спрос на изделия вида В никогда не превышает спрос на изделия вида А более чем на 40 единиц, а спрос на изделия вида А не превышает 90 единиц в день.

Определить план производства изделий, обеспечивающий наибольшую прибыль.