Симплекс-таблицы

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

Переход от одного базиса к другому при этом сводится к пересчету коэффициентов в таблицах, что осуществляется по чисто формальным правилам, хорошо приспособленным к тому же для решения на ЭВМ.

Пусть имеем систему ограничений вида (3.2), в которой r = n - m переменных (x₁,..., x_r) являются свободными, а оставшиеся m переменных (x_r+1, x_r+2,..., x_n) - базисными. Выразив базисные переменные через свободные, приведем систему к единичному базису, но запишем в виде, несколько отличном от системы (3.12) в том смысле, что все переменные (и свободные, и базисные) запишем в левой части, а в правой части - только свободные члены.

То есть в виде

x _r+1 – a _r+1,1 · x₁ - a _r+1,2 · x₂ -.. - a _r+1,p · x_p -.. - a _r+1,r · x_r = b _r+1

x _r+2 – a _r+2,1 · x₁ - a _r+2,2 · x₂ -.. - a _r+2,p· x_p -.. - a _r+2,r · x_r = b _r+2

.......... (3.15)

x _q – a _q,1 · x₁ - a _q,2 · x₂ -.. - a _q,p · x_p -.. - a _q,r · x_r = b _q

..........

x _n – a _n,1 · x₁ - a _n,2 · x₂ -.. - a _n,p · x_p -.. - a _n,r · x_r = b _n

а целевую функцию - в виде:

Ф - Г₁·x₁ – Г₂·x₂ -... - Г_p·x_p -... - Г_r·x_r = Г_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 называются оценками(индексами) соответствующих переменных x_j, строка таблицы, содержащая Г_j ,- индексной строкой.

В соответствии с описанным в предыдущем разделе симплекс-методом мы должны, прежде всего, выяснить имеется ли в выражении (3.13) линейной функции Ф = Гo + Г₁∙x₁ +... + Г_j∙x_j +... + Г_r∙x_r хотя бы один отрицательный коэффициент при свободных переменных x₁,..., x_r. Поскольку при записи в виде (3.16) и при внесении в таблицу 3.1 эти коэффициенты поменяли знаки, то мы должны, следовательно, выяснить имеются ли в последней строке таблицы положительные числа, не считая свободного члена Г_о.

Если таковых нет, то базисное решение, отвечающее данному базису, то есть (0;...; br+1,...; bq;...; bn) согласно случаю I является оптимальным, а

minФ = Го. Задача решена.

Предположим, что в последней строке имеется (не считая Го) положительная оценка - Гp>0. Отмечаем столбец, в котором она находится, вертикальной стрелкой. Этот столбец называется разрешающим столбцом.

Далее просматриваем другие элементы этого столбца. Если среди них нет положительных чисел, это означает, что все a_ip ≥ 0 (i = r+1,n) и задача подпадает под случай II, следовательно, min Ф = - ∞, задача решения не имеет.

И, наконец, пусть среди чисел отмеченного столбца, кроме последнего числа Г_p, имеется хотя бы один положительный элемент, например, - a_ip > 0; Это означает, что a_ip < 0, задача подпадает под случай III, то есть, необходимо сделать следующий шаг по поиску оптимального решения. Для этого строку таблицы, в которой находится данный положительный элемент (- a_ip) выберем в качестве разрешающей строки. Отметим эту строку горизонтальной стрелкой.

Если в разрешающем столбце имеется несколько положительных элементов, то для соответствующих строк таблицы составим оценочные отношения b_i/a_ip и выберем q-ю разрешающую строку из условия , где s– количество строк с положительными элементами в разрешающем р-ом столбце.

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

С этого момента начинается перестройка таблицы, цель которой состоит в переходе к новому базису, содержащему переменную x_p базисной вместо x_q (из таблицы 3.1 видно, что p ≤ r; r+1≤q ≤ n), то есть, q из числа базисных переменных, p - из числа свободных.

Перестройка осуществляется при помощи метода Джордана-Гаусса, как и в аналитическом симплекс-методе. А именно, умножим выделенную разрешающую q-ю строку на такое число, чтобы на месте разрешающего элемента появилась единица, то есть, умножим на 1/a_qp. Это соответствует тому, что q-ое уравнение разрешается относительно новой базисной переменной x_p.

