Метод северо-западного угла
Метод «северо-западного угла» — метод (правило) получения допустимого начального решения транспортной задачи. Этот метод был предложен Данцигом в 1951 г.[1] и назван Чарнесом и Купером[2] «правилом северо-западного угла».[3]
Суть метода[править]
Метод состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок (например, методом потенциалов).[4]
Числовой пример[править]
В этом примере в условиях задачи заданы возможности поставщиков 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]
См. также[править]
- Алгоритм северо-западного угла для ТЗПП (для транспортной задачи с промежуточными пунктами)
Источники[править]
- ↑ 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.
- ↑ Charnes A. and W. W. Cooper, The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems, Management Science 1, 1954—1955.
- ↑ С.Гасс. Линейное программирование (методы и приложения) / Пер. с англ. Гольштейна Е. Г. и Сушкевича М. И., под ред. Юдина Д. Б. Государственное издательство физико-математической литературы, Москва, 1961
- ↑ А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. Минск «Высшая школа», 1978 г.(djvu)
- ↑ http://www.kb.mista.ru/article.php?id=859
- ↑ http://code.activestate.com/recipes/576575-stepping-stone-algorithum-for-solving-the-tranship/
 ↑ [+] | |
|---|---|
| Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
| Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
| Вырожденные случаи | |
