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

Рассмотрим на плоскости х₁Оx₂ совместную систему линейных неравенств:

(1)

Каждое неравенство этой системы геометрически определяет полуплоскость с предельной прямой a_i1x₁ + a_i2x₂ = b_i (i=1,2, ..., т). Условия неотрицательности переменных определяют полуплоскости с предельными прямыми х₁ = 0 и х₂ = 0. Система совместная, поэтому полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых является решением данной системы (рис.1.1).

Рисунок 1.1

Совокупность этих точек (решений) называют многоугольником решений, или областью допустимых планов (решений) задачи линейного программирования. Это может быть точка (единое решение), отрезок, луч, многоугольник, неограниченная многоугольная область.

Если в системе ограничений (1) будет три переменных, то каждая неравенство геометрически будет определять полупространство трехмерного просторнства, предельными плоскостями которого будут a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i (i = 1, 2, ..., т), а условия неотрицательности – полупространства с предельными плоскостями х_j=0 (j = 1, 2, 3), где и – номер ограничения, а j–— номер переменной. Если система ограничений совместная, то эти полупространства как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Он может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.

Пусть в системе ограничений (1) количество переменных больше, чем три: х₁, х₂,…х_n; тогда каждая неравенство определяет полупространство n-мерного пространства с предельной гиперплоскостью а_i1x₁ + a_i2x₂ + a_i3x₃ + … +a_inx_n = b_i (i = 1, 2, ....., т). Каждому ограничению вида (1) отвечают гиперплоскость и полупространство, которое лежит с одного стороны этой гиперплоскости, а условия неотрицательности — полупространства с предельными гиперплоскостями х_j = 0 (j=1, 2, 3, ..., n).

Если система ограничений совместная, то по аналогии с трехмерным пространством она образует общую часть в n-мерном пространстве — выпуклый многогранник допустимых решений.

Итак, геометрически задача линейного программирования представляет собой отыскание координат такой точки многогранника решений, при подстановке которых в целевую линейную функцию последняя достигает максимального (минимального) значения, причем допустимыми решениями являются все точки многогранника решений.

Целевую функцию

в п-мерном пространстве основных переменных можно геометрически интерпретировать как семью параллельных гиперплоскостей, положение каждой из которых определяется значением параметра Z.

Рассмотрим геометрическую интерпретацию задачи линейного программирования на примере. Пусть фермер принял решение выращивать озимую пшеницу и сахарнаю свеклу на площади 20 га, отведя под сахарную свеклу не меньше, чем 5 га. Технико-экономические показатели выращивания этих культур указаны в табл.1.1:

 

Таблица 1.1 - Показатели выращивания сельскохозяйственных культур

Показатель (из расчета на 1 га)	Озимая пшеница	Сахарная свекла	Имеющийся ресурс
Затраты работы, человеко-дней
Затраты работы механизаторов, человеко-дней
Урожайность, тонн	3,5		—
Прибыль, тыс. грн	0,7		—

Критерием оптимальности является максимизация прибыли.

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

х₁ — искомая площадь посева озимой пшеницы, га;

х₂ — искомая площадь посева сахарной свеклы, га.

Задача линейного программирования имеет такой вид:

max Z = 0,7x₁ + x₂ (1.8)

при условиях:

x₁ + x₂ ≤20; (1.9)

5x₁ + 25x₂ ≤270; (1.10)

2x₁ + 8x₂ ≤80; (1.11)

x₂ ≥5; (1.12)

x₁ ≥0, x₂ ≥0.(1.13)

Геометрическая интерпретация задачи изображена на рис.1.2.

Рисунок 1.2 Область допустимых решений задачи

 

Область допустимых решений этой задачи получаем так. Каждое ограничение, например х₁ + х₂ 20, задает полуплоскость с предельной прямой х₁ + х₂ = 20. Строим ее и определяем полуплоскость, которая описывается неравенствою х₁ + х₂ 20. С этой целью в неравенство х₁+х₂ 20 подставляем координаты характерной точки, скажем, х₁=0 и х₂=0. Убеждаемся, что эта точка принадлежит полуплоскости х₁+х₂ 20. Этот факт на рис.1.2 иллюстрируем соответствующей направленной стрелкой. Аналогично строим полуплоскости, которые отвечают неравенствам (1.10)—(1.13). В результате сечения этих полуплоскостей образуется область допустимых решений задачи (на рис.1.2 – четырехугольник ABCD). Целевая функция Z = 0,7x₁ + x₂ представляет собой семью параллельных прямых, каждая из которых отвечает определенному значению Z. В частности, если Z=0, то имеем 0,7х₁ + х₂ = 0. Эта прямая проходит через начало системы координат. Когда Z=3,5, то имеем прямую 0,7х₁ + х₂ = 3,5.