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

Глава IV

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

4.1. Введение

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

4.2 Рекуррентная природа вычислений ДП

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

Пример 4.2-1. (Задача о кратчайшем пути)

Предположим, необходимо выбрать кратчайший путь между двумя городами. Сеть дорог, показанная на рис. 10.1, представляет возможные маршруты между исходным городом, находящимся в узле 1, и конечным пунктом, который находится в узле 7. Маршруты проходят через промежуточные города, обозначенные на сети узлами с номерами 2-6.

Рекомендуемые материалы

Мы можем решить эту задачу посредством полного перебора всех маршрутов между узлами 1 и 7 (имеется пять таких маршрутов). Однако в большой сети полный перебор является неэффективным с вычислительной точки зрения.

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

Общая задача состоит в вычислении кратчайших (постепенно накапливаемых) расстояний ко всем вершинам этапа с последующим использованием этих расстояний в качестве исходных данных для следующего этапа. Рассматривая узлы, относящиеся к первому этапу, замечаем, что каждый из узлов 2, 3 и 4 связан с начальным узлом 1 единственной дугой (рис. 4.2). Следовательно, для первого этапа имеем следующее.

Этап 1. Итоговые результаты.

Кратчайший путь к узлу 2 равен 7 миль (из узла 1),

Кратчайший путь к узлу 3 равен 8 миль (из узла 1),

Кратчайший путь к узлу 4 равен 5 миль (из узла 1).

