Задачи распределения

Следующая простая задача типична для класса задач, называемых иногда задачами распределения. Имеются два источника жидкости: А дает 100 галлонов в минуту, Источники должны снабжать два бассейна С и потребность каждого из которых 75 галлонов в минуту.

Рис. 2.7. Расположение источников жидкости и бассейнов (расстояния измеряются в милях).

Жидкость может подаваться от источника к бассейну с помощью труб с максимальной пропускной способностью 75 галлонов в минуту. Пусть источники и бассейны расположены так, как это показано на рис. 2.7, и соединения труб допускаются только в местах расположения источников и бассейнов. Спрашивается, как следует подсоединять трубы, чтобы при этом полная длина труб была наименьшей.,

Представление этой задачи в пространстве состояний выглядит следующим образом:

Описания состояний. Состояния описываются списком величин избыточного расхода жидкости, который имеется в точках А, В, С и D. Так, начальное состояние описывается списком

Операторы. Операторы соответствуют передаче избытка «жидкости в минуту» из одной точки в другую. В задачах,

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

1. Передать 25 галлон/мин из Л в В.

2. Передать 25 галлон/мин из Л в С.

12. Передать 25 галлон/мин из В в Л.

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

Критерий цели. Целевое состояние описывается списком

Рис. 2.8. Часть графа для задачи распределения.

Часть графа, получающегося таким образом пространства состояния, показана на рис. 2.8. Обозначение типа около Дуг графа показывает, что соответствующий оператор передает избыток в 25 галлон/мин от Л к Стоимости, написанные рядом с каждой дугой, показывают, сколько миль труб нужно добавить для подачи этого избытка. Число нуль при этом

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