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

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

.

При этом . Отсюда следует, что двойственная переменная y_i является коэффициентом при b_i и, следовательно, показывает, как изменится целевая функция при изменении i- го ресурса на единицу. В литературе двойственные переменные часто называют двойственными оценками. В отчетах EXCEL двойственная оценка называется теневой ценой.

Теорема равновесия. План прямой задачи и план соответствующей двойственной задачи являются оптимальными при выполнении следующих условий:

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

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

Таким образом, в парах соотношений

из знака строгого неравенства во одном соотношении каждой пары следует знак строгого равенства в другом.

Условия теоремы равновесия часто записывают в виде

и называют условиями дополняющей нежесткости.

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

Значения двойственных оценок можно определить по симплексной таблице решения прямой задачи следующим образом: -( ), где j-номера столбцов единичных векторов из исходной симплекс-таблицы (на начальной итерации); -окончательные оценки из последней симплекс-таблицы, соответствующие этим векторам. При этом индексы двойственных оценок определяются номером ограничения, которому они соответствуют. Например, из симплексной таблицы 6 можно определить, что двойственная оценка для трудовых ресурсов , для сырья и для финансов .

Необходимо заметить, что если в качестве канонической формы рассматривается задача максимизации, то сумма берется без знака “-“.

5. Задачи дробно-линейного программирования

Общая задача дробно-линейного программирования состоит в определении максимального (минимального) значения функции

при условиях

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

Сформулированная задача может быть сведена к задаче линейного программирования. Для этого следует обозначить

и ввести новые переменные

.

Используя введенные обозначения, исходную задачу сведем к следующей - найти максимум (минимум) функции

при условиях

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

Пример . Для производства двух видов изделий A и В используются два типа технологического оборудования. Первое изделие проходит обработку только на втором типе оборудования, второе - на первом и на втором. Время обработки каждого из изделий на оборудовании данного типа приведено в табл. 9. Там же указаны затраты, связанные с производством одного изделия каждого вида.

Таблица 9

Тип оборудования	Затраты времени (ч) на обработку одного изделия
	A	B
I		2
II	1	2
Затраты на производство Одного изделия	5	4

Оборудование II типа предприятие может использовать не более 52 часов. При этом оборудование I типа целесообразно использовать не менее 16 часов. Требуется определить, сколько изделий каждого вида следует изготовить, чтобы себестоимость одного изделия была минимальной.

Составим математическую модель задачи. За x₁ обозначим количество выпускаемых изделий вида A, за x₂ – количество изделий вида B. Себестоимость определяется следующим образом: С=З/K, где К – количество выпускаемых изделий, З - общие затраты на их производство. Тогда получим следующую задачу дробно-линейного программирования:

;

Преобразуем ограничения-неравенства данной задачи в равенства:

;

Сведем данную задачу к задаче линейного программирования. Для этого обозначим через y₀ и введем новые переменные .

В результате приходим к следующей задаче: найти минимум функции

при условиях

Система ограничений задачи содержит всего одну базисную переменную y₄. Поэтому составим расширенную задачу путем введения двух искусственных переменных y₅ и у₆. :

при условиях

Решение задачи методом искусственного базиса приведено в табл. 10.

Таблица 10

x	c	b	5	4	0	0	0	M		M
			y1	y2	y3	y4	y0	y6		y5
Y5	М	0	0	2	-1	0	-16	0		1
y4	0	0	1	2	0	1	-52	0		0
y6	М	1	1	1	0	0	0	1		0
0			-5	-4	0	0	0	0		0
1			1	3	-1	0	-16	0		0
y2	4	0	0	1	-1/2	0	-8	0
y4	0	0	1	0	1	1	-36	0
y6	M	1	1	0	1/2	0	-6	1
0			-1	0	-2	0	-32	0
M			1	0	1/2	0	-6	1
y2	4	0	0	1	-1/2	0	-8	0
y1	5	0	1	0	1	1	-36	0
y6	M	1	0	0	-1/2	-1	30	1
0			0	0	-16/3	5	-220	0
M			0	0	-1/2	-1	30	0
y2	4	8/30	0	1	-19/30	-8/30	0
y1	5	36/30	1	0	12/30	-6/30	0
y0	0	1/30	0	0	-1/60	-1/30	1
220/30			0	0	-12/30	-72/30	0

Из таблицы видно, что оптимальным планом задачи является

.

Учитывая, что , находим оптимальный план исходной задачи:

. F(X^*)=220/30.

5. Решение транспортных задач линейного программирования

Пусть имеется m пунктов отправления , из которых сосредоточен однородный груз в количестве единиц, и n пунктов назначения , потребности которых в грузе составляют единиц. Стоимость перевозки единицы груза из пункта A_i в пункт B_j равна с_ij. Необходимо составить такой план перевозки грузов (т.е., определить сколько единиц груза необходимо перевезти из каждого пункта отправления в каждый пункт назначения), который бы обеспечивал вывоз всех грузов из пунктов отправления, удовлетворение всех потребностей в пунктах назначения и имел бы минимальную стоимость.

Обозначим через x_ij количество груза, перевозимого из пункта A_i в пункт B_j. Тогда математическая модель данной задачи может имеет следующий вид:

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