Вырожденность опорного плана транспортной задачи. Как избавиться?

вырожденность опорного плана

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

Опорный план транспортной задачи называется невырожденным, если число базисных ячеек равно r=n+m-1,  где  m - количество строк, n - количество столбцов транспортной задачи. Если число перевозок меньше чем r=n+m-1, то такой план называется вырожденным.

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

Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество поставщиков, n - количество потребителей транспортной задачи.

Что же делать, если количество заполненных ячеек опорного плана меньше необходимого?

 

На некотором шаге получения первоначального плана может сложиться ситуация, когда одновременно удовлетворяются потребности магазина и опустошается склад.  В этом случае происходит "потеря" базисной клетки. Это приводит к тому, что система определения потенциалов имеет не единственное решение. 

Чтобы обойти эту ситуацию, добавим к базисным ячейкам недостающее количество ячеек с нулевыми значениями. Нулевое значение поставим в клетку, стоящую рядом с базисной клеткой, которая обусловила "пропажу" базисного значения. 

Вырожденность опорного решения транспортной задачи — пример 1:

Построить первоначальный план для следующей ситуации:

вырожденность опорного плана

Количество поставщиков (складов) = 3, количество потребителей (магазинов) = 4

60 + 30 + 40 = 40 + 50 + 10 + 30     — спрос равен предложению — задача закрытая.

Методом северо — западного угла получим опорный план.

Начинаем с самой верхней левой ячейки.

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

Потребности первого магазина выполнены полностью, но на складе еще остался груз. Заполняем дальше.

Остатки груза с первого склада 60 - 40 = 20 перевозим в магазин второй. При этом, первый склад опустел, но потребности магазина не выполнены полностью.

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

Переходим ко второму складу. Все 30 единиц груза переносим в магазин второй, потребности которого совпали с предложением склада 50 - 20 = 30.

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

потеря базисной клетки

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

Продолжим.

С третьего склада направим 10 единиц груза в магазин 4 для полного выполнения его потребностей. На 3-м складе  остается 40 - 10 = 30 единиц груза, которые перенесем в последний магазин.

опорный план 

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

Количество базисных ячеек равно 6 = 3 + 4 - 1.  Условие невырожденности выполнено! 

Вырожденность опорного решения транспортной задачи — пример 2:

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

вырожденная транспортная задача пример

Задача закрытая:

12 + 10 + 14 = 36

4 + 18 + 8 + 6 = 36 

Первоначальный план получим методом северо — угла.

Начнем с заполнения ячейки (1;1).

получение первоначального плана вырожденной транспортной задачи 

Запасы первого склада распределили по первому и второму магазину, при этом запасы склада исчерпаны, а потребность второго магазина не удовлетворена. Переходим ко второму складу.

Все 10 единиц груза направляем во второй магазин, потребности которого на данный момент равны 18 - 8 = 10. Заметим, что на данном шаге одновременно удовлетворяются потребности второго магазина и закончились запасы второго склада. Произошла потеря одного базисного значения. 

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

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

Чтобы компенсировать потерю, мы должны ввести нулевую ячейку, рядом с заполненной. Можем поместить ее правее, левее или ниже значения 10.

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

Закончим заполнение таблицы:

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

Получили первоначальный план методом северо — западного угла. Количество базисных ячеек равно 4 + 3 - 1 = 6.

Можно приступать к решению задачи методом потенциалов! 

Статистика

Эконометрика

Английский язык

Матметоды в экономике