Далее переходим ко второму этапу для вычисления кратчайших (накопленных) расстояний к узлам 5 и 6. Рассматривая узел 5 первым, из рис. 10.2 замечаем, что есть три возможных маршрута, по которым можно достичь узла 5, а именно (2, 5), [ (3, 5) и (4, 5). Эта информация вместе с кратчайшими расстояниями к узлам 2, 3, и 4 определяет кратчайшее (накопленное) расстояние к узлу 5 следующим образом.

Аналогично для узла 6 имеем следующее.

Этап 2. Итоговые результаты.

Кратчайший путь к узлу 5 равен 12 миль (из узла 4),

Кратчайший путь к узлу 6 равен 17 миль (из узла 3).

Последним шагом является третий этап. Конечный узел 7 можно достигнуть  как из узла 5, так и 6. Используя итоговые результаты этапа 2 и расстояния от узлов 5 и 6 к узлу 7, получаем следующее:

Этап 3. Итоговые результаты.

Кратчайший путь к узлу 7 равен 21 миле (из узла 5).

Привеленные вычисления показывают, что кратчайшее расстояние между узлами 1 и 7 равно 211 миле. Города, через которые проходит кратчайший маршрут, определяется следующим образом. Из готовых результатов третьего этапа следует, что узел 7 связывается с узлом 5. Далее из итоговых результатов второго этапа следует, что узел 4 связывается с узлом 5. Наконец, из готовых результатов первого этапа следует, что узел 4 связывается с узлом 1. Следовательно, оптимальным маршрутом является последовательность 1-4-5-7.

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

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

Определение состояния системы приводит к следующему унифицированному положению.

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

Применение принципа оптимальности демонстрируется вычислениями из примера 10.2-1. Например, на этапе 3 мы используем кратчайшие пути к узлам 5 и 6 и не интересуемся, как эти узлы были достигнуты из узла 1.

Упражнения 4.2,а

Решите задачу из примера 10.2-1 в предположении, что используются следующие длины маршрутов:

, , ,

, ,

, ,

,

.

2.Я — заядлый турист. Прошлым летом мой друг и я отправились в пятидневный поход по прекрасным Белым Горам в штате Нью-Гемпшир. Мы решили ограничить наше путешествие территорией, на которой находится три хорошо известные вершины: Вашингтон, Джефферсон и Адаме. Гора Вашингтон имеет шестимильную тропу от подножия до вершины. Аналогичные тропы гор Джефферсона и Адамса имеют длину 4 и 5 миль соответственно. Тропы, соединяющие подножия этих трех гор, имеют следующую длину: 3 мили между вершинами Вашингтона и Джефферсона, 2 мили между вершинами Джефферсона и Адамса и 5 миль между вершинами Адамса и Вашингтона. В первый день мы стартовали от подножия вершины Вашингтона и вернулись в эту же точку к концу пятого дня. Нашей целью было пройти как можно более длинный путь. Мы также решили подниматься каждый день только на одну вершину и располагаться лагерем у подножия той горы, на которую мы решили восходить на следующий день. Кроме того, мы решили, что не будем подниматься на одну и ту же вершину в течение двух дней подряд. Каким было расписание нашего похода?

4.3. Рекуррентные алгоритмы прямой и обратной прогонки

В примере 4.2-1 вычисления проводились последовательно: от первого этапа до третьего. Такая последовательность вычислений известна как алгоритм прямой прогонки. Этот же пример может быть решен с помощью алгоритма обратной прогонки, в соответствии с которым вычисления проводятся от третьего этапа до первого.

Алгоритмы прямой и обратной прогонки приводят к одному и тому же решению. Несмотря на то, что алгоритм прямой прогонки представляется более логичным, в специальной литературе, посвященной динамическому программированию, неизменно используется алгоритм обратной прогонки. Причина этого в том, что в общем случае алгоритм обратной прогонки может быть более эффективным с вычислительной точки зрения. Продемонстрируем использование алгоритма обратной прогонки на примере 4.2-1. Мы также представим вычисления динамического программирования в компактной табличной форме.

Пример 3-1

Рекуррентное уравнение для алгоритма обратной прогонки в примере 4.2-1 имеет вид

где  для . Соответствующей последовательностью вычислений будет

Этап 3. Так как узел 7 ( = 7) связан с узлами 5 и 6 (х₃ = 5 и 6) в точности одним маршрутом, альтернативы для выбора отсутствуют, а результаты третьего этапа можно подытожить следующим образом.

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

Оптимальное решение второго этапа означает следующее. Если вы находитесь в узле (городе) 2 или 4, кратчайший путь к узлу 7 проходит через узел 5, а если находитесь в узле 3, кратчайший путь к узлу 7 проходит через узел 6.

Этап I. Из узла 1 мы имеем три альтернативных маршрута: (1,2), (1,3) и (1,4). Используя значения , полученные на втором этапе, вычисляем данные следующей таблицы.

Оптимальное решение на первом этапе показывает, что кратчайший путь проходит через город 4. Далее из оптимального решения на втором этапе следует, что из города 4 необходимо двигаться в город 5. Наконец, из оптимального решения на третьем эта­пе следует, что город 5 связан с городом 7. Следовательно, полным маршрутом, имеющим кратчайшую длину, является 1-4-5-7, и его длина равна 21 миле.

Упражнения 4. 3,а

1. Для задачи из упр. 4.2,а(1) получите рекуррентное соотношение обратной прогонки и используйте его для получения оптимального решения.

2. Для задачи из упр. 4.2,а(2) получите рекуррентное соотношение обратной прогонки и используйте его для получения оптимального решения.

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

4.4. Некоторые приложения динамического программирования

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

2. Определение на каждом этапе вариантов решения (альтернатив).

3. Определение состояний на каждом этапе.

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

1. Какие соотношения связывают этапы вместе?

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

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

4.4.1. Задача о загрузке

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

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

Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) п наименований. Пусть m_i — количество предметов i-го наименования, подлежащих загрузке, r,- — прибыль, которую приносит один загруженный предмет i-го наименования, w_i — вес одного предмета i-го наименования. Общая задача имеет вид. следующей целочисленной задачи линейного программирования.

Максимизировать

при условии, что

                      

Три элемента модели динамического программирования определяются следующим образом.

1. Этап i ставится в соответствие предмету i-го наименования,  

2. Варианты решения на этапе  описываются количеством m_i предметов i-го наименования, подлежащих загрузке. Соответствующая прибыль равна r_im_i. Значение т_i заключено в пределах от 0 до , где  — целая часть числа

3. Состояние x_i на этапе i выражает суммарный вес предметов, решения о погрузке которых приняты на этапах п. Это определение отражает тот факт, что ограничение по весу является единственным, которое связывает п этапов вместе.

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

Шаг 1.           Выразим  как функцию  в виде

                                  

                        где

Шаг 2.           Выразим  как функцию ,• для гарантии того, что левая часть последнего уравнения является функцией лишь . По определению -представляет собой вес, загруженный на этапе i т.е. – или =-Следовательно, рекуррентное уравнение приобретает следующий вид.

Пример 4.4-1

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

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

