МОТС / Часть2 / 18. Графический метод решения ЗЛП

2

18. Геометрическое решение ЗЛП.

Если задача линейного программирования в стандартной форме содержит всего лишь две переменные x₁ и x₂ (т.е. n=2), то ее можно решить следующим способом, основанным на ее геометрической интерпретации.

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

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

Для решения задачи линия уровня сдвигается в пределах области допустимых решений (многогранника допустимых решений) в направлении вектора-градиента до самой крайней точки области для задачи максимизации, и в направлении антиградиента для задачи минимизации. Координаты этой точки и определяют решение ЗЛП (оптимальный план задачи).

Пример.

Студент имеет 10 часов дневного времени, которое он должен распределить на учебу и развлечения. Развлечения привлекательнее в два раза. Однако для того, чтобы успешно учиться, на развлечения нельзя тратить более 4 часов дневного времени. Как распределить дневное время, чтобы получить максимальное удовольствие от работы и отдыха.

Решение. Составим экономико-математическую модель для данной задачи. Пусть х₁ – количество времени, потраченное на работу, х₂ – количество времени, потраченное на игры.

Тогда целевая функция имеет вид:

и условия-ограничения можно записать следующим образом:

допустимых решений задачи. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств:

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

Рис. 1.

Направление стрелок от каждой граничной прямой определяется путем непосредственной подстановки в неравенство координат произвольно взятой точки, например (0,0), и при удовлетворении данного неравенства направляем стрелки в сторону контрольной точки, в противном случае – наоборот. Полученное пространство решений есть многоугольник АВСD.

Угловые точки многоугольника решений имеют следующие координаты: А(0;10), B(4;6), C(4;0), D(0;0).

Для нахождения максимума целевой функции строим начальную прямую и вектор-градиент N(1;2). Координатами вектора N являются коэффициенты целевой функции при переменных х₁ и х₂. Для построения графика целевой функции задаем произвольное значение F(X). Если F(X)=0, то прямая проходит через начало координат.

Вектор-градиент показывает направление возрастания целевой функции. Передвигая начальную прямую параллельно самой себе в направлении вектора-градиента N, находим точку максимума целевой функции. Она будет в точке А(0;10), и максимальное значение

Таким образом, студент тратит 0 часов дневного времени на работу и 10 часов на игры, получая максимальное удовольствие в 20 единиц.