1.3. Задача размещения

Задано множество мест возможного размещения производства I={1,...,N} и множество клиентов J={1,...,M}. Пусть CI – единовременные затраты, связанные с размещением производства в пункте I, а CIj – транспортные затраты (не зависящие от объемов), связанные с поставкой продукции от производителя I клиенту J.

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

Введем переменные

Потоки зададим переменными XIj – доля потребности клиента J, которую удовлетворяет производитель I.

Тогда равенства

Соответствуют полному удовлетворению потребностей клиента J, а

(1.1)

Ограничивают поставки продукции только из пунктов, где производство размещено.

Целевая функция

Ограничения (1.1) можно заменить на более жесткие, сузив тем самым допустимую область. Действительно, условие, что положительный поток может быть только из открытых производств можно записать в виде

(1.2)

Задача размещения также может быть записана в комбинаторной постановке. Заметим, что в случае известного множества S Í I открытых производств каждый клиент будет связан с одним «ближайшим» производителем. Это замечание приводит к постановке

< Предыдущая		Следующая >