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

Транспортная задача. Методы решения

Транспортная задача, это специальный вид задачи линейного программирования. Для решения транспортной задачи можно использовать методы решения задач линейного программирования, однако ввиду специфического вида задачи, были построены алгоритмы специально для решения этой задачи. Целью транспортных методов является определение наилучших путей перевозки груза из нескольких пунктов снабжения (производства) в несколько пунктов назначения (потребления), обеспечивающих наименьшие суммарные затраты по производству и транспортированию товаров. Задача рассматривается как однопродуктовая, т.е. решается применительно к одному или группе однотипных (взаимозаменяемых) товаров. Диктуется это требование тем, что объемы производства разных товаров в различных пунктах производства, а главное – спрос в различных пунктах потребления, сильно различаются. Метод «Северо-западного угла» для построения первого допустимого решения задачи или правило «Северо-западного угла» – это систематизированная процедура назначения величин перевозок из пункта производства (строка) в пункт потребления (столбец), которая требует, чтобы определение числа перевозимых единиц товара начиналось в левом верхнем углу таблицы, заканчивалось – в правом нижнем и выполнялось в соответствии со следующими требованиями:

1) следует израсходовать всю мощность завода-изготовителя (в строке) прежде, чем двинуться вниз к следующей строке;

2) следует удовлетворить потребность каждого потребителя в колонке прежде, чем двинуться к следующей колонке вправо;

3) в завершение следует проверить, что все потребности удовлетворены, а мощности полностью использованы (израсходованы). Заметим, что правило «Северо-западного угла» – не единственный способ построения первого допустимого плана.

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

При нахождении опорного плана транспортной задачи методом северо-западного угла, заполнение клеток таблицы условий начинают с верхней левой клетки K ₁₁ поэтому метод и называется "метод северо- западного угла").

Рассмотрим метод на конкретном примере.

Пример 1. На три базы A ₁, A ₂, A ₃ поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B ₁, B ₂, B ₃, B ₄ в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей

.

Найти план перевозок данной транспортной задачи методом северно-западного угла.

Решение. Запишем все данные в таблицу условий:

.

Число пунктов отправления m =3, а число пунктов назначения n =4. Следовательно опорный план задачи определяется числами, стоящими в m+n −1=3+4−1=6 заполненных клетках таблицы.

Наличие груза у поставщиков равно: ∑ A_i =140+160+120=420.

Общая потребность в грузе в пунктах назначения равна: ∑ B_j =150+90+100+80=420.

∑ A_i =∑ B_j. Модель транспортной задачи является закрытой. Следовательно, она разрешима.

Найдем опорный план задачи методом северно-западного угла.

A ₁≤ B ₁. Следовательно в клетку (A ₁, B ₁) помещаем число min(A ₁, B ₁)=140. Запасы пункта A ₁ полностью исчерпаны. Поэтому исключаем из рассмотрения строку A ₁ и будем считать потребности пункта B ₁ равными 150−140=10.

.

A ₂ > B ₁. Следовательно в клетку (A ₂, B ₁) помещаем число min(A ₂, B ₁)=10. Потребности пункта B ₁ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B ₁ и будем считать запасы пункта A ₂ равными 160−10=150.

Таким образом, продолжая процедуру в m+n −1-ом шаге получим:

Запишем полученный опорный план:

.

При этом плане стоимость перевозок вычисляется так:

F= 2·140+8·10+4·90+ 1·60+3·40+6·80=1380.