При решении сложной оптимизационной задачи объем вычислений перебором всех вариантов может оказаться очень большим. В этом случае может помочь метод динамического программирования. Суть его в том, что задача разбивается на этапы и на каждом этапе проводится оптимизация. Но оптимизируется решения не для данного этапа, а для совокупности этого этапа со всеми рассмотренными ранее.
Пример 1. Пусть требуется проложить дорогу из пункта А в пункт В, показанные на схеме на рис.12. Прокладывать следует по линиям сетки. Стоимость прокладки на каждом участке показана. Требуется проложить маршрут так, чтобы стоимость его прокладки была минимальной.
 11
| В | ||||||
| А |
Рис.12
Начнем расчет с последнего шага. В пункт В можно попасть из двух соседних пунктов – слева или снизу. В каждом из этих пунктов в кружке напишем стоимость прокладки оставшейся части дороги (14 и 3) и направление ее прокладки.
Затем рассматриваем пункты, отстоящие от конечного на два шага, на первой таблице они обозначены жирными точками. Для каждого из них рассматриваем всевозможные продолжения и стоимость прокладки дороги до конечного пункта по этим продолжениям. Для верхнего и нижнего пунктов, находящихся на границе, продолжения единственные. В соответствующих кружках ставим соответственно 9+14=23 и 5+3=8. В среднем пункте возможны два продолжения. Если двигаться вверх, то получим стоимость 5+14=19, если же двигаться направо – то 10+3=13. Выбираем меньшее, обозначаем направление направо.
| В | ||||||
| А |
Рис.13
Далее таким же образом заполняем вершины третьего уровня, и т.д. Если в какой-нибудь вершине стоимость по обоим направлениям оказывается одинаковой, направление задаем произвольно. Когда дойдем до начальной вершины А, получим минимальную стоимость прокладки дороги и соответствующую цепочку направлений. Эта цепочка начинается с вершины А и продолжается далее по стрелкам. В нашем случае эта стоимость равна 72.
Оптимальное распределение ресурсов. Имеется некоторое количество ресурсов (материальные, трудовые, финансовые), которые необходимо распределить либо между производственными участками, либо по годам или другим периодам. При этом нужно получить максимальную суммарную эффективность от выбранного способа распределения. Показателем эффективности может служить, например, прибыль, себестоимость, суммарные затраты и т.д.
Пример 2. Хозяйство приобрело 6 единиц специализированной техники, которую нужно распределить между четырьмя отделениями с тем, чтобы максимально повысить общий уровень технической готовности. Для каждого i -гоотделения известен уровень технической готовности fi (u), который отделение будет иметь, если получит u единиц техники. Эти данные приведены в таблице. Оптимизационная задача заключается в том, чтобы сделать максимальной сумму всех уровней.
| u | f1(u) | f2(u) | f3(u) | f4(u) |
| 0,65 | 0,90 | 0,72 | 0,81 | |
| 0,74 | 0,92 | 0,79 | 0,85 | |
| 0,81 | 0,93 | 0,84 | 0,88 | |
| 0,85 | 0,94 | 0,88 | 0,91 | |
| 0,88 | 0,95 | 0,91 | 0,93 | |
| 0,90 | 0,95 | 0,92 | 0,94 | |
| 0,91 | 0,95 | 0,92 | 0,95 |
Вычисления будем проводить средствами EXCEL в специальной таблице. Считаем, что техника отправляется последовательно в первое, второе, третье, четвертое отделения. Анализ начинаем с последнего шага, то есть четвертого отделения. Используем следующие параметры:
s – количество нераспределенных единиц техники, оставшихся к данному шагу;
ui (s) – количество единиц техники, которое может быть выделено i -му отделению (рассматриваемому на данном шаге заполнения таблицы). Это количество выделяется из s нераспределенных, значит, ui (s) ≤ s.
Wi (s) – максимальный суммарный уровень технической готовности, который достигается при данном значении ui (s) с учетом всех рассмотренных ранее шагов.
| s | i = 4 | i = 3 | i = 2 | i = 1 | ||||
| u 4(s) | W 4(s) | u 3(s) | W 3(s) | u 2(s) | W 2(s) | u 1(s) | W 1(s) | |
| 0,81 | 1,53 | |||||||
| 0,85 | 1,60 | |||||||
| 0,88 | ||||||||
| 0,91 | ||||||||
| 0,93 | ||||||||
| 0,94 | ||||||||
| 0,95 |
При i = 4 столбцы u 4(s) и W 4(s) заполняются очень просто. Возможные значения u 4(s) совпадают с s, так как это последнее отделение и больше распределять технику не придется. Суммарный уровень технической готовности – это уровень технической готовности 4-го отделения, он просто переносится из первой таблицы.
При i = 3 и i = 2 для заполнения столбцов необходимы специальные вычисления. Рассмотрим i = 3. При s = 0 не осталось нераспределенной техники, поэтому u 3(0) = 0 и W 3(0) = f 3(0) + W 4(0) = 0,72 + 0,81 = 1,53. При всех других значениях s требуется производить сравнение. При s = 1 возможные значения u 3(0) это 0 или 1. Тогда для 4-го отделения останется соответственно 1 или 0 единиц техники, и суммарный уровень технической готовности будет соответственно f 3(0) + W 4(1) = 0,72 + 0,85 = 1,57 и f 3(1) + W 4(0) = 0,79 + 0,81 = 1,60. Выбираем большее, делаем вывод, что u 3(1) = 1 и W 3(1) = 1,60. Для s = 2 придется сравнивать уже три суммы f 3(0) + W 4(2), f 3(1) + W 4(1) и f 3(2) + W 4(0). Наибольшая из этих сумм принимается за W 3(2), а соответствующий аргумент при f 3 – значение u 3(2).
В общем случае для нахождения ui (s) и Wi (s) сравниваем суммы
fi (0) + Wi- 1(s), fi (1) + Wi- 1(s – 1), fi (2) + Wi- 1(s – 2), …, fi (s) + Wi- 1(0). (1)
Выбираем из них максимальную и берем в качестве Wi (s). Соответствующий аргумент при fi будет значением ui (s).
Суммируемые значения находятся в столбцах первой и второй таблицы, причем расположены там в обратном порядке. Это дает возможность организовать вычисления в EXCEL. При этом отметим, что EXCEL только уменьшает объем работы, но для задач большой размерности он все равно будет достаточно большим. Здесь следует использовать специальное программное обеспечение.
Скопируем таблицы WORD на лист EXCEL. Вторая таблица будет основной расчетной таблицей. Создадим вспомогательные таблицы, как показано на рисунке 14.
Рис.14
В столбец G вспомогательной таблицы будем копировать соответствующий столбец из первой таблицы, который мы хотим записать в обратном порядке, то есть создать его инверсию. На рис.14 туда отправлен столбец значений f 3(u). В столбце Н сформируем эту инверсию. Для этого в ячейки Н2 – Н8 введем формулы =$G$8, =$G$7, …, =$G$2. Рядом в столбце I выпишем значения соответствующих значений u.
Теперь создадим расчетную таблицу для вычисления сумм (1). В столбец К скопируем содержимое очередного столбца Wi- 1(s) основной расчетной таблицы. На рис.2 мы видим там содержимое столбца W 4(s). В столбцы L и M скопируем массив G2 – I8 так, чтобы его последняя строка оказалась против первой заполненной числами строки предыдущего столбца.
В столбцах N – T будем вычислять значения сумм (1). В ячейку N12 вводим формулу =K12+L12, протягиваем ее вниз до строки 18 и производим в получившемся массиве команду заменить: K на $K$ и L на $L. Этот массив копируем и вставляем в следующие столбцы, сдвигая каждый раз на одну строку выше. В получившихся ячейках и будут вычисляться суммы (1). При этом следует иметь в виду, что нужные нам суммы будут находиться в строках начиная с 12 и выше.
Мы уже имеем возможность заполнить столбцы u 3(s) и W3(s) основной расчетной таблицы. Для s = 0 выбирать не приходится, так как сумма единственная. Вносим в основную расчетную таблицу значения u 3(0) = 0, W3(0) = 1,53. Эти значения следует набирать вручную, а не копировать, чтобы они не менялись при последующей работе с таблицей.
При s = 1 мы выбираем уже из двух сумм, равных 1,6 и 1,57. Выбираем большую, переносим ее в основную расчетную таблицу вместе с соответствующим значением u = 1. Так же поступаем со всеми следующими суммами. При равенстве двух наибольших значений выбираем любое. В результате столбцы основной расчетной таблицы для i = 3 будут заполнены.
Рис.15
Для i = 2 меняем только содержимое двух массивов. В столбец G копируем значения столбца f 2(u) первой таблицы, в столбец K – только что полученное содержимое столбца W 3(s) основной расчетной таблицы. Анализируем образовавшиеся суммы и вносим значения в основную расчетную таблицу так же, как для i = 3.
Так же поступаем для всех остальных значений i, кроме последнего i = 1. Здесь нам уже не придется выбирать для нахождения u 1(s), так как все нераспределенное к этому шагу достанется первому отделению. Это значит, что u 1(s) = s. Из всех сумм мы рассматриваем только суммы из последнего столбца для s = 6 и просто переносим получившиеся значения в основную расчетную таблицу.
Рис.16
Расчеты закончены. Результат показан на рис.16. Подведем итоги. Видим, что максимальное значение целевой функции W1(s), равное 3,44, достигается при u 1(s), равном 3 или 2. Если u 1(s) = 3, то есть первому отделению достается 3 машины, то остается распределить s = 3 машины. В строке основной таблицы, соответствующей s = 3, в столбце u 2(s) имеем значение 0, то есть второму отделению не достается машин. Значит, значение u 3(s) также ищем при s = 3, оно равно 2. Это количество машин достается третьему отделению, и четвертому остается 1 машина.
Если же взять u 1(s) = 2, то дальше для u 2(s) придется искать значение в строке s = 4, оно также равно 0. Тогда значение u 3(s) также ищем при s = 4, оно равно 3. Четвертому отделению опять остается 1 машина.