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

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


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

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

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


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

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

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

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

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


Пример10.4-1

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


Потому что вес 1-го предмета wi для всех наименований и наибольший вес W Динамическое программирование принимают целочисленные значения, состояние хi может принимать только цело­численные значения.


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

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


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

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

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


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


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


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

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



Пример 10.5-1

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

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

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



Упражнения 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 баксов. Цена замораживания и хранения 1-го фунта фарша обходится ресторану приблизительно в 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) Какую из 2-ух Динамическое программирование стратегий следует утвердить?

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

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

6. Отель употребляет внешнюю прачечную для стирки полотенец. За денек в отеле Динамическое программирование на­капливается 600 запятанных полотенец. Прачечная конфискует эти полотенца и подменяет их незапятнанными через неизменные промежутки времени. Цена однократной дос­тавки полотенец в прачечную и назад равна 81 бакс. Стирка 1-го полотен­ца обходится в $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). Цена стирки 1-го грязного Динамическое программирование полотенца равна 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. В модели управления припасами, рассмотренной в этом разделе, представите, что цена хранения единицы продукта в единицу времени равна h1, если объем хра­нимого продукта меньше q единиц, и h2 в неприятном случае, h1 > h2. Покажите, как в данном случае можно Динамическое программирование найти экономный размер партии хранимого продукта.

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

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

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


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


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

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


dihanie-stroenie-i-funkcii-dihatelnoj-sistemi-dihatelnij-centr.html
dihanie-v-soedinenii-s-dvizheniem.html
dihanie-vo-vremya-dzadzen.html