Задача 2. Фирма «Форсаж», занимающаяся организацией и осуществлением экспедирования и перевозок экспортных, импортных и транзитных грузов

Фирма «Форсаж», занимающаяся организацией и осуществлением экспедирования и перевозок экспортных, импортных и транзитных грузов, заключила контракт на доставку Q т цемента от Новороссийского цементного завода (Краснодарский край) до Олимпийского центра в Сочи.

Сеть железных и автомобильных дорог в регионе, схема расположения автотранспортных предприятий, портов, перевалочных пунктов и распределительного центра получателя, представлена на рисунке. Числами на схеме указаны расстояния между объектами, выраженные в километрах.

Рис. 2. Маршрутная карта, расстояния обозначены в км.

Транспортировка может осуществляться по нескольким схемам:

1 и 2 схемы: Автомобильным транспортом из Новороссийска до Сочи. В данном случае необходимо учесть тот факт, что собственного автомобильного транспорта цементный завод не имеет, следовательно, необходимо обращаться к автотранспортным предприятиям, расположенным в Анапе или в Крымске.

3 схема: Железнодорожным транспортом от Новороссийска, через Адыгейск, Горячий ключ и Туапсе до Сочи. Причем Новороссийский цементный завод имеет собственный железнодорожный транспорт.

4, 5 и 6 схемы: Морским транспортом от Новороссийска до Сочи, вдоль береговой линии. При выборе данного варианта транспортировки цемента возможно воспользоваться услугами как НМТП(Новороссийского морского торгового порта), так и обратиться в ближайшие порты для аренды морских судов (Анапа). Также выбор морского транспорта обязывает доставить партию цемента в порт под погрузку ж/д транспортом цементного завода, расходы на данную перевозку по городу берет на себя завод и при расчетах ею можно пренебречь.

Для обеспечения этих поставок фирма «Форсаж» заключает контракты с автотранспортными предприятиями на перевозку и с цементным заводом на перевалку и хранение цемента. В регионе имеются два транспортных предприятия, отвечающих требованиям, предъявляемым к автомобильным перевозчикам: первое – в г.Анапа, второе – в г.Крымске.

Необходимо выбрать оптимальную схему транспортировки нефтепродуктов, используя в качестве критерия минимум полных затрат. Возможные варианты схем транспортировки приведены в табл.5.

Таблица 5

Варианты схем транспортировки цемента

Показатель	Схема 1	Схема 2	Схема 3	Схема 4	Схема 5	Схема 6
Перевалка	Новороссийский цементный завод	Новороссийский цементный завод	Новороссийский цементный завод	Новороссийский цементный завод	Новороссийский цементный завод	Новороссийский цементный завод
Перевозчик	Анапское АТП	Крымское АТП	Железнодорож-ный транспорт Новороссийск	Морской транспорт Новороссийск	Морской транспорт Анапа	Морской транспорт Геленджик
Маршрут	Новороссийск– Туапсе– Сочи.	Новороссийск– Туапсе– Сочи.	Новороссийск– Адыгейск – Туапсе– Сочи.	Новороссийск– Туапсе– Сочи. (вдоль береговой линии)	Новороссийск– Туапсе– Сочи. (вдоль береговой линии)	Новороссийск– Туапсе– Сочи. (вдоль береговой линии)

Также известны тариф за подачу транспорта к месту погрузки T_подачи для всех видов транспорта, тарифная стоимость перевалки T_{перевалки}, тарифы за транспортировку T_{трансп.} и грузоподъёмность транспортных средств.

Исходные данные по вариантам:

Таблица 6

