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.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, нет ни одного положительного числа. В соответствии с критерию оптимальности, базовое ответ есть оптимальным. Возвращаясь к исходной задаче, записываем ответ:
, .