Этап 3. Точный вес, который может быть загружен на этапе 3 (предмет наименования 3), заранее неизвестен, но он должен принимать одно из значений 0,1,...,4 (так как W = 4 тонны). Состояния х₃ = 0 и х₃ = 4 представляют собой крайние случаи, когда предметы третьего наименования совсем не загружаются или загружают самолет полностью. Остальные значения х₃ (= 1, 2 или 3) предполагают частичную загрузку самолета предметами третьего наименования. Действительно, при этих значениях х₃ все оставшиеся емкости самолета могут быть заполнены предметами третьего наименования.

Так как вес w₃ одного предмета третьего типа равен 1 тонне, максимальное количество единиц этого типа, которое может быть загружено, равно [4/1] = 4. Это означает, что возможными значениями х₃ будут О, 1, 2, 3 и 4. Решение т₃ является допустимым лишь при условии, что .Следовательно, все недопустимые альтернативы (те, для которых w₃m₃>x₃) исключены. Следующее уравнение является основой для сравнения альтернатив на этапе 3.

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

Этап 2.

Этап 1.

Оптимальное решение определяется теперь следующим образом. Из условия W = 4 следует, что первый этап решения задачи при  = 4 дает оптимальное решение  - 2, которое означает, что два предмета первого наименования будут загружены в самолет. Эта загрузка оставляет  Решение на втором этапе при х₂= 0 приводит к оптимальному решению  - 0, которое, в свою очередь, дает x₃ = х₂-3т₂ =0-30=0. Далее этап 3 при х₃=0 приводит к m₃*=0. Следовательно, оптимальным решением задачи является m₁*=2 m₂*=0 m₃*=0.Соответствующая прибыль равна 62 000 долларов.

В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для х₁ = 4, так как это последний этап, подлежащий рассмотрению. Однако в таблицу включены также вычисления для х₁ = 0,1,2 и 3, которые позволяют провести анализ чувствительности решения. Например, что произойдет, если максимальная грузоподъемность самолета будет 3 тонны вместо 4? Новое оптимальное решение может быть определено, начиная с х₁ = 3 на первом этапе и продолжая так, как мы поступали при х₁ = 4.

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

Упражнения 4. 4,а

1. В задаче примера 10.4-1 определите оптимальное решение, предполагая, что максимальная грузоподъемность самолета составляет 3 тонны.

2. Решите задачу о загрузке из примера 10.4-1 для каждого из следующих случаев.

·

·

3. Турист собирается в путешествие по дикой местности и должен упаковать в рюкзак предметы трех наименований: пищу, средства первой помощи и одежду. Объем рюкзака составляет 3 кубических фута. Каждая единица пищи занимает 1 кубический фут, упаковка средств первой помощи — четверть кубического фута, а отдельный предмет одежды — примерно половину кубического фута. Турист определил свои предпочтения весовыми коэффициентами 3, 4 и 5 — для пищи, средств первой помощи и одежды соответственно. Это означает, что одежда является самым ценным предметом среди остальных. Опыт подсказывает туристу, что он должен взять не менее одного предмета каждого наименования и не более двух комплектов средств первой помощи. Сколько единиц каждого наименования возьмет турист в поход?

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

           

Какие курсы следует выбрать студенту?

5. У меня во дворе имеется небольшой огород 1020 футов. Этой весной я собираюсь посадить овощи трех видов: помидоры, зеленые бобы и кукурузу. Огород разбит на ряды, длина которых равна 20 футам. Кукуруза и помидоры занимают ряды шириной 2 фута, а зеленые бобы — 3 фута. Помидоры мне нравятся больше, а бобы меньше. По 10-балльной шкале предпочтений я бы присвоил помидорам 10 баллов, кукурузе — 7 баллов и зеленым бобам — 3 балла. Независимо от моих предпочтений, жена настаивает, чтобы я посадил не менее одного ряда зеленых бобов и не более двух рядов помидоров. Сколько рядов каждого вида овощей следует мне посадить?

6. "Жилище для Человечества" — прекрасная благотворительная организация, которая строит дома для бедствующих семей силами добровольцев. Такая семья может выбрать себе дом из трех типоразмеров: 1000, 1100 и 1200 квадратных футов. Дом каждого типоразмера требует выполнения определенного объема работ силами добровольцев. Филиал организации в городе Файтвилл получил пять заявок на предстоящие шесть месяцев. Комитет по надзору дает оценку каждой заявке в численном виде, принимая во внимание различные факторы. Более высокая оценка означает более острую потребность в жилье. В течение предстоящих шести месяцев филиал организации в этом городе может привлечь к работе максимум 23 добровольца. Следующая таблица содержит оценку каждой заявки и необходимое число добровольцев для ее выполнения. Какие заявки следует утвердить комитету?

           

