5.17. Как строить дерево ветвлений и вычислять нижние границы целевой функции для задачи Беллмана-Джонсона?

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

Один из методов вычисления нижней границы продемонстрируем для случая . Пусть приборы обозначены через , и соответственно времена обслуживания заданы в виде таблицы

Если заявки из множества обслуживаются в последовательности , , а остальные заявки обслуживаются в последовательности , то на основании формулы (5.1.1) общее время обслуживания всех заявок равно

.

При этом прибор завершит обслуживание заявок из в момент ; прибор - в момент ; прибор - в момент .

Определим величину , полагая

.

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

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

Можно также определить величину , полагая

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

Если вычисляются обе величины и , то естественно в качестве нижней границы выбирать большую из них.

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

5.18. Описать общий принцип оптимальности в динамическом программировании.

Процедура решения вспомогательных задач трактуется как реализация “шагов” или “этапов” с результатами . Тогда, если эта последовательность оптимальна, то последние решений должны быть оптимальны. Это утверждение называется принципом оптимальности Беллмана в динамическом программировании.

Применение принципа оптимальности на практике сводится к тому, что на каждом этапе решение должно приниматься с учетом будущих этапов. Очевидно, что только на последнем этапе может быть принято решение, доставляющее максимум (или минимум) целевой функции без каких-либо дополнительных условий. Спланировав оптимальным образом этот последний этап, к нему можно “пристраивать” предпоследний и т.д.