| 14/Пз | | | | | Оптимальное решение |
т3 = 0 | т3 = 1 | т3 = 2 | т3 = 3 | т3 = 4 | h(Xi) | "h |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
Этап 2.
f2{x2) = max{47m, + /3(х, -3m,)}, тах{/и,} =
= 1.
47/772 + Н(хг - З/п2) Оптимальное решение
Xl /772 = 0 пь. = 1 h(x2) m
0 0+0=0 -00
1 0 + 14=14 - 14 0
2 0 + 28 = 28 - 28 0
3 0 + 42 = 42 47 + 0 = 47 47 1
4 0 + 56 = 56 47+ 14 = 61 61 1
Этап 1.
| | /, (дг,) = max {3 lm, + /,(*,- 2/n,)}, | max{m,} = | "4" .2. | = 2. |
| 31 m, + f2(xi | -2m,) | Оптимальное решение |
mi =0 | m, = 1 mi = 2 | | | | |
| 0 + 0 = 0 | - - | | | | |
| 0 + 14=14 | - - | | | | |
| 0 + 28 = 28 | 31+0 = 31 - | | | | |
| 0 + 47 = 47 | 31+14 = 45 - | | | | |
| 0 + 61 =61 | 31 + 28 = 59 62 + 0 = 62 | | | | |
Оптимальное решение определяется теперь следующим образом. Из условия W= 4 следует, что первый этап решения задачи при хг = 4 дает оптимальное решение ml = 2, которое означает, что два предмета первого наименования будут загружены
в самолет. Эта загрузка оставляет хг=* хх-2т\ =4-2x2 = 0. Решение на втором этапе при а:2=0 приводит к оптимальному решению т2 =0, которое, в свою очередь, дает х3 = х2- 3т = 0-3x0 = 0. Далее этап 3 при х3 = 0 приводит к т\ =0.
В следующей таблице сравниваются допустимые решения для каждого значения х3.
Следовательно, оптимальным решением задачи является т\ = 2, т\ = О и т\ = 0* Соответствующая прибыль равна 62 ООО долларов.
В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для xt = 4, так как это последний этап, подлежащий рассмотрению. Однако в таблицу включены также вычисления для х, = 0, 1, 2 и 3, которые позво" ляют провести анализ чувствительности решения. Например, что произойдет, если максимальная грузоподъемность самолета будет 3 тонны вместо 4? Новое оптимальное решение может быть определено, начиная с х1 = 3 на первом этапе и продолжая так, как мы поступали при я, = 4.
Задача о загрузке является типичным представителем задачи распределения ресурсов, в которой ограниченный ресурс распределяется между конечным числом видов (экономической) деятельности. При этом целью является максимизация соответствующей функции прибыли. В таких моделях определение состояния на каждом этапе будет аналогично приведенному для задачи о загрузке: состоянием на этапе i является суммарное количество ресурса, распределяемого на этапах i, i + 1,п.
Решение задачи о загрузке в Excel. Природа вычислений в динамическом программировании такова, что делает невозможным разработку универсальных программ для решения задач ДП. Возможно, этим объясняется отсутствие на сегодняшний день коммерческих программных продуктов, рассчитанных на решение широкого класса задач ДП.
Здесь мы покажем, как решается в Excel один подкласс задач ДП - задача о загрузке с одним ограничением (файл chlOKnapsacLxls1). На рис. 10.4 показан рабочий лист Excel для решения задачи о загрузке методом обратной прогонки. Рабочий лист разбит на два раздела. В разделе, ограниченном столбцами Q:V, выводятся результаты вычислений. В другом разделе (столбцы А:Р) в его верхней части (строки 3-6) содержатся входные данные для текущего этапа, нижняя часть (строка 7 и ниже) зарезервирована для вывода результатов вычислений по этапам. Отметим, что максимальное возможное число альтернатив т, на этапе i не должно превышать 10 (ячейки D6:N6).
| | e с | | | | | | | •> | | | | | О P | Q R-j S | T , U V |
| | | | | | Dynamic Prog | lammir | q (Backward) Knapsack Model | | | |
| Input Data and Step* Calculation* | Ouput Solution Summary |
| Ilumber of *taae*1№* | | Re*, limit, W- | | ••Maximum WAv cannot exceed 10 | | | | x 1 m | x 1 m |
| uirent stage- 1 | | | | | | | | | | | | | | |
| Are m vatut* correct? | | | | | | | | | | | | 1 Stage | | |
| | | | | | | | | | | | | | Optimum | | |
| | r"m« | | | | | | | | | | | | Solution | | |
| | | | | | | | | | | | | | f m | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
Puc. 10.4. Шаблон Excel для решения задачи о загрузке
На рис. 10.5 показаны этапы вычислений для задачи примера 10.3.1. Вычисления выполняются последовательно по этапам и пользователю необходимо предос-
1 Эта рабочая книга закрыта паролем от изменений, поэтому она не русифицирована. Кроме того, перед ее использованием следует установить в Windows (Панель управленияЯзык и стандарты) региональные установки Английский (США), иначе не все вычисления в этой книге выполняются корректно. Это замечание относится ко всем рабочим книгам и шаблонам Excel, которые упоминаются в оставшейся части книги. - Прим. ред.
тавить основные данных для каждого этапа. Вычисления начинаются с этапа 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.
Я мог бы автоматизировать все вычисления на рабочем листе, чтобы сразу получить конечный результат. Но я предпочел вовлечь пользователя в процесс получения решения. Усилия со стороны пользователя для этого необходимы минимальные, а наградой ему за эти усилия (я надеюсь) будет углубленное понимание вычислительных деталей решения задачи ДП.