Полученную таким образом строку запишем в новую таблицу на прежнее место, то есть в виде q-ой строки, но с новой базисной переменной x_p вместо x_q. Затем к каждой из остальных строк таблицы 3.1 прибавляем разрешающую строку, умноженную на такое число, чтобы в клетке отмеченного столбца появился нуль - это соответствует исключению неизвестной x_p из остальных уравнений, а также из выражения для Ф. Преобразованные таким образом строки пишем в новую таблицу на место прежних строк.

К новой таблице применяется та же процедура. В результате или находится оптимальное решение (случай I, в индексной строке таблицы нет положительных оценок), или обнаруживается, что minФ = - ∞ (случай II, в разрешающем столбце нет положительных элементов), или же производится следующий шаг по поиску оптимального решения (случай III, в разрешающем столбце имеются положительные элементы) – переходим к новой таблице. И так далее, пока процесс не остановится, то есть, пока не придем к случаю I или случаю II.

Рассмотренная процедура решения изложена применительно к задачам линейного программирования на отыскание минимального значения целевой функции. В задачах, в которых требуется определить максимальное значение целевой функции, анализ индексной строки сводится к выяснению наличия в этой строке отрицательных (кроме Г_о) оценок, что приводит к увеличению значения целевой функции относительно Ф_б = Г_о. в остальном подход к решению задачи сохраняется аналогичным рассмотренному.

Итак, при решении задач ЛП с помощью симплексных таблиц условием оптимальности в задачах на отыскание maxФ является отсутствие отрицательных оценок в индексной строке таблицы, в задачах на отыскание minФ - отсутствие положительных оценок в этой строке.

Вышеизложенное можно записать в виде следующего алгоритма.

1. Выделим исходный допустимый базис и заполним первую таблицу.

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

3. Пусть в оценочной строке имеется положительная оценка, скажем, Г_p (в столбце x_p). Отметим столбец x_p (разрешающий столбец) вертикальной стрелкой. Просматриваем остальные элементы этого столбца. Если среди них нет положительных чисел, то min Ф = -∞ - задача решения не имеет.

4. Если в разрешающем столбце имеются положительные элементы, для каждого из этих чисел a_kp (k ≤ r) составляем оценочное отношение b_k/a_kp, где b_k - первое число в этой строке (свободный член). Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке для базисной переменной x_q. Отметим эту строку (разрешающую строку) горизонтальной стрелкой. Отметим кружочком число a_qp, стоящее в пересечении разрешающей строки и разрешающего столбца - разрешающий элемент таблицы.

5. Переходим к новой таблице. Для этого отмеченную (разрешающую) строку умножаем на 1/a_qp (чтобы на месте разрешающего элемента появилась единица) и запишем ее в новой таблице на месте прежней с новой базисной переменной x_p. К каждой из остальных строк таблицы прибавляем разрешающую строку, умноженную на (-a_ip/a_qp), либо строку, полученную на месте разрешающей строки, умноженную на (-a_ip), чтобы элемент, стоящий в разрешающем столбце, обратился в 0. Полученную строку пишем на месте прежней.

6. С новой таблицей возвращаемся к выполнению пункта 2.

Примечания.

1) на практике при решении задач ЛП удобнее все переменные в столбцах симплекс-таблицы размещать в порядке возрастания их индексов (номеров), не разделяя их на базисные и свободные, как это было сделано в таблице 3.1 для удобства теоретического изложения;

2) практически удобнее все таблицы "пристыковывать" друг к другу (через строку) по вертикали, что позволяет для остальных таблиц, начиная со второй, не писать заглавную строку, то есть, "шапку" таблицы.

3) Если на каком-либо этапе расчета возникает неопределенность в выборе разрешающей строки (оказывается несколько равных минимальных отношений b_k/a_kp), то следует выбирать ту строку, для которой отношение элементов первого столбца свободных переменных к разрешающему столбу является наименьшим. Если при этом снова оказываются равные минимальные отношения, то составляют отношения элементов следующего столбца свободных переменных, и так до тех пор, пока разрешающая строка не определится однозначно.

***************

Пример 3.9. Найти наибольшее значение линейной функции

Ф = 7·x₁ + 5·x₂ → max

при ограничениях: 2·x₁ + 3·x₂ + x₃ = 19,

