Решение оптимизационной задачи линейного программирования

Двойственные задачи линейного  программирования.

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

Если  исходная задача(прямая)      

  при условии  , ,

     то двойственная задача представляет задачу на минимум

  при условии  , ,

      то есть в развернутом виде: 

       прямая:                 

 

 

                             

          двойственная:

       

 

          

В экономике  переменные двойственной задачи линейного  программирования – это «теневые цены» лимитирующих ресурсов прямой задачи линейного программирования. «Теневая цена» ресурса показывает, насколько увеличится значение целевой функции при снижении лимитирующего ресурса на единицу. Увеличение  объема лимитирующего ресурса  на единицу целесообразно только в том случае, если существует возможность его получения по стоимости, которая ниже, чем «теневая цена» данного ресурса.

   Таблица для двойственных задач линейного программирования :                     

 

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

Основные теоремы линейного  программирования.

Теорема 1(теорема существования).

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

Теорема 2(теорема двойственности).

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

Теорема 3(теорема о дополняющей не жесткости).

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

 

 

 

 

 

 

Геометрическое  изображение двойственных задач  при m=n=2.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.2 Основная идея симплекс метода

 

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

Рассмотрим  каноническую форму задачи линейного  программирования:

 

 

 

Задача линейного  программирования, где многогранное множество записано в другом виде:

 

можно представить  в каноническом виде, то есть записать неравенство в виде равенства. Для  этого необходимо ввести неотрицательную  дополнительную переменную    :

 

Аналогично  переменные , на которые не наложено требование не отрицательности переменных, представляются в виде:

 

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

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

Возьмем некоторую экстремальную (угловую) точку .

В силу теоремы  (о характеристике экстремальных  точек) эту точку характеризует  представление матрицы A в виде ,

где В - матрица m x m полного ранга, называемая базисом, N - матрица m x (n-m) .

По этой же теореме вектор может быть представлен

 

Переменные, соответствующие столбцам матрицы В, называются базисными и обозначаются . Остальные переменные, соответствующие столбцам матрицы N,  называются внебазисными.

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

, тогда равенство  можно записать в виде .

Следовательно

( 6.4.1 )

Используя  ( 6.4.1 ) получаем

( 6.4.2 )

Если , то в силу не отрицательности справедливо неравенство

 и - оптимальная экстремальная точка.

Пусть

В частности  пусть для некоторого j компонента

Рассмотрим  точку

, где

 

- (n - m) - мерный единичный вектор

 

 

Тогда из ( 6.4.2 ) следует, что

( 6.4.3)

так как 

 

то

 

при

Положим

   и  рассмотрим 2 случая:

1. Так как , то     для      при всех

Следовательно, x - допустимая точка тогда и только тогда, когда .

Очевидно, что  при     это справедливо для всех . Но тогда из ( 6.4.3) следует, что значения целевой функции не ограничены.

2. . Пусть   определено соотношением

 ( 6.4.4 )

где

   есть i - ая  компонента вектора .

В этом случае компоненты вектора определяются следующим образом:

  ( 6.4.5 )

,  остальные  компоненты равны нулю.

Положительными  могут быть только , то есть не более m компонент.

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

Итак, если задана произвольная экстремальная угловая  точка, то можно 

1. либо установить, что она оптимальна;
2. либо найти экстремальное направление, приводящее к неограниченному значению целевой функции;
3. либо найти экстремальную точку с лучшим значением целевой функции.

В последнем  случае процесс повторяется.

1. начальный этап:

найти произвольную экстремальную точку x c базисом B. Если это сделать трудно, то использовать метод искусственных переменных.

2) основной этап:

шаг 1:

Пусть x  - экстремальная точка c базисом B.

Вычислить

Если этот вектор  , то остановится.

x - оптимальная экстремальная точка.

В противном  случае выбрать наибольшую компоненту вектора 

Предположим такая компонента - .

Если вектор , то остановится, поскольку в этом случае оптимальное значение целевой функции неограниченно вдоль луча

 

где  - (n - m) - мерный единичный вектор.

Если  , то перейти к шагу 2.

шаг 2:

Вычислить номер r в соответствии с ( 6.4.4 ) и построить новую экстремальную точку по формуле ( 6.4.5 ).

Сформировать  новый базис, выводя из B столбец и вводя вместо него Повторить шаг 1.

Табличное представление симплекс - метода.

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

строка - целевая  функция 

 

строки-ограничения

 

Эти равенства  можно свести в следующую симплекс - таблицу, в которой правая часть(ПЧ) соответствует  их правым частям.

 

			ПЧ
1			0
0	B	N	b

 

Строки-ограничения  преобразуются умножением на (). К строке целевая функция прибавляются новые строки- ограничения, умноженные на . При этом получается следующая преобразованная таблица:

				ПЧ
	1
	0	1

 

Базисные  переменные отмечены в таблице слева, а значения базисных переменных записаны в правой части таблицы.

Эта таблица  содержит всю информацию, необходимую  для завершения первого шага симплекс метода.

Если     процесс прекращается, то есть текущая точка является оптимальной.

В противном случае:

 при просмотре  строки целевой функции можно  выбрать внебазисную переменную с положительным значением

 

где

- вектор

- матрица

- вектор

- скаляр

Если  - то процесс прекращается - значение целевой функции неограниченно.

Если , то

так как записаны под ПЧ и соответственно,  то следуя ( 6.4.4 ) легко вычислить .

Базисная  переменная , соответствующая минимальному отношению в ( 6.4.4 ), выводится из базиса, а вводится в базис.

Далее проводим ведущее преобразование:

Строка, соответствующая  (выводимая переменная из базиса) - ведущая строка.

Столбец, соответствующий  (вводимая переменная в базис) - ведущий столбец.

1. Разделить ведущую строку(соответствующую ) на ведущий элемент ;
2. Умножить новую r - ую строку на и результат вычесть из i - ой строки ограничений для всех
3. Умножить новую r - ую строку на   и результат вычесть из строки целевой функции.

Пример:

 

 

 

 

 

Графически:

 

 

 

 

 

 

Оптимальной является точка  . Значение функции

1. приводим задачу линейного программирования к канонической форме:

 

 

 

 

 

 

Возьмем в  качестве В матрицу

 

Так как ,

то найдена  экстремальная точка:

						ПЧ
	1	-1	3	0	0	0
	0	-1	2	1	0	6
	0	1	1	0	1	5

 

- выводится  из базиса

- вводится  в базис

Новый базис 

						ПЧ
	1		0		0	-9
	0		1		0	3
	0		0		1	2

 

Теперь:

- выводится  из базиса

- вводится  в базис.

Новый базис 

 

						ПЧ
	1	0	0
	0	0	1
	0	1	0

Так как  , то получено оптимальное решение.

Выбор начальной  экстремальной точки.

Для использования  симплекс - метода необходимо задать некоторую  начальную экстремальную точку.