Метод минимальной стоимости

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

В рамках условий примера 1 необходимо построить первоначальный план поставок методом минимальной стоимости.

Решение.

Шаг № 1. Среди всех незаполненных клеток табл. 3.2 у клетки (2, 3) наименьшая стоимость перевозки груза – 2. Поэтому делаем поставку, соответствующую этой клетке: min (30, 80) = 30. Исключаем 2-ю строку как полностью израсходованную.

 

Таблица 3.9 – Транспортная таблица, полученная на шаге № 1

Поставщики	Потребители	Запасы
Потребности

Шаг № 2. Среди всех незаполненных клеток табл. 3.9 у клеток (1, 1), (3, 1) и (3, 2) наименьшая стоимость перевозки груза, равная 4. Для клетки (1, 1) – min (160, 100) = 100, для клетки (3, 1) – min (90, 100) = 90, для клетки (3, 2) – min (90, 40) = 40. Выбираем ту клетку, которая соответствует возможной наибольшей поставке. Так как 100 > 90 > 40, то это клетка (1, 1). Исключаем 1-й столбец как полностью удовлетворенный.

 

Таблица 3.10 – Транспортная таблица, полученная на шаге № 2

Поставщики	Потребители	Запасы
Потребности

Шаг № 3. Среди всех незаполненных клеток табл. 3.10 у клетки (3, 2) наименьшая стоимость перевозки груза, равная 4: min (90, 40) = 40. Исключаем 2-й столбец как полностью удовлетворенный.

Таблица 3.11 – Транспортная таблица, полученная на шаге № 3

Поставщики	Потребители	Запасы
Потребности

 

Продолжая эту процедуру, получаем окончательный план перевозок (см. табл. 3.12).

 

Таблица 3.12 – Итоговая транспортная таблица

Поставщики	Потребители	Запасы
Потребности

 

Общая стоимость перевозок по полученному опорному плану:

.

 

3.4. Вырожденные планы. Циклы и пополнение плана

Условие (3.5) означает, что среди уравнений системы (3.2)‑(3.3) независимыми являются только уравнений, поэтому в любом базисном решении этой системы должно быть базисных переменных.

Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные – свободными.

План называется вырожденным, если количество базисных клеток в нем меньше, чем .

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

Циклом в таблице называется несколько клеток, соединенных замкнутой ломаной линией так, что две соседние вершины ломаной расположены либо в одной строке, либо в одном столбце.

План называется ациклическим, если его базисные клетки не содержат циклов. Оптимальные планы являются ациклическими, первоначальный план также должен быть ациклическим.

Заметим, что планы, полученные с помощью метода северо-западного угла и метода наименьшей стоимости, ациклические.

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

Возвращаясь к примеру 2, видим, что первоначальный план, полученный по методу наименьшей стоимости, имеет пять базисных клеток (см. табл. 3.12), однако . Значит, план нужно пополнить еще одной базисной клеткой. Попробуем выбрать для этого клетку (2, 2). Соединим базисные клетки горизонтальными и вертикальными отрезками (см. рис. 3.1, а).

Рисунок 3.1 – Схема цикличности и ацикличности плана

Видно, что пополненный таким образом план содержит цикл из клеток (2, 2), (2, 3), (3, 3) и (3, 2). Следовательно, клетка (2, 2) была выбрана неудачно. Взяв вместо нее клетку (2, 4), получим ациклический план (см. рис. 3.1). Поэтому можно заполнить эту клетку, положив .

 

Метод потенциалов

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

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

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

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

План является оптимальным, если все разности . В противном случае план можно улучшить в результате перераспределения поставок.

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

Заметим, что в новом плане суммы элементов по строкам и столбцам должны остаться прежними, поэтому изменение значения в одной клетке цикла повлечет за собой соответствующие изменения значений во всех остальных клетках этого цикла. В свободной клетке проставим знак «+».Пройдем по всей ломаной цикла, проставляя поочередно знаки «+» и «–».

В клетках со знаком «+» значение перевозки нужно увеличить на величину ( значения поставок в клетках со знаком «–»), а в клетках со знаком «–» следует уменьшить перевозки на .

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

Оптимизировать план поставок, полученный в примере 1 (cм. табл. 3.13).

 

Таблица 3.13 – Транспортная таблица, полученная методом северо-западного угла

Поставщики	Потребители	Запасы
Потребности

Решение. Проверим, не является ли этот план вырожденным. Так как , и число базисных клеток в плане также равно 6, то план не является вырожденным и в пополнении не нуждается. Найдем потенциалы по базисным клеткам табл. 3.13, положив :

.

Занесем полученные значения в табл. 3.14. Вычислим разности для клеток и проставим эти данные в левых нижних углах.

 

Таблица 3.14 – Промежуточная транспортная таблица

		(–) 20	-4 (+)
					-8
		(+) 30	(–) 60		-4

 

Поскольку , то план не является оптимальным. Перераспределим груз по циклу на величину .

После перераспределения поставок имеем следующий план

 

Таблица 3.14, а – Промежуточная транспортная таблица

 

Новая система уравнений для потенциалов имеет вид

 

.

Вычислив потенциалы и разности для нового плана, видим, что снова есть отрицательная разность (см. табл. 3.15). Перераспределим груз по циклу на величину .

Таблица 3.15 – Промежуточная транспортная таблица

	(–) 40		(+) 20
					-4
	-4 (+)		(–) 40

 

После перераспределения поставок имеем следующий план

 

Таблица 3.15, а – Промежуточная транспортная таблица

 

Полученный план (см. табл. 3.15 а) оказался вырожденным, поэтому его необходимо пополнить. С учетом ацикличности пополним его клеткой (3,1) с нулевым объемом перевозки.

Новая система уравнений для потенциалов имеет вид

 

.

Строим табл. 3.16. Все пересчитанные неотрицательны, следовательно, план оптимален.

 

Таблица 3.16 – Итоговая транспортная таблица

					-4

 

Суммарная стоимость перевозок по итоговому оптимальному плану:

.

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

Например, рассмотрим другой вариант.

После перераспределения поставок имеем следующий план

 

Таблица 3.15, а – Промежуточная транспортная таблица

 

Полученный план (см. табл. 3.15 а) оказался вырожденным, поэтому его необходимо пополнить. С учетом ацикличности пополним его клеткой (2,4) с нулевым объемом перевозки.

Новая система уравнений для потенциалов имеет вид

 

.

Строим табл. 3.16.

 

Таблица 3.16 – Итоговая транспортная таблица

					-2
-2			-2

 

Как видим, есть отрицательные значения , однако нельзя построить цикл для перераспределения поставок с целью дальнейшего улучшения плана. Следовательно, он оптимален.

Задание:

Исходные данные представлены в таблице.

1. Найти оптимальный план поставок. Для построения опорного плана использовать метод северо-западного угла.

 

Таблица – Транспортная таблица с исходными данными

Поставщики	Потребители	Запасы
Потребности

2. Найти оптимальный план поставок. Для построения опорного плана использовать метод минимальной стоимости.