Случай вырождения

Опорное решение, в котором хотя бы одна из базисных переменных принимает нулевое значение, называется вырожденным решением. Задача линейного программирования, имеющая хотя бы одно вырожденное решение, - вырожденной задачей.

Существование вырожденного решения может привести к зацикливанию процесса вычислений. То есть, после нескольких шагов вычислений можно вернуться к ранее встречавшемуся набору базисных и свободных переменных. Особенно опасно «зацикливание» при автоматизированных вычислениях.

Устранение «зацикливания» возможно с помощью следующего правила. Если на каком-то этапе вычислений при выборе разрешающей строки возникает неопределённость, то есть оказывается несколько равных минимальных отношений , то следует выбрать ту строку, для которой будет наименьшим отношение элементов следующего столбца к разрешающему. Если при этом снова окажутся равными минимальные отношения, необходимо перейти к рассмотрению следующего столбца, и так до тех пор, пока разрешающая строка не определится однозначно.

Пример.6. Найти какой-либо опорный план задачи

,

Решение. Введём в систему ограничений неотрицательные балансовые переменные и .

Балансовые переменные сделаем базисными

Составим симплексную таблицу (табл.1.6)

Таблица 1.6 Таблица 1.7

Из таблицы видно, что начальный опорный план есть, так как в столбце свободных членов все элементы положительны - . Можно найти другой опорный план. Для этого в F – строке выбираем элемент (-6), соответствующий переменной . Столбец под переменной будет разрешающим. Затем находим минимальное отношение элементов столбца свободных членов к элементам разрешающего столбца. Поместим эти отношения в столбец (С.С.). Минимальное значение находится в строке, где находится элемент . Эта строка будет разрешающей. Разрешающий элемент стоит на пересечении этой строки и столбца, он равен 4.

В таблице 1.7:

- строка, в которой находится , получена делением разрешающей строки таблицы 1.6 на разрешающий элемент 4;

- столбец, в котором находится , получен делением разрешающего столбца таблицы 1.6 на разрешающий элемент 4 и переменой знака на противоположный;

Остальные элементы вычислены по правилу прямоугольников, в том числе и элементы F – строки. Например, для вычисления элемента строим прямоугольник, показанный в таблице 1.6, и вычисляем этот элемент по формуле прямоугольников (1.10) . Аналогично вычислены остальные элементы таблицы 1.7. В новой таблице меняем местами переменные и .

В итоге, после одного шага симплексных преобразований, получен ещё один опорный план исходной задачи . Он так же, как и предшествующий не является оптимальным, так как в F – строке есть отрицательный элемент.

Пример 7. Для предшествующей задачи найти оптимальный опорный план.

Решение. В таблице 1.7 уже определён один из опорных планов, который можно считать начальным. Чтобы получить оптимальный план, выберем в качестве разрешающего столбца тот, в котором находится коэффициент (-7) F – строки. Добавим к таблице 1.7 симплексный столбец, полученный делением свободных членов на элементы разрешающего столбца

Таблица 1.8 Таблица 1.9

В симплексном столбце таблицы 1.8 только один элемент, он и определяет разрешающую строку. Значит, разрешающим элементом будет элемент 3/2, расположенный на пересечении столбца, в котором находится , и строки, в которой находится . В таблице 1.9 меняем местами и . Вычислим только столбец свободных членов и элементы F – строки. Если в них все элементы будут положительными, то оптимальное решение достигнуто. В таблице 4 именно так и есть. В се элементы в столбце свободных членов и в F – строке положительны, значит достигнут оптимальный план. При этом , а оптимальный план . Решение можно интерпретировать геометрически. На Рис.1.10. точка О(0;0) является опорным планом , точка В(0;2) – опорным планом , точка А(8/3;10/3) - оптимальным опорным планом . Ломаная ОВА (рис. 1.10) показывает путь, продвигаясь по которому от одного опорного плана к другому, достигнуто оптимальное решение.

Пример 8. Найти оптимальный опорный план задачи

,

Решение. Приведём систему ограничений к каноническому виду, введя неотрицательные балансовые переменные и .

Откуда

Составим симплексную таблицу (табл.1.10).

Таблица 1.10 Таблица 1.11

В столбце свободных членов есть отрицательный элемент, следовательно, данный план не является опорным.

