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

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

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

Билет 16

Формулировка двух типов задач поиска решений при использовании детерминированного эквивалента стохастической задачи МП на максимум математического ожидания функции цели и на максимум вероятности (надежности) достижения заданного уровня функции цели.

Рассматривается задача ЛП, в которой требуется найти максимум линейной формыL=(C,X)àMAX при условиях AX≤B и X≥0, причем элементы вектора ограничений, элементы матрицы условий и коэффициенты функции цели могут быть случайными числами как с известными характеристиками (случай риска), так и неизвестными (случай неопределенности).

1) все значения заменяются на мат. ожидании (среднее значение) – максимизация результата при заданной надежности P ≥ Р при Fà max

Случаен только вектор С функции цели, остальная информация детерминирована. Обычный в этой ситуации подход - выбор в качестве критерия математического ожидания функции цели - сводит задачу к детерминированной (критерий имеет вид (^C,X)àMAX, где ~С - математическое ожидание вектора С). Если статистические характеристики вектора С неизвестны, то применяются различные гипотезы и оценки, а также методы анализа зоны неопределенности.

2) максимизация надежности при заданном уровне эффекта F ≥ F при maxP(F). Если случайны не только вектор С, но и другая информация: вектор В и матрица условий А, то необходимо уточнить исходную постановку задачи: определить, что понимается под допустимым решением (планом), а также смысловое содержание показателя качества решений.

Р(SUM Aij*Xj <= Bi) >= Pi; i=1,...,m; 0 =< Pi <= 1 при этом часто матрица А предполагается фиксированной и случаен только вектор ограничений В; если множество возможных состояний природы конечно и известны характеристики (оценки значений и их вероятностей) для каждого элемента Вi (т.е. Bki и Hki для k=1,...,s), то можно определить значения ~Bi, которые удовлетворяют условию P(Bi(q)>=~Bi)>=Pi; действительно, для этого необходимо упорядочить значения Bki в порядке убывания и выбрать наименьшую группу, удовлетворяющую условию: вероятность попадания значения Bi в данную группу больше или равна Pi (для этого суммарная вероятность группы должна быть больше или равна Pi). Тогда задача будет сведена к детерминированной: (^C,X)àMAX AX<=~B, где ~B=(~B1,~B2,...,~Bm)

 

 

Билет 17