Симплекс-таблицы
Оказывается, производя расчеты по симплексному методу, нет необходимости выписывать все вычисления столь подробно, как мы рассматривали в предыдущем разделе, производить громоздкие преобразования системы линейных уравнений. Весь процесс можно записать в виде последовательности однотипно заполняемых таблиц, содержащих коэффициенты при переменных, причем каждому шагу оптимизации будет соответствовать переход к следующей таблице.
Переход от одного базиса к другому при этом сводится к пересчету коэффициентов в таблицах, что осуществляется по чисто формальным правилам, хорошо приспособленным к тому же для решения на ЭВМ.
Пусть имеем систему ограничений вида (3.2), в которой r = n - m переменных (x1, ..., xr) являются свободными, а оставшиеся m переменных (xr+1, xr+2, ..., xn) - базисными. Выразив базисные переменные через свободные, приведем систему к единичному базису, но запишем в виде, несколько отличном от системы (3.12) в том смысле, что все переменные (и свободные, и базисные) запишем в левой части, а в правой части - только свободные члены.
То есть в виде
x r+1 – a r+1,1 · x1 - a r+1,2 · x2 - . . - a r+1,p · xp - . . - a r+1,r · xr = b r+1
x r+2 – a r+2,1 · x1 - a r+2,2 · x2 - . . - a r+2,p· xp - . . - a r+2,r · xr = b r+2
. . . . . . . . . . (3.15)
x q – a q,1 · x1 - a q,2 · x2 - . . - a q,p · xp - . . - a q,r · xr = b q
. . . . . . . . . .
x n – a n,1 · x1 - a n,2 · x2 - . . - a n,p · xp - . . - a n,r · xr = b n
а целевую функцию - в виде:
Ф - Г1·x1 – Г2·x2 -... - Гp·xp - ... - Гr·xr = Гo (3.16)
(с целью упрощения записи значки «’» при коэффициентах и свободных членах уравнений в системе (3.15) упущены).
Системы (3.12) и (3.15) называются приведенными к единичному базису, имея в виду, что коэффициенты при базисных переменных составляют единичную матрицу Е.
Систему (3.15) и (3.16) можно представить в виде таблицы 3.1.
Таблица 3.1.
| Базисные перемен- ные | Свобод- ные члены | свободные переменные | Базисные переменные | ||||||||
| x1 | · · · | xp | · · · | xr | x r+1 | · · · | x q | · · · | x n | ||
| x r+1 | b r+1 | -ar+1,1 | · · · | -ar+1,p | · · · | -ar+1,r | · · · | · · · | |||
| · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · |
| x q | b q | -aq,1 | · · · | - a q,p | · · · | - a q,r | · · · | · · · | |||
| · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · | · · · |
| x n | b n | -an,1 | · · · | - a n,p | · · · | - a n,r | · · · | · · · | |||
| Ф | Гo | - Г1 | · · · | - Гp | · · · | - Гr | · · · | · · · |
Хб = (0; 0; ... ;0; b r+1; b r+2; ...; b n), при этом Фб = Го
Из таблицы 3.1 определим первое базисное решение Хб и соответствующее значение целевой функции Фб: значения базисных переменных и целевой функции «снимаются» из столбца свободных членов таблицы, а свободные переменные приравниваются нулю.
Здесь коэффициенты Гj называются оценками(индексами) соответствующих переменных xj, строка таблицы, содержащая Гj ,- индексной строкой.
В соответствии с описанным в предыдущем разделе симплекс-методом мы должны, прежде всего, выяснить имеется ли в выражении (3.13) линейной функции Ф = Гo + Г1∙x1 + ... + Гj∙xj + ... + Гr∙xr хотя бы один отрицательный коэффициент при свободных переменных x1, ..., xr. Поскольку при записи в виде (3.16) и при внесении в таблицу 3.1 эти коэффициенты поменяли знаки, то мы должны, следовательно, выяснить имеются ли в последней строке таблицы положительные числа, не считая свободного члена Го.
Если таковых нет, то базисное решение, отвечающее данному базису, то есть (0; . . .; br+1, . . .; bq; . . .; bn) согласно случаю I является оптимальным, а
minФ = Го. Задача решена.
Предположим, что в последней строке имеется (не считая Го) положительная оценка - Гp>0. Отмечаем столбец, в котором она находится, вертикальной стрелкой. Этот столбец называется разрешающим столбцом.
Далее просматриваем другие элементы этого столбца. Если среди них нет положительных чисел, это означает, что все aip ≥ 0 (i = r+1,n) и задача подпадает под случай II, следовательно, min Ф = - ∞, задача решения не имеет.
И, наконец, пусть среди чисел отмеченного столбца, кроме последнего числа Гp, имеется хотя бы один положительный элемент, например, - aip > 0; Это означает, что aip < 0, задача подпадает под случай III, то есть, необходимо сделать следующий шаг по поиску оптимального решения. Для этого строку таблицы, в которой находится данный положительный элемент (- aip) выберем в качестве разрешающей строки. Отметим эту строку горизонтальной стрелкой.
Если в разрешающем столбце имеется несколько положительных элементов, то для соответствующих строк таблицы составим оценочные отношения bi/aip и выберем q-ю разрешающую строку из условия 
, где s– количество строк с положительными элементами в разрешающем р-ом столбце.
Элемент таблицы, стоящий на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом. Обведем его кружком.
С этого момента начинается перестройка таблицы, цель которой состоит в переходе к новому базису, содержащему переменную xp базисной вместо xq (из таблицы 3.1 видно, что p ≤ r; r+1≤q ≤ n), то есть, q из числа базисных переменных, p - из числа свободных.
Перестройка осуществляется при помощи метода Джордана-Гаусса, как и в аналитическом симплекс-методе. А именно, умножим выделенную разрешающую q-ю строку на такое число, чтобы на месте разрешающего элемента появилась единица, то есть, умножим на 1/aqp. Это соответствует тому, что q-ое уравнение разрешается относительно новой базисной переменной xp.
Полученную таким образом строку запишем в новую таблицу на прежнее место, то есть в виде q-ой строки, но с новой базисной переменной xp вместо xq. Затем к каждой из остальных строк таблицы 3.1 прибавляем разрешающую строку, умноженную на такое число, чтобы в клетке отмеченного столбца появился нуль - это соответствует исключению неизвестной xp из остальных уравнений, а также из выражения для Ф. Преобразованные таким образом строки пишем в новую таблицу на место прежних строк.
К новой таблице применяется та же процедура. В результате или находится оптимальное решение (случай I, в индексной строке таблицы нет положительных оценок), или обнаруживается, что minФ = - ∞ (случай II, в разрешающем столбце нет положительных элементов), или же производится следующий шаг по поиску оптимального решения (случай III, в разрешающем столбце имеются положительные элементы) – переходим к новой таблице. И так далее, пока процесс не остановится, то есть, пока не придем к случаю I или случаю II.
Рассмотренная процедура решения изложена применительно к задачам линейного программирования на отыскание минимального значения целевой функции. В задачах, в которых требуется определить максимальное значение целевой функции, анализ индексной строки сводится к выяснению наличия в этой строке отрицательных (кроме Го) оценок, что приводит к увеличению значения целевой функции относительно Фб = Го. в остальном подход к решению задачи сохраняется аналогичным рассмотренному.
Итак, при решении задач ЛП с помощью симплексных таблиц условием оптимальности в задачах на отыскание maxФ является отсутствие отрицательных оценок в индексной строке таблицы, в задачах на отыскание minФ - отсутствие положительных оценок в этой строке.
Вышеизложенное можно записать в виде следующего алгоритма.
1. Выделим исходный допустимый базис и заполним первую таблицу.
2. Если в индексной строке полученной таблицы нет положительных оценок, кроме Го, то базисное решение является оптимальным - задача решена.
3. Пусть в оценочной строке имеется положительная оценка, скажем, Гp (в столбце xp). Отметим столбец xp (разрешающий столбец) вертикальной стрелкой. Просматриваем остальные элементы этого столбца. Если среди них нет положительных чисел, то min Ф = -∞ - задача решения не имеет.
4. Если в разрешающем столбце имеются положительные элементы, для каждого из этих чисел akp (k ≤ r) составляем оценочное отношение bk/akp, где bk - первое число в этой строке (свободный член). Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке для базисной переменной xq. Отметим эту строку (разрешающую строку) горизонтальной стрелкой. Отметим кружочком число aqp, стоящее в пересечении разрешающей строки и разрешающего столбца - разрешающий элемент таблицы.
5. Переходим к новой таблице. Для этого отмеченную (разрешающую) строку умножаем на 1/aqp (чтобы на месте разрешающего элемента появилась единица) и запишем ее в новой таблице на месте прежней с новой базисной переменной xp. К каждой из остальных строк таблицы прибавляем разрешающую строку, умноженную на (-aip/aqp), либо строку, полученную на месте разрешающей строки, умноженную на (-aip), чтобы элемент, стоящий в разрешающем столбце, обратился в 0. Полученную строку пишем на месте прежней.
6. С новой таблицей возвращаемся к выполнению пункта 2.
Примечания.
1) на практике при решении задач ЛП удобнее все переменные в столбцах симплекс-таблицы размещать в порядке возрастания их индексов (номеров), не разделяя их на базисные и свободные, как это было сделано в таблице 3.1 для удобства теоретического изложения;
2) практически удобнее все таблицы "пристыковывать" друг к другу (через строку) по вертикали, что позволяет для остальных таблиц, начиная со второй, не писать заглавную строку, то есть, "шапку" таблицы.
3) Если на каком-либо этапе расчета возникает неопределенность в выборе разрешающей строки (оказывается несколько равных минимальных отношений bk/akp), то следует выбирать ту строку, для которой отношение элементов первого столбца свободных переменных к разрешающему столбу является наименьшим. Если при этом снова оказываются равные минимальные отношения, то составляют отношения элементов следующего столбца свободных переменных, и так до тех пор, пока разрешающая строка не определится однозначно.
***************
Пример 3.9. Найти наибольшее значение линейной функции
Ф = 7·x1 + 5·x2 → max
при ограничениях: 2·x1 + 3·x2 + x3 = 19,
2·x1 + x2 + x4 = 13,
3·x2 + x5 = 15,
3·x1 + x6 = 18.
******************** Р Е Ш Е Н И Е ********************
Задача дана в каноническом виде. Имеем систему 4 уравнений с 6 неизвестными переменными. Следовательно, m=4 переменные принять в качестве базисных, а r=n-m=2 переменные – в качестве свободных.
Шаг 1. Выберем в качестве свободных х1 и х2. Выразим базисные переменные х3, х4, х5, х6 через свободные, то есть, приведем систему уравнений к единичному базису и запишем в виде, удобном для применения симплекс-таблиц: x3 + 2·x1 + 3·x2 = 19,
x4 + 2·x1 + x2 = 13,
x5 + 3·x2 = 15,
x6 + 3·x1 = 18.
Целевая функция Ф = 7·x1 + 5·x2 уже выражена через свободные переменные, запишем ее в виде Ф - 7·x1 - 5·x2 = 0.
Заполним исходную таблицу (табл. 3.9.1).
Из этой таблицы определим первое базисное решение Х1= (0; 0; 19; 13; 15; 18) – оно допустимое, и соответствующее значение целевой функции Ф1= 0.
В индексной строке таблицы 3.9.1 имеются отрицательные оценки: -7 и –5 в столбцах х1 и х2. То есть, условие оптимальности не выполнено (при увеличении значений этих переменных значение Ф будет возрастать). Примем к рассмотрению, например, -5 в столбце х2 (переведем ее в базисные) и выделим соответствующий (разрешающий) столбец стрелкой. В этом столбце имеются три положительных элемента: 3, 1, 3 в строках х3, х4, х5.
Вычислим для этих строк оценочные отношения (разделим на эти числа соответствующие свободные члены), получим 19/3, 13/1, 15/3, из которых наименьшее - 15/3 - в строке для х5. Следовательно, строка х5 является разрешающей. Выделим ее стрелкой. Число 3, находящееся на пересечении разрешающей строки и разрешающего столбца, (обведено кружочком) является разрешающим элементом таблицы. На базе этого элемента переходим к новому базису, для чего переменные х2 и х5 меняем местами.
Шаг 2. Базисные переменные - х3, х4, х2, х6. Для составления следующей таблицы разрешающую строку таблицы 3.9.1 умножим на 1/3, чтобы получить на месте разрешающего элемента 1, и полученную таким образом строку пишем в новую таблицу 3.9.2 на месте прежней с базисной переменной х2.
К каждой из остальных строк прибавляем разрешающую, умноженную на такое число (коэффициент перехода), чтобы в соответствующих клетках столбца для х2 появились нули, и преобразованные строки запишем в новую таблицу на прежние места. Этим завершается 1 итерация.
Теперь все рассуждения повторяются применительно к табл. 3.9.2. Вторым допустимым базисным решением является Х2= (0; 5; 4; 8; 0; 18), при этом Ф2= 25. В индексной строке таблицы 3.9.2 имеется отрицательная оценка –7 в столбце х1 (разрешающий). Строка х3 с наименьшим значением оценочного отношения является разрешающей строкой, элемент 2, находящийся на пересечении столбца х1 и строки х3, есть разрешающий элемент. На базе этого элемента переходим к новому базису, то есть, к следующей таблице 3.9.3.
Шаг 3. Базисные переменные – х1, х4, х2, х6. Из таблицы 3.9.3 находим третье допустимое базисное решение Х3= (2; 5; 0; 4; 0; 12), при этом Ф3= 39. В индексной строке таблицы имеется отрицательная оценка –11/6 в столбце х5 (разрешающий столбец), в котором имеются 3 положительных элемента в строках х4, х2, х6. Строка х4 – разрешающая строка, элемент 2/3 – разрешающий элемент, на базе которого переходим к новому базису, то есть, к таблице 3.9.4.
Шаг 4. Базисные переменные – х1, х5, х2, х6. Четвертое допустимое решение Х4= (5; 3; 0; 0; 6; 3), при этом Ф4= 50. В индексной строке таблицы 3.9.4 нет отрицательных оценок, условие оптимальности выполнено, следовательно, получили оптимальное решение и наибольшее значение целевой функции.
Ответ: maxФ = 50 при Хопт= (5; 3; 0; 0; 6; 3).