Двойственность в линейном программировании

Двойственная задача заключается в минимизации общей оценки всего имеющегося количества ресурсов, т.е.

Z = 360 y₁ + 400 y₂ + 134 y₃ + 96 y ₄® min

при условиях

y₁ ³ 0, y₂ ³ 0, y₃ ³ 0, y₄ ³ 0,

где y₁, y₂, y₃, y₄ - условные оценки единицы соответствующего ресурса.

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

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

Теорема 2. (равновесия ). Если в оптимальном плане значение какой - либо переменной строго больше нуля, то соответствующее ограничение двойственной задачи при подстановке в него оптимального плана становится равенством.

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

y₁ = 0, y₂ = 0, y₃ = 2, 75, y₄ = 2, 333.

Переменные y_i являются объективно-обусловленными оценками одной единицы ресурса.

Величина двойственной оценки того или иного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу. Так, если фонд времени работы оборудования увеличить на один станко-час., то можно построить новый оптимальный план, в котором общая прибыль будет на 2, 75 д. ед. выше. Если увеличить на одну единицу рабочую силу, то общая прибыль возрастет на 2, 333 д. ед.. Нулевая оценка, полученная для сырья 1 и 2 вида, показывает, что сырье 1 и 2 вида используется не полностью и дальнейшее увеличение его количества не повлияет на оптимальный план выпуска товара и суммы прибыли.

Двойственные оценки измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи.

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

Таблица 4.3

Постановка двойственной задачи.

	x1	x2	...	xj	...	xn
y1	a 11	a 12	...	a 1j	...	a1n	b1
y2	a 21	a 22	...	a 2j	...	a2n	b 2
...	...	...	...	...	...	...	...
ym	a m1	a m2	...	a mj	...	a mn	bm
	c1	c2	...	cj	...	cn

При использовании теоремы равновесия для отыскания оптимального плана двойственной задачи в верхнюю строку таблицы рекомендуется подставить оптимальный план исходной задачи. Для положительных координат этого плана соответствующий столбец ограничений двойственной задачи превращается в строгое неравенство. Двойственные оценки можно найти, решая систему уравнений. [2], [27], [30].

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