Выбор подвижного состава для организации перевозки

Таблица 9 – Опорный план

	1	2	3	4	Запасы
1	10 270	24	23 52	29	322
2	20	14 300	23	11 17	317
3	12	15 220	25 178	19	398
4	20	23	33	22 278	278
Потребности	270	520	230	295

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, которые удовлетворяют условию (2).

u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10

u₁ + v₃ = 23; 0 + v₃ = 23; v₃ = 23

u₃ + v₃ = 25; 23 + u₃ = 25; u₃ = 2

u₃ + v₂ = 15; 2 + v₂ = 15; v₂ = 13

u₂ + v₂ = 14; 13 + u₂ = 14; u₂ = 1

u₂ + v₄ = 11; 1 + v₄ = 11; v₄ = 10

u₄ + v₄ = 22; 10 + u₄ = 22; u₄ = 12

 

Таблица 10 – Расчет потенциалов    

	v1=10	v2=13	v3=23	v4=10
u1=0	10 270	24	23 52	29
u2=1	20	14 300	23	11 17
u3=2	12	15 220	25 178	19
u4=12	20	23	33	22 278

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых u_i + v_i > c_ij

 

∆₁₂ = 13 + 0 – 24 = – 11

∆₁₄ = 10 + 0 – 29 = – 19

∆₂₁ = 10 + 1 – 20 = – 9 

∆₂₃ = 23 + 1 – 23 = 1 

∆₃₁ = 10 + 2 –12 = 0

∆₃₄ = 10 + 2 –19 = – 7

∆₄₁ = 10 + 12 – 20 = 2 

∆₄₂ = 13 + 12 – 23 = 2 

∆₄₃ = 23 + 12 –33 = 2  

max(1,2,2,2) = 2

 

Выбираем максимальную оценку свободной клетки (4;1): 20

Для этого в перспективную  клетку (4;1) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

Таблица 11 – Определение контуров пересчета   

	1	2	3	4	Запасы
1	10 270[-]	24	23 52 [+]	29	322
2	20	14 300[-]	23	11 17 [+]	317
3	12	15 220 [+]	25 178 [-]	19	398
4	20 [+]	23	33	22 278 [-]	278
Потребности	270	520	230	295

 

270

-

52

+

17

+

300

-

 
 
 

220

+

178

-

 

+

278

-

 

 

Рисунок 4 – Контур перераспределения

 

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е.

 

 

 

 Прибавляем 178 к объемам  грузов, стоящих в плюсовых клетках  и вычитаем 178 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

Таблица 12 – Опорный план    

	1	2	3	4	Запасы
1	10 92	24	23 230	29	322
2	20	14 122	23	11 195	317
3	12	15 398	25	19	398
4	20 178	23	33	22 100	278
Потребности	270	520	230	295

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, которые удовлетворяют условию (2).

 

u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10

u₄ + v₁ = 20; 10 + u₄ = 20; u₄ = 10

u₄ + v₄ = 22; 10 + v₄ = 22; v₄ = 12

u₂ + v₄ = 11; 12 + u₂ = 11; u₂ = -1

u₂ + v₂ = 14; -1 + v₂ = 14; v₂ = 15

u₃ + v₂ = 15; 15 + u₃ = 15; u₃ = 0

u₁ + v₃ = 23; 0 + v₃ = 23; v₃ = 23

 

Таблица 13 – Расчет потенциалов    

	v1=10	v2=15	v3=23	v4=12
u1=0	10 92	24	23 230	29
u2=-1	20	14 122	23	11 195
u3=0	12	15 398	25	19
u4=10	20 178	23	33	22 100

 

Опорный план не является оптимальным, так как существуют оценки свободных  клеток, для которых u_i + v_i > c_ij

∆₁₂ = 15 + 0 – 24 = – 9

∆₁₄ = 12 + 0 – 29 = – 17

∆₂₁ = 10 – 1 – 20 = – 10 

∆₂₃ = 23 – 1 – 23 = – 1

∆₃₁ = 10 + 0 –12 = – 2

∆₃₃ = 12 + 0 – 25 = – 13 

∆₃₄ = 0 + 12 – 19 = – 7 

∆₄₂ = 15 + 10 –23 = 2 

∆₄₃ = 23 + 10 –33 = 0  

Выбираем максимальную оценку свободной клетки (4;2): 23

Для этого в перспективную  клетку (4;2) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

Таблица 14 – Определение контуров пересчета    

	1	2	3	4	Запасы
1	10 92	24	23 230	29	322
2	20	14 122 [-]	23	11 195 [+]	317
3	12	15 398	25	19	398
4	20 178	23 [+]	33	22 100 [-]	278
Потребности	270	520	230	295

 

195

+

122

-

100

-

23

+

 
 
 
 

 

