Приложение а Основные положения теории двойственности а.1. Построение двойственных задач

Двойственная задача – это задача линейного программирования (ЗЛП), которая формулируется с помощью определённых правил непосредственно из условий прямой задачи [3].

Рассмотрим обобщённую формулировку двойственной задачи ЛП, которая применима к любой форме представления исходной задачи. В основу такой формулировки положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к канонической форме.

Пусть имеем прямую ЗЛП в канонической форме:

;

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

.

Заметим, что в состав n переменных x_j включаются так же избыточные и остаточные переменные.

Двойственная задача получается путём структурного преобразования условий прямой задачи в соответствии со следующими правилами (рис. А.1):

• каждому ограничению прямой задачи соответствует переменная двойственной задачи;

• каждой переменной прямой задачи соответствует ограничение двойственной задачи;

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

• коэффициент при переменной в выражении для целевой функции прямой задачи, становится постоянной правой части соответствующего ограничения двойственной задачи;

• направление оптимизации, ограничения и знаки двойственных переменных формируются согласно таблице А.1.

Таблица А.1.

Направление оптимизации целевой функции прямой задачи (в канонической форме)	Двойственная задача
	целевая функция	ограничения	переменные
Максимизация Минимизация	Минимизация Максимизация		Не огр. в знаке Не огр. в знаке

x1	x2	…	xj	…	xn
c1	c2	…	cj	…	cn
a11	a12	…	a1j	…	a1n	b1	y1
a21	a22	…	a2j	…	a2n	b2	y2
…	…		…		…	…	…
ai1	ai2	…	aij	…	ain	bi	yi
…	…		…		…	…	…
am1	am2	…	amj	…	amn	bm	ym

Рис. А.1.

Таким образом, двойственная задача имеет m переменных (у₁, у₂,…,у_m) и n ограничений.

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

Пара симметричных двойственных задач

Прямая задача ;

; (А.1)

.

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

; (A.2)

.

Пара несимметричных двойственных задач

Прямая задача ;

; (A.3)

.

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

; (A.4)

.