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

4. Планы X и Y задач (1)-(2) и (3)-(4) являются оптимальными тогда и только тогда, когда для любого j( j =1,2,..., n) вы-

полняется равенство

m				=0 .
∑aij yi		−c j xj
i=1

§ 8. Геометрическая интерпретация двойственных задач

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

1)обе задачи имеют решения;

2)решения имеет только одна задача;

3)для каждой задачи двойственной пары множество решений

пусто.

Пример. Для задачи

f =x1 +6x2 →max ,

x1 +3x2 ≤9 , x ≥0		, x ≥0
2x1 +x2 ≥4	1	2

составить двойственную пару и найти решение обеих задач. Решение. Стандартная форма системы ограничений первой за-

дачи имеет вид

x1 +3x2 ≤9−2x1 −x2 ≤−4.

— 179 —

Тогда двойственная задача записывается как

F =9y1 −4 y2 →min ,

y −2 y	≥1	, y ≥0 , y		≥0 .
1 2
3y1 −y2 ≥6		1	2

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

Максимальное значение целевая функция первой задачи при-

								3				14
нимает				в	точке	A					;					(левый	рисунок),					следовательно
								5						5
	3		14																				87
X =		;			является оптимальным планом и															fmax		=		.
	5		5																				5
Целевая функция двойственной задачи принимает минимальное
						11					3						11			3
значение в точке						B			;					, значит, Y			=		;		— оптимальный
											5							5		5
						5

план двойственной задачи, и Fmin =875 .

— 180 —

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

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

f =x1 +6x2 →max ,

x +3x	+x =9
1 2	3

2x1 +x2 −x4 =4.

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

x1	x2	x3	x4
y3	y4	y1	y2

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

Базис	x1	x2	x3	x4	B
x3	1	3	1	0	9
	2	1	0	–1	4

— 181 —

Направляющий элемент желательно найти в первом или во втором столбце и во второй строке (свободное место в базисе). По условию подходит элемент a21 =2 . Пересчитаем таблицу. Теперь

можно ввести индексную строку и продолжить решение симплексным методом.

Базис	x1		x2					x3							x4										B
x3	0			5			1									1							7
		2												2
x1	1			1			0							−				1					2
		2
																	2
f	0	11					0							1										–2
			2													2
Базис	x1		x2				x3							x4										B
x2	0	1						2							1								14
								5							5									5
x1	1	0					−			1				−			3								3
																	5						5
							5
f	0	0					−		11					−			3						−			87
																	5
							5																5

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

тимальный план двойственной задачи имеет вид: y1 =115 , y2 =53 , y3 = y4 =0 .

— 182 —

êЦбыеЦ

Приведены некоторые факты теории дифференциального и интегрального исчисления. Материал носит ознакомительный характер.

Çйикйлх Сгь лДейикйЗЦкда

1.Придумайте последовательность, которая имеет предел, равный трем.

2.Сформулируйте определения бесконечно малой и бесконечно большой последовательностей.

3.Приведите примеры функции, непрерывной на всей числовой оси, разрывной в точке x =1 .

4.В чем разница между дифференциалом функции и ее производной, между определенным интегралом и неопределенным интегралом?

	+∞	dx		+∞	dx
	5. Вычислите интегралы ∫		и	∫		.
		x			2
	1			1	x

— 183 —