Метод указания к лаб работам ИСО, страница 8

r = 6

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

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

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

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

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

.

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

.

Сток Исток									Запасы:
		10		7		6		8	31
			31
		5		6		5		4	48
	22		3		23
		8		7		6		7	38
					18		20
Заявки:	22		34		41		20		117

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

Сток Исток									Запасы:
		10		7		6		8	31
			31
		5		6		5		4	48
	22		3		3		20
		8		7		6		7	38
					38
Заявки:	22		34		41		20		117

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

r = 6

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

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

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

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

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

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

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

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

Сток Исток							Запасы:
		10		5		4	40
		6		4		5	23
		7		3		6	20
Заявки:	20		20		43		83

Решение:

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

Сток Исток							Запасы:
		10		5		4	40
	20		20
		6		4		5	23
					23
		7		3		6	20
					20
Заявки:	20		20		43		83

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

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

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

Сток Исток							Запасы:
		10		5		4	40-e
	20		20		e
		6		4		5	23
					23
		7		3		6	20+e
					20-e
Заявки:	20		20		43		83

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

r = 5,

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

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

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

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

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

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

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

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

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

Сток Исток							Запасы:
		10		5		4	40-e
	20		20		e
		6		4		5	23
					23
		7		3		6	20+e
					20-e
Заявки:	20		20		43		83

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

Сток Исток							Запасы:
		10		5		4	40-e
			20		20+e
		6		4		5	23
	20				3
		7		3		6	20+e
					20-e
Заявки:	20		20		43		83

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