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

Геометрическая интерпретация задач линейного программирования представима для случаев n =2 и n =3. Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных х₁ и х₂. Пусть нам задана задача линейного программирования в стандартной форме:

х1 ≥0, х2 ≥0

(3)

Задача линейного программирования в стандартной форме представляет собой следующее: требуется найти экстремум целевой функции при допустимой области, которая есть система линейных равенств и неравенств, а переменные неотрицательны.

Возьмём на плоскости декартову систему координат и каждой паре чисел (х₁, х₂) поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения х₁ ≥0, и х₂ ≥0. Они из всей плоскости вырезают лишь её первую четверть (рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида а₁ х₁+а₂ х₂≤b. Сначала рассмотрим область, соответствующую равенству а₁ х₁+а₂ х₂=b. Это прямая линия. Строить её проще всего по двум точкам.

Пусть b≠0. Если взять х₁=0, то получится х₂=b/а₂. Если взять х₂=0, то получится х₁=b/а₁. Таким образом, на прямой лежат две точки (0,b/а₂) и (b/а₁,0). Дальше через эти две точки можно по линейке провести прямую линию (рис. 2).

Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение х₁ и вычислить соответствующее ему значение х₂.

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части х₁+а₂ х₂<b, а в другой наоборот а₁ х₁+а₂ х₂>b. Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

Пример

Определить полуплоскость, определяемую неравенством 4х₁-6 х₂≤ 3.