В строке, в которой находится неизвестная , находим единственный отрицательный элемент (-2), который будет разрешающим.

Делим на этот элемент все остальные элементы разрешающей строки, и меняем местами неизвестные и . Получаем табл. 1.11.

П олученный план является опорным, но не является оптимальным, так как один из элементов F – строки является отрицательным. Для отыскания оптимального плана необходимо выбрать в качестве разрешающего столбца тот, в котором находится элемент (-14). Но следует обратить внимание на то, что в соответствующем столбце нет ни одного положительного элемента. Это говорит о том, что задача не имеет решения. Геометрически это представлено на Рис. 1.11. Область решений является неограниченной.

Пример 9. Найти оптимальное решение задачи

,

Решение. Перейдём в ограничениях задачи от симметричной формы к канонической, для чего введём балансовые переменные

Балансовые переменные сделаем базисными. Выразим каждую из них через свободные переменные

Составим симплексную таблицу 1.12.

Таблица 1.12 Таблица 1.13

Найденный план не является опорным, так как у него одна координата отрицательная . Чтобы найти опорный план, поступим следующим образом. Разрешающим столбцом будет столбец под переменной . Выберем в качестве разрешающей строку, в которой находится переменная , так как симплексное отношение в ней наименьшее. Тогда разрешающим элементом будет . Делим разрешающую строку на (-2), - разрешающий столбец – на . Все остальные элементы вычисляем по правилу прямоугольника. Меняем местами переменные и . Получаем таблицу 1.13.

Найден начальный опорный план (точка С рис. 1.12), все координаты которого положительны. Этот план не является оптимальным, так как в F – строке имеются отрицательные элементы. Делаем шаг симплексных преобразований. Для этого выбираем в качестве разрешающего столбца тот, в котором наименьший элемент, а именно (-3/2). Вычисляем симплексные отношения. Единственное значение в симплексном столбце, которое даёт возможность определить разрешающую строку это значение 2, в строке, в которой находится неизвестная . Таким образом, разрешающим элементом будет .

Делаем обычные симплексные преобразования, получаем новую таблицу 1.14.

Таблица 1.14 Таблица 1.15

Очередной опорный план (точка В рис.1.12). Он не является оптимальным, так как в F – строке есть ещё один отрицательный элемент. Необходимо сделать следующий шаг симплексных преобразований. Разрешающим столбцом будет столбец под переменной . Вычисляем симплексные отношения. Наименьшим будет отношение 3/2, расположенное в строке, где находится переменная . Тогда разрешающим элементом будет .

Делаем обычный шаг симплексных преобразований, получаем таблицу 1.15, в которой все переменные и элементы F – строки положительны. Значит, найден оптимальный опорный план (точка А рис.1.12). Максимальное значение целевой функции .

Г еометрическое решение изображено на Рис.1.12. Точка С соответствует опорному плану .

Точка В соответствует опорному плану .

Точка А – оптимальному опорному плану

.

Пример 10. Найти решение задачи

,

Решение. Для решения задачи используем соотношение:

,

тогда получим

Ограничения преобразуем к каноническому виду введением балансовых переменных

Балансовые переменные примем за базисные:

Составляем симплексную таблицу 1.16.

Таблица 1.16 Таблица 1.17

Полученное базисное решение не является опорным планом, так как в нём есть отрицательный элемент . Находим опорный план. В строке с неизвестной величиной , там, где свободный член отрицательный, находим наименьший элемент (-2), этот столбец под неизвестной будет разрешающим. Вычисляем элементы симплексного столбца. Находим . Следовательно, разрешающей строкой будет строка, в которой находится неизвестная , а разрешающим элементом будет (-2). Меняем местами и . Проделываем все вычисления одного шага симплексных преобразований. Получаем таблицу 1.17.

Полученный план является опорным, так как все координаты его положительны, но не является оптимальным, так как в – строке есть отрицательный элемент (-5/2). Чтобы найти оптимальный план, сделаем столбец с элементом (-5/2) разрешающим. Вычислим симплексные отношения. Найдём . Следовательно, разрешающий элемент будет находиться в строке, где расположена неизвестная . Проделываем вычисления очередного шага симплексных преобразований, получаем таблицу 1.18

Таблица 1.18

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

.