Этап 3
Этап 2
ц ;.у 1
| | | | | Input Data «пг1 Mar | m ColciilJTtlon | | | Ouput Solution Summary |
Humboi of at»n**lN | | PM.ainit.w- | | | л"»*- cam* rsd | | Stage Optvnum Solution | | t m | | 1 m |
-uueiit ataoe ? | | | 1?» | | | ЭтапЗ | | Этап 2 |
| fivi с... r- i; | | | | | | | | | | | | 0 0 14 1 28 2 42 3 | | 0 0 |
StaueJ | | | | | | | | | | | | | | 14 0 28 D 47 1 |
r2,m2« | | | | | | | | | | | |
| | »2"m2- | | | | | | | | | | | | Г2 m2 |
| | | | i11111 | | | | | | | | | | 0 0 | | 56 4 | | 81 1 |
| | | | 111111 | | | | | | | | | | 14 0 | | | |
| | | | 111111 | | | | | | | | | | 28 0 | | |
| | | | | | | | | | | | | | 47 1 | | |
| | | | | | | | | | | | | | 61 1 | | |
| | | | | | | | | | | | | | | |
Этап I
. J * | В с | | | | | | | | | | . L | | | | | | Г R ~S | | U V |
| | | | | Dynamic Piouiammmfi (Bachwai dl Knapsack Model | | | | | | |
| | | | put Data and Sta, | ft Calculations | | | | Ouput Sokjt | onSummarv |
3 Numbei of stauf-*,M- 4 uiiemctac 1 5 tin ml values correct | | ReaJftaJLVf- | | | | | fC6f 1С" | | | | f rn | | t m |
| | | | | | | | | | ЭтапЗ | | Этап 2 |
| •« | | | | | | | | | Stage | | 0 0 | | 0 0 |
| 1 ml | | | | | | | | | | | Optimum | | 14 1 | | 14 0 |
7 Stage! | rl-ml- | | | | | | | | | | | | Sokiion | | 28 2 | | 28 0 |
8 f? | w1*ml« | | | | | | | | | | | | | | | 42 3 | | 47 1 |
S 3 | xl- 0 | | 111111 | 111111 | | | | | | | | | | | | 56 4 | | 61 1 |
10 14 | xl- 1 | | 111111 | 111111 | | | | | | | | | | | | | | ЭтапЗ |
11 28 | xl- 2 | | | 111111 | | | | | | | | | | | | | 0 0 |
12 47 | xl. 3 | | | 111111 | | | | | | | | | | | | | 14 0 |
13 81 | Xl- 4 | | | | | | | | | | | | | | | | | 31 1 |
I" | | | | | | | | | | | | | | | | | | 47 0 |
| | | | | | | | | | | | | | | | | | 62 2 |
| | | | | | | | | | | | | | | | | |
Рис. 10.5. Этапы решения задачи примера 10.3.1
УПРАЖНЕНИЯ 10.3.13
1. В задаче примера 10.3.1 определите оптимальное решение, предполагая, что максимальная грузоподъемность самолета составляет 3 тонны.
2. Решите задачу о загрузке из примера 10.3.1 для каждого из следующих случаев.
a) w,= 4, г,= 70, ws= 1, г2= 20, w3 = 2, г3= 40, W= 6.
b) и>,= 1, г,= 30, w2= 2, г2= 60, w3= 3, г3= 80, W = 4.
3. Турист собирается в путешествие по дикой местности и должен упаковать в рюкзак предметы трех видов: пищу, средства первой помощи и одежду. Объем рюкзака составляет 3 кубических фута. Каждая единица пищи занимает
В этих упражнениях там, где возможно, выполните вычисления вручную, а затем проверьте полученные результаты с помощью шаблона Excel chlOKnapsack.xls.
1 кубический фут, упаковка средств первой помощи - четверть кубического фута, а отдельный предмет одежды - примерно половину кубического фута. Турист определил свои предпочтения весовыми коэффициентами 3, 4 и 5 - для пищи, средств первой помощи и одежды соответственно. Это означает, что одежда является самым ценным предметом среди остальных. Опыт подсказывает туристу, что он должен взять не менее одного предмета каждого вида и не более двух комплектов средств первой помощи. Сколько единиц каждого наименования возьмет турист в поход? 4. Студент должен выбрать 10 факультативных курсов на четырех различных факультетах, причем на каждом факультете должен быть выбран по меньшей мере один курс. Эти курсы распределяются между факультетами таким образом, чтобы максимизировать объем "знаний". Студент оценивает знания по шкале в сто баллов и приходит к выводам, представленным в следующей таблице.
Номер курса
Какие курсы следует выбрать студенту?
5. У меня во дворе имеется небольшой огород 10 х 20 футов. Этой весной я собираюсь посадить овощи трех видов: помидоры, зеленые бобы и кукурузу. Огород разбит на ряды, длина которых равна 20 футам. Кукуруза и помидоры занимают ряды шириной 2 фута, а зеленые бобы - 3 фута. Помидоры мне нравятся больше, а бобы меньше. По 10-балльной шкале предпочтений я бы присвоил помидорам 10 баллов, кукурузе - 7 баллов и зеленым бобам - 3 балла. Независимо от моих предпочтений, жена настаивает, чтобы я посадил не менее одного ряда зеленых бобов и не более двух рядов помидоров. Сколько рядов каждого вида овощей следует мне посадить?
6. "Жилище для человечества" - прекрасная благотворительная организация, которая строит дома для бедствующих семей силами добровольцев. Такая семья может выбрать себе дом из трех типоразмеров: 1000, 1100 и 1200 квадратных футов. Дом каждого типоразмера требует выполнения определенного объема работ силами добровольцев. Филиал организации в городе Файтвилл получил пять заявок на предстоящие шесть месяцев. Комитет по надзору дает оценку каждой заявке в численном виде, принимая во внимание различные факторы. Более высокая оценка означает более острую потребность в жилье. В течение предстоящих шести месяцев филиал организации в этом городе может привлечь к работе максимум 23 добровольца. Следующая таблица содержит оценку каждой заявки и необходимое число добровольцев для ее выполнения. Какие заявки следует утвердить комитету?
Заявка | Размер дома (фут2) | Оценка | Необходимое число добровольцев |
| 1200 | | |
| 1000 | | |
| 1100 | | |
| 1000 | | |
| 1200 | | |
7. Шериф округа Вашингтон баллотируется на следующий срок. Денежные средства на предвыборную кампанию составляют примерно 10 ООО долларов. Хотя комитет по переизбранию хотел бы провести кампанию во всех пяти избирательных участках округа, ограниченность денежных средств предписывает действовать по-другому. Приведенная ниже таблица содержит данные о числе избирателей и денежных средствах, необходимых для проведения успешной кампании по каждому избирательному участку. Каждый участок может либо использовать все предназначенные деньги, либо вовсе их не использовать. Как следует распределить денежные средства?
Участок | Число избирателей | Необходимые средства (долл.) |
| 3100 | 3500 |
| 2600 | 2500 |
| 3500 | 4000 |
| 2800 | 3000 |
| 2400 | 2000 |
8. Конструируется электронный прибор, состоящий из трех основных компонентов. Все компоненты соединены последовательно, поэтому выход из строя одного из них влечет за собой отказ всего прибора. Надежность (вероятность безаварийной работы) прибора можно повысить путем дублирования каждого компонента. Конструкция прибора допускает использование одного или двух резервных (параллельных) блоков, т.е. каждый компонент прибора может содержать до трех блоков, соединенных параллельно. Следующая таблица содержит данные о надежности г и стоимости компонентов прибора.
Число параллельных блоков | Компонент 1 | Компонент 2 | | Компонент 3 |
| с1 (долл.) | | с2 (долл.) | | сЗ (долл.) |
| 10.6 | 1000 | | 3000 | | 2000 |
| 20.8 | 2000 | | 5000 | | 4000 |
| 30.9 | 3000 | | 6000 | | 5000 |
Общая сумма, выделенная на конструирование прибора, равна 10 000 долл. Как следует сконструировать прибор? (Совет. Наша задача состоит в максимизации надежности г,/у, прибора. Это значит, что целевая функция является мультипликативной, а не аддитивной.)
9. Решите следующую задачу с помощью метода динамического программирования.
Максимизировать z = У\Уг-.-Уп
при условиях
У\ + Уг+ ...+уя=с, у,->0,1 = 1,2.....п.
(Подсказка. Это упражнение аналогично предыдущему упражнению, но с той лишь разницей, что переменные yt являются непрерывными.)
10. Решите следующую задачу с использованием метода динамического программирования.