Геометрическая интерпретация ЗЛП

Приведём геометрическую интерпретацию ЗЛП. Пусть дана ЗЛП от двух переменных:

c₁x₁+c₂x₂ ® max

(3.1)

Из 3.1.1 и 3.1.2 получаем

3.2.1. Область допустимых решений ЗЛП (3.1) является выпуклым многоугольником (возможно, бесконечным) в R² с конечным числом вершин.

3.2.2. Целевая функция ЗЛП (3.1) достигает экстремума в вершине многоугольника допустимых решений. При этом, если целевая функция достигает экстремума в двух вершинах многоугольника решений, то она также достигает экстремума на всей стороне (в любой точке стороны) с концами в этих вершинах.

Наконец, из 3.3.1 вводной Главы 0 получаем

3.3.2. При перемещении линий уровня c₁x₁+c₂x₂=a относительно начала координат в направлении вектора нормали =(c₁, c₂) этих (прямых) линий значение a возрастает, в противоположном направлении a убывает.

Действительно, при перемещении линий уровня c₁x₁+c₂x₂=a относительно начала координат в направлении вектора нормали =(c₁, c₂) значения переменных x₁, x₂ целевой функции c₁x₁+c₂x₂ меняются пропорционально координатам вектора , скажем, с коэффициентом пропорциональности k. И если k растёт, то линии уровня перемещаются относительно начала координат по направлению вектора , а при убывании k линии уровня перемещаются относительно начала координат в противоположном с направлении. Поэтому в первом случае a растёт, во втором a убывает.

На фактах 3.2.1 - 3.2.3 основывается геометрический метод решения задачи (3.1), который заключается в следующем:

1. Построить область (многоугольник) допустимых решений ЗЛП (3.1).

2. Найти крайние положения прямых уровня c₁x₁+c₂x₂=a относительно ОДР. Эти положения будут либо в угловой точке (вершине), либо на стороне ОДР (многоугольника), либо таких точек не существует.

3. По направлению вектора нормали =(c₁, c₂) определить характер экстремума в найденных в пункте 2 точках.

Пример. Решить геометрически ЗЛП:

4x₁+x₂ ® max

Решение. 1. Построим область допустимых решений задачи. Для этого построим полуплоскости, определяемые неравенствами системы ограничений. В свою очередь, для построения полуплоскости, определяемой неравенством a₁x₁+a₂x₂≤b, достаточно построить границу полуплоскости - прямую a₁x₁+a₂x₂=b, и определить, которая из двух полуплоскостей относитель но этой прямой является искомой. Для этого подставляем координаты какой-нибудь точки, не лежащей на прямой a₁x₁+a₂x₂=b, в интересующее нас неравенство. Если получается верное числовое неравенство, то та сторона от прямой, в которой лежит точка, является искомой полуплоскостью.

Построим полуплоскость 2x₁+3x₂≤24.

Прямая 2x₁+3x₂=24 пересекает оси Ox₁ и Ox₂ в точках (0, 8) и (12, 0). Подставим координаты начала координат в неравенство: 2×0+3×0≤24. Так как получилось верное неравенство, то начало координат лежит в искомой полуплоскости. Это означает, что та сторона относительно прямой, в которой лежит начало координат О, является полуплоскостью 2x₁+3x₂≤24. Цифрами в скобках нумеруем границы полуплоскостей в порядке их следования в системе ограничений (Рис.1).

Строим полуплоскость -8x₁+3x₂≤24.

Точки (0, 8), (-3, 0) - точки пересечения границы полуплоскости -8x₁+3x₂≤24 с осями координат. Далее, -8×0+3×0≤24 - верное числовое неравенство. Значит, искомая полуплоскость - та, в которой лежит начало координат (Рис. 2).

Наконец, (0, -4), (6, 0) - точки пересечения прямой 2x₁-3x₂≤12 с осями координат, 2×0-3×0≤12.

Четырёхугольник OABC - ОДР задач. (Рис. 3).

2. Найдём крайние положения прямых уровня 4x₁+x₂=a относительно ОДР. Эти прямые перпендикулярны вектору =(4, 1). Из них мы изобразили три: (5), (6), (7). Крайние положения достигаются в точках O и B. Причём прямая, проходящая через O, получается перемещением этих прямых против направления , а прямая, проходящая через B, получается перемещением этих прямых в направлении . Поэтому в точке O достигается минимум целевой функции f(x₁, x₂)=4x₁+x₂, а в B - максимум. Координаты B находим как координаты точки пересечения прямых (1) и (3), составив и решив систему из их уравнений:

Û

f_min=f(0, 0)=0, f_max=4×9+2=38.

Ответ: При x₁=x₂=0 достигается минимум целевой функции, равной 0; при x₁=9, x₁=2 достигается максимум, равный 38.

3.3. Упражнение. Задания 2) и 3) Упражнения 1.3 решить геометрическим методом.