Распределеительный метод решения транспортной задачи

Данный метод состоит в последовательном улучшении опорного плана перевозок путем отыскания на каждом шаге выгодных циклов переноса грузов. Опорный план для данного метода (как и для других методов решения транспортной задачи методом потенциалов) можно сформировать, применяя метод «северо-западного» угла.

Более подробно рассмотрим теперь процесс формирования очередного цикла переноса на каждом новом шаге алгоритма.

Очевидно, что при перемещении х единиц груза по некоторому циклу с ценой g стоимость перевозок изменяется на величину х× g.

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

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

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

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

Пример 1. Распределительный метод решения транспортной задачи.

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

 

Сток Исток					Запасы:
Заявки:

 

Решение:

Методом «северо-западного» угла найдем опорный план перевозок:

 

Сток Исток					Запасы:
Заявки:

 

1. Составленный с помощью метода «северо-западного угла» опорный план имеет шесть базисных клеток в соответствующей ему транспортной таблице, что позволяет его использовать без модификаций для дальнейшего решения задачи.

r = n + m – 1 = 4 + 3 – 1 = 6

Посчитаем теперь стоимость найденного опорного плана:

L = 22× 10 + 9× 7 + … = 796

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

2. Вычислим цену цикла для каждой свободной клетки. Количество свободных клеток в транспортной таблице данного опорного плана равно: k = 3× 2 = 6.

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

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

 

ij	2, 1	2, 4
g	- 4	- 2	- 2
x
gx	- 88	- 40	- 36

 

5. Выберем ту свободную переменную, которой соответствует наименьшее значение величины и перенесем единиц груза по циклу, соответствующему выбранной переменной: (ij) = (2, 1); g₂₁ = - 4; .

 

Сток Исток					Запасы:
Заявки:

 

Таким образом, мы уменьшим значение целевой функции L – стоимость плана перевозок – на 88 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

 

Сток Исток					Запасы:
Заявки:

 

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

r = 6

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

L = 31× 7 + 22× 5 + … = 708

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

 

2. Вычислим цену цикла для каждой свободной переменной:

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

.

4. Для единственной свободной переменной рассчитаем значение критерия :

.

 

 

Сток Исток					Запасы:
Заявки:

 

Перенесем единиц груза по циклу
(2, 4)⁺, (3, 4)^-, (3, 3)⁺, (2, 3)^-, уменьшив этим значение целевой функции на 40 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

 

Сток Исток					Запасы:
Заявки:

 

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

r = 6

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

L = 31× 7 + 22× 5 + … = 668

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

 

2. Вычислим цену цикла для каждой свободной переменной:

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

 

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

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

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

 

Сток Исток				Запасы:
Заявки:

 

Решение:

1. Методом «северо-западного» угла найдем опорный план перевозок:

 

Сток Исток				Запасы:
Заявки:

 

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

r = n + m – 1 = 3 + 3 – 1 = 5 ¹ 4

План получается вырожденный.

 

Сток Исток				Запасы:
							40-e
				e
							20+e
				20-e
Заявки:

 

Чтобы избежать этого, нарушаем баланс запасов и заявок на e в 1 и 3 строках, не нарушая общего баланса. Теперь:

r = 5,

а найденный опорный план можно использовать в дальнейшем для решения задачи.

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

L = 20× 10 + 20× 5 + 23× 5 + 20× 6 = 535.

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

2. Вычислим цену цикла для k = 4 свободных клеток.

3. Вычислим максимальное количество груза, которое можно перенести по циклам с отрицательной ценой.

4. Для свободных переменных с отрицательной ценой цикла вычислим характеристику .

(i, j)	2, 1	2, 2	3, 1	3, 2
g	- 5	- 2	- 5	- 4
g× max x	- 100	- 40	- 100	- 80

 

 

5. Перенесем max x₂₁ = 20 единиц груза по циклу свободной переменной х₂₁, уменьшив значение целевой функции на 100 единиц, то есть:

 

Сток Исток				Запасы:
							40-e
				e
							20+e
				20-e
Заявки:

 

В результате получим следующий (уже не вырожденный) план перевозок:

 

Сток Исток				Запасы:
							40-e
				20+e
							20+e
				20-e
Заявки:

 

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

r = 5

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

L = 20× 5 + 20× 4 + 20× 6 + 3× 5 + 20× 6 = 435

Попытаемся еще улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

2. Вычислим цену цикла для каждой свободной переменной.

3. Максимальное количество груза, которое можно перенести по циклу свободной переменной х₃₂ = 20.

4. g₃₂× max x₃₂ = - 80.

 

Сток Исток				Запасы:
							40-e
				20+e
							20+e
				20-e
Заявки:

 

5. Перенесем 20 единиц груза по циклу переменной x₃₂, , уменьшив значение целевой функции на 80 единиц.

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

 

Сток Исток				Запасы:
							40-e
				40+e
							20+e
				e
Заявки:

 

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

r = 5

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

L = 40× 4 + 20× 6 + 3× 5 + 20× 3 = 355

Еще раз попытаемся улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

2. Вычислим цену цикла для каждой свободной переменной.

3. Максимальное количество груза, которое можно перенести по циклу единственной свободной переменной х₂₂, имеющей отрицательную цену цикла, равно бесконечно малой величине e. Полагая e = 0, получим окончательный оптимальный план перевозок:

4.

 

Сток Исток				Запасы:
Заявки:

 

стоимость которого равна:

L = 40× 4 + 20× 6+ 3× 5 +20× 3 =355

 

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

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

Рассмотрим теперь другой метод решения транспортной задачи – метод потенциалов.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: