8.4. Метод Фогеля
Способ Фогеля рассмотрим в табл. 8.12. Процесс начинается с определения разностей между двумя наименьшими элементами каждой строки и каждого столбца таблицы. Так, в столбце В5 минимальный элемент равен 3, следующий за ним по величине элемент — 8, разность между ними равна 5. Эта и другие разности по строкам и столбцам записаны в таблицу. Затем из всех разностей выбирается наибольшая. В приведенном примере это А = 6 в строке А6. Минимальный элемент в соответствующей строке равен 5 и совпадает с клеткой (А6В4), сюда же записывается поставка (см. табл. 8.12).
Все запасы А6 исчерпаны, поэтому эту строку в дальнейшем не рассматриваем (ее можно вычеркнуть).
Смысл способа Фогеля легко понять. Найденные разности показывают, насколько больше будут затраты, если в соответствующем столбце (или строке) поставка будет записана не в клетку, где находится минимальный в этом столбце (строке) элемент, а в клетку, где находится элемент, следующий за ним по величине.
Теперь, когда из рассмотрения исключены элементы столбца Вь изменяются разности по строкам, но по столбцам они не изменяются (см. 4-ю строку и столбец). В столбце В2 осталась разность А = 6, она и является наибольшей.
Находим в столбце В2 минимальный элемент, равный 3, и в клетку А{В2 делаем поставку. Вновь находим разности (см. 5-ю строку и столбец).
Опять имеем две максимальные разности в строке А3 ив столбце В3 (А = 4). В строке А3 минимальный элемент 13 в А3В3, но он
Таблица 8.12 Пример нахождения опорного плана методом Фогеля В2 *3 В, *5 Bi Запа-сы Разности по строчкам 1 2 3 4 5 Al 1
17 3
12 5 7 9 п 4
1 30 2 2 2 1 1 а2 14 12 10 10 8
26 6 3
3 29 3 3 3 3 3 А3 7 9 13
19 17
8 21 24
1 29 28 2 2 2 4 4 а4 35 32 29 26 23 20 27 20 27 0 0 0 0 0 As 7 10 13 16 12 8
11 5
15 26 2 2 2 3 3 А6 25 20 15 5
25 11 17 23 25 6 — — — — Ау 10 8 9 16 12 17 10 24 24 1 1 1 1 1 As 2 5 8 8 3
23 15 21 23 1 1 — — — Потреб-ности 17 12 19 33 49 39 43 212 1 Разности по столбцам 1 2 3 2 5 2 1 2 1 2 3 1 5 2 1 3 6 6 4 3 1 2 1 4 - 6 4 3 1 2 1 5 - - 4 3 1 2 1
не является минимальным в своем столбце.
Точно также не являет-ся минимальным в своей строке минимальный элемент столбца В3.Если учитывать, что мы ищем не абсолютный оптимум, а лишь один из базисов, можно произвольно выбрать или строку Л3, или столбец В3. Но можно вычислить в соответствующих столбце и строке вторые разности — это разности между минимальными эле- ментами и элементами, не ближайшими к ним по величине, а сле-дующими за ними.
Вторая разность для столбца В3 равна (9 — 5 = 4), а для строки А3 (21 — 13 = 8), поэтому поставку надо сделать в клетку А3В3.
Проводя аналогичные рассуждения, можно получить допустимый план (см. табл.), общие затраты на перевозку составляют Z = 1818.