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

Дискретный вариант динамического программирования

Пусть имеется дискретный ОУ, на вход которого в моменты времени поступают управляющие воздействия . Выходной сигнал объекта фиксируется в те же моменты времени.

u(t_i)=u_i y y(t_i)=y_i

Состояние объекта управления характеризуется вектором состояния:

Здесь переменные состояния связаны со значениями выходного сигнала в настоящий и предыдущие моменты времени.

Поведение объекта описывается разностным уравнением:

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

Запишем критерий оптимальности в развернутом виде:

Показатель качества состоит из N слагаемых, причем каждое слагаемое зависит от вектора состояния и управляющего воздействия в соответствующий момент времени.

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

.

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

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

Предположим, что задача минимизации показателя решена и получено оптимальное управление . Это управление зависит от вектора состояния , поэтому будем называть его условно-оптимальным управлением. Подставим оптимальное управление в показатель . Он примет минимальное значение, которое обозначим через и будем называть функцией Беллмана. Функция Беллмана представляет собой минимальное значение показателя качества, в которое он обращается при подстановке в него оптимального управления.

В данном случае принцип оптимальности Беллмана проявляется в том, что оптимальное управление в момент времени не зависит от предыстории объекта, а определяется лишь вектором состояния в этот момент времени и целью управления .

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

.

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

.

Используя разностное уравнение объекта управления, представим вектор в виде и подставим его в предыдущее выражение:

.

Заметим, что вспомогательный показатель по-прежнему зависит только от одной переменной и этот факт значительно упрощает процедуру минимизации.

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

.

Шаг 3. Рассуждая аналогично первым двум шагам, введем в рассмотрение вспомогательный показатель качества

.

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

,

решив которую, найдем оптимальное управление и функцию Беллмана для третьего шага.

Шаг N. Продолжая вводить в рассмотрение все новые и новые слагаемые показателя качества , придем в итоге к исходному показателю качества

Из этого условия находим оптимальное управление , как функцию от начального состояния объекта. Начальное состояние объекта задано, поэтому оптимальное управление для момента времени найдено окончательно, и может быть также вычислено минимальное значение показателя качества для всей процедуры управления , хотя оптимальные управления для остальных моментов времени окончательно не найдены; они пока носят статус условно-оптимальных.

Рассмотрен первый этап решения задачи оптимального управления, который принято называть этапом попятного движения. На втором этапе решения задачи интервал управления просматривается в прямом направлении и вычисляются оптимальные управления для остальных моментов времени. На этом этапе используются разностное уравнение объекта и выражения для условно-оптимальных управлений, полученные на каждом шаге попятного движения. Эта процедура выглядит следующим образом.

На основании известных оптимального управления и начального состояния объекта управления вычисляется оптимальное состояние объекта для момента времени : . Это состояние объекта используется затем для вычисления оптимального управления . Переходим к моменту времени и находим оптимальное состояние объекта и оптимальное управление . Прямое движение, организованное по этой схеме, продолжается до момента времени . Оптимальное управление является последним в списке оптимальных управлений, и теперь можно приступать к непосредственному управлению реальным объектом, подавая на еговход найденные оптимальные управляющие воздействия.

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

Предприятие стремится найти оптимальный план производства в течение 4 месяцев, в каждом из которых необходимо отгрузить единиц продукции. Запасы к началу планируемого периода на предприятии составляют единиц изделий, в каждом из планируемых месяцев предприятие может изготовить не более единиц продукции, а на складе может одновременно храниться не более изделий.

Затраты, связанные с производством 1000, 2000, 3000, 4000 изделий, составляют соответственно руб., а затраты на хранение 1000 изделий равны руб. Числовые данные содержатся в табл. 1.

Требуется найти такой план выпуска продукции, при котором общая сумма затрат на её производство и хранение окажется минимальной, а спрос на необходимые изделия будет удовлетворён своевременно и полностью.

Таблица 1

Экономические показатели
Потребность в продукции в каждом из месяцев (), шт.
Начальный запас продукции на складе, , шт. планируемого периода (b), шт.
Максимальный месячный объём производства, , шт. производства (d), шт.
Затраты на производство 1000, 2000, 3000, 4000 изделий (), руб.
Затраты на хранение 1000 изделий, , руб. (q), руб.
Ёмкость склада, , шт.

Формализация задачи. Сформулируем исходную задачу в терминах динамического программирования. Введем в рассмотрение объект управления, под которым будем понимать предприятие.

u(t_i) = u_i y(t_i) = y_i

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

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

y ₁=2000 y ₂ y ₃ y ₄ y ₅= y (T)

u ₁ u ₂ u ₃ u ₄

Рис. 5

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

Это уравнение имеет первый порядок, поэтому состояние ОУ полностью характеризуется его выходным сигналом, и нет оснований вводить в рассмотрение вектор состояния.

Сформулируем показатель качества, представляющий собой суммарные затраты на производство и хранение изделий на протяжении всего планового периода и свяжем с ним критерий оптимальности

.

Здесь - затраты на производство и хранение изделий в каждом месяце планового периода. Эти зависимости заданы табличным способом (см. табл. 1).

В итоге сформированы все аспекты дискретной задачи оптимального управления.

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