Прямой алгоритм симплексного метода

1. Рассмотрим прямой алгоритм симплексного метода, в котором используется рассмотренный математический аппарат, имея в виду при этом представ­ление задачи линейного программирования в канони­ческой форме.

Задача линейного программирования может быть представлена в канонической форме следующим об­разом:

с помощью элементарных преобразований,

в результате преобразования в уравнения исходных ограничений, имеющих неравенства вида £ («меньше или равно»),

путем введения в уравнения системы некоторых ис­кусственных переменных.

Пусть задача линейного программирования пред­ставлена в канонической форме в следующем виде:

найти

x_j ³ 0 (j =1, 2, …, p, p +1, …, p + m) (5.1)

при условиях

(5.2)

c₁x₁ + c₂x₂ + ··· + c_px_p + c_p+1x_p+1 + ··· + c_p+mx_p+m = z à min (5.3)

В такой постановке задачи исходные уравнения сис­темы (5.2) содержат в числе других также m переменных x_p+1, x_p+2, …, x_p+m, при которых коэффициенты образу­ют единичную матрицу, или базис. Отметим, что порядковые номера базисных переменных здесь не играют роли; важно, чтобы каждая из таких переменных входила лишь в одно уравнение, причем с коэффициентом (+1).

В целевую функцию переменная может входить с любым коэффициентом (положительным, отрицательным или нулевым).

Для подготовки задачи к ее решению по прямому алгоритму выразим целевую функцию z через небазис­ные переменные. Для этого значения x_p+1, x_p+2, …, x_p+m, полученные соответственно из первого, второго, …, последнего уравнения системы (5.2), подставим в целе­вую функцию. Затем целевую функцию запишем в виде уравнения, перенеся z (со знаком минус) в одну часть вместе с переменными x_j, а свободный член c₀' (с обратным знаком) — в другую. Будем называть это уравнение целевым уравнением или z -строкой. Тогда задача будет представлена в следующем виде:

x_j ³ 0 (j =1, 2, …, p, p +1, …, p + m) (5.1)

удовлетворяющее соотношениям

(5.2)

