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

Пусть требуется найти максимальное значение целевой функции

Z(x) = c₁x₁ + c₂x₂

При ограничениях

Допустим, что система ограничений совместна, т.е. имеет решение, а многоугольник ее решений (ОДР) ограничен. Каждое из неравенств (ОДР) определяет полуплоскость с границей a_i1x₁ + a_i2x₂ = b_i, i=1,2,…,m или х₁=0, х₂=0. Представим этот многоугольник на плоскости Ох₁х₂ (рис.1).

Рис.1

Линейная функция (2.1) при фиксированных значениях Z(x) является уравнением прямой линии

c₁x₁ + c₂x₂ = const.

Изобразим эту прямую при Z(x) = 0. Эта прямая пройдет через начало координат через начало координат. Другим значениям Z(x) будут соответствовать прямые параллельные друг другу.

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

Известно, что коэффициенты при переменных в уравнении прямой являются координатами нормального вектора к соответствующей прямой или плоскости. Следовательно, нормальный вектор линий уровня п имеет координаты с₁,с₂, т.е. п=(с₁,с₂). Если перемещать линию уровня параллельно ее начальному положению в направлении вектора п , то для данного случая (рис.1) последней точкой, в которой линия уровня коснется ОДР будет точка С.

Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей, называется опорной прямой.

Теорема. Значения целевой функции в точках линии уровня увеличиваются, если линию уровня перемещать параллельно начальному положению в направлении нормали, и убывает при перемещении в противоположном направлении.

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

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

2. Строится вектор п =(с₁,с₂) с точкой приложения в начале координат.

3. Перпендикулярно вектору п проводится одна из линий уровня, например, линия уровня соответствующая прямой с₁х₁ + с₂х₂ = 0.

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находится минимум или максимум функции.

В зависимости от вида ОДР и целевой функции задача может иметь единственное решение (рис.2а), бесконечное множество решений (рис.2б) или не иметь решения (рис.2в)

Рис.2.

Графически можно решать задачу с п переменными, если выполняются условия: задача задана в канонической форме и n – r  2, где n – число неизвестных системы; r – ранг системы векторов-условий (число линейно независимы уравнений системы).

Литература

1. Общий курс высшей математики для экономистов /под ред.ЕрмаковаВ.И., стр.516-529.

Лекция 3.

Свойства задачи линейного программирования