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

Лекция 3. Симплекс-метод решения задачи ЛП Симплексный метод является основным методом решения задач линейного программирования. Он применяется к задаче, записанной в канонической форме , (3.1) , (3.2) (j=1,2,…,n), (3.3) где (i=1,2,…,m). Система ограничений (3.2) может быть представлена в векторной форме (3.4) где - векторы: ,…,, Равенство (3.4) можно рассматривать как разложение вектора по векторам . В этом случае переменные или компоненты вектора суть коэффициенты разложения вектора . Напомним, что вектор называется планом или допустимым решением задачи линейного программирования, если он удовлетворяет условиям (3.2) и (3.3). План называется опорным, если положительным (ненулевым) компонентам вектора X соответствуют линейно независимые векторы в разложении (3.4). Опорный план называется невырожденным, если он содержит m ненулевых компонент, в противном случае план называется вырожденным. План, доставляющий наименьшее (наибольшее) значение линейной функции (3.1) называется оптимальным планом или решением задачи линейного программирования. Множество планов данной задачи образует многогранник в m-мерном пространстве, называемый многогранником решений. В теории линейного программирования доказывается, что если целевая функция ограничена на многограннике решений, то существует такая угловая точка (вершина) многогранника, в которой целевая функция достигает своего наименьшего (наибольшего) значения, и что каждой угловой точке соответствует опорный план. Следовательно, для отыскания оптимального плана достаточно исследовать только опорные планы. Симплексный метод позволяет переходить от одного опорного плана к другому, более близкого к оптимальному. Геометрически симплекс-метод можно трактовать, как перемещение по ребрам многогранника решений от вершины к вершине в строну оптимального плана. Симплексный метод можно применить, если известен какой-нибудь исходный опорный план. Такой опорный план можно непосредственно записать, если в разложении (3.4) имеется m линейно независимых единичных векторов . Пусть, например, т.е. система ограничений (3.2) имеет вид . (3.5) Единичные векторы образуют базис m-мерного векторного пространства; соответствующие им переменные называют базисными, а остальные переменные свободными. Полагая в системе уравнений (4.5) свободные переменные равными нулю, получаем Вектор является опорным планом, так как он удовлетворяет системе ограничений (3.5), его компоненты неотрицательны и нулевым компонентам соответствуют линейно зависимые векторы . Проверку исходного опорного плана на оптимальность и дальнейшие вычисления удобно вести в специальной, так называемой симплексной таблице, в которую вначале заносят исходные данные задачи (табл. 3.1). После заполнения таблицы вычисляют показатели (m+1)-й строки. В этой строке в столбце записывается значение целевой функции , соответствующее первоначальному опорному плану , (3.6) а в следующих столбцах – величины , (3.7) называемые оценками плана. Оценки служат критерием оптимальности плана. Если при решении задачи на минимум целевой функции все оценки неположительные (j=1,2,..,n), (3.8) то план является оптимальным. При решении задачи на максимум условие оптимальности – неотрицательность всех оценок: (j=1,2,…,n). (3.9) Если условие оптимальности нарушено хотя бы для одной из оценок, то необходимо в соответствующем столбце просмотреть величины : если все хотя бы для одного из таких столбцов, то задача линейного программирования не имеет решений (целевая функция не ограничена в области допустимых решений). Если же в столбце, где нарушено условие оптимальности, есть положительные величины , то нужно перейти к другому опорному плану. Перейти к новому опорному плану – значит разложить вектор по другому базису. Новый базис можно получить, выведя из старого базиса один из векторов и введя в него один из небазисных векторов. В принципе, модно вводить в базис любой из векторов, однако для целенаправленного и наиболее быстрого движения к оптимуму применяется следующий алгоритм выбора вектора, вводимого в базис. 1. Для каждого столбца с нарушением условия оптимальности вычисляется величина , где минимум берется по тем i, для которых . Соответствующее значение каким-либо образом отмечается в таблице. 2. Вычисляются величины и определяется (3.11) при решении задачи на минимум и (3.12) при решении задачи на максимум. Элемент , отмеченный на предыдущем шаге и стоящий в столбце, соответствующем условию (3.11) или (3.12), выделяется в качестве ведущего элемента; строка и столбец, содержащие ведущий элемент, называются направляющими. Если имеется несколько одинаковых максимальных значений при решений задачи на минимум, то в соответствующих столбцах ведущим элементом выбирается отмеченный элемент в столбце, которому соответствует наименьшее . В аналогичном случае при решении задачи на максимум ведущим принимается отмеченный элемент в столбце, которому соответствует наибольшее . 3. С учетом выбранного ведущего элемента выполняется преобразование по методу полного исключения над всеми элементами столбцов , включая (m+1)-ю строку, и заполняется новая симплексная таблица (табл. 3.2). При этом вектор направляющей строки выводится из базиса, а вектор направляющего столбца становится базисным. Правильность вычислений проверяется пересчетом элементов (m+1)-й строки по формулам (3.6),(3.7). В столбце стоят компоненты нового опорного плана . Если для нового опорного плана выполнены условия оптимальности, то решение задачи на этом заканчивается. Если условия оптимальности не выполнены, то, как и на предыдущем шаге, выясняем, не оказалась ли задача неразрешимой и если нет, то переходим к следующему опорному плану, повторяя шаги 1-3. Как известно из теории, после конечного числа таких этапов(итераций) мы либо приходим к оптимальному плану, либо убеждаемся в том, что задача не имеет решения. (Мы пренебрегаем возможностью так называемого зацикливания ввиду того, что оно практически не встречается в реальных задачах). Если в симплексной таблице с оптимальным опорным планом нулевые оценки соответствуют только базисным векторам, то оптимальный план единственный. Если ненулевые оценки есть у небазисных векторов, то решение неединственное. Таблица 3.1 I Базис … … … … … … … … 1 1 … … … … 2 1 … … … … … … … … … … … … … … … … … … … r … 1 … … … … … … … … … … … … … … … … … … m … … 1 … … m+1 … … … … Таблица 3.2 I Базис … … … … … … … … 1 1 … … … … 2 1 … … … … … … … … … … … … … … … … … … … r … … … 1 … … … … … … … … … … … … … … … … m … … 1 … … m+1 … … … … Пример 1. Симплексным методом решить следующую задачу линейного программирования: , (j=1,2,…,6). Решение. Задача записана в канонической форме, система ограничений имеет положительные правые части и содержит три единичных линейно независимых вектора , поэтому можем заполнить первую симплексную таблицу (табл. 3.3.). Таблица 3.3 i Базис 1 1 1 1 1 5 1 -1 -2 2 1 3 1 2 -3 1 3 1 5 1 2 -5 6 m+1 13 3 -8 5 Вносим в нее исходные данные задачи и вычисляем элементы (m+1)-й строки. Значение вычисляется следующим образом: элементы столбца умножаются на соответствующие элементы столбца (компоненты вектора ) и эти произведения суммируются: . Значения оценок вычисляются аналогично, но из суммы произведений вычитается соответствующее значение , записанное сверху в шапке таблицы, например и т.д. . Среди оценок есть положительные ( и ), значит первоначальный опорный план не оптимальный и необходимо перейти к новому опорному плану. Такой переход возможен, так как в столбцах и , где нарушено условие оптимальности, есть положительные элементы . Находим и отмечаем элемент , дающий этот минимум, а также находим и отмечаем элемент Затем вычисляем и Поскольку решается задача на минимум и , то в базис надо ввести вектор , а так как ведущий элемент стоит во второй строке (взят в рамочку в табл. 4.4), то из базиса выводится вектор . Таблица 3.4 i Базис 1 1 1 1 1 13/2 1 ½ -3/2 -3/2 2 3/2 ½ 1 -3/2 ½ 3 1 2 -1 1 -2 5 m+1 17/2 -3/2 -7/2 7/2 Чтобы не сбиться в дальнейших вычислениях, рекомендуется выделить записанную направляющую строку, а рядом записывать множители, умножая на которые эту строку и складывая с остальными строками первой таблицы, будем получать соответствующие строки во второй таблице. В качестве множителей берем соответствующие элементы столбца с противоположными знаками. Перевычисляемую строку в первой симплексной таблице рекомендуется отделить с помощью линейки или полоски бумаги с тем, чтобы опять же не сбиться в вычислениях. Заполнив вторую симплексную таблицу, пересчитываем элементы (m+1)-й строки по формулам (3.6),(3.7): … Убедившись в правильности расчетов, приступаем к анализу второй таблицы: план не оптимальный – есть положительная оценка , и так как в столбце есть положительные элементы, то можем перейти к следующему опорному плану. Находим , выделяем ведущий элемент и, выполняя преобразования по методу полного исключения, заполняем третью симплексную таблицу (табл.3.5) и проверяем ее Таблица 3.5 i Базис 1 1 1 1 1 71/10 1 1/5 3/10 -21/10 2 13/10 3/5 -1/10 1 -13/10 3 2/5 -1/5 1/5 -2/5 1 3/2 ½ 7/2 m+1 71/10 -4/5 -7/10 -21/10 Пересчетом элементов последней строки. Все оценки в этой таблице неположительны, следовательно, записанный в ней опорный план является оптимальным, минимизирующим целевую функцию. Значения базисных переменных , записанные в таблице в столбце , свободные переменные равны нулю, т.е. . Минимальное значение целевой функции записано в (m+1)-й строке столбца : . Заметим, что последовательные симплексные таблицы записываются вместе под одной общей шапкой.