c'₁x₁ + c'₂x₂ + ·· ·+ c'_px_p + (— z) = — c'₀ (5.3')

Систему уравнений (5.2) — (5.3') будем называть пред­ставленной в полной канонической форме, в которой, кроме базисных переменных x_p+1, x_p+2, …, x_p+m, пере­менную (— z) будем принимать также за базисную. [Учитывая, что базисные переменные принимаются с ко­эффициентами (+1) можно (— z) представить в виде, например, x_z ].

Для полной канонической формы базисным решением будет следующее: x₁= 0, х₂= 0, …, x_р= 0, x_p+1=b₁, x_р+2=b₂, …, x_р+m=b_m, z=c'₀, котороё принимается в качестве первоначального решения задачи. Поскольку каноническая форма вытекает из стандартной, а в последней свободные члены сделаны положительными ве­личинами, будем говорить, что задача представлена в допустимой канонической форме.

2. Как только что было установлено, каноническая форма позволяет непосредственно найти соответствую­щее базисное допустимое решение. Каноническую форму можно использовать также для выяснения, будет ли до­пустимое базисное решение минимальным, для чего ко­эффициенты c'_j (j = 1, 2, …, р) целевого уравнения про­веряются на оптимальность. Коэффициенты с'_j будем называть относительными оценками, так как их значе­ния зависят от выбора базисного множества переменных. Отмеченное выше основывается на следующих предло­жениях о критерии оптимальности:

А. Базисное допустимое решение является минималь­ным допустимым решением со значением z=c'₀, если все относительные оценки неотрицательны:

c'_j ³ 0(j = 1, 2, …, р)

Действительно, для канонической формы очевидно, что если все коэффициенты целевого уравнения неотрицательны, то наименьшая величина суммы c'₁x₁ + c'₂x₂ + ··· + c'_px_p + c'_p+1x_p+1 + ··· + c'_p+mx_p+m есть нуль при любом выборе неотрицательных x_j. Следовательно, наименьшая величина разности (z – c'₀) равна нулю и min z ³ c'₀. В частности, для допустимого базисного решения z=c'₀; по­этому min z ³ c'₀, и решение оптимально. Очевидно так­же следующее другое предложение.

Б. Пусть дано минимальное допустимое базисное ре­шение с относительными оценками с'_j ³ 0; тогда любое другое допустимое решение (не обязательно базисное) при x_j= 0 для всех c'_j > 0 также является минимальным решением. Если же это решение обладает тем свойст­вом, что для некоторого j как x_j > 0, так и c'_j > 0, то оно не может быть минимальным решением.

В. Базисное допустимое решение является минимальным допустимым решением, если c'_j > 0 для всех небазисных переменных.

3. В п. 1 нами получено первоначальное решение линейной задачи (в общем виде), которое является базис­ным допустимым решением. Теперь перейдем к другому базисному допустимому решению, улучшив последнее.

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

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

В первом столбце таблицы 1 записаны базисные переменные, а так­же базисная переменная (– z). В следующих столбцах пишем коэффициенты при переменных в полной канонической системе. В последнем столбце – свободные члены (компоненты вектора В). В последней строке записаны коэффициенты с_j, из линейной формы (целевой функ­ции).

Первая (исходная) таблица 1 имеет следующий вид:

Таблица 1

Симплекс-таблица (исходная).

А. Первым шагом в анализе первоначального допус­тимого базисного решения является проверка его на оп­тимальность. Она заключается в отыскании в последней z -строке максимального по модулю отрицательного коэффициента. Столбец c максимальным по модулю отрицательным коэффициентом (пусть это будет с'_k) назовём ключевым, а переменная этого столбца x_k будет новой базисной переменной, которая вводится в базис. В случае если окажется несколько равных по модулю отрицательных коэффициентов, то можно выбрать любой из них.

Если в z -строке отрицательных чисел нет, то получе­но минимальное (оптимальное) решение.

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

(a_ik > 0, a_rk > 0).

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

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

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

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

В. Переходим к построению следующей таблицы. В этой таблице прежде всего заполняются клетки строки x_r с вводимой переменной х_k. Для этого все элементы ключевой строки делятся на ключевой элемент; таким об­разом, x_r -уравнение разрешается относительно х_k. Полу­чаем следующие элементы строки:

, , …, , …, 1, …, , 0, …, , …, 0, .

С помощью элементарных преобразований системы уравнений можно, как известно, любую переменную исключить из всех уравнений системы, кроме какого-либо одного. В данном случае нам необходимо исключить пе­ременную х_k из всех уравнений (строк), кроме одного (ключевой строки). Чтобы исключить х_k из всех уравне­ний системы, надо, чтобы в клетках ключевого столбца (кроме ключевого элемента а_rk =1) на месте элементов а_1k, а_2k, …, а _{r-1; k}, а _{r+1; k}, …, а_mk были нули. Это достигается следующим образом. Пусть мы хотим исключить переменную х_k из i -гo уравнения. Для этого достаточно уравнение с ключевым элементом а_rk =1 умножить на (– а_ik) и прибавить к i -му уравнению. После исключе­ния х_k из всех уравнений система уравнений преобра­зуется в эквивалентную ей систему.

Остальные элементы таблицы (коэффициенты при переменных и свободные члены) будут связаны с коэф­фициентами при переменных и свободными членами ис­ходной системы так называемыми формулами исключе­ния;

(i r, a_rk > 0),

(i r, a_rk > 0).

Эти формулы легко запомнить, если посмотреть на прямоугольник в таблице 1, в вершины которого по­местить, например, элементы, входящие в формулу ис­ключения (эти элементы выделены в таблице 1). Для того чтобы найти элемент , который будет стоять в клетке новой таблицы на месте элемента a_ij надо из последнего вычесть произведение элементов (a_ik · a_rj), стоящих в вершинах побочной диагонали, и разделить на элемент а_rk, стоящий по главной диагонали. Указан­ное правило относится и к нахождению свободных чле­нов. Преобразованные по формулам исключения элемен­ты записываем в соответствующие клетки новой табли­цы. Для практических расчетов следует иметь в виду следующее:

в новой таблице на месте ключевого элемента пишем 1, а на месте остальных элементов ключевого столбца— нули;

если в ключевой строке (старой таблицы) окажется нуль, то соответствующий ему столбец переписываем в новой таблице без изменения;

если в ключевом столбце окажется нуль, то соответ­ствующую ему строку перепишем в новой таблице без изменения.

Отметим, что для нахождения элементов z -строки ис­пользуем те же формулы исключения.

Г. После того как составлена вторая симплексная таблица, просматриваем в ней z -строку, чтобы выявить, получено ли оптимальное (минимальное) решение с по­мощью критерия оптимальности. Если все элементы этой строки (соответствующие небазисным переменным) ока­жутся положительными или равными нулю, то получено оптимальное решение (, , …, х_k, …, ), для кото­рого имеем min z.

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

Затем устанавливаем, какая переменная будет выве­дена из базиса (по правилу, указанному в п. Б). Далее переходим к построению новой симплексной таблицы (по правилу, указанному в п. В), по z -строке которой уста­навливаем, получено ли оптимальное (минимальное) базисное решение, т. е. исследуем на оптимальность до­пустимое базисное решение.

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

Рассмотренный нами вычислительный процесс с по­мощью прямого алгоритма симплексного метода можно наглядно показать на блок-схеме 1.

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

Блок-схема 1

Алгоритм прямого симплекс-метода.