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

Глава 6 Решение транспортной задачи по распределению СПГ

Общая постановка задачи

В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз
A₁, A₂,…, A_m n потребителям В₁, В₂,..., В_n. Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a₁, a₂, …, a_m, а общее количество имеющегося в наличии груза – а:

a = a₁ + a₂ + … + a_m,

заказы каждого из потребителей (потребности) обозначим соответственно
b₁, b₂, …, b_n, а общее количество потребностей – b:

b = b₁ + b₂ + … + b_n.

Тогда при условии

a = b

мы имеем закрытую модель, а при условии

a ≠ b

– открытую модель транспортной задачи.

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

Также существуют одноэтапные модели задач, где перевозка осуществляется напрямую с базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется «перевалочный пункт», например, склад.

План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Таблица 6.1 – Таблица перевозок

Условие а = b или a ≠ b означает, с какой задачей мы имеем дело: с за- крытой моделью или открытой моделью транспортной задачи. Переменное x_ij означает количество груза, перевозимого с базы А_i потребителю В_j: совокупность этих величин образует матрицу (матрицу перевозок).

Очевидно, переменные х_ij должны удовлетворять условиям:

(6.1)

(6.2)

Система (6.1) содержит m + n уравнений с mn неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (6.1) могут быть разделены на две группы: первая группа из m первых уравнений («горизонтальные» уравнения) и вторая группа из n остальных уравнений («вертикальные» уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (6.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях. Для решения транспортной задачи необходимо, кроме запасов и потребностей, знать также и тарифы с_ij, т. е. стоимость перевозки единицы груза с базы А_i потребителю В_j. Совокупность тарифов с_ij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

Таблица 6.2

Сумма всех затрат, т.е. стоимость реализации данного плана перевозок, является линейной функцией переменных х_ij:

(6.3)

Требуется в области допустимых решений системы уравнений (6.1) и (6.2) найти решение, минимизирующее линейную функцию (6.3).

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для её решения применяют симплекс-метод и метод потенциалов.

6.2 Методы составления начального опорного плана

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

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

Во втором случае исключается строка, содержащая заполняемую клетку, и считается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потребности заказчика, в столбце которого находится заполняемая клетка.

Начиная с первоначально данной таблицы и повторив m + n – 2 раз описанный шаг, мы придём к «таблице», состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причём потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив
m + n – 1 шагов, мы и получим искомый опорный план.

Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки.

Для рассматриваемого примера начальная транспортная таблица имеет вид:

Таблица 6.3

В колонке справа, в нижней строке расположены соответственно объёмы груза в пунктах производства и пунктах потребления. Внутри таблицы в маленьких квадратах расположены тарифы перевозок единицы груза. В результате реализации начального опорного плана должны быть заполнены
m + n – 1 = 3 + 3 – 1 = 5 клеток с базисными переменными, а остальные
(m – 1) · (n – 1) = (3 – 1) · (3 – 1) = 4 клетки с небазисными переменными не заполняются.

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

Решение транспортной задачи начинается с отыскания первого опорного плана. На каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного х₁₁ и заканчивается в клетке неизвестного х_mn, т. е. идёт как бы по диагонали таблицы перевозок.

Первая база А₁ может полностью удовлетворить потребность первого заказчика В₁ (a₁ = 30, b₁ = 20, a₁> b₁). Полагая x₁₁ = 20, вписываем это значение в клетку x₁₁ и исключаем из рассмотрения первый столбец.

Рисунок 6.1 – Пояснение №1 методу северо-западного угла

На базе А₁ остаётся изменённый запас а' = 10. В оставшейся новой таблице с тремя строками A₁, A₂, A₃ и двумя столбцами B₂, B₃ северо-западным углом будет клетка для неизвестного х₁₂. Первая база с запасом а'₁ = 10 может полностью удовлетворить потребность второго заказчика В₂ (а'₁ = 10, b₂ = 5, a'₁>b₂).

Полагаем x₁₂ = 5, вписываем это значение в клетку х₁₂ и исключаем из рассмотрения второй столбец. На базе А₁ остаётся новый остаток (запас)
a''₁ = 5.

Рисунок 6.2 – Пояснение №2 методу северо-западного угла

В оставшейся новой таблице с тремя строками A₁, A₂, A₃ и одним столбцом B₃ северо-западным углом будет клетка для неизвестного x₁₃. Теперь третий заказчик B₃ может принять весь запас с базы А₁ (а"₁ = 5, b₃ = 45,
а"₁ < b₃).

Полагаем x₁₃ = 5, вписываем это значение в клетку x₁₃ и исключаем из рассмотрения первую строку. У заказчика из В₃ осталась ещё не удовлетворённой потребность b'₃ = 40.

Рисунок 6.3 – Пояснение №3 методу северо-западного угла

Теперь переходим к заполнению клеток для неизвестного х₂₃ и х₃₃. Потребности B₃ будут полностью удовлетворены базами А₂, и А₃. Исключаем третий столбец.

Рисунок 6.4 – Пояснение №4 методу северо-западного угла

План составлен. Базис образован неизвестными x₁₁, x₁₂, x₁₃, x₂₃, x₃₃. Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.

Общий объём перевозок для этого плана составит:

S₁ = 20·10 + 5·20 + 5·30 + 15·20 + 25·10 = 1000.