1. ѕерва¤ теорема двойственности

ќсновна¤ теорема двойственности линейного программировани¤. ѕусть рассматриваетс¤ пара двойственных задач:

 (1)      (2)

≈сли одна из этих задач обладает оптимальным решением, то и двойственна¤ к ней задача также имеет оптимальное решение. ѕричем экстремальные значени¤ соответствующих линейных форм равны: .

≈сли же у одной из этих задач линейна¤ форма не ограничена, то двойственна¤ к ней задача противоречива.

ƒоказательство: ѕусть основна¤ задача (1) имеет конечное решение и получена окончательна¤ симплексна¤ таблица:

		=	Е.	=	=	Е.	=	=
			Е.			Е.		1
	=		Е.			Е.
Е.	Е.	Е.	Е.	Е.	Е.	Е.	Е.	Е.
	=		Е.			Е.
	=		Е.			Е.
Е.	Е.	Е.	Е.	Е.	Е.	Е.	Е.	Е.
	=		Е.			Е.
1	=		Е.			Е.

“ак как данна¤ таблица, по предположению, соответствует оптимальному решению задачи (1), то и . ѕри этом достигаетс¤ при .

–ассмотрим полученную таблицу двойственной задачи. ѕолага¤ значени¤ переменных слева (небазисных) равными нулю:

,

найдем , Е, , , Е, . —ледова­тельно, получено опорное решение:

, Е, , , Е, .

»з последнего столбца,

в точке

будет минимальным в силу того, что , . —ледовательно, .

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

,

то есть система ограничений двойственной задачи противоречива. “ак как из неотрицательности следует неположительность (нельз¤ сделать ее положительной). “о есть, система несовместна.

“еорема доказана.