7. Шериф округа Вашингтон принимает участие в переизбрании на следующий срок. Денежные средства на предвыборную кампанию составляют примерно 10000 долларов. Хотя комитет по переизбранию хотел бы провести кампанию во всех пяти избирательных участках округа, ограниченность денежных средств предписывает действовать по-другому. Приведенная ниже таблица содержит данные о числе избирателей и денежных средствах, необходимых для проведения успешной кампании по каждому избирательному участку. Каждый участок может либо использовать все предназначенные деньги, либо вовсе их не использовать. Как следует распределить денежные средства?

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

Общая сумма, выделенная на конструирование прибора, равна 10000 долларов. Как следует сконструировать прибор? (Совет. Наша задача состоит в максимизации надежности  прибора. Это значит, что целевая функция является мультипликативной, а не аддитивной.)

9. Решите следующую задачу с помощью метода динамического программирования.

Максимизировать

            при условиях

                                                          

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

10. Решите следующую задачу с использованием метода динамического программирования

                                   Минимизировать

при условиях

                                                                     

                                                                     

11. Решите следующую задачу посредством метода динамического программирования.

Максимизировать

            при условиях

                                                          

12. Решите следующую задачу с помощью метода динамического программирования.

                                               Минимизировать

при условиях

                                              

Найдите решение задачи при условии, что  и

4.4.2. Задача планирования рабочей силы

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

            Предположим, что проект будет выполняться в течение п недель и минимальная потребность в рабочей силе на протяжении -й недели составит b_i рабочих. При идеальных условиях хотелось бы на протяжении -й недели иметь в точности b_i рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей. Если — количество работающих на протяжении -й недели, то возможны затраты двух видов: 1)  — затраты, связанные с необходимостью содержать избыток - b_i рабочей силы и 2)  — затраты, связанные с необходимостью дополнительного найма  рабочих.

Элементы модели динамического программирования определяются следующим образом.

1. Этап i представляется порядковым номером недели

2. Вариантами решения на -м этапе являются значения x_i — количество работающих на протяжении -й недели.

3. Состоянием на -м этапе является х_i-1 — количество работающих на протяжении й недели (этапа).

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

           

где. Вычисления начинаются с этапа п при х_п =b_n  и заканчиваются на этапе 1.

Пример 4-2

Строительный подрядчик оценивает минимальные потребности в рабочей силе на каждую из последующих пяти недель следующим образом: 5, 7, 8, 4 и 6 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долларов за одного рабочего в неделю, а наем рабочей силы на протяжении одной недели обходится в 400 долларов плюс 200 долларов за одного рабочего в неделю.

Выражая С₁ и С₂ в сотнях долларов, имеем следующее.

Этап 5. .

Этап 4.

Этап 3.

Этап 2.

Этап 1.

Оптимальное решение определяется последовательно следующим образом.

                       .

Полученному решению соответствует следующий план.

Упражнения 4. 4,b

1.         Решите задачу из примера 4-2 при следующих минимальных потребностях в рабочей силе.

a)

b)

2.         Пусть в примере 4-2 каждому уволенному рабочему выплачивается выходное пособие в размере 100 долларов. Найдите оптимальное решение задачи.

3.         Туристическое агентство организовывает недельные поездки в Египет. В соответствии с договором на ближайшие четыре недели агентство должно обеспечить туристические группы арендными автомобилями в количестве семь, четыре, семь и восемь штук соответственно. Агентство заключает договор с местным дилером по прокату автомобилей. Дилер назначает арендную плату за один автомобиль 220 долларов в неделю плюс 500 долларов за любую арендную сделку. Агентство, однако, может не возвращать арендованные автомобили в конце недели, и в этом случае оно должно будет только арендную плату в 220 долларов. Каково оптимальное решение проблемы, связанной с арендой автомобилей?

