Постановка и основные свойства транспортной задачи

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

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

Рассмотрим два случая.

1. Вырожденный план является начальным Х0. Тогда выбирают некоторые н

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

2. Вырожденный план получается при построении плана Хk+1 на базе Хk, если цепочка в плане Хk содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Хk+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге , то при переходе от Хk к Хk+1 значение целевой функции не изменяется, а в базис вводится элемент , для которого перевозка станет равной .

Пример 2. Решим Т-задачу со следующими условиями (см. Табл.6)

Проверим условие баланса

Предварительный этап. Методом минимального элемента строим начальный базисный план Х0 (Табл. 5)

Таблица 5

Так как m + n – 1 = 6; k = 4, то план х0 – вырожденный; l = m+ n -1 – k = 2.

Два нулевых элемента Х0 делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов , и положим их равными .

Схема перевозок для плана Х0 показана на рис. 6.

Рис. 6.

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

,

Для проверки оптимальности плана х0 строим матрицу С1, элементы которой вычисляем по соотношению

Так как в матрице С1 элемент С23 = – 3 < 0, то план Х0 – неоптимальный.

Первая итерация. Второй этап.

 Скачать реферат