Движение в прямом направлении

На последнем шаге попятного движения найдено оптимальное управление для начального момента времени . Оптимальные управления для остальных моментов времени находятся на этапе прямого движения. Рассмотрим эту процедуру с помощью временной оси (рис. 6).

t ₁ p ₁=2000 t ₂ p ₂=3000 t ₃ p ₃=4000 t ₄ p ₄=2000 t ₅= T t

Рис. 6

В начальный момент времени объект находится в состоянии . Оптимальное управление найдено на последнем шаге попятного движения. Под воздействием этого управления объект перейдет к моменту времени в состояние . Для этого состояния из табл. 4 извлекаем оптимальное управление . Под его воздействием ОУ перейдет к моменту времени в состояние . Из табл. 3 для состояния объекта находим оптимальное управление . Под воздействием этого управления объект перейдет к моменту времени в состояние . Для этого состояния из табл. 2 извлекаем оптимальное управление , под воздействием которого ОУ переходит в конечное состояние .

Нулевое конечное состояние ОУ означает, что к началу следующего производственного цикла на складе не будет запаса готовой продукции. Такой результат обусловлен начальной постановкой задачи, в которой конечное состояние ОУ не задавалось (задача со свободным правым концом траектории). Конечное состояние ОУ определилось в результате оптимального решения задачи на основе минимума суммарных затрат на производство и хранение продукции. Если к началу следующего производственного цикла по каким-то соображениям нужен задел готовой продукции, то он должен быть задан в исходной постановке задачи в виде конечного состояния ОУ.

2.4. Пример: задача оптимального складирования

Постановка задачи. Имеется склад ограниченной емкости V, предназначенный для хранения некоторого товара. Период хранения разбит на N промежутков времени. Решения о пополнении и расходовании запасов принимаются в начале каждого промежутка в моменты времени t_i (). Товар можно покупать и продавать в различных количествах по ценам текущего момента времени. Покупка товара характеризуется затратами α_i на единицу продукции, продажа товара со склада - выручкой β_i на единицу продукции (). Известны начальный и конечный уровни запасов товара на складе (конечный уровень может и не задаваться).

Возможны три варианта очередности пополнения и расходования запасов в каждом из промежутков времени [5]:

-пополнение предшествует расходованию,

-расходование предшествует пополнению,

-очередность любая (выбирается оптимальным образом в каждый момент принятия решения).

i
αi
βi

Определить оптимальную политику покупок и продаж, обеспечивающую максимальную суммарную прибыль от функционирования склада при следующих данных: число периодов хранения N=5, емкость склада V=50, начальный запас товара y₀=35. Затраты на приобретение товара и выручка от реализациитовара , заданы в табл. 5.

Таблица 5

Формализация задачи. Объектом управления в данной задаче является склад. На вход ОУ в дискретные моменты времени t_i () поступают управляющие воздействия , представляющие собой решения о пополнении и расходовании товара. Здесь - величина пополнения (закупки) товара по цене , - величина расходования (продажи) товара со склада по цене . Процедуру управления можно пояснить на временной оси (рис. 7).

В качестве выходного сигнала ОУ примем количество товара на складе в момент времени t_i (). Разностное уравнение, описывающее поведение ОУ, имеет вид:

.

Показателем качества является суммарная прибыль от функционирования склада

.

Управляющие воздействия подвержены ограничениям, характер которых зависит от очередности пополнения и расходования товара:

а) пополнение предшествует расходованию:

б) расходование предшествует пополнению:

t₀ t₁ t₂ t₃ t₄ t₅=T t

y₀=35 y₁ y₂ y₃ y₄ y₅

u₀ u₁ u₂ u₃ u₄

Рис. 7

Решение задачи (пополнение предшествует расходованию). Решение задачи состоит из этапов попятного и прямого движения.

1. Этап попятного движения. Это многошаговый процесс, который протекает от конца интервала управления к его началу.

Шаг 1. Отступим на один шаг от конца интервала управления и найдем управляющее воздействие , от которого зависит только последнее слагаемое в показателе качества . Образуем на его основе целевую функцию

.

Дополним целевую функцию ограничениями

или

На данном шаге попятного движения имеем задачу линейного программирования с двумя переменными , которую целесообразно решать графическим способом. Ограничения образуют область допустимых решений в виде многоугольника ОАВС, изображенного на рис. 8. Вершины многоугольника характеризуются координатами: О (0,0), А (0, ), В (V - , V), С (V - ,0). Состояние склада является неизвестным, поэтому неизвестен конкретный вид многоугольника ОАВС. Состояние зависит от управлений в предыдущие моменты времени, которые еще не рассматривались, поэтому состояние может принять любое значение в диапазоне от 0 до V. При многоугольник превращается в треугольник; при многоугольник превращается в отрезок, лежащий на вертикальной оси. Однако при любой конфигурации многоугольника решением задачи будет одна и та же из его вершин.

Найдем градиент целевой функции

и изобразим его на рис. 9. Проведем вспомогательную линию, перпендикулярную к градиенту и пересекающую многоугольник ОАВС, и будем перемещать ее параллельно самой себе в направлении градиента до тех пор, пока она не коснется крайней вершины многоугольника – вершины В, которая и является решением задачи.

Рис. 9

Рис. 8

Координаты т. B формируют оптимальное управление на данном шаге: , которое интерпретируется следующим образом: заполнить склад полностью, а затем весь товар продать. Подставим оптимальное управление в показатель качества . Он примет максимальное значение, которое принято обозначать через и называть функцией Беллмана:

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

.

Заменим последнее слагаемое его максимальным значением , а состояние выразим через разностное уравнение ОУ: . В итоге получим целевую функцию

,

которую дополним ограничениями

Данная оптимизационная задача также является задачей линейного программирования, графическое решение которой показано на рис. 10. Здесь ограничения представлены многоугольником ОАВС, а градиент целевой функции имеет направление:

.

Решением задачи является т. А , которая формирует оптимальное управление : ничего не закупать, весь товар продать.

Подставим оптимальное управление в показатель качества . Он примет максимальное значение

.

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

.

Ограничения носят вид

и приводят к допустимому многоугольнику ОАВС (рис. 11). Градиент целевой функции : .

Решением задачи на третьем шаге является т. О (0,0), которая формирует оптимальное управление : товар не закупать, товар не продавать. Максимальное значение показателя после подстановки в него оптимального управления равно

.

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

.

Ограничения носят вид

и приводят к допустимому многоугольнику ОАВС (рис. 12). Градиент целевой функции : . Вспомогательная линия параллельна стороне ОС, поэтому решением задачи может служить т. О (0,0) или т. С (V - ,0), или любая точка отрезка ОС.

а) Рассмотрим в качестве решения задачи т. О (0;0), которая дает оптимальное управление : товар не закупать, товар не продавать. Максимальное значение показателя при таком управлении имеет вид

.

б) Если за решение задачи взять т. С , то оптимальное управление : заполнить склад до отказа, но ничего не продавать. Максимальное значение показателя при таком управлении имеет вид

.

Шаг 5. Это последний шаг попятного движения, на котором участвуют все слагаемые показателя качества . Заменим последние четыре слагаемых на их максимальное значение, полученное на предыдущем шаге:

.

а) Возьмем за оптимальное решение на предыдущем шаге т. О. В этом случае функцию следует заменить функцией

.

Показатель качества примет вид

.

Ограничения на этом шаге имеют вид

и приводят к допустимому многоугольнику ОАВС (рис. 13). Градиент целевой функции : . Решением задачи является т. В (), которая формирует оптимальное управление : заполнить склад до отказа, затем весь товар продать. Начальный запас товара на складе задан: , поэтому можем найти конкретный вид оптимального управления . Показатель качества примет максимальное значение

.

б) Возьмем за оптимальное решение на предыдущем шаге т. С. В этом случае функцию следует заменить функцией

.

Показатель качества примет вид

.

Градиент этой целевой функции имеет такое же направление, как в пункте а. Решением задачи по-прежнему является т. В. Показатель качества примет максимальное значение

2. Движение в прямом направлении. Решение задачи на втором этапе целесообразно проводить с помощью временной оси (рис. 14), на которой показаны моменты принятия решений, состояние склада, управляющие воздействия.

Оптимальное управление для момента времени найдено на последнем шаге попятного движения: . Оно предписывает закупить 15 ед. товара, чтобы полностью заполнить склад, а затем продать весь товар в количестве 50 ед.

Рис. 14

К моменту времени склад будет находиться в состоянии

.

Оптимальное управление найдено на 4 шаге попятного движения в двух вариантах: в виде т. О и в виде т. С. Поэтому будет два варианта решения задачи в целом.

а) Рассмотрим первый вариант, приняв за оптимальное управление координаты т. О, т.е. : товар не закупаем, товар не продаем.

К моменту времени состояние склада . Оптимальное управление найдено на 3 шаге попятного движения: - товар не закупаем, товар не продаем.

К моменту времени склад будет находиться в состоянии

.

Оптимальное управление : товар не закупаем, товар не продаем.

К моменту времени склад будет находиться в состоянии

.

Оптимальное управление найдено на 1 шаге попятного движения: , которое интерпретируется следующим образом: закупаем товар в количестве 50 ед. до полного заполнения склада, а затем весь товар продаем.

В результате решения задачи конечное состояние склада, которое в исходных данных не задавалось, оказалось нулевым. Прибыль от функционирования склада составила 850 ед. Она найдена на последнем шаге попятного движения, но может быть проверена в соответствии со схемой пополнения и расходования товара (рис. 14):

.

б) Вернемся к моменту времени и рассмотрим второй вариант решения задачи, приняв за оптимальное управление координаты т. С, т.е. : закупаем товар в количестве 50 ед. до полного заполнения склада, товар не продаем. Для остальных моментов времени рассуждения носят аналогичный характер. Предоставим читателю возможность провести эти рассуждения самостоятельно и убедиться, что второй вариант решения задачи соответствует рис. 15.

Рис. 15

Обобщение задачи. Рассмотрим коротко 2 вариант очерёдности, когда расходование предшествует пополнению. В этом случае изменятся ограничения, налагаемые на управляющее воздействие. На каждом шаге попятного движения они примут вид

Этим ограничениям соответствует область допустимых решений ОАВС (рис. 16), конкретная конфигурация которой зависит от состояния склада .

Обсудим 3 вариант функционирования склада, когда очередность выбирается оптимальным образом на каждом шаге попятного движения. Предположим, что на i- м шаге сложилась ситуация, показанная на рис. 17. Многоугольник ОАВС отражает 1 вариант очередности, решением задачи является т. В. Многоугольник ОАDС соответствует 2 варианту очередности, решением задачи служит т. D. Показатель качества принимает большее значение в т. В, поэтому на данном шаге попятного движения принимается 1 вариант очередности: пополнение предшествует расходованию, и оптимальное управление формируется на основе т. В.

Рис. 16

Дата добавления: 2014-11-29