3.2. Геометрическая интерпретация злп

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

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₂= относительно начала координат в направлении вектора нормали =(c₁, c₂) этих (прямых) линий значение  возрастает, в противоположном направлении  убывает.

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

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

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

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

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₂= относительно ОДР. Эти прямые перпендикулярны вектору =(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. Упражнение. Задания 2) и 3) Упражнения 1.3 решить геометрическим методом.