Пример:

Решение:

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

Таблица1

		0	7	3	0	0
	БП	БР
0		20	5	2	1	0
0		38	8	4	0	1
		0	-7	-3	0	0

Таблица2

		0	7	3	0	0
	БП	БР
7		4	1			0
0		6	0			1
		28	0			0

Таблица3

		0	7	3	0	0
	БП	БР
7		1	1	0	1	-0,5
3		7,5	0	1	-2	1,25
		29,5	0	0	1

Решение получено, но оно не является целочисленным.

Строим сечение:

Т.е. .

И тогда

Помещаем это ограничение за последней строкой симплекс-таблицы (это связано с объявлением новой неизвестной).

Таблица4

		0	7	3	0	0	0
	БП	БР
7		1	1	0	1	-0,5	0
3		7,5	0	1	-2	1,25	0
0		0,5	0	0	0	0,25	-1
		29,5	0	0	1		0

Таблица5

		0	7	3	0	0	0
	БП	БР
7		2	1	0	1	0	-2
3		5	0	1	-2	0	5
0		2	0	0	0	1	-4
		29	0	0	1	0	1

Итак, F_max=29, X^*=(2,5).

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

Определение двойственной задачи.

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

Прямая задача ЛП в канонической форме состоит в определении максимального (минимального) значения функции при ограничениях:

;

.

Заметим, что в состав n переменных включаются также дополнительные балансовые переменные. Чтобы сформулировать условия двойственной задачи, расположим коэффициенты, фигурирующие в условиях прямой задачи, так, как схематически показано в табл.1.

Таблица1.

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

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

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

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

Из указанных правил построения двойственной задачи следует, что она имеет m переменных ( , ,…, ) и n ограничений (соответствующих n переменным прямой задачи ( , ,…, ).

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

Таблица2.

Прямая задача в канонической форме	Двойственная задача
	Целевая функция	Ограничения	Переменные
Максимизация	Минимизация	≥	Не ограничены в знаке
Минимизация	Максимизация	≤	Не ограничены в знаке

Для пары симметричных двойственных задач имеем соотношения (см. Таблица3):

Таблица3.

Целевая функция		Ограничения		Переменные
Прямая задача	Двойственная задача	Прямая задача	Двойственная задача	Прямая задача	Двойствен- ная задача
max	min	≤	≥	≥0	≥0
min	max	≥	≤	≥0	≥0

Пример:

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

максимизировать z=5x_l+12x₂+4x₃ при ограничениях

х_l+ 2х₂+ х₃≤10,

2х_l—x₂+3x₃=8,

х_l, х₂, х₃≥0.

Прямая задача в канонической форме:

максимизировать z=5x_l+12x₂+4x₃+0x₄ при ограничениях

х_l+ 2х₂+ х₃+x₄=10,

2х_l—x₂+3x₃+0x₄ =8,

х_l, х₂, х₃, x₄ ≥0.

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

минимизировать w=10y_l+8y₂ при ограничениях

y_l +2y₂ ≥5,

2y_l —y₂ ≥12,

y_l+3y₂ ≥4,

y_l+0y₂ ≥0, (т.е. y_l ≥0)

И тогда y₂, не ограничена в знаке.

Соотношения двойственности.

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

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

максимизировать z=5x_l+12x₂+4x₃ при ограничениях

х_l+ 2х₂+ х₃≤10,

2х_l—x₂+3x₃=8,

х_l, х₂, х₃≥0.

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

минимизировать w=10y_l+8y₂ при ограничениях

y_l +2y₂ ≥5,

2y_l —y₂ ≥12,

y_l+3y₂ ≥4,

y_l+0y₂ ≥0, (т.е. y_l ≥0)

И тогда y₂, не ограничена в знаке.

Решение этих задач задано в таблицах:

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

Прямая задача:(таблица1)

0 итерация (начало вычислений)

		0	5	12	4	0	-М
	БП	БР					R
0		10	1	2	1	1	0
-М	R	8	2	-1	3	0	1
		8М	-5-2М	-12+М	-4-3М	0	0