1) Исходные данные задачи записываются в таблицу, отличающуюся от формы таблицы предыдущего способа тем, что она имеет дополнительную строку и столбец разностей.
2) Рассматривается расстояние по столбцам. Определяются 2 наименьших расстояния и разница между ними записывается в строку разностей, а разницу между двумя наименьшими расстояниями по строкам записывается в столбец разностей.
3) Из всех разниц, полученных по строкам и столбцам выбираем наибольшую. Клетка с наименьшим расстоянием (при решении задач на минимум) расположенная в строке или столбце, имеющем наибольшую разницу, загружается максимальным количеством груза. Если окажется несколько одинаковых разниц, имеющих наибольшее значение, то в соответствующих им строках и столбцах загружают седловую точку. Седловой точкой называют клетку, расстояние которой имеет наименьшее значение (при решении задач на минимум) из всех расстояний ее строки и столбца при наличии независимых седловых точек, т. е. расположенных в разных строках и столбцах таблицы их загружают одновременно.
В соответствии с выше указанным алгоритмом выполняется загрузка клеток с учетом имеющихся ограничений по спросу и предложению. Оставшиеся разницы столбцов или строк перечеркиваются и ставиться знак «К», т. е. окончание проверки, означающей, что перераспределение груза закончено. Определяются новые разницы для всех строк и столбцов таблицы, при этом загруженные и свободные клетки, расположенные в строках или столбцах, в которых исчерпаны ограничения по спросу или предложению во внимание не принимаются. Если вновь полученная разница отличается от полученной ранее, то последняя зачеркивается и пишутся новые. Действие повторяется до тех пор, пока весь груз не будет распределен. Последнюю одну или две клетки загружают без определения разностей, полученный по методу аппроксимации Фогеля план перевозки проверяется на оптимальность по методу Моди, если полученное распределение груза окажется не оптимальным, то дальнейшее решение производится по алгоритму метода Моди.
Таблица № 6
| ГО | ГП | вывоз | столбец разности | ||||||||||||||||
| Б1 | Б2 | Б3 | Б4 | Б5 | Б6 | Б7 | |||||||||||||
| А1 | 8-4=4 4-4=0 16-4=12 12-4=18 7-4=3 5-4=1 К | ||||||||||||||||||
| X | X | X | X | X | |||||||||||||||
| А2 | 4-4=0 8-4=4 12-4=8 11-4=7 5-4=1 7-4=3 К | ||||||||||||||||||
| X | X | X | X | ||||||||||||||||
| А3 | 14-4=10 5-4=1 4-4=0 12-4=8 16-4=12 К | ||||||||||||||||||
| X | X | X | X | ||||||||||||||||
| А4 | 5-4=1 8-4=4 9-4=5 11-4=7 12-4=8 4-4=0 К | ||||||||||||||||||
| X | X | X | X | ||||||||||||||||
| ввоз | |||||||||||||||||||
| строка разности | 5-4=1 8-4=4 14-4=10 4-4=0 К | 5-4=1 8-4=4 4-4=0 К | 16-4=12 12-4=8 9-4=5 4-4=0 К | 11-8=3 12-8=4 8-8=0 К | 9-5=4 11-5=6 14-5=9 5-5=0 К | 7-5=2 12-5=7 5-5=0 К | 5-4=1 7-4=3 16-4=12 4-4=0 К | ||||||||||||
Транспортная работа согласно полученному допустимому решению –
L(x) =50*4+10*5+80*4+0*5+4*100+8*30+5*40+5*200+4*20+5*20=1690 т*км
Метод Моди
Для оценки оптимальности решения потенциалы подбираются следующим образом: потенциал первой строки берется равным 0, по расстоянию загруженных клеток подбирается потенциал для других строчек и столбцов таблицы. Расстояние каждой загруженной клетки должно быть равно сумме потенциалов строки и столбца, в которой находится данная клетка.
Находим потенциалы для всех строчек и столбцов таблицы. Если число загруженных клеток будет меньше, чем условие m+n-1, то потенциал для некоторых строк и столбцов будет невозможно найти, недостающее количество клеток загружаем нулями. Загружать нулями, следует клетки, которые лежат на пересечении строк и столбцов, не имеющих потенциалов, со строками и столбцами для которых потенциалы уже определены. При этом наиболее целесообразно выбирать из этих клеток такие, в которых имеются наименьшие расстояния. После того как потенциалы всех строк и столбцов определены, определяется их сумма для каждой свободной клетки, сумма потенциалов указывается в верхнем левом углу свободной клетки. При решении задач на минимум оптимальный вариант получится в том случае, когда в каждой свободной клетке сумма потенциалов для этой клетке не превышает указанного в ней расстояния.
Если оптимальное решение не получено, то выявляется наиболее потенциальная клетка. Наиболее потенциальной клеткой при решении задач на минимум является та клетка, у которой имеется наибольшая разность между суммой потенциалов и указанного в ней расстояния. Далее строится контур для этой клетки и по данному контуру производится перераспределение груза. Действие повторяется до тех пор, пока не будет найден оптимальный вариант.
Таблица № 7
| ГО | ГП | вывоз,т | потенциал | |||||||||||||
| Б1 | Б2 | Б3 | Б4 | Б5 | Б6 | Б7 | ||||||||||
| А1 |  7
|  5
| ||||||||||||||
| А2 |  5
| 3
| -2 | |||||||||||||
| А3 | -2 | |||||||||||||||
| ||||||||||||||||
| А4 | -1 | |||||||||||||||
| ввоз, т | ||||||||||||||||
| потенциал |
Условие m+n-1 соблюдается- 7+4-1=10
L(x)= 50*4+10*5+100*4+80*4+30*8+40*5+20*5+0*5+20*5+20*4=1690 т*км
Найдено альтернативное оптимальное решение, так как в каждой свободной клетке сумма потенциалов не превышает указанного в ней расстояния.