Транспортная задача распределительным методом

 

Цикл приведен в таблице (2,1; 2,4; 3,4; 3,2; 5,2; 5,1; ). 

Оценка свободной клетки равна Δ21 = (5) - (3) + (4) - (5) + (0) - (0) = 1 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4[+]	4	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4[10]	2[80]	4	90
5	0[110]	0[10]	0	0	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (2,2; 2,4; 3,4; 3,2; ). 

Оценка свободной клетки равна Δ22 = (4) - (3) + (4) - (5) = 0 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4[+]	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4[10][+]	2[80][-]	4	90
5	0[110]	0[10]	0	0	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (2,3; 2,4; 3,4; 3,2; 4,2; 4,3; ). 

Оценка свободной клетки равна Δ23 = (4) - (3) + (4) - (5) + (4) - (2) = 2 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6[+]	5[110][-]	6	4[15]	125
4	8	4[10]	2[80]	4	90
5	0[110][-]	0[10][+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (3,1; 3,2; 5,2; 5,1; ). 

Оценка свободной клетки равна Δ31 = (6) - (5) + (0) - (0) = 1 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110][-]	6[+]	4[15]	125
4	8	4[10][+]	2[80][-]	4	90
5	0[110]	0[10]	0	0	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (3,3; 3,2; 4,2; 4,3; ). 

Оценка свободной клетки равна Δ33 = (6) - (5) + (4) - (2) = 3 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8[+]	4[10][-]	2[80]	4	90
5	0[110][-]	0[10][+]	0	0	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (4,1; 4,2; 5,2; 5,1; ). 

Оценка свободной клетки равна Δ41 = (8) - (4) + (0) - (0) = 4 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4[10][-]	2[80]	4[+]	90
5	0[110]	0[10]	0	0	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (4,4; 4,2; 3,2; 3,4; ). 

Оценка свободной клетки равна Δ44 = (4) - (4) + (5) - (4) = 1 

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

 

 

 

 

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4[10][+]	2[80][-]	4	90
5	0[110]	0[10][-]	0[+]	0	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (5,3; 5,2; 4,2; 4,3; ). 

Оценка свободной клетки равна Δ53 = (0) - (0) + (4) - (2) = 2 

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

	1	2	3	4	Запасы
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4[10]	2[80]	4	90
5	0[110]	0[10][-]	0	0[+]	120
Потребности	110	130	160	120

 

Цикл приведен в таблице (5,4; 5,2; 3,2; 3,4; ). 

Оценка свободной клетки равна Δ54 = (0) - (0) + (5) - (4) = 1 

Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения. 

Таким образом, последний опорный план является оптимальным. 

Минимальные затраты составят: 

F(x) = 3*80 + 3*105 + 5*110 + 4*15 + 4*10 + 2*80 + 0*110 + 0*10  = 1365 

Если в оптимальном решении задачи имеется несколько оценок равных нулю, то это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым — минимальным. Их принято называть альтернативными. 

Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп—(m+n—1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 — 361 цикл. 
ЗАКЛЮЧЕНИЕ

 

 

Таким образом, в настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Одним из распространенных методом решения транспортных задач является распределительный метод.

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

Решение задачи распределительным методом производиться поэтапно:

• разработка начального плана (опорного решения);
• расчет потенциалов;
• проверка плана на оптимальность;
• поиск максимального звена неоптимальности;
• составление контура перераспределения ресурсов;
• определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;
• получение нового плана.