Критерий оптимальности плана перевозок

• Если среди оценок оптимальности все отрицательные, то опорный план является оптимальным и единственным.

• Если среди оценок оптимальности есть только отрицательные и нулевые, то опорный план является оптимальным, но не единственным.

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

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

Замечание. Если есть несколько таких оценок, то выбирают клетку с меньшим тарифом.

Для этой выбранной клетки строим цикл перераспределения поставок. Цикл изображается ломаной линией, все углы поворота которой прямые, одна вершина его находится в выбранной клетке, а другие – в заполненных. Для перераспределения поставок в выбранной клетке ставим знак “+”, затем знаки чередуем. Среди клеток со знаком “–” выбираем наименьшее количество груза и в клетки со знаком “+” будем прибавлять это число, а в клетках со знаком “–” будем это число отнимать. В результате такого перераспределения поставок получаем новый опорный план транспортной задачи.

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

Рисунок 3 – Циклы перераспределения поставок

Замечание. Грузы, которые не принимали участие в перераспределении, переписываются без изменений.

Решение транспортной задачи рассмотрим на примере.

Пример 2.6.1. Найти оптимальный план перевозок.

B A		B1	B2	B3
		10	20	20
А1	20
А2	40
А3	35

Решение. Вначале необходимо проверить наличие баланса между спросом и предложением: 20 + 40 + 35 = 95; 10 + 20 + 30 = 50. Баланса нет.

Для того, чтобы данную транспортную задачу закрыть, необходимо ввести фиктивного потребителя В₄ с потребностью 45 единиц груза (95 – 50 = 45) и нулевыми тарифами.

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

Таблица 2.6.1

B A		B1	B2	B3	B4
		10	20	20	45
А1	20	10	10
А2	40		10	20	10
А3	35				35

В нашем случае число заполненных клеток должно быть

т + п – 1 = 3 + 4 – 1 = 6.

Все 6 клеток являются заполненными, т.е. опорный план транспортной задачи является невырожденным.

Опорный план, соответствующий таблице 1, имеет вид

.

В таблице 1 сумма затрат на перевозку составляет

z₁ = 10 · 6 + 10 · 3 + 10 · 2 + 20 · 6 + 10 · 0 + 35 · 0 = 230.

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

Таким образом, таблица 2.6.1 примет вид:

Таблица 2.6.2

B A		B1	B2	B3	B4	ui
		10	20	20	45
А1	20	– 10	+ 10	(3)	(-)	0
А2	40	(2)	– 10	20	+ 10	-1
А3	35	(5) +	(-)	(-)	– 35	1
	vj	6	3	5	–1

Опорный план Х₁, который соответствует таблице 2.6.2 оптимальным не является.

Для построения цикла перераспределения груза нужно выбирать клетку с самой большой положительной оценкой. В нашем случае это (А₃, В₁). Таким образом цикл начинается в клетке (А₃, В₁), затем он продолжается к клетке (А₃,В₄), в которой поворачивает в клетку (А₂, В₄), затем – в клетку (А₁, В₂), затем – в клетку (А₁, В₁), и возвращается в начальную клетку (А₃, В₁).

В клетке (А₃, В₁) ставим знак “+”, далее чередуем знаки: в клетке (А₃, В₄) – знак “–”, в клетке (А₂, В₄) – знак “+”, в клетке (А₂, В₂) – знак “–”, в клетке А₁, В₂) – знак “+”, в клетке (А₁, В₁) – знак “–”.

В нашем случае наименьшее количество груза в клетках со знаком “–” это 10, которое клетки со знаком “+” будем прибавлять, а от клеток со знаком “–” будем отнимать.

Количество грузов, которые не принимали участие в цикле, переписываем без изменений. В нашем случае это клетка (А₂, В₃).

Таким образом, таблица 2.6.3 имеет вид:

Таблица 2.6.3

B A		B1	B2	B3	B4	ui
		10	20	20	45
А1	20	(-)	- 20	(5) +	(1)	0
А2	40	(-)	+ 0	– 20	20	-1
А3	35	10	(2)	(-)	25	-1
	vj	3	3	7	1

В таблице 2.6.3 число заполненных клеток равно 5, что меньше т + п – 1 = 6, т.е. нужно заполнить пустую клетку нулем, тогда их будет 6. В клетку (А₂, В₂) с наименьшим тарифом 2 поставим нуль и будем считать ее заполненной.

Далее расписываем потенциалы и находим оценки оптимальности, отражая эти действия в таблице 2.6.3.

Опорный план, соответствующий таблице 2.6.3, имеет вид

.

Опорный план Х₂ оптимальным не является, сумма затрат на перевозку составляет при этом

z₂ = 20 · 3 + 0 · 2 + 20 · 6 + 20 · 0 + 10 · 2 + 25 · 0 = 200.

Для построения цикла перераспределения груза нужно выбирать клетку с самой большой положительной оценкой (А₁, В₃).

В нашем случае цикл начинается в клетке (А₁, В₃), затем он продолжается до клетки (А₁, В₂), в которой поворачивает в клетку (А₂, В₂), затем – в клетку (А₂, В₃), и возвращается в исходную клетку (А₁, В₃).

В клетке (А₁, В₃) ставим знак “+”, далее чередуем знаки: в клетке (А₁, В₂) – знак “–”, в клетке (А₂, В₂) – знак “+”, в клетке (А₂, В₃) – знак “–”.

В нашем случае наименьшее количество груза в клетках со знаком “–” это 20. Тогда в клетках со знаком “+” это количество груза будем прибавлять к уже имеющемуся, а в клетках со знаком “–” будем отнимать.

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

В нашем случае это грузы, находящиеся в клетках (А₁,В₃), (А₂,В₄), (А₃,В₄).

Таким образом, таблица 2.6.4 имеет вид:

Таблица 2.6.4

B A		B1	B2	B3	B4	ui
		10	20	20	45
А1	20	(-)	(-)	20	0	0
А2	40	(-)	20	(-)	20	0
А3	35	10	(-)	(-)	25	0
	vj	2	2	2	0

В таблице 3 число заполненных клеток равно 5, что меньше 6, т.е. нужно заполнить незагруженную клетку нулем, тогда их будет 6. В клетку (А₁,В₄) с наименьшим тарифом 0 поставим нуль и будем считать ее заполненной.

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

.

Опорный план Х₃ является оптимальным, сумма затрат на перевозку в этом случае равна

z₃ = 20 · 2 + 0 · 0 + 20 · 2 + 20 · 0 + 10 · 2 + 25 · 0 = 60.

Литература – [5].