Пример №15.
ЗЛП представлена в табл. 3.8.
Чтобы увеличить целевую функцию, которая на OP 
=(0; 0; 0; 1) равна нулю, переведем в базисные переменную 
с отрицательной оценкой
Так как
причем
то заменять базисную переменную можно в любом уравнении. Пусть переменная 
станет свободной (табл. 3.9, ч. I).
Целевая функция увеличилась на 8. OP 
= (2; 0; 0; 0; 0) — вырожденное, две базисные переменные — 
и 
— равны нулю. Превратим это ОР в невырожденное, заменив нули числом 
, > 0. Положим, что число может быть сколь угодно малым. Тогда
и это ОР уже невырожденное (табл. 3.9, ч. II).
Вернемся назад к табл. 3.8 и выясним, какой она должна быть, чтобы из нее получилась табл. 3.9, ч. II.
Базисная переменная третьего уравнения — это снова переменная Изменение правых частей влияет только на правые части (следует из формул пересчета (3.20), включая оценку 
). Запишем формулы пересчета правых частей.
Если числа 
линейно зависят от , то новые правые части также линейно зависят от . В нашем случае
Если теперь переменную перевести в базисные, уравнение, в котором заменится базисная переменная, определится однозначно:
и достигается на отношении
ОР = (0; 4; 0; 2; 2) превратилось в ОР 
. Так как может быть сколь угодно малым, все значения базисных переменных остаются положительными, даже если входит в выражение для правых частей со знаком минус.
Продолжим процесс увеличения целевой функции, ведь переменная 
имеет отрицательную оценку (см. табл. 3.9, ч. II).
Заменим базисную переменную в первом уравнении. Переменная 
становится базисной переменной первого уравнения. Переменная 
становится свободной (табл. 3.11).
Целевая функция возросла на величину З. Ее увеличение можно продолжить, так как
Но ОР 
— вырожденное. Заменим нулевую правую часть второго уравнения (значение базисной переменной 
) числом
Тогда
будет уже невырожденным (табл. 3.12,ч.1).
Вследствие подобной замены правые части становятся полиномами второй степени от параметра . Вследствие бесконечной малости 
справедливо неравенство 
для всякого 
, поэтому дополнительные слагаемые, содержащие член , на знак изменившихся правых частей влиять не будут. Покажем, как изменяются ОР 
(табл. 3.12, ч. II и III).
Продолжим увеличение целевой функции (табл. 3.13). Свободная переменная сменяет базисную переменную во втором уравнении:
Целевая функция возросла на число 2.
оптимально, так как все оценки свободных переменных положительны. Обратим в 0. ОР (2, 0, 0,0, 0) — это решение исходной задачи, которое мы уже рассматривали. Но тогда выбор базисных переменных был «неудачным» — не выполнялся признак оптимальности ОР. Теперь же, когда в качестве базисных выбраны переменные 
оценки свободных переменных 
больше нуля, можно утверждать, что 
.
Рассмотренный пример позволяет сформулировать общий способ избавления от вырожденности. Когда во время перебора опорных решений вырожденное ОР встретится первый раз, нужно заменить нулевые правые части числом и продолжить увеличение целевой функции. Если снова встретится вырожденное ОР, нужно заменить нули числом и продолжать увеличивать целевую функцию. Если вырожденное ОР встретится вновь, нужно заменить нули числом 
и т.д., тогда все просмотренные ОР будут невырожденными, а значения целевой функции будут монотонно возрастать. Ввиду конечности множества ОР (конечно число возможных наборов базисных переменных) обязательно найдется невырожденное ОР, для которого выполнится признак оптимальности — все оценки свободных переменных неотрицательны. Положив = 0, получим ОР исходной задачи (быть может, вырожденное) с теми же самыми неотрицательными оценками — оптимальное решение данной ЗЛП.
Итак, среди ОР данной ЗЛП, имеющей решение, всегда есть оптимальное, с неотрицательными оценками свободных переменных.
Ясно, что все приведенные рассуждения остаются в силе, если искать минимум целевой функции ЗЛП.
Эта задача взята со страницы решения задач по предмету «линейное программирование»:
Решение задач по линейному программированию
Возможно эти страницы вам будут полезны:
