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

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

 

Исходная задача	Двойственная задача

 

Две приведенные задачи образуют двойственную пару.

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

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид "£", в задаче на минимум — вид "³";

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица А^т в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;

5) если переменная x_j исходной задачи может принимать только положительные значения, то j-ое условие в системе ограничений двойственной задачи является неравенством вида "≥". Если же переменная может принимать как положительные, так и отрицательные значения, то j-ое условие представляет собой уравнение. И наоборот, если i-ое соотношение в системе ограничений исходной задачи является неравенством, то i-ая переменная двойственной задачи y_i. В противном случае переменная y_i может принимать как положительные, так и отрицательные значения.

В теории двойственности используются четыре пары двойственных задач (приведем их в матричнойформе записи):

Исходная задача	Двойственная задача
Симметричные пары
1.	1.
2.	2.
Несимметричные пары
3.	3.
4.	4.

 

Первая теорема двойственности.

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

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

Вторая теорема двойственности.

План исходной задачи и план двойственной задачи являются оптимальными планами этих задач тогда и только тогда, когда для любых i и j выполняются равенства:

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

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

 

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

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

Преобразованную систему уравнений запишем в векторной форме:

,

где ; ; ; ; ; .

Среди векторов P₁, P₂, P₃, P₄, P₅, только два единичных вектора (P₃ и P₄), т.е. единичного базиса нет. Поэтому составим расширенную задачу. Для этого в левую часть третьего уравнения системы ограничений добавим искусственную переменную . Её нужно как можно быстрее вывести из базиса. Поэтому в целевую функцию в задаче максимизации новая переменная войдёт с очень большим отрицательным коэффициентом –М. Расширенная задача имеет опорный план , определяемый системой трёх единичных векторов: .

Составим симплексную таблицу для I итерации:

 

	Базис								-М
				-1
		-М						-1
		F0		-2	-3
		-3	-2	-1

 

Вычислим оценки разложений векторов по базису опорного решения по формуле , где z_j находится как скалярное произведение вектора P_j (j=1,m) на вектор С_б=(с₁, с₂, ...,с_m):

.

Оценки векторов, входящих в базис, всегда равны нулю.

Значение F₀ равно скалярному произведению вектора P₀ на вектор С_б: F₀=1*0+8*0+3*(-М) = -3М.

Значения F₀ и состоят из двух слагаемых . Слагаемое, которое не содержит М, записываем в 4-й строке, а число, стоящее при М – в 5-й.

Начальное опорное решение не является оптимальным, так как в 5-й строкеимеется два отрицательных числа и . Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов. Чтобы перейти к новому опорному решению в базис можно ввести любой из векторов P₁ и P₂. Выберем P₁, так как ему соответствует наибольшая по модулю оценка. Для определения вектора, подлежащего выводу из базиса, находят для всех a_ij>0. Для вектора P₁получим ( , поэтому отношение не рассматриваем). Минимум достигается при i=3. В третьей строке столбца «Базис» находится вектор Р₆. Следовательно, его из базиса исключаем.

Далее выполним преобразование Жордана с разрешающим элементом =2: 1) разделим всю третью строку на 2 и запишем результат в новую симплексную таблицу; 2) остальные элементы первого столбца нужно занулить, для этого полученную 3-ю строку сложим с первой, результат запишем в первую строку новой симплексной таблицы; 3) умножим новую 3-ю строку на -2 (или прежнюю на -1) и сложим со второй строкой, результат запишем во вторую строку новой симплексной таблицы.

Получим симплексную таблицу для II итерации:

 

Базис

-М

5/2

5/2

-1/2

1/2

-1

3/2

1/2

-1/2

1/2

-2

-1

 

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

Получили новый опорный план и значение целевой функции F₀ = 3.

Рассмотрим элементы 4-й строки. В столбце векторов и имеются отрицательные числа, значит, найденный план не является оптимальным. Вводить в базис будем вектор , исключать . Получим симплексную таблицу для III итерации.

 

Базис

-М

2/5

-1/5

1/5

-1

-1/5

-2/5

2/5

4/5

-7/5

7/5

 

Последняя строка снова содержит отрицательное число. В базис вводим вектор , исключаем .

 

Базис

-М

2/5

1/5

-1

-1/5

2/5

4/5

7/5

В 4-й строке последней симплексной таблицы нет отрицательных чисел. Значит, найденный опорный план является оптимальным. Значение целевой функции .

 

Составим двойственную задачу.

Умножим третье ограничение на -1, тогда все неравенства будут содержать знак «≤». Задача примет вид исходной задачи симметричной пары 1 (см. выше):

 

Число переменных в двойственной задаче равно числу ограничений в исходной задаче, т.е. трём: .

Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функцию: .

Целевая функция исходной задачи исследуется на максимум, следовательно, целевая функция двойственной задачи исследуется на минимум.

Матрица системы ограничений исходной задачи имеет вид: . Транспонируем её и получим аналогичную матрицу двойственной задачи - . Так как в исходной задаче обе переменные неотрицательные, то оба ограничения двойственной задачи будут являться неравенствами. правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи. И так как все три ограничения исходной задачи являются неравенствами, то все три переменные двойственной задачи будут неотрицательными.

Окончательно двойственная задача имеет следующий вид:

.

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

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

Третье ограничение выполняется в виде строгого неравенства, следовательно, .

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

Учитывая, что , получим:

Решив систему, получим

Окончательно

Решение двойственной задачи можно получить другим способом, используя формулу .

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

 

 

Ответ: , ;