Математическая модель. Определим логические переменные задачи: , если коммивояжер переезжает из города в город , и

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

_.

при ограничениях

, – только один въезд в город ,

, – только один выезд из города .

В задаче коммивояжера необходимо еще одно условие, а именно:

_{, , .}

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

Задача о доставке

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

Дата добавления: 2014-01-13