Метод северо-западного угла

Материал из Циклопедии
Перейти к: навигация, поиск

Метод «северо-западного угла» — метод (правило) получения допустимого начального решения транспортной задачи. Этот метод был предложен Данцигом в 1951 г.[1] и назван Чарнесом и Купером[2] «правилом северо-западного угла».[3]:189

Содержание

[править] Суть метода

Метод состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок (например, методом потенциалов).[4]:112

[править] Числовой пример

В этом примере в условиях задачи заданы возможности поставщиков Ai и потребности потребителей Bj. Требуется найти допустимые объемы перевозки от каждого поставщика к каждому потребителю Xij.

Потребитель B1, потребность 20 кг Потребитель B2, потребность 30 кг Потребитель B3, потребность 30 кг Потребитель B4, потребность 10 кг
Поставщик A1, запас 30 кг
Поставщик A2, запас 40 кг
Поставщик A3, запас 20 кг

[править] Шаг 1

Первая ячейка — с которой начинается распределение — будет «северо-западная» ячейка в левом верхнем углу таблицы X11 (1-й поставщик, 1-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 20 и 30 кг, то есть 20 кг). Поскольку спрос 1-го потребителя полностью удовлетворен, ячейки соответствующего столбца заполняться больше не будут, для ясности закрашиваем 1-й столбец в серый цвет.

Потребитель B1, потребность 20-20=0 кг Потребитель B2, потребность 30 кг Потребитель B3, потребность 30 кг Потребитель B4, потребность 10 кг
Поставщик A1, запас 30-20=10 кг X11=20 кг
Поставщик A2, запас 40 кг
Поставщик A3, запас 20 кг

[править] Шаг 2

Переходим в следующую «северо-западную» ячейку, не считая окрашенной серым цветом (в таблице выше) уже распределенной области. Этой ячейкой будет X12 (1-й поставщик, 2-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 30 и 10 кг, то есть 10 кг). Соответственно, уменьшаем оставшиеся не распределенными объемы поставки и потребления в строке и столбце на 10 кг. Запасы 1-го поставщика (в 1-й — верхней — строке) теперь исчерпаны, окрашиваем эту строку в серый цвет (распределение по этой строке завершено).

Потребитель B1, потребность 20-20=0 кг Потребитель B2, потребность 30-10=20 кг Потребитель B3, потребность 30 кг Потребитель B4, потребность 10 кг
Поставщик A1, запас 30-20-10=0 кг X11=20 кг X12=10 кг
Поставщик A2, запас 40 кг
Поставщик A3, запас 20 кг

[править] Шаг 3

Переходим в следующую «северо-западную» ячейку, не считая окрашенной серым цветом (в таблице выше) уже распределенной области. Этой ячейкой будет X22 (2-й поставщик, 2-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 40 и 20 кг, то есть 20 кг). Соответственно, уменьшаем оставшиеся не распределенными объемы поставки и потребления в строке и столбце на 20 кг. Потребности 2-го потребителя теперь полностью удовлетворены, окрашиваем этот столбец таблицы в серый цвет (распределение по этому столбцу завершено).

Потребитель B1, потребность 20-20=0 кг Потребитель B2, потребность 30-10-20=0 кг Потребитель B3, потребность 30 кг Потребитель B4, потребность 10 кг
Поставщик A1, запас 30-20-10=0 кг X11=20 кг X12=10 кг
Поставщик A2, запас 40-20=20 кг X22=20 кг
Поставщик A3, запас 20 кг

[править] Шаг 4

Переходим в следующую «северо-западную» ячейку, не считая окрашенной серым цветом (в таблице выше) уже распределенной области. Этой ячейкой будет X23 (2-й поставщик, 3-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 30 и 20 кг, то есть 20 кг). Соответственно, уменьшаем оставшиеся не распределенными объемы поставки и потребления в строке и столбце на 20 кг. Запасы 2-го поставщика (в 2-й сверху строке) теперь исчерпаны, окрашиваем эту строку в серый цвет (распределение по этой строке завершено).

Потребитель B1, потребность 20-20=0 кг Потребитель B2, потребность 30-10-20=0 кг Потребитель B3, потребность 30-20=10 кг Потребитель B4, потребность 10 кг
Поставщик A1, запас 30-20-10=0 кг X11=20 кг X12=10 кг
Поставщик A2, запас 40-20-20=0 кг X22=20 кг X23=20 кг
Поставщик A3, запас 20 кг

[править] Шаг 5

Распределение оставшихся у последнего поставщика 20 кг груза по двум потребителям по 10 кг:

Потребитель B1, потребность 20-20=0 кг Потребитель B2, потребность 30-10-20=0 кг Потребитель B3, потребность 30-20-10=0 кг Потребитель B4, потребность 10-10=0 кг
Поставщик A1, запас 30-20-10=0 кг X11=20 кг X12=10 кг
Поставщик A2, запас 40-20-20=0 кг X22=20 кг X23=20 кг
Поставщик A3, запас 10-10=0 кг X33=10 кг X34=10 кг

Таким образом, весь груз от поставщиков должен быть распределён по потребителям. Если наблюдается недостаток или избыток груза, то это означает, что была допущена арифметическая ошибка, или задача не была приведена к закрытому виду (см. раздел Транспортная задача#Балансировка задачи). Чтобы убедиться в правильности полученного решения, полезно сверить исходные объемы каждого поставщика, которые заданы в условиях транспортной задачи, с суммами отгрузок в соответствующей строке, а исходные объемы каждого потребителя, которые также заданы в условиях — с суммами отгрузок по соответствующим столбцам (см. раздел Транспортная задача#Проверка правильности распределения объемов).

[править] Дальнейшая оптимизация решения

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

[править] Программная реализация

В коде для 1С:Предприятие 8.2 по ссылке метод представлен функцией РаспределениеМетодомСевероЗападногоУгла.[5] В коде для Python по ссылке метод представлен функцией NorthWest. [6]

[править] Источники

  1. Dantzig, G. В., Application of the Simplex Method to a Transportation Problem, chap. XXIII of // Koopmans T.C. (ed.), Activity Analysis of Production and Allocation, Cowles Commission Monograph 13, John Wiley & Sons, Inc., New York, 1951.
  2. Charnes A. and W. W. Cooper, The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems, Management Science 1, 1954—1955.
  3. С.Гасс. Линейное программирование (методы и приложения) / Пер. с англ. Гольштейна Е. Г. и Сушкевича М. И., под ред. Юдина Д. Б. Государственное издательство физико-математической литературы, Москва, 1961
  4. А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
  5. http://www.kb.mista.ru/article.php?id=859
  6. http://code.activestate.com/recipes/576575-stepping-stone-algorithum-for-solving-the-tranship/


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты