Тема 3.3. Динамическое программирование. Примеры моделей динамического программирования.

Содержание вопросов

Примеры моделей динамического программирования. Решение линейных оптимизационных задач методом динамического программирования.

Вопросы и задания для самостоятельной работы:

1. Подготовить ответы на контрольные вопросы по теме 3.3.:

1.1. Постановка задачи динамического программирования?

1.2. Основные идеи вычислительного метода динамического программирования?

1.3.Применение алгоритма динамического программирования для решения задач, допускающих табличное задание рекуррентных соотношений?

1.4. Принцип оптимальности Беллмана?

1.5.Задача «о найме работников» и применение для ее решения вычислительных методов динамического программирования?

1.6.Однопродуктовая задача управления запасами и применение вычислительной схемы динамического программирования для ее решения?

1.7. Задачи замены, ремонта и определения надежности оборудования?

1.8. Задачи массового обслуживания?

1.9. Задачи упорядочения и согласования?

1.10.Решение линейных оптимизационных задач методом динамического программирования?

2. Тестовые задания для самостоятельного контроля уровня подготовки студентами вопросов темы 3.3.

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

А. рассматриваются методы, позволяющие путем поэтапной (многошаговой) оптимизации получить общий (результирующий) оптимум;

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

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

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

Г. мультипликативная функция распадается на произведение положительных функций различных переменных: . Логарифм такой функции является аддитивной функцией.

2.2. Основные идеи вычислительного метода динамического программирования:

А. изложим сущность вычислительного метода динамического программирования на примере задачи оптимизации функции

при ограничениях

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

В. поставленная задача решается последовательно для каждого актива. Если на первом шаге принято решение о вложении в й актив единиц, то на остальных шагах мы сможем распределить единиц ресурса;

Г. Абстрагируясь от соображений, на основе которых принималось решение

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

Если оставшееся количество ресурса обозначить через , то величину объема ресурса можно выразить как функцию от :

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

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

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

т.е. значению целевой функции при одномоментном распределении ресурса.

2.3. Применение алгоритма динамического программирования для решения задач, допускающих табличное задание рекуррентных соотношений:

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

Б. Уравнение , выражающее оптимальное решение на ом шаге через решения, принятые на предыдущих шагах, называется рекуррентным соотношением динамического программирования;

В. Рассмотрим процесс решения задачи

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

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

Поскольку принимает конечное число целых значений от 0 до .

Это позволяет путем перебора значений , найти функцию и задать ее в форме таблицы.

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

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

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

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

и т.д. или, в общем виде, ;

Г. одно из преимуществ описанного метода с точки зрения его практической реализации в рамках программного обеспечения для ЭВМ: на каждом шаге алгоритма непосредственно используется только таблица, полученная на предыдущем шаге, т.е. нет необходимости сохранять ранее полученные таблицы.

2.4. Принцип оптимальности Беллмана:

А. основной смысл подхода, реализуемого в динамическом программировании, заключен в замене решения исходной многомерной задачи последовательностью задач меньшей размерности;

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

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

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

-задача не должна зависеть от количества шагов и быть определенной на каждом из них;

-состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;

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

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

Планом задачи или стратегией управления называется вектор ,

компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия, между каждыми двумя последовательными состояниями объекта существует известная функциональная зависимость, включающая также выбранное управление: Тем самым, задание начального состояния объекта и выбор плана однозначно определяет траекторию поведения объекта;

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

2.5. Задача «о найме работников» и применение для ее решения вычислительных методов динамического программирования:

А. основной принцип динамического программирования заключается в том, что

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

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

В качестве примера рассмотрим задачу о найме работников, т.е., задачу об использовании рабочей силы;

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

однако влечет дополнительные затраты либо за счет нерационального использования рабочей силы, либо ввиду повышения оплаты за интенсивный труд. Размеры этих дополнительных издержек описываются функциями где отклонение фактической численности работающих от планово необходимой , причем . Управленческое решение на шаге заключается в выборе величины изменения числа сотрудников , что однозначно определяет количество работающих в течение следующего периода: Затраты по изменению количества работников (найму и увольнению) при переходе от периода к периоду

задаются функцией , где, также, Тогда суммарные издержки, вызванные принятым на шаге решением, характеризуются значением функции

Г. план задачи (стратегия управления) заключается в выборе поэтапных изменений количества работников, а его суммарная эффективность описывается аддитивной функцией

На основе сформированной модели ставится задача минимизации целевой функции (издержек).

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

втором-требуемое количество в периоде .

2.6. Однопродуктовая задача управления запасами и применение вычислительной схемы динамического программирования для ее решения:

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

Б. пусть имеется некоторая система снабжения, планирующая свою работу на периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т.е. не допускать задолженности и отказы). Также предполагается, что заказ выполняется мгновенно;

В. после получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период , составит Учитывая смысл параметра _, можно записать соотношение:

Расходы на получение и хранение товара в период описываются функцией

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

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

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

Поскольку и

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

2.7. Задачи замены, ремонта и определения надежности оборудования:

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

Б. С точки зрения проводимого анализа, различают три типа задач:

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

- задачи по замене оборудования с целью предупреждения его полного выхода из строя (отказа), когда вероятность отказа возрастает с увеличением срока службы (возраста);

