- •50. Что выражает функция Беллмана в задаче о замене оборудования?
- •51. Запишите рекуррентные соотношения Беллмана для задачи о замене оборудования.
- •1. Двойственная задача лп.
- •2. Экономическая интерпретация двойственной задачи.
- •3. Основные соотношения двойственности.
- •4. Предварительный анализ оптимального решения задачи линейного программирования.
- •5. Чувствительность целевой функции к изменениям ограничений.
- •6. Устойчивость оптимального базисного плана к изменениям ограничений.
- •7. Транспортная задача: постановка задачи.
- •8. Транспортная задача: понятие базисного плана перевозок.
- •9. Методы построения начального базисного плана.
- •10. Распределительный метод решения транспортной задачи. Проверка достаточных условий оптимальности
- •11. Распределительный метод решения транспортной задачи. Вычисление максимально допустимой циркуляции.
- •12. Метод потенциалов решения транспортной задачи.
- •13. Задача целочисленного линейного программирования: постановка, подходы к разработке методов.
- •14. Метод ветвей и границ: общая схема.
- •15. Решение целочисленной задачи линейного программирования методом ветвей и границ.
- •16. Алгоритм Гомори: построение правильного отсечения, его присоединение к симплексной таблице, выбор разрешающей строки и ведущего столбца.
- •17. Динамическое программирование: предмет исследования, математическая модель многошагового процесса.
- •18. Задача распределения ресурсов: постановка и анализ (вывод соотношений Беллмана).
- •19. Задача о замене оборудования: постановка и анализ (вывод соотношений Беллмана))
6. Устойчивость оптимального базисного плана к изменениям ограничений.
Можно найти ресурс, который обеспечивает максимальную скорость возрастания целевой функции. Увеличивая его количество, можно увеличить прибыль предприятия. Однако с количеством ресурсов напрямую связан оптимальный план производства: изменяем количество ресурсов – изменяется план производства. При больших изменениях в наличии ресурсов возможны значительные изменения в оптимальном плане производства. Изменение в структуре производства крайне нежелательны. Структура оптимального плана – состав его базисных (ненулевых) и небазисных (нулевых) компонент. В экономической интерпретации: в каких пределах можно управлять запасами ресурсов, чтобы при этом не изменилась структура производства? Предположим, что правая часть i-го ограничения bi изменилась на величину Θ, т.е. стала равной bi+Θ, - соответствующий (новый) оптимальный план. Связь между старым x* и новым оптимальными планами описывается соотношением , где zi – i-ый столбец обратной базисной матрицы . Величина изменения правой части i-го ограничения Θ должна быть такой, чтобы выполнялось неравенство: , Θ – интервал устойчивости к изменениям правой части i-го ограничения и обозначим . ,где – максимально возможное уменьшение, – максимально возможное увеличение правой части i-го ограничения. При этом
Таким образом, для исследования устойчивости оптимального базисного плана к изменениям правых частей ограничений необходимо найти интервалы устойчивости.
7. Транспортная задача: постановка задачи.
Модель транспортной задачи
,
ai — запасы продукции на складах поставщиков, bj — потребность в продукции потребителей. xij — неизвестный план поставки продукции от i-го поставщика к j-му потребителю, cij — стоимость доставки единицы продукции от от i-го поставщика к j-му потребителю. Произвольный набор чисел называется планом задачи.
Требуется найти такой план перевозок X от поставщика к потребителю, который бы обладал минимальными затратами на его реализацию. Обычно требования задачи сводятся в таблицу следующего вида:
потр пост |
b1
|
…
|
bn
|
a1
|
c11 x11 |
|
c1n x1n |
…
|
|
|
|
am
|
сm1 xm1 |
|
сmn xmn |
При этом в таблицу заносятся только ненулевые значения xij. Поэтому клетка, в которой записано значение xij, называется заполненной, в отличие от пустой клетки, в которую не занесено значение xij.
Задача имеет решение тогда и только тогда, когда выполняется условие баланса
Задача, в которой выполняется это равенство , называется транспортной задачей закрытого типа, в отличие от задач открытого типа, в которых условие баланса не выполняется.
Если транспортная задача является открытой, то она обычно сводится к закрытой посредством введения фиктивного (m+1)-го поставщика, если спрос превышает предложение, или фиктивного (n+1)-го потребителя в противном случае.
Фиктивному поставщику в качестве объема его поставки приписывается разница между суммарным спросом и суммарным предложением. Затраты на доставку продукции принимаются нулевыми. Аналогичным образом вводится фиктивный потребитель, если суммарное предложение превышает спрос.