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

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

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

Все вышесказанное относится и к случаю, когда система ограничений включает равенства. ЦФ при фиксированном значении представляет на плоскости прямую линию. Изменяя значения целевой функции L, получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на осях координат, а угловой коэффициент прямой останется постоянным. Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора.

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

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

В рассматриваемом примере содержатся только две переменные x₁ и x₂, поэтому задачу можно решить графически.

1) На плоскости x₁, x₂ строим область допустимых значений переменных, определяемую ограничениями задачи:

x₁ + 2x₂ 3 (А)

3x₁ + 1x₂ 3 (Б)

x₁, x₂ 0.

Последнее ограничение определяет первый квадрант плоскости. Чтобы построить множество точек удовлетворяющих неравенству (А), нанесем на плоскость график прямой, определяющий границу этого множества: x₁ + 2x₂ = 3 (Б).

Приведем это уравнение к виду: . А это уравнение прямой «в отрезках» и для построения этой прямой используются две точки (a, 0) и (0, b). (рис. 1.1)

Рис. 1.1

Запишем уравнение границы допустимой области из неравенства (А):

.

Аналогично, из неравенства (Б) получим уравнение второй границы:

Построим обе прямые на плоскости. Множества точек, удовлетворяющие неравенствам (А) и (Б) будут полуплоскости, лежащие под соответствующими прямыми, а множество допустимых значений переменных будет пересечением (общей частью) этих полуплоскостей, лежащее в первом квадранте: четырехугольник ABCD (рис. 1.2).

Рис. 1.2.

2) На множестве допустимых решений (ABCD) найдем точку, в которой целевая функция Z = 2x₁ + x₂ имеет максимальное значение. Для этого посмотрим линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:

Z = 2x₁ + x₂ = К,

где К - задаваемая постоянная.

При К = 1 уравнение линии уровня будет:

2x₁ + x₂ = 1.

или (в отрезках): .

При К = 2, аналогично:

2x₁ + x₂ = 2,

или .

Нанеся линии уровня на область допустимых решений (рис. 1.3), получим, что при увеличении значения Z соответствующая линия уровня перемещается параллельно предыдущей вправо и вверх. Таким образом, точкой из многоугольника ABCD, в которой целевая функция Z имеет максимальное значение, будет вершина С. Эта точка и определяет решение задачи.

Рис. 1.3.

3) Вычисление координат оптимальной точки (С).

Точка C лежит на пересечении прямых (А) и (Б), поэтому, чтобы определить ее координаты надо решить систему уравнений:

x₁ + 2x₂ = 3 (А)

3x₁ + x₂ = 3 (Б)

Решение:

x₁^* = 0,6; x₂^* = 1,2;

максимальное значение Z:

Z^* = 2·0,6 + 1,2 = 2,4.

Задание 2. Решение задачи ЛП в симплекс-таблицах.

Поиск по сайту: