Линейное программирование

normal;line-height:150%;margin:0pt 28.35pt 0pt 0pt;text-align:justify;text-indent:35.45pt">min Z = C*X,

A*X = B,

X ≥ 0

(П) Прямая задача.

Каждому i–му (i = 1,m) ограничению поставим в соответствие переменное ui, положительное, отрицательное или нуль (называемое двойственным переменным), и рассмотрим ЗЛП.

max W = U*B

U* AT ≤ C, AT*U ≤ C

(Д) Двойственная задача

где U есть, так называемый, вектор–строка (u1, u2, …, um).

Линейная задача (Д) тесно связана с линейной задачей (П):

- матрица ограничений (Д) есть транспонированная матрица задачи (П);

- вектор "цен"  для задачи (П) есть вектор правых частей ограничений задачи (Д) и наоборот.

Данная таблица соответствий между прямой и двойственной задачами позволяет  записать непосредственно двойственную задачу для любой линейной задачи.

Теорема двойственности. Если X и U - соответственно допустимые решения произвольных прямой и двойственной задач, то Z = C*X ≥ W = U*B.

Следствие из теоремы. Если X*, U* - соответственно решения прямой и двойственной задач, удовлетворяющих равенству C*X* = U*B, то планыX* и  U*– оптимальные решения прямой и двойственной задач соответственно.

Теорема. Пусть заданы прямая и двойственная задачи:

а) если прямая и двойственная задачи имеют решения, то каждая из этих задач имеет оптимальное решение и

Z* = min(П) = max(Д) = W*

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

Теорема. Два решения (X и U) соответственно прямой и двойственной задач оптимальны тогда и только тогда, если выполняется условие:

(U* Aj - cj)*xj = 0; j = 1, n,  где Aj  –  j–й столбец матрицы A.

 

2.2. Двойственный симплекс-метод

Метод работает с теми же симплексными таблицами, что и прямой  метод, но исследование начинается с двойственно-допустимого решенияи сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис [1,3].

            Вычислительная схема

            Начинаем с симплексной таблицы

            Шаг 1. Если , i=1,...,5 то решение

                        

                        оптимальное.

            Шаг 2. Выбираем среди номеров i, для которых  < 0 , номер

К  с максимальным по модулю значением

                                   

Строка K объявляется ведущей.

            Шаг 3. Если в строке

                                   

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

прямая задача не имеет допустимых решений. Процесс решения завершается.

            Шаг 4. Выбираем среди отрицательных элементов строки

                                    

элемент с номером  S , для для которого выполняется равенство

                                   

Столбец S объявляется ведущим, а элемент   - ведущим элементом.

            Шаг 5. Проводим стандартное преобразование симплексной таблицы (шаг 5 из прямого симплекс-метода).

            Пример

Решить задачу ЛП двойственным симплекс-методом

                        

Приводим задачу к каноническому виду

                        

            Знаки в ограничениях изменили на противоположные для того, чтобы переменные

                                   

можно было взять в качестве базисных. Симплексная таблица имеет вид

                                   

            Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку - эта строка переменной

                                               

ведущий столбец - это столбец переменной После преобразования таблица принимает вид

            

            Так как в cтолбце есть отрицательная величина

                                                

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

                                   

которая является оптимальной. Соответствующее оптимальное решение

имеет вид

                        

 

 

 

3. Решение задачи линейного программирования двойственным симплекс-методом

3.1. Постановка задачи

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

 

 

при условиях

 

Где

 

 

и среди чисел имеются отрицательные.

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

Таким образом, можно найти:

 

 

На основе исходных данных составляют симплекс-таблицу, в которой некоторые элементы столбца вектора являются отрицательными числами. Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора P0 не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е. для любого

Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора Po отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число bl. Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор Pl. Чтобы определить, какой вектор следует ввести в базис, находим

, где

 

Пусть это минимальное значение принимается при j=r, тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы в столбце вектора Р0 стоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

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

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

 

 

3.2.Аналитическое решение задачи.

 

 

 

Составим двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции

Строим симплекс таблицу:

 

Итерация 0:

Базис						Решение	Оценка
	-7	2	0	0	0	0
	1	1	1	0	0	5
	2	-3	0	1	0	6	3
	-3	-1	0	0	5	3	-

 

Условие допустимости выполняется, так как в графе «Решение» все значения положительные, но не выполняется условие оптимальности, так как -строка содержит отрицательный коэффициент. Продолжаем наши действия

 

Итерация 1:

Базис						Решение
	0	9	7	0	0	35
	1	1	1	0	0	5
	0	-5	-2	1	0	-4
	0	2	3	0	5	18