Экономико-математическое моделирование /
←предыдущая следующая→
1 2
до¬стигнутого в результате предыдущих шагов), и условно оптимальный вы¬игрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) опти¬мальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последне¬го шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.
III. Пример задачи динамического программирования
Выбор состава оборудования технологической линии.
Есть технологическая линия , то есть цепочка, последовательность операций.
На каждую операцию можно назначить оборудование только каго-то одного вида, а оборудования, способного работать на данной операции, - несколько видов.
Исходные данные для примера
i 1 2 3
j 1 2 1 2 1 2
10 8 4 5 8 9
12 8 4 6 9 9
20 18 6 8 10 12
Стоимость сырья
Расходы , связанные с использованием единицы оборудования j-го типа на i-ой операции
Производительности, соответственно, по выходу и входу и для j-готипа оборудования, претендующего на i-ую операцию.
Решение:
Для того, чтобы решить данную задачу методом динамического программирования введем следующие обозначения:
N = 3 – число шагов.
- Технологическая линия.
= (0,0,0)
= ( )
– выбор оборудования для i-ой операции.
Ui – область допустимых УВ на i-м шаге.
т.е.
Wi – оценка минимальной себестоимости, полученная в результате реализации i-го шага.
S – функция общего выигрыша т. е. минимальная себестоимость .
- вектор – функция, описывающая переход системы из состояния в состояние под действием УВ.
- вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния xi-1 в состояние xi , т.е. оптимальный выбор оборудования за N шагов.
Si+1( ) – максимальный выигрыш ( в нашем случае минимальная себестоимость), получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.
S1( ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S1( ), если = 0.
Запишем вектора допустимых значений
Запишем вектора допустимых управляющих воздействий
Запишем вектор – функцию, описывающую переход системы из состояния в состояние под действием УВ.
Запишем основное функциональное уравнение
1) Обратный проход
Для i=3
Учитывая то, что этот шаг у нас последний и следующей операции
уже не будет, а также то, что мы на обратном проходе, вместо функции
возьмем стоимость сырья
при =
при =
т. е.
Для i=2
при =
при =
при =
при =
т. е.
Для i=1
при =
при =
при =
при ==
при =
при =
при =
при =
т. е.
2) Прямой проход
Учитывая то, что и = (0,0,0) имеем
i=1
i=2
i=3
Таким образом оптимальный выбор составаоборудования технологической линии предполагает следующее:
На 1-ую операцию назначим оборудование 2-го вида
На 2-ую операцию назначим оборудование 1-го вида
На 3-ью операцию назначим оборудование 2-го вида
Оценка минимальной себестоимости составит 105,5.
←предыдущая следующая→
1 2
|
|