ГЛАВА 12. ПРИМЕНЕНИЕ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

§ 1. Обобщенная задача о ранце

1.1. Следующая задача является естественным обобщением сформулированной в § 2 гл. 2 задачи о ранце.

Максимизировать

при условиях

Делаются следующие предположения:

1°. — конечные множества.

2°. - произвольные функции одной переменной (никаких ограничений типа выпуклости, дифференцируемости и т. п. не накладывается).

3°. - функции одной переменной, принимающие целые значения при любых .

4°. для всех (здесь — известные целые положительные числа).

Из условия 4° сразу следует, что для любого

Ограничение (1.2) может иметь произвольный характер, например или же «двоичное разложение содержит ровно 10 единиц».

1.2. Описываемый способ решения задачи (1.1) — (1.3) по существу сочетает в себе идеи динамического программирования и локального подхода к некоторым дискретным задачам (см. гл. 13). В его основе лежит прежде всего отсев «доминируемых» значений переменных которые заведомо не могут входить в оптимальный план. Правила отсева даются следующей теоремой.

Теорема 1.1. Пусть для некоторого

Тогда значение переменной не может входить в оптимальный план задачи

Доказательство. Пусть входит в некоторый оптимальный план

Рассмотрим вектор

Вектор также является планом. Действительно, используя условие б), получаем

так что ограничение (1.2) выполняется. Далее для всех имеем кроме того, Тем самым выполнено и ограничение (1.3). Наконец, из условия в)

Таким образом, план не является оптимальным.

Основываясь на теореме 1.1, проведем «отсев» заведомо не оптимальных значений переменных Пусть множество значений, которые принимает когда пробегает Рассмотрим произвольное Определим

Ясно, что для каждого достаточно сохранить только одно возможное значение х а именно Обозначим теперь через через Получим следующую задачу, эквивалентную задаче (1.1)-(1.3).

Максимизировать

при условиях

Заметим, что из сделанных выше относительно задачи (1.1) — (1.3) предположений и из неравенства (1.4) сразу следует, что

б) - конечные множества, причем .

1.3. Перейдем теперь к изложению алгоритма. Шаг 1. Рассмотрим задачу, которую будем называть задачей

Максимизировать

при условиях

Здесь целое,

Все задачи можно решать одновременно, производя полный перебор всех наборов удовлетворяющих условиям (1.10). В результате следует запомнить: 1) множество тех при которых задача разрешима, 2) для каждого соответствующий оптимальный план и оптимальное значение целевой функции

Множества после этого вычеркиваются из памяти. Переходим к шагу 2.

Для объема перебора и объема памяти имеют место оценки (с учетом необходимости помнить множества )

здесь оценка сверху для

Шаг От предыдущего шага имеется следующая информация: 1) множество тех при которых разрешима задача максимизировать

при условиях

2) для каждого — соответствующий оптимальный план и оптимальное значение целевой функции

Для объема информации запоминаемой от предыдущего шага, имеет место оценка

Рассмотрим задачу, которую будем называть задачей

Максимизировать

при условиях

Все задачи можно решать одновременно, производя перебор всех наборов удовлетворяющих условиям (1.16) — (1.17). При этом следует запомнить: 1) множество тех при которых задача разрешима; 2) для каждого соответствующий оптимальный план и оптимальное значение целевой функции

После этого из памяти вычеркивается информация, оставшаяся от шага, и множество Переходим к шагу.

Для объема перебора 1 имеет место оценка

а для объема вновь запоминаемой информации

что вместе с информацией запомненной от предыдущего шага, и с информацией о множествах. даст следующую оценку для максимального объема запоминаемой информации:

Шаг От предыдущего шага имеется следующая информация: 1) множество тех при которых разрешима задача для каждого соответствующий оптимальный план и оптимальное значение целевой функции

Для объема информации запомненной от предыдущего шага, справедлива оценка

Рассмотрим теперь следующую эквивалентную задаче задачу Максимизировать

при условиях

Задача решается полным перебором всех наборов удовлетворяющих условиям (1.25), (1.26). Оптимальный план этой задачи будет также оптимальным планом задачи (1.5) — (1.7).

Для объема перебора справедлива оценка

а для объема необходимой памяти —

1.4. Укажем в заключение оценки для общего объема необходимого перебора и максимального объема одновременно хранимой информации