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

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

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

a₁₁x₁ + a₁₂x₂ + b₁ ≤ 0;

(2.4)

a₂₁x₁ + a₂₂x₂ + b₂ ³ 0;

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

a_m1x₁ + a_m2x₂ +b_m ≤ 0.

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

a_i1x₁ + a_i2x₂ + b_i = 0.

(2.5)

Выпуклой называется такая область G векторной переменной х, для которой справедливо следующее свойство: если из любых двух значений векторов х ¹ и х ², принадлежащих этой области (х ¹ Ì G, х ² Ì G), образовать выпуклую линейную комбинацию

х ³ = λ х ¹ + (1 – λ) х ²,

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

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

а) б)

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

(2.6)

Линейная форма (2.1) в случае двух переменных принимает вид

L= c₁x₁ + c₂x₂.

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