Простая модель развозки (Balinski M.L., Quandt R.E., On an integer program for adelivery problem. Operat. Res., 1964. 12, N2, 300-304.)

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

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

Под способом развозки будем понимать любую допустимую комбинацию выполнения заказов. Говоря точнее, способ развозки представляет собой -мерный столбец, -я компонента которого равна единицы, если -й заказ в этом способе удовлетворяется, и равна нулю в противном случае. Для любой реальной задачи при небольших значениях можно фактически выписать все такие способы развозки. Число этих способов будет зависеть не только от этих параметров, но и, например, от числа складов на каждом маршруте, объема заказов и так далее. Кроме того, каждому способу развозки легко сопоставить связанные с ним затраты (учитывающие, помимо упомянутых выше затрат по доставке, также стоимость работ по выгрузке и тому подобное).

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