4.         Компания на следующие четыре года заключила контракт на поставку авиационных двигателей, по 4 двигателя в год. Доступные производственные мощности и стоимость производства меняются от года к году. Компания может изготовить пять двигателей за 1-й год, шесть— за 2-й, три— за 3-й и пять— за 4-й. Стоимость производства одного двигателя на протяжении следующих четырех лет равна соответственно 300 000, 330 000, 350 000 и 420 000 долларов. В течение года компания может произвести больше двигателей, чем необходимо, но в этом случае двигатели должны надлежащим образом храниться до их отгрузки потребителю. Стоимость хранения одного двигателя также меняется от года к году и оценивается в 20 000 долларов для первого года, 30 000 долларов — для второго, 40 000 долларов — для третьего и 50 000 долларов — для четвертого. В начале первого года компания имеет один двигатель, готовый к отгрузке. Разработайте оптимальный план производства двигателей.

5.         Фирма выпускает пять типов электронных игр (Е1, Е2, ..., Е5) и пять типов меха­нических игрушек (Ml, М2„..., М5). На рынке порядок предпочтения электронных игр таков: . Это означает, что клиент будет покупать игру с более высоким предпочтением, если она имеется в продаже. Известен также порядок предпочтения механических игрушек: . Недельный спрос на пять типов электронных игр равен 100, 180, 90, 250 и 190 единиц соответственно. Аналогичные показатели для механических игрушек равны 300, 190, 240, 280 и 260 единиц соответственно. Производство одной игры Е1,Е2,...,Е5 обходится в 10, 12, 8, 9 и 6 долларов соответственно. Изготовление же одной игрушки Ml,Ml,...,М5 обходится фирме в 4, 5, 3, 2 и 3 доллара соответственно. Организация производства каждой электронной игры или игрушки обходится в 500 долларов. Определите оптимальный план производства игрушек.

4.4.3. Задача замены оборудования

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

Предположим, что мы занимаемся заменой механизмов на протяжении n лет.  В нчале каждого года принимается решение либо об эксплуатации механизма еще один год, либо о замене его новым. Обозначим через и  и прибыль от эксплуатации летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) — стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I. Элементы модели динамического программирования таковы.

1. Этап i представляется порядковым номером года i,i= 1,2,...,п.

2. Вариантами решения на i-м этапе (т.е. для i-го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале i-го года.

3. Состоянием на i-м этапе является срок эксплуатации t (возраст) механизма к на­чалу i-гo года.

Пусть — максимальная прибыль, получаемая за годы от i до п при условии, что в начале i-го года имеется механизм t-летнего возраста.

Рекуррентное уравнение имеет следующий вид.

где

Пример 4-3

         Компания планирует определить оптимальную политику замены имеющегося в настоящее время трехлетнего механизма на протяжении следующих 4 лет (n=4),  т.е. вплоть до начала пятого года. Приведенная таблица содержит относящиеся к задаче данные. Компания требует замены механизма, который в эксплуатации 6 лет. Стоимость нового механизма равна 100000 долларов.

            Определение допустимых значений возраста механизма на каждом этапе является нетривиальной задачей. На рис 4 представлена рассматриваемая задача замены оборудования в виде сети. В начале первого года имеется механизм трехлетнего возраста. Мы можем либо заменить его (3), либо эксплуатировать (С) на протяжении следующего года. Если механизм заменили, то в начале второго года его возраст будет равен одному году, в противном случае его возраст будет 4 года. Такой же подход используется  в начале каждого года, начиная со второго по четвертый.

Если однолетний механизм заменяется в начале второго или третьего года, то заменивший его механизм к началу следующего года также будет однолетним. К тому же, в начале 4-го года 6-летний механизм обязательно должен быть заменен, если он еще эксплуатируется; в конце 4-го года все механизмы продаются (П) в обязательном порядке. На схеме сети также видно, что в начале второго года возможны только механизмы со сроком эксплуатации 1 или 4 года. В начале третьего года механизм может иметь возраст 1, 2 или 5 лет, а в начале четвертого — 1,2,3 или 6 лет.

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

На рис. 5 показана последовательность получения оптимального решения. В начале первого года оптимальным решением при t = 3 является замена механизма. Следовательно, новый механизм к началу второго года будет находиться в эксплуатации 1 год. При t = 1 в начале второго года оптимальным решением будет либо использование, либо замена механизма. Если он заменяется, то новый к началу третьего года будет находиться в эксплуатации 1 год, иначе механизм будет иметь возраст 2 года. Описанный процесс продолжается до тех пор, пока не будет определено оптимальное решение для четвертого года.

Следовательно, начиная с первого года эксплуатации механизма, альтернативными оптимальными стратегиями относительно замены механизма будут (3, С, С, 3) и (3, 3, С, С). Общая прибыль составит 55 300 долларов.

Упражнения 4.4,с

1. Постройте сеть и найдите оптимальное решение в задаче из примера 4-3 в каждом из следующих случаев.

a) В начале первого года имеется механизм, находящийся в эксплуатации 2 года.

