Раздел 3

Улучшение неоптимального плана перевозок

(циклы перераспределения)

Чтобы улучшить неоптимальный план перевозок, выбирается клетка транспортной таблицы с отрицательной оценкой; если таких клеток несколько, то обычно (но необязательно) выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой.

Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом все отрезки контура образуют друг с другом прямые углы, то есть направления отрезков могут быть только горизонтальными или вертикальными. В вершинах контура расставляются поочередно знаки „+” и „–”, начиная с выбранной свободной клетки.

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

В таблице 7 построим цикл перераспределения перевозок для клетки с отрицательной оценкой .

Таблица 7



35 – 150	28 + 20
+	– 180	– 3
		– 3

В вершинах контура поставим поочередно знаки „+”, и „–”, начиная с клетки . В клетках со знаком „–” выберем минимальную величину поставки . В таблице 8 вычислим новый план перевозок.

Таблица 8



—	30 – 30	25 +
			– 3
	+ 400	–200	– 3

Вычислим значение целевой функции, соответствующее улучшенному плану перевозок по формуле:

(ден. ед.).

Проверим улучшенный план перевозок на оптимальность методом потенциалов. Расчет потенциалов представлен в таблице 8. Вычислим оценки свободных клеток:

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

Таблица 9



	—
						– 3
						– 2

Вычислим значение целевой функции, соответствующее улучшенному плану перевозок по формуле:

(ден. ед.)

Проверим улучшенный план перевозок на оптимальность методом потенциалов. Расчет потенциалов представлен в таблице 9.

Вычислим оценки свободных клеток:

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

Ответ. Минимальная стоимость перевозок грузов от поставщиков к потребителям составляет ден. ед.

Оптимальное распределение поставок .

Пример решения транспортной задачи открытого типа.

Составить оптимальный план перевозок некоторого однородного груза с трех баз к четырем потребителям . Исходные данные и матрица транспортных издержек приведены в транспортной таблице (таблица 10).

Таблица 10

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




Заявки потребителей,

Определим тип транспортной задачи путем проверки баланса суммарной мощности поставщиков: (тонн) и потребителей: (тонн). Спрос и предложение несбалансированны: , следовательно, данная задача открытого типа.

Приведем задачу к каноническому виду. Так как предложение меньше спроса, то есть , следует ввести „фиктивного” поставщика с запасом (тонн) с транспортными издержками , , получим задачу закрытого типа (таблица 11).

Составим начальное распределение методом учета наименьших затрат и решим задачу методом потенциалов.

Таблица 11


3 – 25	4 + 0	—	—
—		—
+ —	—	– 30	—
—	– 25	+ 45	—	– 4

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

Найдем суммарную стоимость перевозок, соответствующую начальному распределению:

(ден. ед.)

Вычислим оценки свободных клеток таблицы:

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

В клетках со знаком „–” выберем минимальную величину: , получили величину перераспределяемой поставки. Так как величина равна поставке не в одной, а сразу в двух вершинах контура со знаком „–”, то освободим только одну клетку , а клетку оставим занятой с „нулевой поставкой”.

Таблица 12





		—				– 6

Найдем суммарную стоимость перевозок, соответствующую улучшенному распределению:

(ден. ед.)

Вычислим оценки свободных клеток таблицы:

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