2.3.2 ВЫРОЖДЕННОСТЬ
З а д а ч а 2.5
Три торговых склада (С1, С2 и С3) могут осуществлять поставки 6, 3 и 4 единиц продукта в три магазина (М1, M2, М3), спрос которых равен 4, 5 и 1 единицам соответственно. Значения единичной стоимости транспортировки указаны в приведенной ниже таблице.
2.29П Исходная информация Торговый склад Стоимость перевозки единицы изделия, у. е. Общее предложение М1 М2 М3 С1 6 4 9 6 С2 5 3 2 3 С3 2 3 6 4 Общая потребность 4 5 1 Как следует распределить перевозки, чтобы общая стоимость транспортировки была минимальной?
Решение.
Общее предложение составляет 13 единиц, что превышает общую потребность в 10 единиц, поэтому в задачу вводится фиктивный магазин, потребность которого в продукции балансирует излишек предложения торговых складов. Чтобы найти начальное распределение перевозок, применим метод Вогеля.
Значение стоимости транспортировки составит 28 у.е. Для того, чтобы решение являлось базисным, оно
должно включать (3 + 4 - 1) = 6 переменных, тогда как в нашей задаче число перевозок равно лишь пяти.
Найденное решение является вырожденным. Поступая в соответствии с алгоритмом метода МОДИ, мы должны ввести нулевую перевозку, чтобы использовать в качестве заполненной одну из пустых клеток. Этот прием позволяет получить требуемое число перевозок, равное шести. Затем можно будет рассчитать значения всех компонент u и v, следовательно, и теневые цены.
Реализацию алгоритма метода МОДИ мы начнем, используя пять заполненных клеток, соответствующих начальному распределению перевозок.
Дополнительная нулевая перевозка будет введена только тогда, когда без нее продолжение алгоритма будет невозможно. Обратимся к таблице.2.30П Начальное распределение перевозок, полученное методом Вогеля
Торговый склад Розничный магазин Общий объем Штрафная стоимость М1 М2 М3 Ф предлож ения 1 2 3 С1 - 6 3 4 - 9 31 0 630 41 2 2 С2 - 5 2 3 12 2 - 0 320 2 1 2 С3 4з 2 - 3 - 6 0 0 40 2 1 1 Общая потребно сть 4
0 5 0 1
0 3 0 13 1-й штраф 1 101 2 0 2-й штраф 9 2 0 2 0 3-й штраф - 0 2 0 Заполненные клетки используются для расчета соответствующих компонент по строкам и столбцам из соотношения: Cj = u, + Vj при условии, что u, = 0. Значения v2, v4 , v3 , u2 , не испытывая никаких
затруднений, однако значения и3 и V1 рассчитать нельзя. Для этого необходимо иметь дополнительную заполненную клетку.
2.31П Применение метода МОДИ для проверки на оптимальность вырожденного решения Торговый склад Розничный магазин Общий объем предложения М1 М2 М3 Ф С1 © Ll 4
3 1 (+6) LL 3 Ш 6 ui = 0 С2 © LL 2 Ш . LI © ш 3 U2 = - 1 С3 3 Ll © ^ © Li ©ы 6 u3 = 3 Общая потребн ость 4 5 1 3 13 V1 = - 1 V2 = 4 V3 = 3 V4 = 0 Нулевую перевозку нужно поместить в пустую клетку столбца v1 или строки и3. Какая из этих клеток будет выбрана, значения не имеет. Пусть выбрана клетка (С3, М3). Теперь можно завершить алгоритм и найти значения теневых цен для пустых клеток из соотношения Sj = Cj - (и, + Vj). Соответствующие величины приведены в таблице. Как видно из таблицы, в двух клетках теневые цены принимают отрицательные значения. Следовательно, полученное распределение перевозок не является оптимальным, и необходимо осуществить их перераспределение, используя при этом клетки (С3, М2) или (С3, Ф). Начнем с клетки (С3, М2), поскольку ей соответствует большее по абсолютной величине значение теневой цены. Ступенчатый цикл для клетки (С3, М2) можно представить в виде таблицы.
Чтобы определить число единиц, которое следует перемещать вдоль построенного цикла, обратимся к клеткам (С2, М2) и (С3, М3), помеченным знаком «-», количество перевозок в которых равно 2 и 0
единицам.
2.32П Ступенчатый цикл для (С3, М2) М2 М3 С2 Заполненная клетка 2 Заполненная клетка
+
1 С3 Клетка, подвергнутая проверке
+
1 Нулевая перевозка 0 Это означает, что по циклу следует осуществлять перемещение нулевой перевозки таким образом, чтобы клетка (С3, М3) снова стала пустой, а клетку (С3, М2) предполагается использовать при распределении перевозок, поскольку в нее помещается нулевая перевозка.
2.33П Применение метода МОДИ для проверки на оптимальность Торговый склад Розничный магазин Общий объем предложения М1 М2 М3 Ф С1 (+3) 6 3 4 С6) Lil 3 Ш 6 u1 = 0 С2 © Li 2 Li 1 Ш 3 U2 = - 1 С3 4 Li ® Ч © ш ©ш 4 u3 = - 1 Общая потребно сть 4 5 1 3 13 vi = 3 V2 = 4 V3 = 3 v4 = 0 Остальные перевозки остаются без изменений.
При дальнейшей проверке данного распределения на оптимальность выясняется, что значения всех теневых цен положительны. Данное распределение перевозок оптимальное. Это предполагает, что начальное решение, включающее 5 переменных, также оптимально. Обратимся к данным таблицы.Такие результаты далеко не всегда имеют место в случае вырожденного решения. В некоторых ситуациях при перераспределении перевозок определенное количество единиц продукта помещается в клетку с нулевой перевозкой, и тем самым данная клетка вводится в новое распределение перевозок. Это приводит к исчезновению врожденности решения. Затем, для получения улучшенного распределения перевозок, применяются обычные алгоритмы.