b) В начале первого года имеется механизм, находящийся в эксплуатации 1 год.

c) В начале первого года куплен новый механизм.

2. Мой тринадцатилетний сын занимается собственным бизнесом — косит газоны десяти клиентам. Каждому клиенту он косит траву три раза в год, получая за один скошенный газон 50 долларов. Он купил косилку за 200 долларов. На протяжении первого года затраты на содержание и использование косилки равны 120 долларов, и через год они увеличиваются на 20%. Одногодичная косилка может быть продана за 150 долларов, и с каждым годом ее стоимость уменьшается на 10%. Мой сын планирует продолжить свой бизнес, пока ему не исполнится 16 лет, и считает, что более выгодно менять косилку через каждые два года. Он объясняет это тем, что цена новой косилки увеличивается за год лишь на 10%. Справедливо ли его решение?

3. Группа ферм владеет трактором двухлетней давности и планирует разработать стратегию его замены на следующие пять лет. Трактор должен эксплуатироваться не менее двух и не более пяти лет. В настоящее время новый трактор стоит 40 000 долларов, и эта цена за год увеличивается на 10%. Текущая годичная стоимость эксплуатации трактора составляет 1300 долларов и, как ожидается, будет увеличиваться на 10% в год.

a) Сформулируйте задачу в виде задачи о кратчайшем пути.

b) Постройте соответствующее рекуррентное уравнение.

c) Определите оптимальную стратегию замены трактора на следующие пять лет.

4. Рассмотрим задачу замены оборудования на протяжении п лет. Цена новой единицы оборудования равна с долларов, а стоимость продажи после t лет эксплуатации равна s(t)=2(n-t) при п>t и нулю — в противном случае. Годичная прибыль от эксплуатации является функцией возраста оборудования t и равна r(t)=r²-t² при п>t и нулю — в противном случае.

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

b) Определите оптимальную стратегию замены оборудования двухгодичной давности при с=10 000 долларов, считая, что п=5.

5. Решите задачу из предыдущего упражнения, предполагая, что возраст оборудования составляет 1 год и п = 4, с = 6000 долларов, r(t) = n/(n + 1).

4.4.4. Задача инвестирования

Предположим, что в начале каждого из следующих п лет необходимо сделать инвестиции p₁, p₂, ..., Р_п соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r₁, а второй— r₂. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы. Премиальные меняются от года к году, и для i-го года равны q_i1 и q_i2 в первом и втором банках соответственно. Они выплачиваются в конце года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находиться там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиций на следующие п лет.

Элементы модели динамического программирования следующие.

1. Этап i представляется порядковым номером года i, i= 1,2,..., n.

2. Вариантами решения на i-м этапе (для i-го года) являются суммы  и, инвестиций в первый и второй банк соответственно.

3. Состоянием х_i на i-м этапе является сумма денег на начало i-го года, которые могут быть инвестированы.

Заметим, что по определению . Следовательно,

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

Пусть  — оптимальная сумма инвестиций для интервала от -го до n-го года при условии, что в начале -го года имеется денежная сумма . Далее обозначим через - накопленную сумму к концу п-го года при условии, что  и (-) — объемы инвестиций на протяжении -го года в первый и второй банк соответственно. Обозначая  i = 1,2, мы можем сформулировать задачу в следующем виде.

                                   Максимизировать

где

           

Так как премиальные за п-й год являются частью накопленной денежной суммы от инвестиций, в выражения для s_n добавлены q_n1 и q_n2.

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

                      

где х_i+1 выражается через  в соответствии с приведенной выше формулой, af_n+1(x_n+l)0.

Пример 4-4

Предположим, вы хотите инвестировать 4000 долларов сейчас и 2000 долларов 3в начале каждого года, от второго до четвертого, считая от текущего года. Первый банк выплачивает годовой сложный процент 8% и премиальные на протяжении следующих четырех лет в размере 1.8%, 1.7%, 2.1% и 2.5% соответственно. Годовой сложный процент, предлагаемый вторым банком, на 0.2% ниже, чем предлагает первый банк, но его премиальные на 0.5% выше. Задача состоит в максимизации накопленного капитала к концу четвертого года.

Используя введенные выше обозначения, имеем следующее.

                         

Этап 4.

где

Функция  является линейной по I₄ в области 0<I₄<x₄ и, следовательно, ее максимум достигается при I₄=0 из-за отрицательного коэффициента при I₄. Следовательно, оптимальное решение для этапа 4 может быть представлено в следующем виде.

Этап 3.

где

Следовательно,

           

            Этап 2.

где

Следовательно,

           

           

            Этап 1.

где

Следовательно,

           

При вычислениях в обратном направлении получаем следующее.

            Следовательно, оптимальное решение будет записано следующим образом.

Упражнения 4.4, d

            1. Решите задачу из примера 10.-4 в предложении, что   Кроме того, пусть .

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

3. Фермер имеет k овец. В конце каждого года он принимает решение, сколько овец продать и сколько оставить. Прибыль от продажи одной овцы в i-й год равна p_i. Количество овец в конце i-гo года удваивается к концу (i+1)-го года. Фермер планирует в конце п-го года полностью продать овец.

a) Получите общее рекуррентное уравнение для решения задачи.

c) Решите задачу при следующих данных: n=3  года, k=2 овцы, p₁=$100, р₂ = $130, р₃=$120.

d)

4.4.5. Модели управления запасами

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

4.5. Проблема размерности

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

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

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

Пример 4.5-1

Предприятие обрабатывающей промышленности выпускает два вида продукции. Производственный процесс составляет 430 минут в день. Для производства единицы продукции первого вида требуется 2 минуты, а второго — 1 минута. На дневной объем производства продукции первого вида ограничений нет (кроме возможностей производственного процесса), максимальный ежедневный спрос на второй вид продукции равен 230 единиц. Реализация единицы продукции первого вида приносит прибыль в 2 доллара, а второго — 5 долларов. Необходимо найти оптимальное решение задачи максимизации прибыли методами динамического программирования.

Данная задача является следующей задачей линейного программирования.

Максимизировать z = 2х₁ + 5х₂

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

Элементы модели динамического программирования таковы.

1.         Этап i соответствует продукции i,i - 1,2.

2.         Альтернативой х_i на i-м этапе является объем производства продукции  i,i=l,2.

3.         Состояние  представляет количество ресурсов, необходимое для производства продукции вида 1 и 2 (производственное время и ограничение на спрос) и используемое на этапах 1 и 2.

4.         Состояние (v₂, w₂) представляет количество ресурсов, необходимое для производства продукции вида 1 и 2 (производственное время и ограничение на спрос) и используемое на этапе 2.

Этап 2.

Пусть f₂(v₂, w₂) представляет максимальную прибыль для этапа 2 (прибыль от выпуска продукции вида 2) при заданном состоянии (v₂, w₂). Тогда

Следовательно,  имеет место при . Имеем следующее решение для второго этапа.

           

            Этап 1.

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

     

Графически можно легко проверить, что функция  достигает максимального значения при . Итак получаем следующее:

Для определения оптимального значения х₂ заметим, что

Следовательно

.

Итак, оптимальное решение имеет вид:

 единиц,  единиц, .

Упражнения 4.5,а

1. Решите следующие задачи линейного программирования методами динамического программирования.

а)  Максимизировать z = 4x₁ + 14х₂

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

b) Максимизировать z = 8x₁ + 7х₂

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

c) Максимизировать z = 7x₁² +6x₁ +5х₂²

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

2. Пусть в задаче из примера 4.4-1 о загрузке предметов п наименований ограничения самолета по весу и объему представлены величинами W и V соответственно. Величины w_i, v_i и r_i представляют соответственно вес, объем и прибыль, отнесенные к одному предмету наименования. Необходимо записать рекуррентное уравнение обратной прогонки для алгоритма динамического программирования решения сформулированной задачи.

4.6. Заключение

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

Литература

Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N. J., 1987.

Denardo E. Dynamic Programming Theory and Application, Prentice Hall, Upper Saddle River, N. J., 1982.

Dreyfus S., Law A. The Art and Theory of Dynamic Programming, Academic Press, N. Y., 1977.

Sniedovich M. Dynsmic Programming, Marcel Dekker, N. Y., 1991.

Комплексная задача

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