- •4. Основные теоремы линейного программирования: сформулировать все, доказать теорему о существовании опорного плана (теорема 3).
- •5. Основные теоремы линейного программирования: сформулировать все, доказать теорему об оптимальности выпуклой комбинации планов злп (теорема 4).
- •6. Основные теоремы линейного программирования: сформулировать все, доказать теорему о существовании оптимального опорного плана злп (теорема 5).
- •Доказательство:
- •20. Обоснование решения транспортной задачи (тз) методом потенциалов. Проиллюстрировать метод на примере тз:
- •22. Постановка задачи динамического программирования (дп). Рекуррентные уравнения Беллмана (обратное и прямое), метод Беллмана. Решить методом Беллмана задачу распределения инвестиций:
- •23. Постановка задачи динамического программирования (дп). Рекуррентные уравнения Беллмана (обратное и прямое), метод Беллмана. Решить методом Беллмана задачу замены оборудования:
- •24. Управление запасами: стационарный детерминированный спрос. Формулы Уилсона.
- •28. Постановка задачи динамического программирования (дп). Рекуррентные уравнения Беллмана (обратное и прямое), метод Беллмана. Решить методом Беллмана задачу:
- •29. Определение оптимальных уровней запасов y* при вероятностном спросе и линейных функциях затрат.
28. Постановка задачи динамического программирования (дп). Рекуррентные уравнения Беллмана (обратное и прямое), метод Беллмана. Решить методом Беллмана задачу:
Для трёх предприятий выделяются средства в объёме bo (млн. руб.). Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами суммарных затрат (С) (млн. руб.) и доходов (R) (млн. руб.), связанных с реализацией каждого из проектов. Соответствующие данные (Cj, Rj, j=1,2,3) приведены в таблице. Включение проектов с нулевыми затратами позволяет возможность отказа от расширения предприятия. Найти оптимальное распределение инвестиций, максимизирующее доход от инвестиций в объёме bo, bo = 8 млн. руб.
Проект |
Предприятие 1 |
Предприятие 2 |
Предприятие 3 |
||||
|
C1 |
R1 |
C2 |
R2 |
C3 |
R3 |
|
1 |
3 |
5 |
3 |
4 |
0 |
0 |
|
2 |
4 |
6 |
4 |
5 |
2 |
3 |
|
3 |
- |
- |
5 |
8 |
3 |
5 |
|
4 |
- |
- |
- |
- |
6 |
9 |
Ответ:
Постановка задачи динамического программирования (ДП)
максимизировать (7.1.1)
при условиях (7.1.2 )
Рекуррентные уравнения Беллмана (обратное и прямое), метод Беллмана.
Прямое уравнение Беллмана.
Обратное уравнение Беллмана.
при ограничениях
Решение задачи.
29. Определение оптимальных уровней запасов y* при вероятностном спросе и линейных функциях затрат.
Рассмотрим частный случай модели при вероятностном спросе, когда функции затрат , и -линейные. В этом случае величину можно определить аналитически.
Действительно,
,
тогда
, (7.3.31)
Отсюда для нахождения оптимального уровня запасов получим уравнения
; (7.3.32)
где - функция распределения случайного спроса.
В частности, для спроса, распределенного по закону Рэлея,
,
имеем
,
отсюда
.
Для показательного распределения спроса получим
,
откуда
.
Рассмотрим случай дискретного распределения спроса :
(7.3.33)
Соответственно
(7.3.34)
Найдем приращение
. (7.3.35)
Д окажем существование и единственность оптимального решения , для чего исследуем знак приращения . При
,
а при
. (7.3.36)
Итак, монотонность функции обеспечивает однократность смены знака приращения . Очевидно, выбор должен производиться из условий:
, (7.3.37)
которые можно свести к системе неравенств:
. (7.3.38)
Найдем расходы за период так же, как и в детерминированном случае (рис. 7.15):
а) при средний положительный запас равен , а время его существования ;
б) при получим средний положительный запас , средний дефицит , время существования запаса и время существования дефицита .
Общие расходы в единицу времени составляют
.
30. Модель управления запасами при вероятностном спросе и мгновенных поставках.
Рассмотрим некоторые задачи управления запасами при вероятностном спросе. Простейшим случаем управления запасами является однократное принятие решений на пополнение запасов [І8]. Рассмотрим этот вариант.
I вариант. Рассмотрим модель управления запасами при вероятностном спросе и мгновенных поставках. Пусть - запас продукта к началу операции; - запас после пополнения ( ), а ( ) - случайный спрос за время операции ; - плотность распределения спроса; - расходы на пополнение запасов.
Предположим, что заказ на пополнение выполняется мгновенно. Если к концу операции на складе остается часть невостребованного запаса , то система снабжения несет расходы на сохранение избыточного запаса (при , ). Наоборот, при неполном удовлетворении спроса ( ) система платит штраф за дефицит . Тогда математическое ожидание суммарных расходов системы за период равно
. (7.3.28)
Найдем, при каких значениях величина будет минимальной. Для этого определим
, (7.3.29)
где , , - обозначены частные производные по соответствующим функциям ( в (7.3.29) учтено, что , и положим ).
В общем случае функция при фиксированных может иметь несколько минимумов.
Обозначим через абсциссу абсолютного минимума , а через , , точки следующих относительных минимумов, причем пусть < < < .< (рис. 7.12). Пусть далее , , - точки, удовлетворяющие таким условиям: < < < <.; = ,
= и т.д.
Тогда оптимальная стратегия управления запасами будет такой [18; 49]:
п ри заказывать ;
при ничего не заказывать;
при заказывать и т.д.
Приведем достаточные условия, при которых оптимальная стратегия имеет более простую форму, отвечающую одному минимуму функции [49]:
a) - не является относительным минимумом и
;
в) уравнение имеет не более одного вещественного корня;
c) → ∞ при → ∞.
Поясним физический смысл условий: а) экономическая целесообразность создания положительного запаса; с) неэффективность слишком больших запасов.
О бозначим через решение уравнения (рис. 7.13). Тогда оптимальная стратегия единственная и будет следующей:
при заказывать (делать заказа на поставку) ;
при ничего не заказывать.
ІІ вариант. Допустим, что стоимость пополнения запасов равна при и нулю при . Как видим, в этом случае в сравнении с вариантом І появился дополнительный член (фиксированная плата за заказ). В этом случае заказ целесообразно делать лишь при условии
. (7.3.30)
Е сли уравнение (7.3.30) имеет единственное решение , то оптимальная стратегия, как видно из рис. 7.14, имеет вид [49]:
при заказывать ;
при ничего не заказывать.
В литературе эта стратегия называется 'стратегией двух уровней' или (S,s)-стратегией [49].