На автобазе имеется  различных грузов, которые требуется развести и заказчикам. Для доставки грузов база располагает т машинами, причем т <С п. Возможны только радиальные маршруты: к любому из заказчиков можно проехать только от базы.

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

Приняв решение отправить в первую очередь бампер ст № 3 и № 8, мы гарантируем, что штраф за них ограничится суммой 30+9. Ожидавшийся прирост штрафа за пролеживание грузов, равный 15+9=24, мы предотвратили. Штрафы за остальные грузы будут расти, но, как мы видели, этот прирост меньше, следовательно, мы максимально снизили ожидаемый штраф.

Поясним, что изложенный метод и есть метод ветвей и границ. Мы на каждом этапе для фиксированных моментов времени t=3, 7, 9 . . ., когда производилась погрузка, выбирали те грузы, где ожидалось наибольшее приращение штрафа. Таким образом минимизировался фактический штраф для каждого из таких этапов. По существу каждый раз выбирался в скрытом виде вариант с достижимой нижней границей, поскольку действительно предотвращалось максимальное приращение штрафа. Так как мы не считали, какой бы вырос штраф, если бы все грузы кроме уже доставленных ожидали отправки, то не вычисляли величины нижней границы штрафа. Это, конечно, можно было бы сделать, но не нужно. Мы сравнивали между собой вычитаемые, выбирали из них наибольшее, следовательно, гарантировали наименьшее значение разности, равное фактическому штрафу, Итак, это наименьшее значение, с одной стороны, является нижней границей, с другой, поскольку это фактический штраф, – это достижимая нижняя граница. А раз это так, то задача решена точно.