8. Конечность симплекс-метода

Определение 10. Последовательность операций от проверки оптимальности текущего БДР до построения нового базиса и приведения задачи к этому базису образуют итерацию симплекс-метода. □

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

Может быть более одного “претендента” на роль направляющего столбца (если задача ограниченна и в (22) не одно отрицательное _j) или направляющей строки (если в (31) минимум достигается не для одного i). При правильном разрешении таких “спорных” случаев базисы не повторяются и алгоритм конечен (так как базисов конечное число [9, замечание 29] ). А именно: из подходящих столбцов следует выбирать столбец с наименьшим номером, а из подходящих строк — ту, которой соответствует базисная переменная с наименьшим номером. Это алгоритм Блэнда [9, с. 150]. Следовательно, симплекс-метод завершает работу за конечное число шагов.

Замечание 8. Если задача совместна, то за конечное число итераций симплекс-метод либо обнаружит, что она неограниченна, либо построит оптимальное решение и оптимальный базис (см. определение 9). Следовательно, для разрешимости линейной задачи максимизации необходимо и достаточно, чтобы она была совместна и ее ЦФ была ограниченна сверху на множестве допустимых решений (в задаче минимизации ЦФ, естественно, должна быть ограниченна снизу). Это утверждение справедливо для произвольной задачи ЛП, так как разрешимость, совместность, ограниченность задачи эквивалентны соответственно разрешимости, совместности, ограниченности ее канонической формы, к которой мы применяем симплекс-метод [9, замечание 26]. □

Замечание 9. Из описания симплекс-метода ясно, что, если задача ЛП разрешима, он всегда находит базисное оптимальное решение ее канонической формы и оптимальный базис для этого решения. □

9. Построение исходного базисного допустимого решения 3

В некоторых случаях исходное БДР возникает без дополнительных усилий, как, например, в задаче, записанной в стандартной форме (9), при переходе ее к канонической форме, где столбцы переменных недостатка образовали базис; задача оказалась приведенной к этому базису, так как ЦФ не зависит от переменных недостатка.

В общем случае исходное БДР можно найти следующим методом искусственного базиса [1, гл. V, § 5].

Пусть дана задача в канонической форме (14) – (16). Будем считать, что (этого можно добиться, умножив некоторые уравнения на –1). Снимем сделанное в начале раздела 1.3. предположение о линейной независимости строк матрицы А⁰.

В левую часть каждого уравнения введем неотрицательную вспомогательную переменную t_i (если какая-то переменная входит в уравнение i с коэффициентом 1 и не входит в другие уравнения, то можно включить в исходный базис столбец этой переменной, а переменную t_i не вводить). Положим и рассмотрим задачу

35 (35)

Это задача ЛП. Полагая t = b⁰ и х = 0, получим ее БДР с базисом, состоящим из столбцов вспомогательных переменных. Задача имеет оптимальное решение, так как ее ЦФ ограничена сверху нулем (см. замечание 8). Исходное БДР известно, поэтому к задаче (35) можно применить описанный выше симплекс-метод. Найдем оптимальное базисное решение задачи (35) (x^*, t^*) с базисом . Пусть NX() и NT() — множества номеров основных и, соответственно, вспомогательных базисных переменных. Возможны следующие случаи.

Случай 1: t^*  0. Тогда g(x^*,t^*) < 0 и задача (14) – (16) несовместна.

Случай 2: t^* = 0 и в базисе  есть столбцы вспомогательных переменных, . Пусть Р — результат приведения задачи (35) к базису . Если , то переменная t_k в задаче Р является базисной для одного из уравнений, обозначим его номер r(k). Правая часть этого уравнения равна (см. формулу (21) и замечание 3). Поэтому в задаче Р уравнение с номером r(k) для имеет вид

36 (36)

В условиях случая 2 возможны следующие ситуации. 4

Случай 2.1: для некоторого k  NT() существует s  NX() такое, что . Выполним в Р жорданово исключение с разрешающим элементом . В новый базис войдет x_s вместо t_k, но, как следует из (30), правые части ограничений не изменятся, поскольку Пусть  — новое БДР. В решениях и значения общих базисных переменных совпадают (равны правым частям ограничений). Значения общих небазисных переменных тоже совпадают (равны нулю). Кроме того, каждая из переменных x_s и t_k в одном из рассматриваемых решений небазисная и равна нулю, а в другом — базисная и равна Поэтому  = , мы нашли другой базис для того же решения, но число базисных вспомогательных переменных уменьшилось на единицу. Положим  = ; это теперь текущий базис для БДР . Возвращаемся к случаю 2.

Случай 2.2: случай 2.1 не выполняется. Следовательно, найден базис  для , при котором в (36) для всех j  NX() и k  NT(). Тогда (36) не зависит от основных переменных и при t = 0 обращается в равенство 0 = 0. Это значит, что строки исходной задачи с номерами r(k) для k  NT() линейно зависят от остальных и их можно исключить. Соответствующие уравнения можно исключить из вспомогательной задачи вместе с переменными t_k, , которые в других уравнениях не участвуют. Столбцы сохраненных базисных переменных образуют базис  для оставшихся уравнений. Положим (текущий базис). В этом базисе нет столбцов вспомогательных переменных, поэтому выполнены условия случая 3.

Случай 3: t^* = 0 и NT() = 0. Тогда x^* — базисное допустимое решение задачи (14) – (16) с базисом . □

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