6. Устойчивость оптимального базисного плана к изменениям ограничений.

Можно найти ресурс, который обеспечивает максимальную скорость возрастания целевой функции. Увеличивая его количество, можно увеличить прибыль предприятия. Однако с количеством ресурсов напрямую связан оптимальный план производства: изменяем количество ресурсов – изменяется план производства. При больших изменениях в наличии ресурсов возможны значительные изменения в оптимальном плане производства. Изменение в структуре производства крайне нежелательны. Структура оптимального плана – состав его базисных (ненулевых) и небазисных (нулевых) компонент. В экономической интерпретации: в каких пределах можно управлять запасами ресурсов, чтобы при этом не изменилась структура производства? Предположим, что правая часть i-го ограничения b_i изменилась на величину Θ, т.е. стала равной b_i+Θ, - соответствующий (новый) оптимальный план. Связь между старым x^* и новым оптимальными планами описывается соотношением , где zⁱ – i-ый столбец обратной базисной матрицы . Величина изменения правой части i-го ограничения Θ должна быть такой, чтобы выполнялось неравенство: _, Θ – интервал устойчивости к изменениям правой части i-го ограничения и обозначим . ,где – максимально возможное уменьшение, – максимально возможное увеличение правой части i-го ограничения. При этом

Таким образом, для исследования устойчивости оптимального базисного плана к изменениям правых частей ограничений необходимо найти интервалы устойчивости.

7. Транспортная задача: постановка задачи.

Модель транспортной задачи

,

a_i — запасы продукции на складах поставщиков, b_j — потребность в продукции потребителей. x_ij — неизвестный план поставки продукции от i-го поставщика к j-му потребителю, c_ij — стоимость доставки единицы продукции от от i-го поставщика к j-му потребителю. Произвольный набор чисел называется планом задачи.

Требуется найти такой план перевозок X от поставщика к потребителю, который бы обладал минимальными затратами на его реализацию. Обычно требования задачи сводятся в таблицу следующего вида:

потр пост	b1	…	bn
a1	c11 x11		c1n x1n
…
am	сm1 xm1		сmn xmn

При этом в таблицу заносятся только ненулевые значения x_ij. Поэтому клетка, в которой записано значение x_ij, называется заполненной, в отличие от пустой клетки, в которую не занесено значение x_ij.

Задача имеет решение тогда и только тогда, когда выполняется условие баланса

Задача, в которой выполняется это равенство , называется транспортной задачей закрытого типа, в отличие от задач открытого типа, в которых условие баланса не выполняется.

Если транспортная задача является открытой, то она обычно сводится к закрытой посредством введения фиктивного (m+1)-го поставщика, если спрос превышает предложение, или фиктивного (n+1)-го потребителя в противном случае.

Фиктивному поставщику в качестве объема его поставки приписывается разница между суммарным спросом и суммарным предложением. Затраты на доставку продукции принимаются нулевыми. Аналогичным образом вводится фиктивный потребитель, если суммарное предложение превышает спрос.