Первоначальное распределение поставок

Прежде чем начать заполнение клеток таблицы поставками, нужно установить число таких клеток. Как отмечалось в предыдущем параграфе, оно определяется числом линейно независимых уравнений системы ограничений (6.1).

На первом этапе рассмотрим те задачи, которые имеют закрытую модель, т. е. для них выполняется ограничение (6.2): .

В этом случае хотя в системе ограничений (6.1) содержится k + l уравнений, но число ее линейно независимых уравнений на единицу меньше.

Действительно, если сложить все k первых уравнений, относящихся к поставщикам, и все l уравнений, относящихся, к потребителям, и учесть, что то получим полное совпадение левых и правых частей составленных таким образом сумм. Это свидетельствует о том, что система (6.1) в закрытых моделях линейно зависима. Если же из системы исключить одно, безразлично какое, уравнение, то она становится линейно независимой.

Отсюда следует, что число линейно независимых уравнений и число заполняемых клеток равно k+ l– 1. При этом число незаполненных клеток составляет kl — (k + l – 1).

Как же заполнить поставками k + l – 1 клеток таблицы? Существуют различные правила такого заполнения, а следовательно, и получения первоначального распределения поставок. Рассмотрим два из них: правило учета наименьших затрат и правило «северозападного угла».

Пример 6.1. Пусть требуется получить первоначальное распределение поставок в следующей транспортной задаче (табл. 6.2).

Таблица 6.2 - Данные к примеру 6.1

Поставщики	Мощности поставщиков	Потребители и их спрос
I
I
III
IV

Решение. Убедимся прежде всего, что задача имеет закрытую модель: в самом деле, т.е . Здесь число поставщиков k = 4; число потребителей l = 5; число всех клеток 4×5 = 20; число заполненных клеток 4 +5–1=8; число свободных клеток 20 – 8= 12.

Правило учета наименьших затрат. Снабдим каждую клетку двойным номером, совпадающим с индексами соответствующей этой клетке переменной (первый индекс совпадает с номером поставщика, второй – с номером потребителя). Например, клетка (2.3) стоит на пересечении 2-й строки и 3-го столбца. В таблице берем клетки, имеющие наименьший показатель затрат. Такой показатель, равный 1, находится в двух клетках: (1.4) и (3.1).

Дадим поставку в клетку (1.4). Чтобы решить вопрос о величине этой поставки, заметим, что поставщик 1 располагает 100 ед. груза, а потребителю 4 требуется 75 ед. груза. Размер поставки определяется минимальным из этих двух чисел, т. е. в клетку (1.4) следует записать поставку, равную 75 ед. Потребитель 4, получив сполна 75 ед. груза, может быть вычеркнут из таблицы, и на следующем этапе распределения таблица уже имеет размер 4x4, причем мощность поставщика 1 составляет уже 25 ед. груза.

Заполняем клетку (3.1). Учитывая, что min {75; 85} = 75, даем в эту клетку поставку, равную 75 ед. При этом заполнении из таблицы вычеркивается 3-я строка, а спрос потребителя 1 сокращается до 10 ед.

Следующий по величине показатель затрат, равный 2, стоит в клетках (1.2) и (1.5), клетки (3.2) и (4.4) в расчет не берутся, поскольку они стоят в вычеркнутых строке и столбце.

Учитывая, что у поставщика 1 осталось только 25 ед. груза, передаем этот груз в клетку (1.2) (min {25; 65} = 25) и вычеркиваем 1-ю строку. Клетки (2.3), (2.5), (4.5) имеют показатель затрат, равный 3 ед.

Таблица 6.3 – Распределение поставок по правилу учета наименьших затрат

Дадим поставку в клетку (2.3). Размер этой поставки равен 80 ед. (min {80; 125} = 80). Из таблицы вычеркиваем 3-й столбец, а мощность поставщика 2 сократилась до 45 ед.

Эти 45 ед. груза передадим в клетку (2.5) и вычеркнем 2-ю строку. Недостающие потребителю 5 25 ед. груза возьмем у поставщика 4 и вычеркнем 5-й столбец.

Оставшиеся у поставщика 4 50 ед. груза можно передать потребителям 1 или 2.

Обеспечим прежде всего потребителя 2, так как в клетке (4.2) стоит меньший показатель затрат, чем в клетке (4.1). Но потребителю 2 требуются не все 50 ед. груза, а только 40, поэтому в клетку (4.2) записываем 40 ед. и вычеркиваем 2-й столбец, а оставшиеся 10 ед. груза помещаем в клетку (4.1). После последней операции из таблицы вычеркнуты одновременно и 1-й столбец, и 4-я строка. Заметим, что только на последнем этапе произошло вычеркивание и строки, и столб­ца, а на предыдующих этапах передача поставки в какую-либо клетку сопровождалась вычеркиванием либо одного столбца, либо одной строки.

Получив распределение, подсчитаем количество заполненных клеток. Их оказалось 8, т. е. именно столько, сколько должно быть. Мож­но также убедиться, что по каждой строке и по каждому столбцу со­блюден баланс, а именно от каждого поставщика запланирована от­правка всего груза, которым он располагает, и каждому потребителю планируется то количество груза, в котором он нуждается.

Является ли полученное распределение оптимальным? Оставив пока этот вопрос открытым, познакомимся со вторым правилом первоначального распределения поставок.

Правило «северо-западного угла». В этом случае не обращают внимания на показатели затрат. Начав заполнение с клетки (1.1) – «северо-западного угла» таблицы, ступенями спускаются вниз до клетки (k.l), вычеркивая либо одну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k-я) строка и последний (l -й) столбец. При практическом заполнении таблицы вычеркивание строк и столбцов производится лишь мысленно.

В таблице 6.4 дано первоначальное распределение поставок по правилу «северо-западного угла» для рассматриваемой задачи.

Таблица 6.4 – Распределение поставок по правилу «северо-западного угла»

Количество заполненных клеток снова равно 8. Нетрудно показать, что первоначальное распределение поставок в таблице 6.4, выполненное по правилу «северо-западного угла», значительно хуже, чем распределение поставок в табл. 17.3, проведенное с учетом наименьших затрат. Для этого достаточно подсчитать и сравнить затраты на перевозки при этих первоначальных распределениях поставок. В самом деле, суммируя произведения показателя затрат на величину поставки, для распределений, приведенных в таблице 6.3 и 6.4, соответственно получим:

F ₁ = 50 + 75 + 240+135 + 75 + 60 +160 + 75 = 870 ден. ед.,

F ₂ = 340 + 30 + 250 + 225 + 25 + 420+10 + 210=1510 ден. ед.,

т. е. распределение поставок в таблице и 6.4значительно дальше отстоит от оптимального, чем распределение поставок в таблице 6.3.

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