Отыскание оптимального решения основной задачи линейного программирования

В предыдущем параграфе мы научились отыскивать опорное решение системы уравнений ОЗЛП; при поисках этого опорного решения мы вовсе не занимались минимизируемой функцией L. Теперь мы займемся оптимизацией решения, т. е. отысканием такого опорного решения, которое обращает в минимум линейную функцию:

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

Пример 1. Найти решение задачи линейного программирования с уравнениями

обращающее в минимум линейную функцию

Решение. Все свободные члены в (8.1) неотрицательны, значит, опорное решение налицо:

Является ли оно оптимальным? Нет, так как коэффициенты при в (8.2) положительны, значит, увеличивая эти переменные, мы уменьшаем L.

Запишем (8.1) и (8.2) в виде стандартной таблицы (табл. 8.1).

Так как коэффициенты в первой строке при положительны, любую из этих переменных можно вывести из числа свободных. Пусть это будет Какой из элементов столбца взять разрешающим? Этот элемент должен быть положительным. Значит, у нас есть выбор: 1 в строке или 1 в строке Выберем тот их них, для которого отношение к нему свободного члена минимально (обоснование см. в § 5).

Отношения равны Минимальное из них 1. Значит, в качестве разрешающего нужно взять элемент 1 в столбце строке Произведем замену (см. табл. 8.2, 8.3).

Таблица 8.1

Таблица 8.2

Таблица 8.3

Таблица 8.4

В верхней строке табл. 8.3 есть положительный коэффициент при значит, иадо вывести из свободных переменных. Выбираем в качестве разрешающего тот положительный элемент столбца для которого отношение к нему свободного члена минимально. Но в столбце единственный положительный элемент 2, его и выбираем в качестве разрешающего (см. табл. 8.4 и 8.5).

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

выбираем в качестве разрешающего элемент 3/2 в строке и столбце и продолжаем процедуру оптимизации (см. табл. 8.6 и 8.7).

В первой строке табл. 8.7 нет ни одного положительного элемента; значит, оптимальное решение достигнуто; оно будет:

При этих значениях переменных линейная функция L достигает своего минимального значения, равного

Возникает вопрос: а что если в столбце, содержащем положительный элемент строки L, не найдется ни одного положительного элемента, чтобы сделать его разрешающим? Легко убедиться, что в этом случае функция L не ограничена снизу и ОЗЛП не имеет оптимального решения.

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

Итак, сформулируем правила нахождения оптимального решения ОЗЛП симплекс-методом.

1. Если все свободные члены (не считая строки L) в симплекс-таблице неотрицательны, а в строке L (не считая свободного члена) нет ни одного положительного элемента, то оптимальное решение достигнуто.

Таблица 8.5

Таблица 8.6

Таблица 8.7

Таблица 8.8

Таблица 8.9

Таблица 8.10

2. Если в строке L есть положительный элемент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то линейная функция L не ограничена снизу, и оптимального решения не существует.

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

В заключение остановимся на так называемом «вырожденном» случае, когда один (или более) свободных членов в уравнениях-ограничениях получается равным нулю. Это означает, что в данном опорном решении обращаются в нуль не только свободные переменные, но и некоторые из базисных. Рассмотрим пример.

Пример 2. Найти решение задачи линейного программирования с условиями

обращающее в минимум линейную функцию

Решение. Записываем (8.3) и (8.4) в виде стандартной таблицы (см. табл. 8.8).

Согласно общему правилу, ищем в столбце разрешающий элемент, для которого отношение к нему свободного члена неотрицательно и минимально. Сравнивая отношения останавливаемся на разрешающем элементе 1 в строке для которого это отношение равно нулю. Производим замену (см. табл. 8.9 и 8.10).

При переходе от табл. 8.8 к табл. 8.10, естественно, не произошло уменьшения линейной функции L (она как была, так и осталась равной нулю), зато элементы верхней строки стали все неположительными, из чего видно, что оптимальное решение достигнуто: минимум функции равен нулю и достигается при

Сделаем еще одно, последнее, замечание по поводу так называемого «зацикливания». Мы уже видели, что при наличии «вырождения» может оказаться, что замена одной из свободных переменных на базисную и обратно приводит только к перестановке переменных, без уменьшения линейной функции L. В очень редких случаях может оказаться, что последовательное применение правила выбора разрешающего элемента приводит к тому, что после нескольких замен мы вновь возвращаемся к тому же набору базисных и свободных переменных, с которого начали. Это и называется «зацикливанием». Практически для того, чтобы избежать этого, достаточно бывает при повторении взять разрешающий элемент не так, как он был взят первый раз (например, в другом столбце). При организации алгоритма линейного программирования на ЭЦВМ в программу должно быть введено соответствующее указание.