Показатель	Вариант №1	Вариант №2	Вариант №3	Вариант №4	Вариант №5	Вариант №6
Варианты схем транспортировки	1,2,3,4	1,3,5,6	1,2,3,5	3,4,5,6	1,3,4,5	2,3,4,6
Q, тыс.т
Tподачи, у.е./км	Автомобильный транспорт	0,45	0,5	0,26	0,32	0,44	0,39
Морской транспорт	0,7	0,69	0,72	0,8		0,85
Tперевалки, у.е./т.			7,7		8,2	8,5
Tтрансп., у.е./ткм	Анапское АТП		1,8
Крымское АТП	1,9	1,5
Железнодорожный транспорт	0,8	0,9
Морской транспорт: Новороссийск	1,3	1,5
Морской транспорт: Анапа	1,4	1,7
Морской транспорт: Геленджик	1,9	1,2
q, т	Автомобильный транспорт
Железнодорожный транспорт
Морской транспорт	7 000

РАЗРАБОТКА МАРШРУТОВ ДОСТАВКИ ТОВАРОВ АВТОТРАНСПОРТОМ. Задача коммивояжера*

Компания – поставщик «Текстиль Импорт» занимается поставкой тканей из Европы. В исследуемом районе находится пять магазинов, приобретающих продукцию компании «Текстиль Импорт». Необходимо разработать маршрут таким образом, чтобы сэкономить затраты времени и снизить протяженность полученного пути. Расположение потребителей представлено на рисунке 3.

Рис. 3. Расстояние между магазинами – потребителями, км.

Методические рекомендации:

Исходной информацией для решения задачи являются условные схемы размещения пунктов, которые должны быть включены в маршрут, и матрица расстояний C = (c_ij) между этими пунктами, (табл. 7) в километрах.

Таблица 7

Магазины - потребители	Магазины - потребители
А	Б	В	Г	Д
А	-
Б		-
В			-
Г				-
Д					-

Алгоритм решения состоит из нескольких этапов.

Этап 1. Исходную матрицу (табл. 7) необходимо заполнить таким образом, чтобы матрица стала симметричной по отношению к главной диагонали (табл.8).

Таблица 8

Магазины – потребители (пункт отправления) i	Магазины – потребители (пункт назначения) j	min
А	Б	В	Г	Д
А	-
Б		-
В			-
Г				-
Д					-

Этап 2. Получение приведенной матрицы, т.е. такой матрицы, которая имеет хотя бы один нулевой элемент. Для получения приведенной матрицы в каждой строке необходимо найти минимальный элемент и выписать его с правой стороны матрицы. Это вектор-столбец вида (6,10,12,6,10) (табл.8). Из элементов соответствующей строки вычитаем минимальное значение элемента этой строки и получаем приведенную матрицу по строкам (табл. 9).

Таблица 9

Магазины – потребители (пункт отправления) i	Магазины – потребители (пункт назначения) j
А	Б	В	Г	Д
А	-
Б		-
В			-
Г				-
Д					-
min

Затем в каждом столбце находится минимальный элемент и записывается внизу матрицы. Это вектор-строка вида (0, 1, 5, 0, 1) (табл. 9). Из элементов соответствующего столбца вычитается минимальное значение элемента этого столбца и получают приведенную матрицу (табл.10). Математически доказано, что сделанные описанным способом процедуры получения приведенной матрицы (табл. 10) сохраняют свойства исходной матрицы.

Элемент приведенной матрицы c_ij называется полюсом, если c_ij = 0.

Таблица 10

Магазины – потребители (пункт отправления) i	Магазины – потребители (пункт назначения) j
А	Б	В	Г	Д
А
Б
В
Г
Д

Этап 3. Последовательно для каждого полюса нужно выполнить следующее:

· для строки i₀, где находится полюс, находим минимальный элемент этой строки, исключая значение только для самого этого полюса:

· для столбца j₀, где находится полюс, находим минимальный элемент этого столбца, исключая значение только для самого этого полюса.

Находим значение параметра d(i₀, j₀) по формуле:

d(i₀, j₀) = min (c_i0j) + min(c_ij0 )

Имеем:

d₁₄ = 3 + 0 = 3,

d₂₁ = 0 + 0 = 0,

d₂₃ = 0 + 1 = 1,

d₂₅ = 0 + 3 = 3,

d₃₄ = 2 + 0 = 2,

d₄₁ = 1 + 0 = 1,

d₅₁ = 0 + 0 = 0,

