Пример построения двойственной задачи

Построить двойственную задачу к следующей задаче ЛП.

Прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной: согласовать знаки неравенств в ограничениях с целевой функцией. Так как ЦФ минимизируется, то неравенства должны быть записаны с помощью знака «». Для этого второе неравенство умножим на -1:

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

Задача слева – исходная прямая задача, задача справа – двойственная к исходной задаче.

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

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

(12)

Пусть решение задачи найдено одним из стандартных методов: . Построим двойственную задачу:

(13)

По первой теореме двойственности задача разрешима, причем . Найдем оптимальный план задачи (13), используя вторую теорему двойственности. Подставим координаты вектора в ограничения задачи (12). Получим

Следовательно, в силу УДН, неравенство должно выполняться как равенство, т. е. . Далее так как , то в силу УДН,

Получаем систему линейных уравнений и решаем ее:

Планы и удовлетворяют УДН, следовательно, в силу второй теоремы двойственности, являются оптимальными в задачах (12) и (13) соответственно.

Пример проверки вектора на оптимальность

Исследовать вектор на оптимальность в задаче ЛП.

Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:

Так как второе ограничение выполняется как строгое неравенство, то в силу УДН для оптимальности вектора необходимо выполнение равенства .

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

Поскольку , то из третьего и четвертого ограничений получаем . Но по УДН из условия следует, что должно выполняться равенство в первом ограничении двойственной задачи:

Подставляя значения получим Следовательно, УДН не выполняются и вектор не является оптимальным в исходной задаче.

Пример решения задачи ЦЛП

Решить задачу ЦЛП.

Решаем задачу ЛП симплекс-методом. Оптимальная таблица имеет вид

	b
L	-14/3	-4/3	-2/3
	5/3	1/3	2/3
	4/3	2/3	-2/3

Оптимальное решение не является целочисленным. Выберем среди нецелочисленных переменных переменную с максимальной дробной частью и построим соответствующее отсечение:

Приписывая это ограничение к симплексной таблице и проводя стандартное преобразование двойственным симплекс-методом, получим:

	b
L	-14/3	-4/3	-2/3
	5/3	1/3	2/3
	4/3	2/3	-2/3
	-2/3	-1/3	-2/3

	b
L	-4	-1	-1
	1	0	1
	2	1	-1
	1	1/2	-3/2

Полученная таблица является оптимальной. Соответствующее оптимальное решение является целочисленным. Значение функции на этом решении .

Пример построения опорного плана методом

северо-западного угла

				1		2	3
		1		15		20		35	20	0	0
		2				0	30	30	30	30
15	20		30		=
0	20		30
0	0		30
0	0		0

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

Пример построения опорного плана методом

минимальной стоимости

				1		2	3
		1		⁹		5⁷	30¹	35	5	5	5
		2		15²		15³	⁸	30	30	15	0
15	20		30		=
15	20		0
0	20		0
0	5		0