4. Выражаем целевую функцию через небазисные переменные

Из каждого уравнения (21) выразим x_j(i) и подставим в (19):

или

22 , где и . (22)

Из (22) получаем выражение для z, в котором участвуют только небазисные переменные:

23 . (23)

Замечание 4. Если (x, z) удовлетворяет условию (17), то z = f (x) для любого х. Если же для (x, z) выполнено (22) или (23), то z = f (x) только для х, удовлетворяющих (21) (и, следовательно, допустимых в исходной задаче), так как соотношения (21) использовались при выводе (22). В частности, при х = х⁰ имеем для j  N() (см. замечание 3) и из (22) следует, что

24 . (24)

Таким образом, F есть значение ЦФ (14) на векторе х⁰ = х^ (см. определение 6), который на этом этапе является текущим БДР. □

Определение 8. Рассмотрим задачу ЛП с матрицей А размерности m × n,  — произвольный базис матрицы А и N() = { j(1),…, j(m)}. Задача приведена к базису , если:

(а) она записана в канонической форме;

(б) целевая функция выражена через небазисные переменные;

(в) в каждом уравнении есть базисная переменная (x_j(i) для уравнения i), которая входит в него с коэффициентом 1 и не входит в другие уравнения. □

Замечание 5. Задачу (14) – (16) можно привести к базису , т. е. преобразовать в эквивалентную задачу, приведенную к базису :

(а) систему уравнений A⁰ = b⁰ умножить слева на (если базис  допустим, то правые части уравнений преобразованной системы будут неотрицательны);

(b) условие неотрицательности переменных сохранить;

(c) целевую функцию представить в виде , где _j = 0 для j  N(), а _j для j  N() и константа F рассчитаны по формулам (22).

По замечанию 4 значение ЦФ на базисном решении системы уравнений (15), порожденном базисом , равно F. □

Формулы (21) и (22) описывают результат приведения задачи (14) – (16) к текущему базису.

5. Проверяем оптимальность текущего базисного решения

Теорема 1 (признак оптимальности). Если в (22) _j  0 для всех j, то текущее БДР является оптимальным решением задачи (14) – (16).

Доказательство в [9, с. 144]. □

Эта теорема оправдывает следующее определение.

Определение 9. Если в (22) _j  0 для всех j, то текущий допустимый базис назовем оптимальным. □

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

6. Проверяем ограниченность задачи

Теорема 2 (признак неограниченности задачи). Если существует такое s, что _s < 0 в (22) и a_is ≤ 0 в (21) для всех i, то задача (14) – (16) неограниченна.

Доказательство в [9, с. 145]. □

Если выполнены условия теоремы 2, то задача неограниченна, процесс решения закончен; иначе переходим к следующему шагу.

7. Переход к другому базису 2

Если мы дошли до этого этапа, то по теоремам 1 и 2 существует такое s, что s  N(), _s < 0 и a_rs > 0 для какого-то r.

Заметим, что a ^s не является линейной комбинацией столбцов a ^j(i), i  r (так как в отличие от a ^s они имеют нули в строке r). Поэтому столбцы a ^j(i), i  r и a ^s линейно независимы. Тогда и в исходной матрице А⁰ соответствующие столбцы линейно независимы и образуют базис , где k(i) = j(i) при i  r и k(r) = s (вводим в базис столбец вместо ).

Базису  соответствует вектор (см. определение 6). Выясним, является ли допустимым решением и как изменяется значение ЦФ при переходе от х⁰ к .

Замечание 6. Чтобы это выяснить, достаточно уравнение (21) с номером r разделить на a_rs, выразить из него переменную х_s (в этом выражении не будут участвовать базисные переменные x_j(i) для j  r), а результат подставить в остальные уравнения (21) – (22). Тогда х_s станет базисной переменной для уравнения r (войдет в него с коэффициентом 1 и исчезнет из других уравнений и из ЦФ). Коэффициенты при переменных x_j(i) для j  r не изменятся. Другими словами, мы приведем задачу к новому базису  (см. определение 8). Тогда, в соответствии с замечанием 3, справа в преобразованных ограничениях (21) окажутся базисные (относительно базиса ) компоненты вектора . Если они неотрицательны, то есть БДР. А правая часть (22) после подстановки укажет значение ЦФ на (см. замечание 5). □

