ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ПАРАМЕТРА y.
По ТДН, если (b - Ax)i > 0, т.е. i-й ресурс имеется в избытке, то yj =0, а если , то (b - Ax)i = 0, т.е. весь ресурс выработан и его можно докупить. Прибыль равна c¢ x = y¢ b = S yi ×bi. Þ yi = и при изменении i-го ресурса на ei прибыль изменится на величину yi×ei Т.е. yi является предельным значением цены ресурса, при которой производитель не терпит убытка. Ценность ресурса для производителя определяется производимыми товарами и выражает максимальную прибыль, какую может дать правильное использование единицы ресурса.
№7. Пример: Проверить, является ли y*= (0, 1, 5/3)решением двойственной задачи
6y1+4y2+7y3 àmin Выпишем ограничения прямой задачи и проверим их дляy*:
y1 +3y3 ³ 5 5=5 x1+3x2 -x3£ 6
3y1+y2+ y3 ³ 2 2⅔>2 Þ x2=0 x2+x3£ 4 y2¹0 Þ x2+x3=4
-y1+y2 ³ 1 1=1 3x1+x2 £ 7 y3¹0 Þ 3x1+x2 =7.
yj³0 j=1,2,3 xi³0 i=1,2,3
Мы использовали условия ТДН: (c’-y’A)2 ·x2=0, y2 ·(b-Ax)2=0 иy3 ·(b-Ax)3=0.
Для решения прямой задачи имеем 3 уравнения с 3 неизвестными. x*=(7/3,, 0, 4). Проверим ограничение 1 прямой задачи: 7/3+3·0 –4<6 Þ y* и x* - решения!
УСТОЙЧИВОСТЬ РЕШЕНИЯ В ЛП.
Пусть x, y - решение задачи ЛП с параметрами A,b,c. Предположим, что какие-нибудь параметры изменились. Останется ли пара (x, y) оптимальной?
1) Замена ресурса: b®b+e. Допустимость y остается, т.к. не зависит от b.
y¢A³c¢, y³0 Ax£b,x³0 Ax£b+eÛe³Ax–b- условия допустимости
(c¢ -y¢A)ixi=0 yj·(b–Ax)j=0 yj ·(b+e–Ax)j=0 Ûyj ·ej=0 - оптимальности.
Из оптимальности пары (x, y) следует:
yj>0 Þостаток ресурса (b–Ax)j=0, т.е. ресурс дефицитный и ej=0
yj=0 Þ (b–Ax)j³0, т.е. ресурс достаточный и ej ³ (Ax–b)j
Избыточный ресурс остается достаточным, а дефицитный – неизменным!!!
2) Меняем цену: c®c+d. Допустимость xостается, т.к. не зависит от с.
Новые ограничения: y¢A³c¢+d¢Ûd¢£y¢A- c¢, (c¢ +d¢ -y¢A)ixi=0 Ûdi ·xi=0
Из оптимальности пары (x, y) в обеих задачах следует:
xi>0 Þтовар производимый и di=0, т.е. цена на него неизменна.
xi=0 Þ(c¢–y¢A)i £0, т.е. цена не превышает ценности и di £ (y¢A– c¢)i
Цены на производимые товары – неизменны, а на непроизводимые - неприбыльны.
Пример (продолжение): x* = ( 7/3 , 0, 4 ) y* = (0, 1, 5/3) , ε³ Ax*-b
y1 =0 Þ ε1 ³ (Ax*-b)1 = 7/3 *1 +3*0-4-6=-72/3 , y2, y3 >0 Þ ε2= ε3=0
Продавать можно остатки 1-го ресурса, а докупать в первую очередь 3-й.
x1 , x3>0 Þδ1 ,δ3=0 Þизменение цен на продукты 1 и 3 меняет прибыль, а на второй – нет.
δ2 £ (y*’A-c’)2 = 3*0+1+5/3-2=2/3 т.е. δ2£ 2/3 , т.е. цена на товар 2 может увеличиться, но не более, чем на 2/3.
ТРУДОЕМКОСТЬ ЛП.
Если в множестве {x³0 | Ax £ b} есть хотя бы одна вершина, то решение ЛП можно искать среди его вершин. Вершинам n-мерного пространства соответствуют системы из n равенств среди m ограничений. Число способов выбора = . Решение системы из n линейных уравнений имеет трудоемкость O(n3), вычисление функционала – O(n) Þ полный перебор - O().
Задача ЛП была впервые сформулирована в 1939 году Л.Канторовичем как инструмент планирования централизованной экономики СССР. В 1975 г. Канторович получил Нобелевскую премию по экономике. Д.Данциг (США, 1947) предложил для решения ЛП симплекс-метод, имеющий в худшем случае экспоненциальную трудоемкость. Математики всего мира долго пытались построить для ЛП полиномиальный алгоритм. Доказать полиномиальную разрешимость ЛП удалось Л.Хачияну (Москва,1979), используя обобщение на Ân метода половинного деления в Â1- метод эллипсоидов (Н.Шор, Москва,1977).
Основная идея метода:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.