Вырожденное решение

Для того чтобы иметь возможность решить систему уравнений (3.1) при поиске оптимального плана перевозок по методу потенциалов, необходимо, чтобы количество базисных переменных всегда было в точности равно M+N-1. Если некоторые из базисных переменных принимают нулевые значения, то решение называется вырожденным. Необходимо учитывать некоторые особенности поиска оптимального плана при появлении вырожденного решения. Такое решение возникает в следующих случаях:

· при поиске допустимого плана – в случае, если запас товара у поставщика оказывается в точности равен спросу потребителя;

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

Рассмотрим пример, в котором возникают оба случая вырожденного решения.

Пример 3.5. С двух карьеров (К1 и К2) поставляются стройматериалы на три стройки (С1, С2, С3). Возможности карьеров по поставке стройматериалов (тонны), потребности строек (тонны) и стоимости перевозок одной тонны стройматериалов с каждого карьера на каждую из строек (ден.ед.) приведены в табл. 3.23.

Таблица 3.23

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

Решим эту задачу, как показано в подразделах 3.2.2.2 и 3.2.2.3.

Для определения допустимого решения воспользуемся методом минимального элемента. Наиболее дешевыми (6 ден.ед. за тонну) являются перевозки с карьера К2 на стройку С2. карьер К2 поставляет стройке С2 15 тонн стройматериалов, так как карьер может поставить 45 тонн, а стройке требуется 15 тонн. Стройка С2 исключается из рассмотрения (второй столбец вычеркивается из расчетной таблицы), а в карьере К2 остается 30 тонн стройматериалов.

В сокращенной расчетной таблице минимальный элемент соответствует перевозкам с карьера К2 на стройку С1. Запас стройматериалов в карьере К2 в точности равен потребности стройки С1 (30 тонн). Карьер К2 поставляет стройке С1 30 тонн стройматериалов. Из рассмотрения можно исключить или поставщика (карьер К2), или потребителя (стройку С1), но не обоих вместе. Пусть исключается карьер К2 (вторая строка из расчетной таблицы). При этом считается, что спрос стройки С1 остается н еудовлетворенным на 0 тонн стройматериалов.

В оставшейся части расчетной таблицы выбирается минимальный элемент. Он соответствует перевозкам с карьера К1 на стройку С1 (14 ден.ед. за тонну). Карьер может поставить 30 тонн стройматериалов, а стройке требуется 0 тонн. Поэтому величина поставок стройматериалов с карьера К1 на стройку С1 принимается равной нулю, однако переменная Х₁₁=0 включается в базис. Стройка С1 исключается из рассмотрения.

В карьере К3 имеется запас стройматериалов в размере 30 тонн. Такое количество стройматериалов требуется стройке С3. Поэтому карьер К1 поставляет стройке С3 30 тонн стройматериалов. На этом поиск допустимого плана перевозок завершается. Он приведен в табл. 3.24.

Полученный допустимый план перевозок состоит в следующем. Карьер К1 поставляет 30 тонн стройматериалов стройке С3; карьер К2 поставляет 30 тонн стройматериалов стройке С1 и15 тонн – стройке С2. Общие затраты на перевозки составят 1080 ден.ед.

Таблица 3.24

Переменная x₁₁=0 включена в базис только для того, чтобы количество базисных переменных было равно M+N-1 (в данном случае – 4). Никаких перевозок с карьера К1 на стройку С1 не выполняется.

Найдем оптимальный план перевозок, используя метод потенциалов. Составим систему уравнений для определения платежей:

U₁+V₁=14

U₁+V₃=25

U₂+V₁=8

U₂+V₂=6

Принимая U₁=0, найдем платежи: V₁=14, V₃=25, U₂=–6, V₂=12. Найдем псевдостоимости , затем разности стоимостей и псевдостоимостей D_ij = С_ij – С’_ij.

Эти величины приведены в табл. 3.25. Величина D₂₃ оказалась отрицательной. Это означает, что имеющийся план перевозок не является оптимальным. Переменная x₂₃ включается в базис. Для определения нового плана перевозок строится цикл (см. табл. 3.25).

Таблица 3.25 Таблица 3.26

Обе переменные, обозначенные знаком «минус» (x₁₃ и x₂₁), имеют одинаковые значения, равные 30. Любую из этих переменных (но только одну) можно исключить из базиса. Пусть исключается переменная x₂₁. Вычисляются новые значения базисных переменных: все переменные, отмеченные знаком «плюс», увеличиваются на 30 (т.е. на величину переменной, исключаемой из базиса), а переменные, отмеченные знаком «минус» – уменьшаются на ту же величину. Переменная x₁₃ становится равной нулю, но остается в базисе (так как исключается из базиса только одна переменная – x₂₁). Новый план перевозок приведен в табл.3.26.

Проверим полученный план на оптимальность. Составим систему уравнений для определения платежей:

U₁+V₁=14

U₁+V₃=25

U₂+V₂=6

U₂+V₃=10

Найдем платежи: U₁=0, V₁=14, V₃=25, U₂=–15, V₂=21. Найдем псевдостоимости, затем – разности стоимостей и псевдостоимостей. Эти величины приведены в табл. 3.27.

Все разности стоимостей и псевдостоимостей оказались положительными. Это означает, что получено оптимальное решение. Таким образом, план перевозок должен быть следующим. Карьер К1 поставляет 30 тонн стройматериалов стройке С1; карьер К2 поставляет 15 тонн стройматериалов стройке С2 и 30 тонн – стройке С3. Общие затраты на перевозки составят 810 ден.ед.

Таблица 3.27

Дата добавления: 2015-07-21