Способ, которым мы исключим х_s из уравнений (21) с отличными от r номерами и из (22), называется жордановым исключением и является составной частью метода Жордана–Гаусса для решения систем линейных алгебраических уравнений. Столбец a^s и строку a_r матрицы А будем называть направляющими, а ее элемент a_rs — разрешающим. Подчеркнем, что направляющий столбец a^s и направляющую строку a_r мы выбрали так, что _s < 0 и a_rs > 0.

Не принимая пока во внимание специфическую структуру матрицы А, запишем уравнения (21) в общем виде, выделив переменную x_s:

25 (25)

Разделим обе части уравнения (25) с номером r на a_rs  0:

26 (26)

Для каждого i  r умножим (26) на a_is и результат вычтем из (25) (исключим x_s):

27 (27)

В результате уравнения (25) примут вид , где

28 при при i  r (28)

29 (29)

30 (30)

Здесь (28) описывает преобразованные элементы направляющей строки r в соответствии с (26) и направляющего столбца s с учетом того, что x_s отсутствует в (27); соотношения (29) получены из (27); наконец, выражения (30) для правых частей преобразованных уравнений очевидным образом следуют из (26) и (27).

Итак, (см. замечание 6). При каких условиях этот вектор неотрицателен? Вспомним, что b  0 (так как это базисная часть БДР х⁰, порожденного базисом ) и a_rs > 0. Тогда и по (30). В соответствии с (30), при i  r эквивалентно неравенству

Если a_is ≤ 0, то последнее неравенство выполняется, так как его левая часть неположительна, а правая — неотрицательна. Если же a_is > 0, то разделив на это число обе части неравенства, получим условие

31 (31)

Мы получили правило выбора направляющей строки: если направляющий столбец зафиксирован, то из строк, где он имеет положительные элементы, следует выбрать ту, для которой отношение правой части к элементу направляющего столбца минимально. Из (30) следует, что это минимальное отношение равно  — значению переменной x_s в новом БДР (в предшествующем БДР х⁰ она была равна нулю как небазисная). Напротив, переменная x_j(r), которая в х⁰ могла иметь положительное значение, теперь стала небазисной и равна нулю.

Таким образом, при правильном выборе направляющей строки мы построим новое БДР с базисом , который получается из  заменой столбца столбцом ; переменная x_s становится базисной для строки r (вместо x_j(r)). Понятно, что

32N( ) \ {s} = N() \ {j(r)}. (32)

Запишем (22) в виде

, где

_j для j  N() определены в (22) и _j = 0 для j  N(). Вычтем отсюда уравнение (26), умноженное на _s . Получим

33 (33)

Пусть j  N( ) и j  s. Тогда j  N() по (32) и _j = 0. Матрица А соответствует системе уравнений, приведенной к базису , переменная x_j является базисной для некоторой строки i, j = j(i), поэтому столбец a ^j имеет ненулевой элемент только в этой строке. Но i  r, так как из (32) следует j  j(r). Поэтому a_rj = 0. Следовательно, при j  N( ) в (33), в левую часть этого равенства с ненулевыми коэффициентами входят только небазисные (для базиса ) переменные, которые в соответствующем БДР равны нулю.

По замечанию 4 z = f (x) в (33) для любого допустимого решения х. При х = из (33) и (24) следует, что

34 (34)

Замечание 7. Вспомним, что b  0 (так как базис  допустим), _s < 0 и a_rs > 0 по выбору r и s. Поэтому (34) влечет . Если , то значение ЦФ при переходе к новому БДР возрастает. Если же b_r = 0, то , а БДР х₀ вырожденно (см. определение 7), так как b_r — значение его базисной компоненты . Кроме того, при b_r = 0 из (30) следует для всех i, а тогда : построен новый базис для той же вершины. □

В любом случае задача приведена к новому базису, он становится текущим, становится текущим БДР, и мы возвращаемся к проверке оптимальности текущего БДР.