Вырожденность в транспортной задаче

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

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

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

 

Пример 1

Фирма должна отправить некоторое количество изделий с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 изделий, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 изделий. Стоимость перевозки одного прибора со склада в магазин приведены в таблице.

Как следует спланировать перевозку, чтобы её стоимость была минимальной?

Решение. Построим опорный план для рассмотренной выше задачи. В начале построим его с помощью метода "минимального элемента ".

Исходная транспортная таблица:

Построение опорного плана.

Находим в таблице наименьшую стоимость перевозки - это 0. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу). Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12. Находим следующую наименьшую по стоимости ячейку - их несколько, например,11. Присваиваем ей значение3, а сумму по столбцу заменяем на 17. Вычеркиваем первую строку. Выбираем ячейку 33, присваиваем ей значение 5. сумма по третей строке равна 15 - вычеркиваем третий столбец. Выбираем ячейку 25, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец. Выбираем ячейку 31, присваиваем ей 15. Уменьшаем первый столбец на 5 и вычеркиваем третью строку. Ячейке 21 присваиваем 2.

Опорный план построен.

Х11=3, Х12=12, Х21=2, Х24=8, Х25=15, Х31=15, Х33=5.

Все остальные Хij=0.

F=3*1+0*12+5*2+3*8+3*15+5*1=147

Проверим оптимальность этого плана. Для этого воспользуемся методом потенциалов.

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

Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета 22. Получим:

Строим следующую транспортную таблицу.

Проверим полученный план на оптимальность. Теперь ячейка 12 не заполнена.

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

Строим следующую транспортную таблицу.

Проверим построенный план на оптимальность.

Полученный план является оптимальным. Х11=15, Х22=12, Х24=8, Х25=5, Х31=5, Х33=5, Х35=10. Все остальные Хij=0.

F=1*15+1*12+3*8+3*5+4*5+1*5+3*10=121

 

Пример 2.

На двух складах имеется по 90 т горючего, которое нужно доставить в 3 пункта. Каждому пункту необходимо по 60 т горючего. Стоимость доставки тонны горючего из первого склада в пункт 1 равна 1ден.ед, в пункт 2 – 3 ден.ед, в пункт 3 – 5 ден.ед. Стоимость доставки из второго склада – 2,5 и 4 ден.ед. соответственно. Определить оптимальный план, минимизирующий стоимость доставки.

 

Решение. Построим опорный план для рассмотренной выше задачи. В начале построим исходную транспортную таблицу и заполним ее с помощью метода "минимального элемента ":

 

	Пункт 1	Пункт 2	Пункт 3	запасы
Склад1	60 1	30 3	х 5	90	U1=0
Склад 2	х 2	30 5	60 4	90	U2=
потребность	60	60	60
	V1	V2	V3

Проверим оптимальность полученного опорного плана. Для этого, используя заполненные клетки таблицы, рассчитаем потенциалы U2, V1, V2, V3. Потенциалу U1 присвоим значение 0. Используя клетку 11, получаем U1+V1 =1 -> V1=1; V2 находим из соотношения  V2+U1=3, справедливого для клетки 12, составляя аналогичные соотношения для всех заполненных клеток, получаем U1=0; U2=2; V1=1; V2=3; V3=2.

Проверяем соотношения оптимальности для оставшихся незаполненных клеток:

для клетки 13: V3+U1=2<С13=5; для клетки 21: V1+U2=3>С21=2. Следовательно, построенный план не оптимален, и может быть улучшен, если мы перераспределим перевозки таким образом, чтобы заполнить клетку 21.

Построим цикл, включающий эту клетку, этот цикл будет содержать клетки 21-11-12-22.

Присвоим единственной пустой клетке 21 знак +, а затем присвоим знаки остальным клеткам цикла последовательно чередуя + и -. Получим клетки 12 и 21 имеют знак +, а клетки 11 и 22 знак -. Из «минусовых» клеток выберем клетку с минимальным объемом перевозок; в нашем случае это клетка 22 с объемом перевозок, равным 30. Перераспределим перевозки по циклу следующим образом: из «минусовых» клеток вычтем, а к «плюсовым» клеткам добавим по 30, получим новый план:

 

	Пункт 1	Пункт 2	Пункт 3	запасы
Склад1	30 1	60 3	х 5	90	U1=0
Склад 2	30 2	х 5	60 4	90	U2=
потребность	60	60	60
	V1	V2	V3

Теперь незаполненной осталась ячейка 22.

Проверим оптимальность полученного плана. Рассчитаем потенциалы, используя заполненные клетки: U1=0, U2=1, V1=1, V2=3, V3=3. Проверим соотношения оптимальности для незаполненных клеток 13 и 22: для клетки 13 – U1+V3=3<5; для клетки 22 – U2+V2=4<5. Условия оптимальности выполнены, мы получили оптимальный план перевозок. Стоимость перевозок при этом равна С= 30*1+60*3+30*2+60*4= 520.

 

Задачи для самостоятельного решения.

1.Запасы товара на двух складах равны 150 и 90 соответственно. Потребности трех магазинов равны 60, 70 и 110. Матрица стоимости перевозок:

 

С = 6 10 4. Найти оптимальный план перевозок.

   12 2 8

 

2. Запасы на трех базах составляют А =(28, 56, 56). Потребности четырех магазинов – В=(49, 14, 42, 42). Стоимость доставки грузов задана матрицей тарифов перевозок:

 

     5 4 2 1

С = 4 3 2 3. Составить план перевозок с минимальными транспортными

    4 3 3 6

  издержками.

 

3. Дана исходная таблица транспортной задачи:

	1	2	3	4	запасы
А	1	2	3	4	60
В	4	3	2	0	80
С	0	2	2	1	100
потребность	40	60	80	60

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