Математическая модель

Определим булевы переменные задачи: xij = 1, если коммивояжер переезжает из города i в город j, и xij = 0, если коммивояжер не переезжает из города i в город j.

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

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

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

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

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

, i ≠ j, i, j = 2,…, n

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

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

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

Математическая модель.

Рис. 1. Диалоговое окно Добавление ограничения для задания двоичной переменной

Введем переменные xj с условиями: xj = 1, если выбран j-ый маршрут, и xj = 0 в противном случае, j = 1, …, n. Введем величины aij так, что aij = 1, если i-ый клиент обслуживается по маршруту j, и aij = 0 в противном случае i = 1, …, m, j = 1, …, n. Стоимость доставки по маршруту j обозначим как сj.

Целевая функция, выражает суммарные расходы доставки по всем выбранным маршрутам