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

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

, .

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


Интересные записи:

Понравилась статья? Поделиться с друзьями: