тавить основные данных для каждого этапа. Вычисления начинаются с этапа 3, для которого надо ввести следующие данные.

Что вводится Ячейки Количество этапов, N = 3 D3

Ограничение загрузки, W = 4 G3

Текущий этап = 3 С4

w3 = 1 Е4

гЗ = 14 G4

т3 = (0,1, 2, 3, 4) D6:H6

Отметим, что допустимыми значения для т3 являются числа 0, 1, [W/w3] = = [4/1] =4 так же, как в примере 10.3.1. Рабочий лист автоматически проверяет правильность значений т, и выводит соответствующие сообщения в строке 5 (сообщения вида yes ( да ), по ( нет ) и delete ( исключить )).

После ввода данных для этапа 3 рабочий лист оживает и выполняет все необходимые вычисления автоматически (в столбцах В:Р). Значения -111111 указывают, что соответствующий вариант загрузки недопустим. Оптимальное решение (/з, тг) этого этапа приведено в столбцах О и Р. В столбце А выводятся значения /4. Поскольку вычисления начинаются с этапа 3, ft = 0 для всех значений х3. Поэтому ячейки А9:А13 оставлены пустыми (или могут быть заполнены нулями).

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

Шаг 1. Скопируйте значения х3 (диапазон С9:С13) и вставьте их в ячейки диапазона Q5:Q9, где будет храниться оптимальное решение 3-го этапа. Далее скопируйте значения (f3, m3) (диапазон 09:Р13) и вставьте их в диапазон R5:S9. Напомним, что необходимо скопировать и вставить только значения (а не формулы, по которым вычислялись эти значения). Для этого после копирования данных и выделения диапазона, где будут вставлены эти данные, выполните команду ПравкаОСпециальная вставка и после появления одноименного диалогового окна установите в нем переключатель Значения; затем щелкните на кнопке ОК.

Шаг 2. Скопируйте значения f} из диапазона R5:R9 в диапазон А9:А13 (без использования диалогового окна Специальная вставка).

Шаг 3. Введите число 2 в ячейку С4, а также новые значения w2, г2 и т2. На этом заканчивается подготовка к выполнению этапа 2.

После выполнения этапа 2 рабочий лист следует подготовить к этапу 1 так же, как описано выше. После завершения этапа 1 полученное оптимальное решение интерпретируется точно так же, как показано в примере 10.3.1.

Я мог бы автоматизировать все вычисления на рабочем листе, чтобы сразу получить конечный результат. Но я предпочел вовлечь пользователя в процесс получения решения. Усилия со стороны пользователя для этого необходимы минимальные, а наградой ему за эти усилия (я надеюсь) будет углубленное понимание вычислительных деталей решения задачи ДП.

Этап 3

Этап 2

ц ;.у 1

Этап I

Рис. 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 добровольца. Следующая таблица содержит оценку каждой заявки и необходимое число добровольцев для ее выполнения. Какие заявки следует утвердить комитету?