Рисунок 5 – Контур перераспределения

 

 

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е.

 

 

 

Прибавляем 100 к объемам  грузов, стоящих в плюсовых клетках  и вычитаем 100 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

 

Таблица 15 – Опорный план    

	1	2	3	4	Запасы
1	10 92	24	23 230	29	322
2	20	14 22	23	11 295	317
3	12	15 398	25	19	398
4	20 178	23 100	33	22	278
Потребности	270	520	230	295

 

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, которые удовлетворяют условию (2).

u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10

u₄ + v₁ = 20; 10 + u₄ = 20; u₄ = 10

u₄ + v₂ = 23; 10 + v₂ = 23; v₂ = 13

u₂ + v₂ = 14; 13 + u₂ = 14; u₂ = 1

u₂ + v₄ = 11; 1 + v₄ = 11; v₄ = 10

u₃ + v₂ = 15; 13 + u₃ = 15; u₃ = 2

u₁ + v₃ = 23; 0 + v₃ = 23; v₃ = 23

 

Таблица 16 – Расчет потенциалов    

	v1=10	v2=13	v3=23	v4=10
u1=0	10 92	24	23 230	29
u2=1	20	14 22	23	11 295
u3=2	12	15 398	25	19
u4=10	20 178	23 100	33	22

 

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых  u_i + v_i > c_ij

 

∆₁₂ = 13 + 0 – 24 = – 11

∆₁₄ = 10 + 0 – 29 = – 19

∆₂₁ = 10 + 1 – 20 = – 9 

∆₂₃ = 23 + 1 – 23 = 1 

∆₃₁ = 10 + 2 –12 = 0

∆₃₃ = 13 + 2 – 25 = – 10 

∆₃₄ = 10 + 2 – 19 = – 7 

∆₄₃ = 23 + 10 – 33 = 0 

∆₄₃ = 10 + 10 – 22 = – 2  

 

Выбираем максимальную оценку свободной клетки (2;3): 23

Для этого в перспективную  клетку (2;3) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

Таблица 17 – Определение контуров пересчета    

	1	2	3	4	Запасы
1	10 92 [+]	24	23 230 [-]	29	322
2	20	14 22 [-]	23 [+]	11 295	317
3	12	15 398	25	19	398
4	20 178 [-]	23 100 [+]	33	22	278
Потребности	270	520	230	295

 

230

-

92

+

22

-

+

 
 
 
 

178

-

100

+

 

 

Рисунок 6 -  Контур перераспределения

 
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е.

 

 

 

Прибавляем 22 к объемам  грузов, стоящих в плюсовых клетках  и вычитаем 22 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

Таблица 18 – Опорный план    

	1	2	3	4	Запасы
1	10 114	24	23 208	29	322
2	20	14	23 22	11 295	317
3	12	15 398	25	19	398
4	20 156	23 122	33	22	278
Потребности	270	520	230	295

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10

u₄ + v₁ = 20; 10 + u₄ = 20; u₄ = 10

u₄ + v₂ = 23; 10 + v₂ = 23; v₂ = 13

u₃ + v₂ = 15; 13 + u₃ = 15; u₃ = 2

u₁ + v₃ = 23; 0 + v₃ = 23; v₃ = 23

u₂ + v₃ = 23; 23 + u₂ = 23; u₂ = 0

u₂ + v₄ = 11; 0 + v₄ = 11; v₄ = 11

 

Таблица 19 – Расчет потенциалов    

	v1=10	v2=13	v3=23	v4=11
u1=0	10 114	24	23 208	29
u2=0	20	14	23 22	11 295
u3=2	12	15 398	25	19
u4=10	20 156	23 122	33	22

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию (2).

Посчитаем грузооборот:

 

 

 

При нахождении опорного плана методом северо-западного  угла, полученный план не всегда является оптимальным, поэтому дальнейшим этапом решения является перемещение груза  по строкам из клеток с большим  расстоянием в клетки с меньшим  расстоянием. Для дальнейшей оптимизации  матрицы допустимого плана перевозок  используем метод аппроксимации  Фогеля. При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными расстояниями. Как правило, применение данного метода позволяет получить оптимальный план (табл. 20).

Аппроксимация Фогеля    Таблица 20  

Пункты  отправления	Пункты  назначения				Запасы Qа , тыс.т	Разности  по строкам
	В1	В2	В3	В4
А1	10 270	24	23 52	29	322	13	1	1	1	0
А3	20	14	23 22	11 295	317	3	3	9	9	0
А8	12	15 242	25 156	19	398	3	4	10	10	0
А10	20	23 278	33	22	278	2	1	10	-	-
Потребности Qн , тыс. т	270	520	230	295
Разности  по столбцам	2	1	2	8
	-	1	2	8
	-	1	2	-
	-	1	2	-
	-	-	2	-