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

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

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

Суть метода

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

Числовой пример

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

Шаг 1

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

Шаг 2

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

Шаг 3

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

Шаг 4

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

Шаг 5

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

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

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

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

Метод Фогеля (англ. Vogel’s approximation method) — один из методов получения начального решения транспортной задачи. В отличие от метода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.

Поиск по сайту: