Алгоритм решения ЗЛП симплекс-методом

⇐ ПредыдущаяСтр 5 из 10Следующая ⇒

1. Привести систему ограничений канонической ЗЛП к допустимому виду. Выделить базис переменных. Соответствующим образом записать целевую функцию ЗЛП (она должна зависеть от свободных переменных).

2. Построить начальный опорный план (базисное решение) и найти значение целевой функции на начальном опорном плане.

3. Проверить выполнимость условия теоремы 5.1. Если условие теоремы 5.1 выполняется (случай 1), то построенное в пункте 2 базисное решение является оптимальным. Задача решена.

4. Если условие теоремы 5.1 не выполняется, то проверить выполнимость условий теоремы 5.2. Если условие теоремы 5.2 выполняется (случай 2), то данная ЗЛП не имеет оптимального решения. Задача решена.

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

Пример 5.3. Найти оптимальное решениеЗЛП допустимого вида

( ),

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

Перепишем систему ограничений в виде

Введем целевую функцию . Значение целевой функции на базисном решении равно .

Заметим, что условия теорем 5.1 и 5.2 не выполняются, значит, имеем случай 3. В целевой функции при свободной переменной стоит отрицательный коэффициент ( ), а в системе ограничений при этой же переменной стоят два отрицательных коэффициента: (случай 3.2). Составим вспомогательное число

Разрешающим элементом является элемент (он выделен в прямоугольник). Тогда необходимо изменить базис переменных: . Для этого из системы ограничений допустимого вида необходимо выразить переменную через переменную . Получим

Подставляя в систему ограничений вместо переменной полученное выражение, получим новую систему ограничений

Соответствующим образом изменим целевую функцию

Итак, получаем новую ЗЛП допустимого вида

( ).

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

, .

Решение задачи линейного программирования

При помощи симплекс-таблиц

В предыдущем параграфе был рассмотрен симплекс-метод решения ЗЛП. Алгоритм симплекс-метода основан на последовательном улучшении (минимизации) целевой функции и построении базисного (опорного) решения (плана). Оптимальное решение достигается последовательным улучшением начального опорного плана за определенное число этапов (итераций). Переход к следующему опорному решению проводится на основе метода Жордана–Гаусса для систем линейных алгебраических уравнений. Направление перехода от одного базисного решения к другому выбирается на основе двух теорем (принципов оптимальности ЗЛП, теорема 5.1, теорема 5.2). Полученный опорный план на каждом шаге симплекс-метода проверяется на оптимальность. Процесс оканчивается за конечное число шагов. Причем на последнем шаге либо получается оптимальный опорный план и соответствующее ему оптимальное значение целевой функции (теорема 5.1), либо выявляется неразрешимость задачи (конечного оптимума нет).

Оказывается, что все вычисления по симплекс-методу удобно производить в так называемых симплекс-таблицах.

Как и в предыдущем параграфе, рассмотрим ЗЛП в допустимом виде

(6.1)

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

. (6.2)

Приведем ЗЛП (6.1) – (6.2) к каноническому виду

(6.3)

. (6.4)

Рассмотрим алгоритм решения ЗЛП, используя результаты предыдущего параграфа (теоремы 5.1, 5.2). В целях наглядности рассмотрим ЗЛП

(6.3′ )

, (6.4′ )

в которой три базисные переменные и три свободные переменные , причем .

Составим начальную симплекс-таблицу (табл. 6.1). В столбце БП выписываем базисные переменные , в столбце СЧ – коэффициенты в правой части системы ограничений (6.3′ ). В следующих столбцах выписываются коэффициенты при переменных в левой части системы (6.3′ ). Последняя строка таблицы составляется по коэффициентам при переменных в целевой функции (6.4′ ).

Табл. 6.1

БП	СЧ

По табл. 6.1 построим начальный: (значения свободных переменных равны нулю); соответственно значение целевой функции на базисном решении равно .

Проверим построенное базисное решение на оптимальность. Возникают три случая:

Случай 1. Пусть в последней строке симплекс-таблицы все коэффициенты при свободных переменных неположительны:

Это условие равносильно тому, что . Тогда согласно теореме 5.1 базисное решение является оптимальным:

, .

Случай 2. Пусть в последней строке симплекс-таблицы среди коэффициентов есть положительный коэффициент (предположим для определенности: ), а все коэффициенты при соответствующей свободной переменной отрицательные (в нашем случае все коэффициенты , , при соответствующей свободной переменной отрицательны). Это условие равносильно тому, что

, .

Тогда согласно теореме 5.2, ЗЛП не имеет оптимального решения.

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

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

Табл. 6.2

БП	СЧ	Преобразования

Согласно симплекс-методу, необходимо изменить базис переменных: переменную вывести из базиса, а ввести в базис. Для этого составляется новая симплекс-таблица (табл. 6.3) по следующему правилу:

1) Базисными переменными являются , свободными – переменные (переменная сменила переменную в базисе);

2) Разрешающая строка (в данном случае строка коэффициентов при переменной ) делится на разрешающий элемент (в нашем случае на число ). Полученная строка записывается в новую строку следующей таблицы, соответствующей новой базисной переменной;

3) В разрешающем столбце таблицы 6.2 (в столбце коэффициентов при ) необходимо получить нули. Для этого применяем элементарные преобразования над строками таблицы 6.2. Полученные результаты записываем в соответствующие строки табл. 6.3.

Табл. 6.3

БП	СЧ

Покажем, что в табл. 6.3 коэффициенты , , неотрицательны. Действительно, (так как по , ).

Далее, если даже коэффициент отрицательный, то в силу того, что :

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

Итак, в любом случае коэффициент неотрицательный. Аналогично показывается, что коэффициент неотрицательный.

Это показывает, что вектор-столбец , полученный при нулевых значениях свободных переменных, является допустимым решением ЗЛП.

Значение целевой функции на базисном решении равно

Так как по условию , , , то , а значит,

то есть в процессе смены базиса целевая функция ЗЛП уменьшилась на значение , что является оправданием шага симплекс-метода.

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

Пример 6.1. Решить ЗЛП при помощи симплекс-таблиц.

Решение. 1) Приведем ЗЛП к каноническому виду. Введем в систему ограничений балансовые переменные . Так как , то введем функцию

сведя задачу к поиску минимума функции : .

Получили следующую ЗЛП канонического вида

2) Для полученной ЗЛП базис переменных . Составим базисное решение , . Получаем симплекс-таблицу (табл. 6.4).

Табл. 6.4

БП	СЧ				Преобразования
				–1
		–2	–1
			–3
	– 5		–3

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

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

3) Составляем следующую симплекс-таблицу. Для этого делим -строку табл. 6.4 на разрешающий элемент и при помощи элементарных преобразований обнуляем элементы, стоящие под разрешающим элементом. Получаем табл. 6.5.

Табл. 6.5

БП	СЧ				Преобразования
			– 1
			– 1
		– 5		– 1
	– 17	– 7		– 2

Переменные образуют базис переменных: . Составим базисное решение , . Как видно, , то есть в результате шага симплекс-метода целевая функция уменьшила свое значение на 12.

4) Проверим базисное решение на оптимальность. Как видно из табл. 6.5, разрешающим столбцом является -столбец, разрешающим элементом – элемент 5. Происходит смена базиса: . В результате шага симплекс-метода получаем таблицу 6.6.

Табл. 6.6

БП	СЧ


		– 1	–
	–	– 4	–

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

, .

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