d₅₂ = 0 + 2 = 2.

Этап 4. Находим параметр h(i₀,j₀) по формуле:

h(i₀,j₀) = max (d(i₀, j₀))

Если таких значений будет несколько, можно выбрать любое. Выбранный параметр h(i₀,j₀) показывает направление движения: нужно двигаться из пункта i₀ в пункт j₀. Чтобы не было возврата, делаем запрет, полагая c(j₀,i₀) = ∞.

В исследуемом примере – это h₁₄ = 3 и h₂₅ = 3.

Возьмем первый случай: h_14. Так как i₀ = 1, а j₀ = 4, то будем двигаться из пункта 1 в пункт 4 (рис. 4). В этом случае запрет будет иметь вид с₄₁=∞.

Этап 5. Вычеркиваем строку i₀ и столбец j₀, сохраняя номера строк и столбцов матрицы неизменными. Для нашего примера это будет матрица табл.11.

Таблица 11

i	j
А	Б	В	Д
Б
В
Г	∞
Д

Этап 6. Если после вычеркивания в полученной матрице нет ни одного полюса, то необходимо создать полюсы, применяя процедуры, описанные для этапа 2. Получив приведенную матрицу, в которой имеются полюсы, переходим к этапу 3.

Если после вычеркивания получаем матрицу (2Х2), то эту матрицу будем называть тривиальной, так как она позволяет однозначно достроить маршрут до кольцевого маршрута и получить решение задачи.

Рассмотрим последовательность действий для нашего примера.

Так как в табл.11 имеются полюсы, то для каждого полюса находим d-параметры:

d₂₁= 0 + 0 = 0

d₂₃= 0 + 1 = 1

d₂₅= 0 + 8 = 8

d₅₁= 0 + 0 = 0

d₅₂= 0 + 2 = 2

Находим h-параметр. Получим: h(i₀,j₀) = d₂₅ = 8

Вычеркиваются строка i₀ = 2 и столбец j₀ = 5 и полагаем элемент c₅₂=∞. Проводим стрелку от пункта 2 к пункту 5, согласно процедуре этапа 4 (рис. 5).

После этого составляется новая матрица (табл. 12).

Таблица 12

I	J
А	Б	В
В
Г	∞
Д		∞

Так как в табл. 11 имеются полюсы, снова рассчитываем d- и h-параметры. Получим: d₅₁ = 2 + 11 = 13

Находим h-параметр. Получим: h(i₀,j₀) = d₅₁ = 13

Организуем перевозку из пункта 5 в пункт 1(рис.6). Чтобы избежать зацикливания 2-5-1-4-2, полагаем с₄₂=∞. Вычеркивается строка i₀ = 5 и столбец j₀ = 1. Чтобы избежать зацикливания, полагаем с₁₅=∞. (в нашем случае этот элемент отсутствует) Получаем матрицу табл. 13.

Таблица 13

I	J
Б	В
В
Г	∞

Получена тривиальная матрица (2х2). По значениям этой матрицы строим две связи: 4 – 3 (т. к. по табл.13 «расстояние» между этими пунктами самое короткое) и 3 – 2, чтобы получить замкнутый циклический маршрут (см. рис. 7 и 8 соответственно).

Протяженность кольцевого маршрута составляет 28 км. Это можно проверить по исходным данным табл. 5, обходя по контуру маршрута, начиная с пункта 1:

Маршрут L:1-4-3-2-5-1

L=6+12+15+11+10=54 (км).

Рис 4.	Рис 5.	Рис 6.
Рис 7.	Рис 8.

Варианты заданий для самостоятельной работы:

Задача 3*

Компания «Капелька» является поставщиком бытовой химии. В исследуемом районе находится пять магазинов, приобретающих продукцию компании «Капелька». Необходимо разработать маршрут коммивояжера таким образом, чтобы сэкономить затраты времени и снизить протяженность полученного пути. Расположение потребителей по вариантам представлено на рисунках, с указанием расстояния между ними в километрах.

Вариант 1	Вариант 2	Вариант 3