Двойственные оценки и условия сопряженности в задаче ЛП
Для любой линейн модели м б построена двойств к ней..
Показатели Y1…Ym – двойственные оценки ресурсов. Другое название теневые, маржинальные, внутренние цены. Эти оценки характеризуют значимость ресурса для предприятия. Если какой-то ресурс в избытке, то его оценка равна 0, а если он использован полностью, то его оценка положительна. Оценка показывает на какую величину возрастет общий экономический результат при увеличении запаса соответств ресурса на единицу объема. В оптимальном решении оценки то же станут оптимальными.
Оценки столбцов: Каждая оценка ∆j=1,n характеризует эффективность соответствующей технологии. ∑yi*ai1-c1≥0 – эффективность первой технологии. Значимость израсходов-х рес-ов всегда больше рез-та. Эффективной признается такая технология для которой выполняется строгое равенство, когда значимость равна цене.
для текущей вершины если они не оптимальны могут встречаться отрицательные оценки внебазисных столбцов. Предполож что Ак оценка ∆к<0, нужно это устранить, а следовательно перейти на другую вершину соотв Ак это кандидат на ввод в базис. По спец формуле опред-ся среди базисных столбцов кандидат на выброс, если задача разрешима F(x)+ ∆F, ∆F=-∆k*xk – приращение ф-ции цели (на столько она увеличивается в соседней точке). Если кандидат на выброс Аг не находится то задача будет неразрешима из-за неограниченности ф-ции цели
ФОРМАЛЬНО
ПрямаяДвойственная
∑cjxj→max( j=1,n) ∑biyi→min (i=1,m)
∑aijxj≤bi (i=1,m) ∑aijyi≥Cj (j=1,n; i=1,m) –знач-ть всех рес-сов < Эф-та
Y* =(y*1, y*2…y*n) – вектор оптим
всегда рассм две связвнные модели: прямая и двойственная. С1х1+…СnXn→max. Двойственная к этой задаче минимизировать расход ресурсов на выпуск продукции, скалькулированный во внутренних ценах (оценка значимости). Получим Yi*, при прямой задаче получили бы Y*. F(xj*)=Q(Yi*).
Теорема двойственности (8): Если разрешима прямая задача, то и разрешима двойственная и наоборот и для оптим решений F(xj*)=Q(Yi*). Теорема (8.2). Если прямая задача неразрешима из-за нарушения условий, то двойственная задача то же неразреш. из-за неграничености ф-ции цели и наоборот.
Теорема Куна-Такера (9). (условие сопряженности):
Х* и У* - реш прям и двоийств задачей.
{X*= (x*1…x*j…x*n)
{Y*= (y*1…y*i…y*m)
Условия:
I. (∑aijxj*-bi)y*i=0; i=1,m, j-=1,n; y*i≥0,
II. (∑aijy*i-cj)x*j=0; i=1,m, j-=1,n (aijy*i-cj оценка рентабельности способов пр-ва), ∆j=0, xj*>0, ∆j>0, xj*=0
Если имеют место одно из условий сопряженности (а или б) то обе задачи разрешимы, а соответств решения оптимальны.
Эконом истолкование: (I.) ∑aijxj*- оптим расход i-го рес-са, bi- его запас.
- aijxj*≤0. если рес-в в оптим реш остался в избытке, то его двоийств оценка д=0, => он считается неэф-ным.
- aijxj*<0 → y*i=0 если рес-с использован полностью.
- aijxj*=0 → y*i>0 тогда двойств оценка >0 и количественно показывает его предельн эф-тьна V доп привлек рес-са.
Из(I.) => что его оценкаи хар-ют одновременно эф-ть рес-са и его дефицитность.
(II.) (∑aijy*i – суммарный расход всех рес-сов на ед V прод-ции j, оцененнй по их значимости.
∑aijy*i≥0 {…>0 – значимость используемых рес-сов больше, чем получ эф-т, => x*j=0, т.е. такой вид прод-ции в оптим плане не выгоден (не выпускается)
{…=0 –знач-ть и эф-т совпадают => x*j>0, т.е. прод-т б выпускаться.