Экономический смысл двойственности.
Теорема об оценках:
Значение переменных Уi* в оптимальном решении двойственной задачи представляют собой оценки - влияние свободных членов уравнений системы ограничений на величину Zmax.
AikXk = Bi, i=1,..m, k=1,..n
z = CkXk + Co (max), k=1,..n
Yi*=dZmax/dBi
Т.к. Z- линейная, то Zmax=Yi* Bi
Условные оценки позволяют охарактеризовать дефицитность ресурса (если Уi* > 0, то ресурс дефицитный, если =0, то нет). Формула служит для нахождения изменения Zmax при изменении ограничения Bi (берется произвольно).
Пусть требуется найти оптимальный производственный план выпуска 4 видов продуктов, при изготовлении которых используется 3 вида ресурсов А, Б и В.
1 2 3 4
А 4 2 2 1 35
Б 1 1 2 3 30
В 3 1 2 1 40
14 10 14 11
хi 0
(система)
4X1 + 2X2 + 2X3 + X4 35
X1 + X2 + 2X3 + 3X4 30
3X1 + X2 + 2X3 + X4 40
z = 14X1 + 10X2 + 14X3 + 11X4 (max)
Допустим, что мы хотим оценить каждую единицу используемых ресурсов, которые определяют максимальные производственные возможности предприятия. Речь идет об относительной оценке этих ресурсов, которая должна учесть их лимитированность и интенсивность расходования при изготовлении производственных продуктов. Такую оценку условно будем называть ценой. Пусть для рассматриваемого производства оценки 1 кг сырья А, Б и В соответственно равны у1, у2 и у3. Для определения этих оценок будем исходить из следующих соображений: стоимость сырья, затрачиваемого на производство единицы конечного продукта, не должна быть меньше стоимости единицы продукта.
Система (1) :
4у1 + y2 + 3y3 14
2y1 + y2 + y3 10
2y1 + 2y2 + 2y3 14
y1 + 3y2 + y3 11
T = 35y1 + 30y2 + 40y3 (min) (3)
yi 0 (2)
Найти цены у1, у2 и у3, которые удовлетворяли бы (1) и (2) и минимизировали бы (3). Полученная задача является двойственной по отношению к исходной, таким образом если исходная задача заключается в определении оптимального плана выпуска продукции при данных ограниченных ресурсах сырья, обеспечивающего максимум товарной продукции, то двойственная задача заключается в определении оценок единицы каждого из ресурсов из условия минимальной стоимости всех ресурсов.
Хопт = (0; 5; 12,5; 0) Zmax=225
Y опт= (3;4;0)
Ресурсы А и Б используются полностью, В остается в количестве 10.