Метод аппроксимации Фогеля

При этом методе исходная матрица (таблица) дополняется столбцом и строкой разностей (табл. 2.6). В каждой строке и каждом столбце таблицы отыскивают два наименьших элемента и определяют абсолютную разность между ними, которую заносят соответственно разности по строке в столбец разностей, разности по столбцам - в строку разностей. Если две клетки в одной и той же строке или столбце имеют одинаковые значения, то разность для этой строки или столбца (равная нулю) также проставляется в соответствующую строку или столбец.

Затем выбирают наибольшую величину разности независимо от того, стоит ли она в столбце или строке разностей. В клетку с минимальным элементом в данной строке или столбце заносят максимальную загрузку, учитывая при этом соотношение ресурса поставщика и спрос потребителя. Наибольшая разность зачеркивается. Если окажется, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, в соответствующей строке или столбце разностей проставляется буква «к» (конец) и данная строка или столбец матрицы из дальнейшего рассмотрения исключается. После заполнения клетки таблицы разности пересчитывают, и операции повторяются вновь до тех пор, пока не будет составлен исходный опорный план. При наличии двух одинаковых наибольших разностей загружается клетка, которая имеет меньший элемент по строке и столбцу. Такая клетка называется седловой. При наличии независимых седловых точек, т.е. расположенных в разных строках и столбцах, их загружают одновременно. Последние распределения можно сделать без вычисления разностей, поскольку остается несколько незагруженных клеток, поставки в которые очевидны.

Рассмотрим на примере приведенном ранее это метод (см. табл. 2.6).

Наименьшие элементы первой строки - это 4 в клетке А₁В₄ и 6 в клетке А₁В₂. Разность между ними, равная 2, записывается в первую клетку столбца разностей. Аналогично находят разности для остальных строк и столбцов. Наибольшая разность, равная 6, находится в строке разностей по столбцу В₁ и в столбце разностей по строке А₂. Учитывая равность наименьших расстояний, делаем вывод о наличии двух седловых точек (А₃В₁ и А₂В₂). Следовательно, данные клетки загружаются одновременно. В строке разностей по столбцам В₁ и В₂ записывается буква «к », что означает конец вычислений по данным столбцам, т.е. элементы данных столбцов в дальнейших расчетах не учитывают, и клетки этих столбцовотмечают знаком, например Х.

После этого разности пересчитывают вновь, и процесс повторяется. Этапы расчетов по составлению опорного плана перевозок методом аппроксимации Фогеля представлены в табл. 2.6.

Транспортная работа согласно полученному методом аппроксимации Фогеля допустимому решению составит: L(x)= 200*2+400*2+200*12+600*8+200*6+400*4=11 200 ткм.