Определение локальных стоимостей перевозок

Задача заключается в определении стоимости перевозки 1 м³ песка на расстояние, соответствующее длине каждого ребра.

Стоимость транспортировки 1 м³ песка на 1997 год в долларах США определяется по формуле:

Сij = (С(l) * 1, 02 * 1, 57 * 7500*r) / 6000;                                             (2)

где С(l) — тарифная плата за перевозку 1 т песка на 1 км., руб. Она является переменной величиной и зависит от расстояния Lij (таблица 2);

r — плотность песка (1.6 т/м³).

Прочие сомножители являются поправочными коэффициентами, которые учитывают изменение величины тарифной платы вследствие инфляции и влияния рыночных факторов.

Таблица 3 Тарифная плата за перевозку 1 т. груза

 

Расстояние, км	Тарифная плата за перевозку 1 т. груза 1-го км, руб на 1984 год	Расстояние, км	Тарифная плата за перевозку 1 т. груза 1-го км, руб на 1984 год
1	0, 25	16	1
2	0, 30	17	1, 04
3	0, 35	18	1, 08
4	0, 40	19	1, 12
5	0, 45	20	1, 16
6	0, 50	21-25	1, 28
7	0, 55	26-30	1, 48
8	0, 60	31-35	1, 68
9	0, 65	36-40	1, 88
10	0, 70	41-45	2, 06
11	0, 75	46-50	2, 21
12	0, 80	51-60	2, 44
13	0, 85	61-70	2, 72
14	0, 90	71-80	2, 92
15	0, 95	81-90	3, 12
Свыше - за 1 км+ 3, 4 коп		91-100	3, 32

 

Рассчитываем стоимость перевозок исходя из расстояний, указанных на ребрах транспортной сети:

Таблица 4. Локальные стоимости перевозок.

 

Ребро (ЕiЕj)	Расстояние, км	Стоимость перевозки, долл/м3
Е1-Е9	15	3, 04
Е9-Е10	15	3, 04
Е9-Е11	10	2, 24
Е2-Е5	11	2, 40
Е5-Е6	6	1, 60
Е6-Е10	20	3, 71
Е6-Е9	13	2, 72
Е9-Е11	10	2, 24
Е3-Е4	14	2, 88
Е4-Е8	12	2, 56
Е8-Е9	19	3, 59
Е9-Е10	15	3, 04
Е4-Е11	11	2, 40

 

Определение кратчайшего расстояния в транспортной сети

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

Задача решается составлением минимального дерева-остова.

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

Расчет кратчайшего пути производится по формуле:

Uj=(Ui+Lij),

где Uj - кратчайшее расстояние до текущего пункта j, км;

Ui - кратчайшее расстояние до предыдущего пункта i, км;

Lij - расстояние между i и j пунктами, км.

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

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

 

Таблица 5. Кратчайшие маршруты в транспортной сети

Маршрут	Промежуточные пункты	Стоимость перевозки 1м3 песка по маршруту, тыс. руб.	Длина мар-шрута, км
Е1Е10	Е1-Е 9 -Е 10	4, 74	30
Е1Е11	Е1-Е9-Е11	4, 09	25
Е2Е10	Е2-Е5-Е6-Е10	6, 02	37
Е2Е11	Е2-Е5-Е6-Е9-Е11	6, 02	40
Е3Е10	Е3-Е4-Е8-Е9-Е10	7, 81	60
Е3Е11	Е3-Е4-Е11	4, 09	25

 

 

Схема 2.Графическое изображение найденных кратчайших путей в сети

 

2.3. Решение задачи прикрепления пунктов производства к пунктам потребления (транспортная задача)

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

Исходные данные для решения транспортной задачи представляют собой матрицу. В клетках этой матрицы сверху указаны стоимости (Cij) перевозки 1 м³ груза из i-го пункта отправления в j-й пункт назначения, а в нижней части клеток будут показаны объёмы перевозок по этому маршруту (Xij).

Целевая функция транспортной задачи заключается в минимизации общей стоимости всех перевозок:

F =  ® min

Ход решения задачи:

1. Приводим исходную матрицу (вычитаем из Сij каждой строки минимальное значение Сij в этой строке; затем для столбцов, в которых нет ни одного нуля, из каждого Сij в столбце вычитаем минимальное Сij).

           

 

	-10709
	-10038
				-485		-615

 

 

2. Проводим первичное распределение потока ресурсов по клеткам с нулевой стоимостью и закрываем столбцы и строки.

 

 

3. Поскольку распределение оказалось неоптимальным, т.е. не все столбцы оказались закрытыми, проводим преобразование: выбираем минимальное Cij среди клеток, стоящих на пересечении открытых столбцов и открытых строк, и вычитаем это значение Cij из значений Cij открытых столбцов и прибавляем его к Cij закрытых строк. Перераспределяем поток

 

 

 

 

 

4. Распределение все еще не оптимально, но появилась цепочка, т.е. последовательность клеток с Cij, равным последовательно 0®0*®0’. Переносим 35 единиц потока вдоль цепочки. Перераспределяем поток, и получаем оптимальную матрицу.

 

 

Стоимость перевозок, соответствующая оптимальному плану, равна

C = 43000*6, 08 + 5000*5, 28 + 22000*7, 71 + 35000*5, 28 = 642260 долл..

Оптимальные объемы перевозок, полученные в результате решения транспортной задачи:

Е₁Е₁₀ = 43000 м³

Е₁Е₁₁ = 5000 м³

Е₂Е₁₀ = 22000 м³

Е₃Е₁₁ = 35000 м³

Схема 3. Маршруты перевозок песка от каждого карьера до каждого пункта назначения.

 

⇐ Предыдущая1234Следующая ⇒

Поделиться: