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

Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней к соседней, в которой линейная функция принимает лучшее значение до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели.

Пример решения задачи симплексным методом

Задача 1 (п.4.2).

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком “плюс”, так как все неравенства имеют вид «≤».

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

,

,

,

.

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

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

i шаг. Основные переменные: х₃, х₄, х₅, х₆. неосновные переменные: х₁, х₂. Выразим основные переменные через неосновные:

 ,                                                (7)

Положив неосновные переменные равными нулю, т.е. х₁ =0, х₂ = 0, получим базисное решение х₁= (0; 0; 18; 16; 5; 21), которое является допустимым и соответствует вершине О (0;0) многогранника ОАВСDЕ на рис. 2.

 

Рис. 2

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

При решении х₁ значение функции равно . Легко понять, что функцию f можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для f с положительным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная будет неосновной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функций “лучше” (по крайней мере “не хуже”). В данном примере для увеличения f можно переводить в основные либо х₁, либо х₂, так как обе эти переменные входят в выражение дня f со знаком “плюс”. Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент, т.е. в данном случае х₂ (такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки).

Система (1) накладывает ограничения на рост переменной х₂. поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁ = 0 как неосновная переменная):

откуда  

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

Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом ∞. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение). Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ =min (18/3; 16/1; 5/1; ∞} =5. при х₂ =5 переменная х₅ обращается в нуль и переходит в неосновные.

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

ii шаг. Основные переменные: х₂, х₃,х₄, х₆. неосновные переменные: х₁, х₅.

Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х₂):

 

или

                                                                                   (8)

Второе базисное решение  является допустимым и соответствует вершине а (0;5) на рис. 2. Геометрическая интерпретация перехода от х₁ к х₂ — переход от вершины о к соседней вершине а на многоугольнике решений ОАBCDЕ.

Выразив линейную функцию через неосновные переменные на этом шаге, получаем:

 

Значение линейной функции f₂ = f (х₂) =15. изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной функции; в данном случае    

Однако значение f₂ не является максимальным, так как повторяя рассуждения 1 шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной х₁, входящей в выражение для f с положительным коэффициентом. Система уравнений (8) определяет наибольшее возможное значение для х₁: х₁ = min{∞;3/1;11/2; ∞} = 3. второе уравнение является разрешающим, переменная х₃ переходит в неосновные, при этом  

iii шаг. Основные переменные: х₁, х₂, х₄, х₆. неосновные переменные х₃, х₅.

Как и на ii шаге, выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х_i). после преобразований получаем:

,

,

,                                                                                (9)

.

Базисное решение х₃ = (3; 5; 0; 5; 0; 12) соответствует вершине в (3;5). выражаем линейную функцию через неосновные переменные . Проверяем:  Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х₅ в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х₅ в основную переменную. при определении наибольшего возможного значения для х₅ следует обратить внимание на первое уравнение в системе (9), которое не дает ограничений на рост х₅, так как свободный член и коэффициент при х₅ имеют одинаковые знаки. Поэтому . Третье уравнение является разрешающим, и переменная х₄ переходит в неосновные; .

iv шаг. Основные переменные: х₁, х₂, х₅, х₆. неосновные переменные: х₃, х₄.

После преобразований получим:

,

,

,

.

Базисное решение  соответствует вершине с (6; 4) на рис. 2.

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

Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции  и 4 единиц продукции  Дополнительные переменные х₃, х₄, х₅, х₆ показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптимальном плане производства , т.е. остатки ресурсов s₁ и s₂ равны нулю, а остатки, ресурсов s₃ и s₄ равны соответственно 1 и 3 единицам.

Метод искусственного базиса

Суть метода: в каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную у₁,у₂,…, у_k, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию  где м - произвольно большое число, и ищем ее максимум (т-задача). Назовём м-функцией выражение . Справедлива теорема:

1. Если в оптимальном решении т-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е.  т.е. минимум м-функции равен 0).

2. Если имеется оптимальное решение т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

3. Если Т_max= ∞, то исходная задача также неразрешима, причем либо f_max=∞, либо условия задачи противоречивы.

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