2·x₁ + x₂ + x₄ = 13,

3·x₂ + x₅ = 15,

3·x₁ + x₆ = 18.

******************** Р Е Ш Е Н И Е ********************

Задача дана в каноническом виде. Имеем систему 4 уравнений с 6 неизвестными переменными. Следовательно, m=4 переменные принять в качестве базисных, а r=n-m=2 переменные – в качестве свободных.

Шаг 1. Выберем в качестве свободных х₁ и х₂. Выразим базисные переменные х₃, х₄, х₅, х₆ через свободные, то есть, приведем систему уравнений к единичному базису и запишем в виде, удобном для применения симплекс-таблиц: x₃ + 2·x₁ + 3·x₂ = 19,

x₄ + 2·x₁ + x₂ = 13,

x₅ + 3·x₂ = 15,

x₆ + 3·x₁ = 18.

Целевая функция Ф = 7·x₁ + 5·x₂ уже выражена через свободные переменные, запишем ее в виде Ф - 7·x₁ - 5·x₂ = 0.

Заполним исходную таблицу (табл. 3.9.1).

Из этой таблицы определим первое базисное решение Х₁= (0; 0; 19; 13; 15; 18) – оно допустимое, и соответствующее значение целевой функции Ф₁= 0.

В индексной строке таблицы 3.9.1 имеются отрицательные оценки: -7 и –5 в столбцах х₁ и х₂. То есть, условие оптимальности не выполнено (при увеличении значений этих переменных значение Ф будет возрастать). Примем к рассмотрению, например, -5 в столбце х₂ (переведем ее в базисные) и выделим соответствующий (разрешающий) столбец стрелкой. В этом столбце имеются три положительных элемента: 3, 1, 3 в строках х₃, х₄, х₅.

Вычислим для этих строк оценочные отношения (разделим на эти числа соответствующие свободные члены), получим 19/3, 13/1, 15/3, из которых наименьшее - 15/3 - в строке для х₅. Следовательно, строка х₅ является разрешающей. Выделим ее стрелкой. Число 3, находящееся на пересечении разрешающей строки и разрешающего столбца, (обведено кружочком) является разрешающим элементом таблицы. На базе этого элемента переходим к новому базису, для чего переменные х₂ и х₅ меняем местами.

Шаг 2. Базисные переменные - х₃, х₄, х₂, х₆. Для составления следующей таблицы разрешающую строку таблицы 3.9.1 умножим на 1/3, чтобы получить на месте разрешающего элемента 1, и полученную таким образом строку пишем в новую таблицу 3.9.2 на месте прежней с базисной переменной х₂.

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

Теперь все рассуждения повторяются применительно к табл. 3.9.2. Вторым допустимым базисным решением является Х₂= (0; 5; 4; 8; 0; 18), при этом Ф₂= 25. В индексной строке таблицы 3.9.2 имеется отрицательная оценка –7 в столбце х₁ (разрешающий). Строка х₃ с наименьшим значением оценочного отношения является разрешающей строкой, элемент 2, находящийся на пересечении столбца х₁ и строки х₃, есть разрешающий элемент. На базе этого элемента переходим к новому базису, то есть, к следующей таблице 3.9.3.

Шаг 3. Базисные переменные – х₁, х₄, х₂, х₆. Из таблицы 3.9.3 находим третье допустимое базисное решение Х₃= (2; 5; 0; 4; 0; 12), при этом Ф₃= 39. В индексной строке таблицы имеется отрицательная оценка –11/6 в столбце х₅ (разрешающий столбец), в котором имеются 3 положительных элемента в строках х₄, х₂, х₆. Строка х₄ – разрешающая строка, элемент 2/3 – разрешающий элемент, на базе которого переходим к новому базису, то есть, к таблице 3.9.4.

Шаг 4. Базисные переменные – х₁, х₅, х₂, х₆. Четвертое допустимое решение Х₄= (5; 3; 0; 0; 6; 3), при этом Ф₄= 50. В индексной строке таблицы 3.9.4 нет отрицательных оценок, условие оптимальности выполнено, следовательно, получили оптимальное решение и наибольшее значение целевой функции.

Ответ: maxФ = 50 при Х_опт= (5; 3; 0; 0; 6; 3).