Тема 17. Геометрия задачи линейного программирования.

Рассмотренная выше общая задача ЛП имеет явно выраженную геометрическую интерпретацию. Геометрическое представление задачи ЛП служит отправной точкой для наиболее часто используемого метода решения – симплекс метода.

Рассмотрим задачу ЛП в стандартной форме записи:

n

max (min) f(x) = a cjxj

J = 1

при ограничениях

а11х1 + а12х2 + … а1nхn ? b1 ,

а21х1 + а22х2 + … а2nхn ? b2 , (4.8)

……………………………..

аm1х1 + аm2х2 + … аmnхn ? bm ,

хj ? 0, j = 1, n .

Напомним, что множество Х, заданное в данном случае с помощью линейных ограничений, есть подмножество допустимых значений хj в множестве Rn.

Рассмотрим эту задачу в случае n = 2, т. е. множество Х допустимых планов определено в R2 – на плоскости.

Пусть система неравенств (4.8) с тривиальным ограничением хj ? 0 (j = 1, n) совместна (имеет хотя бы одно решение):

а11х1 + а12х2 ? b1 ,

а21х1 + а22х2 ? b2 ,

………………………………....

аm1х1 + аm2х2 ? bm

х1, х2 ? 0.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой аjiх1 + аi2х2 ? bi (i = 1, …, m). Условия неотрицательности определяют полуплоскости с граничными прямыми х1 = 0 и х2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством [17] и представляет собой совокупность точек, координаты (х1, х2) каждой из которых составляют решение данной системы.

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

Если в системе ограничений n = 3, то каждое неравенство геометрически представляет собой полупространство трехмерного пространства R3, граничная плоскость которого аi1х1 + аi2х2 + аi3х3 = bi, а условия неотрицательности – полупространства с граничными плоскостями соответственно хj = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве R3 общую часть Х, которая будет являться многогранником решений.

Рисунок 4.2

Пусть в системе ограничений указанной задачи n > 3, тогда каждое неравенство определяет полупространство пространства Rn (n-мерного) с граничной гиперплоскостью аi1х1 + аi2х2 + … + аinхn = bi (i = 1, …, m), а условия неотрицательности – полупространства с граничными гиперплоскостями хj = 0, j = 1, …, n.

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

Целевая функция задачи ЛП тоже является выпуклой. Она описывается уравнением плоскости (или гиперплоскости – для числа переменных больше трех) f(х) = с1х1 + с2х2 + … + сnхn . Представим, что в вершинах выпуклого многоугольника области допустимых планов мы установим «столбы», высота которых определяет значения целевой функции в данной вершине. На эти «столбы» наложим плоскость (целевую функцию). Очевидно, что максимального и минимального значения целевая функция задачи ЛП достигает либо в вершине выпуклого многогранника, либо на одной из его граней. [18]

Таким образом, задача ЛП представляет собой отыскание максимума (минимума) выпуклой функции на выпуклом множестве, что геометрически представляет собой поиск такой точки многогранника решений, координаты которой доставляют линейной функции наибольшее (наименьшее) значение. Допустимыми решениями (планами) являются все точки этого многогранника, причем, как уже было сказано оптимизирующие f(х) решения находятся в вершинах многогранника (или на его гранях).

В описанной выше задаче о распределении ограниченных ресурсов между предприятиями различных типов n – m = 6 – 4 = 2 (n ­ число неизвестных, m – число уравнений-ограничений). То есть каждое из ограничений, а также целевая функция (линейная) могут быть представлены геометрически в двухмерном пространстве.[19]

Из уравнений-условий можно некоторые переменные можно определить через другие, а именно x3, х4, х5, х6 через х1 и х2. Тогда из уравнений-условий следует:

х3 = 8х1 + 12х2 – 16,

х4 = 16 – 4х1,

х5 = 10 – 2х2,

х6 = 24 – 4х1 – 3х2.

Целевая функция, если выразить ее только через две переменные (х1 и х2), примет вид

y = –2,4•х1 + 0,8•х2 + 22,8 .

В этих выражения x3, х4, х5, х6 – это зависимые переменные, выраженные через независимые переменные х1 и х2.

Если сопоставить преобразованные уравнения-ограничения и последнее из ограничений исходной формулировки задачи (хj ? 0), то

х3 = 8х1 + 12х2 – 16 ? 0,

х4 = 16 – 4х1 ? 0,

х5 = 10 – 2х2 ? 0,

х6 = 24 – 4х1 – 3х2 ? 0.

х1 ? 0;

х2 ? 0.

Чтобы представить ограничения и целевую функцию графически, изобразим две координатные оси, соответствующие независимым переменным х1 и х2. Относительно них и будет производиться построение.

Разделив неравенства условия получившейся системы на некоторые числа, получим

x3 = x1 + 1,5•х2 – 2,

х4 = 4 – х1,

х5 = 5 – х2,

х6 = 6 – х1 – 0,75•х2,

х1 ? 0,

х2 ? 0.

Каждому из неравенств будет соответствовать полуплоскость, в пределах которой находятся допустимые значения хj (j = 1, 2, …, 6). Графики, описываемые этими неравенствами, изобразим на нашей координатной плоскости:

Рисунок 4.3

Например, неравенству x2 ? 0 соответствует полуплоскость вверх от оси х1. Аналогично, неравенству х5 = 5 – х2 соответствует полуплоскость вниз от граничного значения данного неравенства (х5 = 0). Таким же образом можно построить границы, определяемые и другими уравнениями.

Эти границы очерчивают некую область, соответствующую данным неравенствам – шестиугольник ABCDEF. Эта область может быть названа областью допустимых планов, поскольку любая точка в ее пределах отвечает требованиям наложенных ограничений.

Целевой функции соответствует семейство параллельных прямых. Рассмотрим, к примеру, одну из них, проходящую через начало координат, что имеет место при у = 22,8 (см. рис. 4.3). Она имеет наклон вправо относительно оси х2. Задаваясь различными значениями у, можно построить множество прямых, проходящих через точки, в которых значение переменной х2 равно 0. При этом, чем меньше значение у, тем правее будет располагаться соответствующая прямая.

Из всех планов нам более всего интересен оптимальный, при котором у достигает минимума. Тогда нас в наибольшей степени должна интересовать прямая, находящаяся как можно дальше вправо от прямой у = 22,8 и проходящая через многоугольник ABCDEF – прямая уmin.

Видно, что единственной точкой, соответствующей оптимальному плану, будет та вершина многоугольника ABCDEF, которая одновременно с тем, что она принадлежит многоугольнику области допустимых планов, отвечает требованию минимизации у – вершина С многоугольника. Из уравнений прямых, DC и BC, пересекающихся в этой точке, следует что х1 = 4, а х2 = 0.

Подставив полученные значения х1 = 4 и х2 = 0 в уравнения, в соответствии с которыми можно определить значения других, зависимых, переменных, получим следующий оптимальный план, которому будет соответствовать минимум целевой функции у:

х1 = 4,

х2 = 0,

х3 = 8•4 + 12•0 – 16 = 16,

х4 = 16 – 4•4 = 0,

х5 = 10 – 2•0 = 10,

х6 = 24 – 4•4 – 3•0 = 8.

При этом величина издержек будет минимальной:

y = 0,4•4 + 0,5•0 + 0,2•16 + 0,8•0 + 0,6•10 + 0,3•8 = 13,2