Задача о доставке (покрытии множества)

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

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

x_j=1, если маршрут j выбран;

x_j=0, в противном случае,

.

Обозначим элементы a_ij следующим образом:

a_ij=1, если i-й клиент обслуживается по маршруту j;

a_ij=0, в противном случае,

.

Обозначим стоимость доставки по маршруту j через с_j.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

.

ЦФ представляет суммарные расходы доставки по выбранным маршрутам.

Ограничения имеют вид:

Согласно условиям (1) каждый клиент обслуживается один раз в день.

Пример 3.8

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

Таблица обслуживания клиентов по маршрутам
Клиенты	Маршруты
Расходы по маршруту

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

900x₁+1000x₂+800x₃ ®min,

Ограничения имеют вид:

1x₁₁+0x₂₁+1x₃₁=1,

1x₁₂+0x₂₂+0x₃₂=1,

1x₁₃+0x₂₃+1x₃₃=1,

0x₁₂+1x₂₂+0x₃₂=1,

0x₁₃+1x₂₃+1x₃₃=1.

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 3.24. Значения переменных x_j располагаются в блоке ячеек B10:D10 (см. рис. 3.24). Коэффициенты целевой функции, отражающие стоимость доставки по маршруту, находятся по адресам B9:D9. Данные об обслуживании клиентов по маршрутам имеются в блоке B4:D8

Рис. 3.24

Формулы целевой функции и ограничений находятся соответственно в ячейке E10 и ячейках E4:E8 (каждый клиент обслуживается по каждому маршруту только один раз в день) (см. рис. 3.24 и 3.25). Вид электронной таблицы в режиме отображения формул представлен на рис. 3.25.

Рис. 3.25

Запись условий задачи в окне "Поиск решения" можно увидеть на рис. 3.26.

Результаты поиска решения приведены на рис. 3.24.

Рис. 3.26

Порядок выполнения работы

1. Изучить теоретическую часть.

2. Решить задачу (по вариантам) средствами Excel.