Таблица 1.3 - Расчёт кратчайших расстояний до пункта А3
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(?, А3) |
(?, А3) |
(0, ?)* |
(?, А3) |
(?, А3) |
(6, А3) |
(4,А3) |
(?,А3) |
(7,А3) |
(23,А3) |
|
|
2 |
(8,Б2) |
(22,Б2) |
(22,Б2) |
(?, А3) |
(6,А3) |
(4,А3)* |
(?,А3) |
(7,А3) |
(20,Б2) |
||
|
3 |
(8,Б2) |
(22,Б2) |
(22,Б2) |
(14,Б1) |
(6,А3)* |
(Б1,22) |
(7,А3) |
(20,Б2) |
|||
|
4 |
(8,Б2) |
(13,Б4) |
(22,Б2) |
(14,Б1) |
(Б1,22) |
(7,А3)* |
(20,Б2) |
||||
|
5 |
(8,Б2)* |
(13,Б4) |
(22,Б2) |
(14,Б1) |
(11,А1) |
(20,Б2) |
|||||
|
6 |
(13,Б4) |
(16,Б3) |
(14,Б1) |
(11,А1)* |
(20,Б2) |
||||||
|
7 |
(13,Б4)* |
(16,Б3) |
(14,Б1) |
(20,Б2) |
|||||||
|
8 |
(16,Б3) |
(14,Б1)* |
(20,Б2) |
||||||||
|
9 |
(16,Б3)* |
(20,Б2) |
|||||||||
|
10 |
(20,Б2)* |
Таблица 1.4 - Расчёт кратчайших расстояний до пункта А4
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(?,А4) |
(?, А4) |
(?, А4) |
(0, ?)* |
(?, А4) |
(14,А4) |
(14,А4) |
(5, А4) |
(28,А4) |
(22,А4) |
|
|
2 |
(8,Б3) |
(24,Б3) |
(?, А4) |
(?, А4) |
(14,А4) |
(14,А4) |
(5,А4)* |
(28,А4) |
(22,А4) |
||
|
3 |
(8,Б3)* |
(24,Б3) |
(?, А4) |
(?, А4) |
(18,А1) |
(12,А1) |
(28,А4) |
(22,А1) |
|||
|
4 |
(24,Б3) |
(16,Б2) |
(28,Б2) |
(16,Б2) |
(А1,12)* |
(28,А4) |
(22,А1) |
||||
|
5 |
(24,Б3) |
(16,Б2) |
(22,Б1) |
(16,Б2)* |
(28,А4) |
(22,А1) |
|||||
|
6 |
(24,Б3) |
(16,Б2)* |
(22,Б1) |
(23,А3) |
(22,А1) |
||||||
|
7 |
(24,Б3) |
(22,Б1) |
(23,А3) |
(22,А1)* |
|||||||
|
8 |
(29,Б4) |
(22,Б1) |
(23,А3)* |
||||||||
|
9 |
(29,Б4) |
(22,Б1)* |
|||||||||
|
10 |
(29,Б4)* |
Таблица 1.5 - Расчёт кратчайших расстояний до пункта А5
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(?, А5) |
(?, А5) |
(?, А5) |
(?, А5) |
(0, ?)* |
(8,А5) |
(16,А5) |
(?, А5) |
(10,А5) |
(?, А5) |
|
|
2 |
(18,Б1) |
(?, А5) |
(14,Б1) |
(22,Б1) |
(8,А5)* |
(12,Б1) |
(24,Б1) |
(10,А5) |
(?, А5) |
||
|
3 |
(18,Б1) |
(16,Б4) |
(14,Б1) |
(22,Б1) |
(12,Б1) |
(24,Б1) |
(10,А5)* |
(?, А5) |
|||
|
4 |
(16,Б2) |
(16,Б4) |
(14,Б1) |
(22,Б1) |
(12,Б1)* |
(24,Б1) |
(28,Б2) |
||||
|
5 |
(16,Б2) |
(16,Б4) |
(14,Б1)* |
(22,Б1) |
(24,Б1) |
(28,Б2) |
|||||
|
6 |
(16,Б2)* |
(16,Б4) |
(22,Б1) |
(19,А1) |
(28,Б2) |
||||||
|
7 |
(16,Б4)* |
(22,Б1) |
(19,А1) |
(28,Б2) |
|||||||
|
8 |
(22,Б1) |
(19,А1)* |
(28,Б2) |
||||||||
|
9 |
(22,Б1)* |
(28,Б2) |
|||||||||
|
10 |
(28,Б2)* |
Таблица 1.6 - Расчёт кратчайших расстояний до пункта Б1
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(10,Б1) |
(?, Б1) |
(6, Б1) |
(14,Б1) |
(8,Б1) |
(0, ?)* |
(4, Б1) |
(?, Б1) |
(?, Б1) |
(?, Б1) |
|
|
2 |
(8,Б2) |
(22,Б1) |
(6,Б1) |
(14,Б1) |
(8,Б1) |
(4,Б1)* |
(?, Б1) |
(?, Б1) |
(20,Б2) |
||
|
3 |
(8,Б2) |
(22,Б1) |
(6,Б1)* |
(14,Б1) |
(8,Б1) |
(?, Б1) |
(13,А3) |
(20,Б2) |
|||
|
4 |
(8,Б2)* |
(22,Б1) |
(14,Б1) |
(8,Б1) |
(11,А1) |
(13,А3) |
(20,Б2) |
||||
|
5 |
(22,Б1) |
(14,Б1) |
(8,Б1)* |
(11,А1) |
(13,А3) |
(20,Б2) |
|||||
|
6 |
(22,Б1) |
(14,Б1) |
(11,А1)* |
(13,А3) |
(20,Б2) |
||||||
|
7 |
(19,Б4) |
(14,Б1) |
(13,А3)* |
(20,Б2) |
|||||||
|
8 |
(19,Б4) |
(14,Б1)* |
(20,Б2) |
||||||||
|
9 |
(19,Б4)* |
(20,Б2) |
|||||||||
|
10 |
(20,Б2)* |
Таблица 1.7 - Расчёт кратчайших расстояний до пункта Б2
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(4,Б2) |
(18,Б2) |
(4, Б2) |
(14,Б2) |
(16,Б2) |
(4, Б2) |
(0, ?)* |
(?, Б2) |
(?, Б2) |
(16, Б2) |
|
|
2 |
(4,Б2)* |
(18,Б2) |
(4,Б2) |
(14,Б2) |
(16,Б2) |
(4, Б2) |
(7, А1) |
(?, Б2) |
(16, Б2) |
||
|
3 |
(18,Б2) |
(4,Б2)* |
(14,Б2) |
(16,Б2) |
(4, Б2) |
(7, А1) |
(11,А3) |
(16, Б2) |
|||
|
4 |
(18,Б2) |
(14,Б2) |
(12,Б1) |
(4,Б2)* |
(7, А1) |
(11,А3) |
(16, Б2) |
||||
|
5 |
(18,Б2) |
(12,Б3) |
(12,Б1) |
(7,А1)* |
(11,А3) |
(16, Б2) |
|||||
|
6 |
(18,Б2) |
(12,Б3) |
(12,Б1) |
(11,А3)* |
(16, Б2) |
||||||
|
7 |
(18,Б2) |
(12,Б3)* |
(12,Б1) |
(16, Б2) |
|||||||
|
8 |
(18,Б2) |
(12,Б1)* |
(16, Б2) |
||||||||
|
9 |
(18,Б2) |
(16,Б2)* |
|||||||||
|
10 |
(18,Б2)* |
Таблица 1.8 - Расчёт кратчайших расстояний до пункта Б3
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(3,Б3) |
(24,Б3) |
(?, Б3) |
(5, Б3) |
(?, Б3) |
(16,Б3) |
(?, Б3) |
(0, ?)* |
(?, Б3) |
(?, Б3) |
|
|
2 |
(3,Б3)* |
(24,Б3) |
(?, Б3) |
(5, Б3) |
(?, Б3) |
(13,А1) |
(7,А1) |
(?, Б3) |
(17,А1) |
||
|
3 |
(24,Б3) |
(?, Б3) |
(5,Б3)* |
(?, Б3) |
(13,А1) |
(7,А1) |
(33,А4) |
(17,А1) |
|||
|
4 |
(24,Б3) |
(11,Б2) |
(23,Б2) |
(11,Б2) |
(7,А1)* |
(23,А2) |
(17,А1) |
||||
|
5 |
(24,Б3) |
(11,Б2)* |
(23,Б2) |
(11,Б2) |
(33,А4) |
(17,А1) |
|||||
|
6 |
(24,Б3) |
(19,Б1) |
(11,Б2)* |
(18,А3) |
(17,А1) |
||||||
|
7 |
(24,Б3) |
(19,Б1) |
(18,А3) |
(17,А1)* |
|||||||
|
8 |
(24,Б3) |
(19,Б1) |
(18,А3)* |
||||||||
|
9 |
(24,Б3) |
(19,Б1)* |
|||||||||
|
10 |
(24,Б3)* |
Таблица 1.9 - Расчёт кратчайших расстояний до пункта Б4
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(?,Б4) |
(6,Б4) |
(7,Б4) |
(28,Б4) |
(10,Б4) |
(?,Б4) |
(?,Б4) |
(?,Б4) |
(0, ?)* |
(?,Б4) |
|
|
2 |
(?,Б4) |
(6,Б4)* |
(7,Б4) |
(28,Б4) |
(10,Б4) |
(?,Б4) |
(24,А2) |
(30,А2) |
(20,А2) |
||
|
3 |
(?,Б4) |
(7,Б4)* |
(28,Б4) |
(10,Б4) |
(13,А3) |
(11,А3) |
(30,А2) |
(20,А2) |
|||
|
4 |
(?,Б4) |
(28,Б4) |
(10,Б4)* |
(13,А3) |
(11,А3) |
(30,А2) |
(20,А2) |
||||
|
5 |
(15,Б2) |
(25,Б2) |
(13,А3) |
(11,А3)* |
(30,А2) |
(20,А2) |
|||||
|
6 |
(15,Б2) |
(25,Б2) |
(13,А3)* |
(29,Б1) |
(20,А2) |
||||||
|
7 |
(15,Б2)* |
(25,Б2) |
(18,А1) |
(20,А2) |
|||||||
|
8 |
(23,Б3) |
(18,А1)* |
(20,А2) |
||||||||
|
9 |
(23,Б3) |
(20,А2)* |
|||||||||
|
10 |
(23,Б3)* |
Таблица 1.10 - Расчёт кратчайших расстояний до пункта Б5
|
№ шага |
Пункты транспортной сети |
||||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
||
|
1 |
(14,Б5) |
(14,Б5) |
(23,Б5) |
(22,Б5) |
(?,Б5) |
(?, Б5) |
(16,Б5) |
(?,Б5) |
(?, Б5) |
(0, ?)* |
|
|
2 |
(14,Б5)* |
(14,Б5) |
(23,Б5) |
(22,Б5) |
(?,Б5) |
(24,А1) |
(18,А1) |
(17,А1) |
(?, Б5) |
||
|
3 |
(14,Б5)* |
(23,Б5) |
(22,Б5) |
(?,Б5) |
(24,А1) |
(18,А1) |
(17,А1) |
(20,А2) |
|||
|
4 |
(23,Б5) |
(22,Б3) |
(?,Б5) |
(24,А1) |
(18,А1) |
(17,А1)* |
(20,А2) |
||||
|
5 |
(22,Б2) |
(22,Б3) |
(?,Б5) |
(24,А1) |
(18,А1)* |
(20,А2) |
|||||
|
6 |
(22,Б2) |
(22,Б3) |
(30,Б4) |
(24,А1) |
(20,А2)* |
||||||
|
7 |
(22,Б2)* |
(22,Б3) |
(30,Б4) |
(24,А1) |
|||||||
|
8 |
(22,Б3)* |
(30,Б4) |
(24,А1) |
||||||||
|
9 |
(30,Б4) |
(24,А1)* |
|||||||||
|
10 |
(30,Б4)* |
1.2 Построение модели транспортной задачи для заданного варианта перевозок
Задача на минимизацию транспортной работы состоит в определении оптимального варианта закрепления потребителей за поставщиками однородной продукции.
Если обозначить объем выхода груза от некоторого поставщика через Qi, требуемый объём завоза груза некоторому потребителю через Qj, объём груза, перевозимого от i-го поставщика к j-му потребителю, через Qij и кратчайшее расстояние перевозки от i-го поставщика до j-го потребителя через lij, то математическая модель поставленной задачи имеет вид:
(1.3)
(1.4)
(1.5)
(1.6)
В случае, если количество груза у поставщиков равно общему объему завоза груза всем потребителям, то имеет место условие:
(1.7)
Поставленная таким образом задача (целевая функция (1.3) и ограничения (1.4) - (1.7)) является закрытой моделью классической транспортной задачи линейного программирования, в результате решения которой по известным значениям Qi, Qj и lij находятся неизвестные значения объёмов перевозок между i-м поставщиком и j-м потребителей Qij.
Для составления транспортной задачи из исходных данных (вариант № 22) выбираются грузы, перевозимые одним типом подвижного состава.
Перечень этих грузов представлен в таблице 1.12.
Таковыми являются рельсы, овощи, метизы, шифер, шифер, проволока и фрукты.
Таблица 1.12 - Грузы, перевозимые одним типом подвижного состава
|
Грузопотоки |
Род груза |
Объем перевозок, т |
Класс груза |
Вид упаковки |
||
|
из пункта |
в пункт |
|||||
|
А1 |
Б1 |
рельсы |
500 |
1 |
Пакет |
|
|
Б1 |
А1 |
овощи |
200 |
2 |
Ящик |
|
|
А2 |
Б2 |
метизы |
1000 |
1 |
Пакет |
|
|
Б2 |
А2 |
шифер |
200 |
1 |
Пакет |
|
|
А2 |
Б2 |
кирпич |
200 |
1 |
Пакет |
|
|
А3 |
Б2 |
проволока |
250 |
1 |
Пакет |
|
|
А2 |
Б3 |
фрукты |
200 |
2 |
Пакет |