Динамическое программирование

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

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

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

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

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

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

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

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

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

Пример10.4-1

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

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

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

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

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

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

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

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

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

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

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

Пример 10.5-1

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

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

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

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

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

a) К= $100, h = $0.05, D = 30 единиц в день.

b) К = $50,1г = $0.05, D = 30 единиц в день.

c) К - $100, h = $0.01, D = 40 единиц в день.

d) К = $100, h = $0.04, D = 20 единиц в день.

2. Ресторан заказывает мясной фарш в начале каждой недели для удовлетворения недельного спроса в 300 фунтов. Фиксированная стоимость размещения заказа равна 20 долларов. Стоимость замораживания и хранения одного фунта фарша обходится ресторану примерно в 0.03 доллара в день.

a) Определите недельные затраты ресторана, связанные с существующей страте­гией создания запаса.

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

c) Вычислите разность между текущими недельными затратами ресторана и те­ми, которые определяются оптимальной стратегией управления запасами.

3. Компания хранит на складе продукцию, которая потребляется с интенсивностью 50 единиц в день. За размещение заказа компания каждый раз платит 20 долларов. Стоимость хранения единицы продукции на складе обходится в $0.35 в неделю.

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

b) Определите оптимальное количество заказов в течение года (считая, что год имеет 365 дней).

4. Отдел снабжения компании предложил две стратегии управления запасами. Стратегия 1. Объем заказа 150 единиц при точке возобновления заказа в 50 еди­ниц и времени выполнения заказа 10 дней.

Стратегия 2. Объем заказа 200 единиц при точке возобновления заказа в 75 еди­ниц и времени выполнения заказа 15 дней.

Затраты на оформление заказа равны 20 долларов, а стоимость хранения единицы продукции на складе обходится в $0.02 в день.

a) Какую из двух стратегий следует утвердить?

b) Если бы вы отвечали за разработку стратегии управления запасами, какова бы­ла бы ваша рекомендация?

5. Магазин прессует и складывает в поддоны пустые картонные упаковочные короб­ки для их последующей переработки. За день штабелируется пять поддонов. Стоимость хранения одного поддона на заднем дворе магазина составляет 0.10доллара в день. Компания, которая перевозит поддоны в перерабатывающий центр, устанавливает оплату в 100 долларов за аренду своего погрузочного обору­дования плюс 3 доллара за перевозку каждого поддона. Изобразите графически изменение количества поддонов с течением времени и разработайте оптимальную стратегию доставки поддонов в перерабатывающий центр.

6. Отель использует внешнюю прачечную для стирки полотенец. За день в отеле на­капливается 600 грязных полотенец. Прачечная забирает эти полотенца и заменяет их чистыми через постоянные промежутки времени. Стоимость однократной дос­тавки полотенец в прачечную и обратно равна 81 доллар. Стирка одного полотен­ца обходится в $0.60. Стоимость хранения в отеле грязного и чистого полотенец равна $0.02 и $0.01 соответственно. Как часто следует отелю пользоваться служ­бой доставки полотенец? (Подсказка. В этой задаче имеется два типа складируе­мых предметов. Если количество грязных полотенец возрастает, то количество чистых уменьшается с равной интенсивностью.)

7. Дана задача управления запасами, в которой склад пополняется равномерно (вмес­то мгновенного пополнения) с интенсивностью а. Продукция потребляется с ин­тенсивностью D. Так как потребление происходит наряду с периодом пополнения, необходимо, чтобы было a >D. Стоимость размещения заказа равна К, а стои­мость хранения единицы продукции в единицу времени — И. Покажите, что если у — объем заказа и отсутствует дефицит, то

a) максимальный объем запаса равен у(1 - D/a),

b) общие затраты в единицу времени при заданном у равны

d) формулу экономичного объема заказа при мгновенном пополнении запаса можно получить из формулы в п. с).

8. Фирма может производить изделие или покупать его у подрядчика. Если фирма сама выпускает изделие, то каждый запуск его в производство обходится в 20 дол­ларов. Мощность производства составляет 100 единиц в день. Если изделие заку­пается, затраты на размещение каждого заказа равны 15 долларов. Затраты на со­держание изделия на складе, независимо от того, закупается оно или производится на фирме, равны $0.02 в день. Потребление изделия фирмой оценивается в 260 000 единиц в год. Если предположить, что фирма работает без дефицита, оп­ределите, что выгоднее — закупать или производить изделия?

9. Предположим, что в упр. 7 допускается дефицит и удельные потери от него со­ставляют р долл. в единицу времени. Если w— величина дефицита и у— объем заказа, покажите, что имеют место следующие соотношения.

Упражнения 11.3,б

1. Вернитесь к задаче из упр. 11.3,а(6). Стоимость стирки одного грязного полотенца равна 0.60 доллара, но она может быть снижена до 0.50 доллара, если отель по­ставляет в прачечную по меньшей мере 2500 единиц полотенец. Следует ли отелю воспользоваться скидкой?

2. Продукция используется с интенсивностью 30 единиц в день. Стоимость хранения единицы продукции равна 0.05 доллара в день, стоимость размещения заказа со­ставляет 100 долларов. Предположим, что дефицит продукции не допускается, стоимость закупки равна 10 долларов за единицу продукции, если объем закупки не превышает 500 единиц, и 8 долларов в противном случае. Определите опти­мальную стратегию управления запасами при условии, что срок выполнения зака­за равен 21 день.

3. Комплектующие продаются по 25 долларов за единицу, но предлагается 10% скидка при покупке партии от 150 единиц и выше. Компания в день использует 20 единиц комплектующих. Стоимость размещения заказа равна 50 долларов, стои­мость хранения единицы товара составляет 0.30 доллара в день. Следует ли ком­пании воспользоваться скидкой?

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

5. В модели управления запасами, рассмотренной в этом разделе, предположите, что стоимость хранения единицы товара в единицу времени равна h₁, если объем хра­нимого товара меньше q единиц, и h₂ в противном случае, h₁ > h₂. Покажите, как в этом случае можно определить экономичный размер партии хранимого товара.

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

1. Решите задачу из примера 11.3-3 в предположении, что сумма средних запасов всех предметов должна быть меньше 25 единиц.

2. Приведенные ниже данные относятся к задаче управления запасами для четырех видов продукции. Компания желает определить экономичный объем заказа для каждого из четырех видов продукции таким образом, чтобы суммарное количест­во заказов в год (365 дней) было не более 150.

3. Решите предыдущее упражнение в предположении, что единственным ограниче­нием является денежная сумма в 10 000 долларов, которая может быть инвестиро­вана на приобретение запасов продукции. Стоимость закупки единицы продукции вида 1, 2, 3 и 4 равна соответственно 10, 5, 10 и 10 долларов.

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

Точное значение находится выше или ниже 𝛌*. Примените это начальное значе­ние в задаче из примера 11.3-3.