Составление оптимальных маятниковых маршрутов

Схема маятникового маршрута с указанием расстояний (в км) приведена на рис.8.

6 13 7,5

8 15

Рис. 8. Схема маятникового маршрута

Здесь Г – автохозяйство;

А – склад продукции;

Б₁, Б₂ – потребители продукции.

Предположим, что в каждый из пунктов Б₁ и Б₂ необходимо совершить 2 поездки, чтобы доставить грузы со склада А.

При выполнении маятниковых маршрутов с обратным пробегом без груза возникает несколько вариантов движения автомобилей:

1) Продукция поставляется в Б₂, а затем в Б₁ и из Б₁ автомобиль возвращается в автохозяйство Г.

2) Продукция поставляется в Б₁, а затем в Б₂ и из Б₂ автомобиль возвращается в автохозяйство Г.

В любом варианте автомобилю придется совершить по 2 поездки с грузом как в пункт Б₁, так и в пункт Б₂, т. е. проехать с грузом км.

Также в любом варианте автомобилю придется ехать из Г в А (13 км).

Поэтому необходимо разработать такой маршрут, при котором порожний пробег был бы минимальным.

В варианте 1 нам придется проехать из Б₁ в пункт Г (расстояние l(Б₁;Г)), однако не надо 2-ой раз возвращаться в А (расстояние l(А;Б₁)).

В варианте 2 нам придется проехать из Б₂ в пункт Г (расстояние l(Б₂;Г)), однако не надо 2-ой раз возвращаться в А (расстояние l(А;Б₂)).

В общем случае при нескольких пунктах Б_j (j=1,…,n), заканчивая работу в пункте Б_j мы вынуждены дополнительно проехать расстояние l(Б_j;Г), но сокращаем расстояние l(А;Б_j).

Поэтому наилучшее решение получается при такой системе маршрутов, когда автомобиль заканчивает работу в пункте Б_j, для которого величина l(Б_j;Г) - l(А;Б_j) минимальна.

Для решения задачи удобно исходные данные записать в таблицу

Последний пункт назначения	l(Бj;Г)	l(А;Бj)	l(Бj;Г) - l(А;Бj)
Б1
Б2
………
Бn

Рассмотрим применение предложенного алгоритма на конкретном примере, приведенном на рис. 8.

Последний пункт назначения (Бj)	l(Бj;Г)	l(А;Бj)	l(Бj;Г) - l(А;Бj)
Б1			-2
Б2	7,5		-7,5

Минимальное значение l(Б_j;Г) - l(А;Б_j) имеет место для пункта Б₂ (-7,5), который принимается конечным пунктом составляемых маршрутов.

Задание 8.

Составить оптимальный маятниковый маршрут (найти конечный пункт) по данным таблицы по вариантам