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

Экономико-математическая модель задачи линейного программирования в стандартной форме с двумя переменными имеет вид

F = C₀ + C₁X₁ + C₂X₂   ® max,

                                                  (2.6)

x₁ ³ 0, x₂ ³ 0.

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

a₁x₁ + a₂x₂ £ b.                              (2.7)

Рассмотрим прямую на плоскости с уравнением a₁x₁ + a₂x₂ = b. Эта прямая делит плоскость на две полуплоскости, в одной из которых справедливо неравенство (2.6), а в другой – противоположное. Для того чтобы проверить, какая из полуплоскостей состоит из решений неравенства (2.6), следует взять точку из какой-либо полуплоскости и проверить, выполняется ли оно этой точке. Множество решений отдельно взятого линейного неравенства представляет собой полуплоскость. Для системы из нескольких таких неравенств точки, координаты которых удовлетворяют всем неравенствам одновременно, должны находиться во всех соответствующих полуплоскостях, т.е. принадлежать теоретико-множественному пересечению этих полуплоскостей.

Множество точек на плоскости, удовлетворяющих системе ограничений, составляет таким образом некоторую выпуклую многоугольную область. Условия неотрицательности переменных X₁ ³ 0 и X₂ ³ 0 приводят к тому, что эта область находится в первой координатной четверти.

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

Целевая функция задачи геометрически изображается с помощью прямой уровня, т.е. прямой, на которой Z = C₀ + C₁X₁ + C₂X₂ принимает постоянное значение. Если С - произвольная константа, то уравнение прямой уровня имеет вид C₀ + C₁X₁ + C₂X₂ = C.

При изменении константы C получаем различные прямые, параллельные друг другу. При увеличении C прямая уровня перемещается в направлении наискорейшего возрастания функции Z, т.е. в направлении ее градиента. Вектор градиента .

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

Пример 1. Построим на плоскости множество решений системы неравенств для модели (рис.2.5):

               (2.8)

Решим геометрически задачу примера 1 при C₁ = 1, C₂ = 1 (рис.2.6):

                                         

Рис.2.5.

Точкой максимума здесь является точка А, координаты которой определяются из следующей системы уравнений: ,

решая которую, получаем точку максимума А (2;4), Z_max = 6.

2.5. Симплекс-метод решения оптимизационных задач
линейного программирования (ОЗЛП)

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

Этот метод является одним из универсальных, применяемым к любой задаче ЛП в канонической форме. Система ограничений здесь – система линейных уравнений, в которой количество неизвестных больше количества уравнений.

Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной, приходят к искомому оптимуму. На этом принципе основан симплекс-метод.

Симплекс – это выпуклый многогранник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).

Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные: X₁,X₂,...,X_r. Тогда наша система уравнений может быть записана как

              (2.9)

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

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

Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X₁, X₂,..., X_r, то решение {b₁,b₂,...,b_r,0,...,0} будет опорным при условии, что b₁,b₂,...,b_r ³ 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода.

Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение Z самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен.

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

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

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

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

Таким образом, применение симплексного метода распадается на два этапа: 1) нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; 2) нахождение оптимального решения. При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.

Вычисления по симплекс-методу организуются в виде симплекс-таблиц, которые являются сокращенной записью задачи линейного программирования в канонической форме. Для определенности записи считается, что в качестве базисных переменных можно взять переменные X₁,X₂,...,X_r и что при этом b₁,b₂,...,b_r ³ 0 (соответствующее базисное решение является опорным).

Исходная симплекс-таблица выглядит следующим образом:

Баз. Перем.	Своб. члены	X1	X2	....	....	Xr	Xr+1	Xr+2	....	....	....	Xn
X1	b’1	1	0	...	...	0	-a1,r+1	-a1,r+2	...	...	...	-a1n
X2	b’2	0	1	...	...	0	-a2,r+1	-a2,r+2	...	...	...	-a2n
...	...	...	...	...	...	...	...	...	...	...	...	...
Xr	b’r	0	0	...	...	1	-ar,r+1	-ar,r+2	...	...	...	-arn
Z	g0	0	0	...	...	0	-gr+1	-gr+2	...	...	...	-gn

Примечание. Названия базисных переменных здесь взяты лишь для определенности записи и в реальной таблице могут оказаться другими.