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

Рассмотрим такой пример:

при условиях

Рис. 4.1.

Каждое из этих неравенств определяет полуплоскости, пересечение которых дает многоугольник, заштрихованый на рис. 4.1. Этот многоугольник (выпуклый многогранник) и представляет собой допустимое множество решений R(x₁, x₂) задачи ЛП. Теперь рассмотрим целевую функцию

f(x₁,x₂)=4x₁+3x₂,

пусть ее значения

f(x₁,x₂)=12000=Z₁.

График уравнения 4х₁+3х₂=12000 - прямая с отрезками на осях x₁=3000; x₂=4000.

При f(x₁,x₂)=24000 получим прямую z₂.

Прямая z₂ параллельная прямой z₁, но расположена выше от нее. Передвигая прямую z вверх параллельно самой себе, приходим к такому ее положению, когда прямая и множество R будут иметь только одну общую точку А.

Очевидно, что точка А (x₁=2000; x₂=6000) - оптимальное решение, так как она лежит на прямой с максимально возможным значением . Заметим, что эта точка оказалась крайней точкой множества R.

При векторной форме ограничения задачи ЛП записываются так:

(3.1)

где

Рассмотрим допустимое множество A₁, A₂,.,A_n в пространстве данных векторов. Поскольку в формуле (3.1) , то все положительные комбинации векторов A₁,A₂,.,A_n образуют конус. Поэтому вопрос о существовании допустимых решений равнозначен вопросу о принадлежности вектора b этому конусу. Поскольку A₁,A₂,.,A_n m -мерные векторы (n > m), то среди них всегда обнаружится m линейно-независимых векторов, образующих базис m -мерного пространства и содержащих конус, образованный векторами A₁,A₂,.,A_n...

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

Расширенная форма задачи ЛП. Для решения задач ЛП необходимо переходить от ограничений - неравенств к ограничениям в форме уравнений. Для этого в каждое неравенство вводят по одной свободной переменной , чтобы превратить его в равенство. В таком виде задачу ЛП называют расширенной и записывают так:

(3.2)

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

a₁₁x₁+a₁₂x₂+.+a_1nx_n+1x_n+1+0x_n+2+...+0x_n+m=b₁;

a₂₁x₁+a₂₂x₂+.+a_2nx_n+0x_n+1+1x_n+2+...+0x_n+m=b₂;

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

a_m1x₁+a_m2x₂+.+a_mnx_n+0x_n+1+0x_n+2+...+1x_n+m=b_m...

В матричной форме эта задача имеет следующий вид:

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

где

(3.3)

Наконец, векторная форма записи расширенной задачи ЛП:

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

(3.4)

Рис. 4.2.

Рис. 4.3.

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

Установим отношение между элементами R и R₁:

На рис. 4.2 и 4.3 изображены допустимые множества решений обеих задач. Очевидно, что треугольник ОСА (рис. 4.2) - допустимое множество R - есть проекция допустимого множества R₁ (рис.4.3) на подпространство .

В общем случае допустимое множество решений исходной задачи R есть проекция допустимого множества решений расширенной задачи R₁ на подпространство исходных переменных .

2.1.1 Симплексный метод решения задач линейного программирования

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

Симплекс-метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г., который является универсальным методом решения задач линейного программирования. Суть этого метода заключается в том, что вначале получают допустимый план, удовлетво­ряющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение), оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов

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

Из следствия известно, что поиск оптимального решения зада­чи линейного программирования идет только среди базисных решений, число которых (C_n^m) достаточно велико. Симплекс метод вносит определенный порядок при нахождении оптимального решения.

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