- задачи выбора некоторого плана предупредительного ремонта и профилактического обслуживания с целью уменьшения вероятности отказа.

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

Если заменить машину в конце года , то приведенные к настоящему моменту общие затраты составят где приведенная к настоящему моменту стоимость одного доллара, выплачиваемого через лет, равна Приведенная величина затрат эквивалентна выплате сумм в начале каждого года на протяжении лет, где Следовательно, так что

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

Необходимо выбрать так, чтобы минимизировать эквивалентные постоянные затраты, что равносильно минимизации величины , или в виде:

Г. Замена с целью предупреждения отказ узла или элемента и изменения надежности системы: для выбора оптимального срока службы производится сравнение возрастающих эксплуатационных затрат с уменьшающимися амортизационными отчислениями, а также в случае изменения надежности (узла, элемента).

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

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

будет заменена к моменту , получаем, что общее число

_{«лентосмен»} равно

Разделив эту величину на число лент , находим средний срок службы ленты

. После преобразования и приведения членов уравнений получим это

выражение в компактном виде: .

Если обозначить через вероятность разрыва ленты в возрасте, превышающим , то выражения, заключенные в скобки, будут соответственно

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

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

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

НАДЕЖНОСТЬ СИСТЕМЫ. Надежность системы можно повышать, используя

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

где стоимость элемента.

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

Ясно, что всегда тратится сумма, равная , и что затраты распределяются поровну между всеми элементами. В результате, значение выбирается так, чтобы выполнялись неравенства

и чтобы

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

2.8. Задачи массового обслуживания:

А. Система, в которую поступают объекты, нуждающиеся в услугах или производстве работ, называется «обслуживающей системой», а сами объекты носят название «требований» или «заявок». Они могут представлять собой письма, нуждающиеся в подписи, автомашины, которым нужна стоянка, суда, подлежащие разгрузке, детали, требующие сборки, людей, ожидающих обслуживания, т.е., любой материальный объект, над которым или для которого необходимо выполнить некоторую организованную работу. Если требования поступают в систему «слишком часто», то им приходится ожидать обслуживания или обходиться без него. И наоборот, если требования поступают слишком редко, то ожидать (т.е. простаивать) приходится средствам или каналам обслуживания. Ожидающие обслуживания требования или простаивающие каналы образуют очередь. Совокупность правил, пользуясь которыми из очереди выбирают требования для обслуживания, называется дисциплиной обслуживания. Устройство или средство, способное в любой момент времени обслуживать лишь одно требование, называется каналом или пунктом обслуживания. Если обслуживание производится поэтапно некоторой последовательностью каналов, то такую систему массового обслуживания называют многофазной. При наличии нескольких каналов, способных одновременно обслуживать ряд требований, говорят о многоканальной системе. Все каналы или часть их могут выполнять один и тот же вид обслуживания либо различные виды обслуживания. При наличии требований, поступающих на станцию обслуживания таким образом, что либо сами требования, либо средства обслуживания вынуждены ожидать, возникает процесс массового обслуживания.

Б. В условиях протекания процесса массового обслуживания задача обслуживания возникает при следующих условиях:

а) имеется возможность регулирования плотности потока требований или параметра потока (т.е. количество требований, поступающих в систему в единицу времени) или количества средств обслуживания;

б) существуют затраты, обусловленные ожиданием удовлетворения требований или простоем средств обслуживания;

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

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

а для клиента, находившегося в состоянии 1, в этом месяце имеем

Однако справедливы и такие соотношения

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

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

вероятность появления требования в интервале от Поток требований, удовлетворяющий этому допущению, называется пуассоновским, ибо вероятность поступления требований на любом конечном отрезке времени равна Это выражение представляет собой распределение Пуассона с параметром . Здесь - математическое ожидание и дисперсия распределения Пуассона.

2.9. Задачи упорядочения и согласования:

А. Выбор дисциплины обслуживания и порядка обслуживания ожидающих требований в задачах массового обслуживания называется упорядочением, а процедура определения скорости выполнения каждой операция и календарных сроков ее начала и окончания, с оптимизацией по заданному критерию качества реализации всего комплекса - сетевым планированием и управлением (СПУ);

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

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

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

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

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

Задачи согласования - класс задач, в которых в основном рассматривается соотношение между сроком окончания крупного комплекса операций и моментами начала всех операций, входящих в этот комплекс. Эти задачи решаются с помощью метода ПЕРТ или метода критического пути. В комплексе эти задачи называют задачами СПУ.

2.10. Решение линейных оптимизационных задач методом динамического программирования:

А. Общая задача линейного программирования, в которой требуется максимизировать при ограничениях

может быть представлена в виде модели динамического программирования. Для этого каждый вид производственной деятельности следует интерпретировать как этап. Уровень производственной деятельности

представляет варианты решения на этапе . Поскольку переменная

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

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

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

где

Г. для ограничения типа правая часть неравенства уже не будет определять максимальное значение переменной состояния. Это наиболее ярко выражено в случае, когда решение не является ограниченным. Ввиду этого следует вывод о том, что динамическое программирование не может служить эффективным средством решения задач линейного программирования.

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