Лекция: Геометрическая интерпретация задач линейного программирования

В решении задач линейного программирования часто пользуются геометрическими интерпретациями.

Система неравенств (2.2) определяет в пространстве выпуклую область x1, ..., xn – выпуклый многогранник или многоугольник. Для простоты рассмотрим случай для n = 2 переменных:

a11x1 + a12x2 + b1 ≤ 0;

................. .

am1x1 + am2x2 +bm ≤ 0.

Каждое из этих соотношений определяет область, лежащую по одну сторону от прямой:

ai1x1 + ai2x2 + bi = 0.

х3 = λх1 + (1 – λ)х2,

где λ – произвольное действительное число, для которого 0 ≤ λ ≤ 1, то вектор х3 также будет принадлежать этой области: х3 Ì G.

На рис. 2.1 изображены выпуклая и невыпуклая области значений х1 и х2. Действительно, если на рис. 2.1, б выбрать точку х3, равную линейной комбинации точек х1 и х2, то она не будет принадлежать заштрихованной области, и поэтому эта область не будет выпуклой. С другой стороны, нетрудно убедиться, что для любых двух точек, принадлежащих заштрихованной области на рис. 2.1, а, выполняется условие (2.5), и поэтому эта область является выпуклой.

а) б)

Рис. 2.1. Выпуклая (а) и невыпуклая (б) области значений переменных

L= c1x1 + c2x2.

Это уравнение прямой в плоскости (x1, x2), пересекающей оси x1 и x2 в точках L/с1 и L/с2, соответственно (рис. 2.2). Величины с1 и с2 определяют наклон прямой [угол наклона к оси х1 задается формулой cosα = с1/(с12 + с22)1/2 определяет расстояние от начала координат до прямой, которое находится из формулы d = L/(с12 + с22)1/2]. Теперь можно дать геометрическую интерпретацию задачи линейного программирования. Если требуется определить такие x1 и x2, которые придали бы линейной форме минимальное значение, то геометрически это означает, что необходимо провести прямую L [формула (2.6)], проходящую хотя бы через одну точку области и имеющую минимальное расстояние d от начала координат (рис. 2.3,а). В случае максимизации это расстояние должно быть максимальным (рис. 2.3,б). Могут представиться два варианта: прямая имеет с допустимой областью G одну общую точку в вершине области или совпадает с одним из ее ребер. Во втором варианте (рис. 2.4) имеет место вырожденный случай, т.е. линейная функция цели совпадает с левой частью одного из ограничений.

Рис. 2.2. Геометрическая интерпретация линейной функции

а) б)

Рис. 2.3. Геометрическая интерпретация линейного программирования

для случаев минимума (а) и максимума (б)

Рис. 2.4. Геометрическая интерпретация линейного программирования, вырожденный случай