![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Детерминированные модели принятия решений и динамическое программирование
2.1. Рекуррентная природа вычислений динамического программирования. Динамическое программирование есть особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» или «многоэтапным» операциям. Динамическое программирование (ДП) определяет оптимальное решение Вычисления в ДП выполняются рекуррентно в том смысле, что оптимальное решение одной подзадачи используется в качестве исходных данных для следующей. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи. Способ выполнения рекуррентных вычислений зависит от того, как производится декомпозиция исходной задачи. В частности, подзадачи обычно связаны между собой некоторыми общими ограничениями. Если осуществляется переход от одной подзадачи к другой, то должны учитываться эти ограничения. Принцип оптимальности . Каково бы ни было состояние системы Оптимальная стратегия обладает том свойством, что, какими бы ни были начальные состояние и решение, оставшиеся решения образуют оптимальную стратегию для состояния, возникающего после первого перехода. Представим себе некоторую операцию, состоящую из
где Предполагается, что выигрыш (2.1) в данной операции зависит от некоторого управления. Обозначим его буквой
Следует иметь в виду, что Требуется найти такое управление
То управление
Тот максимальный выигрыш, который достигается при этом управлении, мы будем обозначать
Рассмотрим пример многошаговой операции и поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности) Пример. Владелец автомашины эксплуатирует ее в течение 1) продать машину и заменить ее новой; 2) ремонтировать ее и продолжать эксплуатацию; 3) продолжать эксплуатацию без ремонта. Шаговое управление — выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2, 3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны? Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш», но это неважно) равен
где Управление операцией в целом представляет собой какую-то комбинацию чисел 1, 2, 3, например:
что означает: первые два года эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д. Любое управление представляет собой вектор (совокупность чисел):
где каждое из чисел Любую многошаговую задачу можно решать по-разному: либо искать сразу все элементы решения на всех Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше, оказывается, много раз решить сравнительно простую задачу, чем один раз – сложную. Принцип динамического программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем. Что толку, если мы выберем на данном шаге управление, при котором эффективность этого шага максимальна, если этот шаг лишит нас возможности хорошо выиграть на последующих шагах? Значит, планируя многошаговую операцию, надо выбирать управление на каждом шаге с учетом всех его будущих последствий на еще предстоящих шагах. Управление на Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой, принес наибольшую выгоду. Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего, планируется последний, Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на Так мы найдем для каждого исхода Предположим, что все условные оптимальные управления и условные оптимальные выигрыши за весь «хвост» процесса (на всех шагах, начиная от данного и до конца) нам известны. Это значит: мы знаем, что надо делать, как управлять на данном шаге и что мы за это получим на «хвосте», в каком бы состоянии ни был процесс к началу шага. Теперь мы можем построить уже не условно оптимальное, а просто оптимальное управление Таким образом, в процессе оптимизации управления методом динамического программирования, многошаговый процесс «проходится» дважды. Первый раз – от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса. Второй раз – от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление Первый этап условной оптимизации несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений.
2.2. Приложения динамического программирования Модели динамического программирования обычно применяются при решении задач не очень большого масштаба. Вот некоторые типичные области применения моделей динамического программирования при принятии решений: - разработка правил управления запасами, устанавливающих момент пополнения запасов и размер пополняющего заказа; - разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; - определение необходимого объема запасных частей, гарантирующего эффективное использование дорогостоящего оборудования; - распределение дефицитных капитальных вложений между возможными новыми направлениями их использования; - выбор методов проведения рекламной кампании, знакомящей покупателя с продукцией фирмы; - систематизация методов поиска ценного ресурса; - составление календарных планов текущего и капитального ремонта сложного оборудования; - разработка долгосрочных правил замены выбывающих из эксплуатации основных фондов. Процессы принятия решений, к которым относятся ряд упомянутых выше моделей, часто относятся к числу микроэкономических. Однако во многих реально функционирующих системах еженедельно требуется принимать тысячи таких решений. В связи с этим модели динамического программирования (ДП) ценны именно тем, что они позволяют принимать миллионы решений на основе стандартного подхода (часто с использованием ЭВМ) при минимальном вмешательстве человека.
2.2.1. Задача об оптимальной загрузке.
Задача о загрузке – это задача о рациональной загрузке автомашины (самолета, судна и т.п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки автомашины такими грузами, которые приносят наибольшую суммарную прибыль. Перед тем как представить соотношения динамического программирования, заметим, что рассматриваемая здесь задача известна также как задача о снаряжении, где пилот реактивного самолета должен определить наиболее ценные (необходимые) предметы, которые следует взять на борт самолета, или как задача о рюкзаке, в которой турист должен определить наиболее ценные предметы, подлежащие загрузке в рюкзак. Основное рекуррентное соотношение динамического программирования выводится для общей задачи загрузки автомашины грузоподъемностью
при ограничениях:
При этом на
Задача (2.9) - (2.12) называется еще задачей распределения усилий. Для того, чтобы свести эту задачу к задаче динамического программирования, обозначим Тогда итерационный процесс вычисления
где
Таким образом, процесс решения задачи (2.9) - (2.12) сводится к рекуррентным вычислениям по формулам (2.13) - (2.14). Зная, что Пример. Решим задачу распределения усилий общего вида, при следующих данных. Пусть
и товар упакован в каждый из магазинов в соответствии со следующими равенствами Кроме того, будем считать, что все Решение. На нулевом шаге при Шаг Таблица 3
Пусть теперь
Шаг Таблица 4
При Шаг Таблица 5
Процесс выбора оптимальных значений 2.2.2. Простейшая задача управления запасами. Модель, к изучению которой мы приступаем, играет такую же - или почти такую же - роль в исследовании операций, как законы Ньютона в физике. Хотя рассматриваемая ситуация и является идеализированной, в модели все же учитывается множество важных факторов, влияющих на выбор правил управления запасами. Важно отметить, что внедрение модификаций рассматриваемой модели рядом промышленных фирм дало заметный экономический эффект. Разумеется, в таких случаях все необходимые вычислительные операции выполнялись на ЭВМ. Рассмотрим задачу управления запасами на следующем примере. Пример фирмы “Надежный поставщик”. Фирма должна разработать календарную программу выпуска некоторого вида изделий (или поставки некоторого вида товаров ) на плановый период, состоящий из Для разных отрезков спрос неодинаков; кроме того, на экономические показатели влияет размер изготовляемых партий (размер закупки, учитывая кредит). Поэтому фирме нередко бывает выгодно изготавливать (закупать) в течение некоторого периода продукцию в объеме, превышающем спрос в пределах этого периода, и хранить излишки, для удовлетворения последующего спроса. Вместе с тем хранение возникающих при этом запасов связано с определенными затратами (проценты по кредитам). Цель фирмы “Надежный поставщик” - разработать такую программу, при которой общая сумма затрат на производство (закупку) и на содержание запасов (проценты на кредит) минимизируются при условии полного и своевременного удовлетворения спроса на продукцию (что означает получение максимальной прибыли при наличии постоянных покупателей). Анализ этой задачи начнем с преобразования качественного ее описания в математическую модель. Построение модели. Введем переменные:
Тогда целевую функцию можно записать в следующем виде
На переменные Во-первых, предполагается целочисленность объемов выпуска:
Во-вторых, предполагается, что для администрации фирмы желателен нулевой уровень запасов на конец отрезка
В-третьих, ставится условие полного и своевременного удовлетворения спроса в пределах каждого периода. Выполнение этого условия можно выполнить, вводя два ограничения. Первое из них назовем балансовым:
где Второе ограничение заключается в том, чтобы уровень запасов на начало каждого периода и объем выпуска продукции должны быть достаточно велики, чтобы уровень запасов на конец периода был бы неотрицательным
Для того чтобы решить задачу при нелинейности каждой из величин Динамическая постановка. Вспомним, что в задаче о загрузке мы строили вычислительный процесс от конечного состояния к исходному. Такой же подход будет использован и в настоящей задаче. Здесь конечным состоянием будет начало последнего отрезка планового периода, а исходным - начальный момент первого отрезка. Применим следующие обозначения:
Для математической формулировки задачи введем следующие обозначения:
Согласно (2.17), уровень запасов на конец планового периода равен нулю, поэтому можно записать, что
Затем перейдем к
Перейдем к
причем предполагается, что выбранная стратегия для где Очевидно, значения
где Заметим, что, поскольку начальный уровень запасов Процесс станет совершенно понятным, когда мы разберем пример, приводимый ниже. Пример. Для упрощения будем считать, что спрос одинаков для всех отрезков планового периода. Для конкретности примем
где
Далее, производственные мощности и складские площади фирмы (назовем ее “Надежный поставщик”) ограничены; это вводит в задачу дополнительное осложнение. Примем, что выпуск в течение одного отрезка не может превышать 5 единиц, а уровень запасов на конец отрезка - 4 единицы. Иными словами для всех отрезков
Решение. При наличии приведенных выше данных об условия деятельности фирмы “Надежный поставщик” можно составить динамическое рекуррентное соотношение, отображающее специфику задачи. Для
поскольку уровень запасов на конец планового периода равен нулю. В общем виде рекуррентное соотношение можно записать следующим образом:
где Для того чтобы анализ был содержательным, необходимо располагать всеми значениями функций Популярное:
|
Последнее изменение этой страницы: 2016-03-15; Просмотров: 2045; Нарушение авторского права страницы