Двойственные оценки и условия сопряженности в задаче ЛП

Для любой линейн модели м б построена двойств к ней..

Показатели Y₁…Y_m – двойственные оценки ресурсов. Другое название теневые, маржинальные, внутренние цены. Эти оценки характеризуют значимость ресурса для предприятия. Если какой-то ресурс в избытке, то его оценка равна 0, а если он использован полностью, то его оценка положительна. Оценка показывает на какую величину возрастет общий экономический результат при увеличении запаса соответств ресурса на единицу объема. В оптимальном решении оценки то же станут оптимальными.

Оценки столбцов: Каждая оценка ∆_j=1,n характеризует эффективность соответствующей технологии. ∑y_i*a_i1-c₁≥0 – эффективность первой технологии. Значимость израсходов-х рес-ов всегда больше рез-та. Эффективной признается такая технология для которой выполняется строгое равенство, когда значимость равна цене.

для текущей вершины если они не оптимальны могут встречаться отрицательные оценки внебазисных столбцов. Предполож что Ак оценка ∆к<0, нужно это устранить, а следовательно перейти на другую вершину соотв Ак это кандидат на ввод в базис. По спец формуле опред-ся среди базисных столбцов кандидат на выброс, если задача разрешима F(x)+ ∆F, ∆F=-∆k*x_k – приращение ф-ции цели (на столько она увеличивается в соседней точке). Если кандидат на выброс Аг не находится то задача будет неразрешима из-за неограниченности ф-ции цели

ФОРМАЛЬНО

ПрямаяДвойственная

∑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, т.е. прод-т б выпускаться.