Базисные решения и вторая геометрическая интерпретация ЗЛП

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

Если некоторые т столбцов а^{j 1}, а^{j 2},..., а^jm матрицы A явля­ются линейно независимыми, то они образуют базис в простран­стве R^m, и их, вообще говоря, будет достаточно для представ­ления вектора b в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации окажутся неотрицатель­ными, то мы получаем так называемый базисный допустимый план х, у которого не более m компонентов отличны от нуля. Сформулируем определение базисного плана более строго, так как это одно из фундаментальных понятий теории линейного пpогpаммиpования.

F F Пусть задана некоторая каноническая ЗЛП (D,f), А —матрица системы ограничений задачи, и β= {а^j1, аj2,..., а^jm} —линейно независимая система столбцов матрицы А, образующая базис R^m. Обозначим множе­ство номеров столбцов, входящих в систему b, через N (β) = {j₁, j₂,..., j_m}. План х называется базисным планом задачи (D,f), если его компоненты, соответствующие базисным столбцам и называемые базисными компонен­тами, больше или равны нулю (х_j ≥ 0, j Î N (β)}, а все остальные компоненты (небазисные) — равны нулю (x_j = 0, j Ï N (β)).

F F Базисный план х называется невырожденным, если все его базисные компоненты строго

положительны, и вы­рожденным в противном случае.

1.3.2. Свойства базисных планов. Следующая теорема трактует понятие базисного плана в терминах первой геометри­ческой интерпретации ЗЛП.

Доказательство.

Ради простоты положим, что базисными векторами являют­ся первые m столбцов матрицы A, т. е. β={ a ^l, a ²,..., a^m }. Тогда утверждение теоремы 1.3 может быть переформулировано сле­дующим образом:

Если существует такой n-мерный вектор

что x ₁ a ¹ + х ₂ а ² +...+ x_k a^k = b, то х есть угловая точка множе­ства D.

Проведем доказательство от противного, т. е. предположим, что рассматриваемый базисный план х не является угловой точ­кой множества D. Тогда ее можно представить в виде выпуклой комбинации некоторых двух различных допустимых планов х ¹ и х ²:

x = λ x ¹+(1-λ) x ², 0<λ<1.

В координатной форме последнее утверждение означает

Поскольку последние (n - k) компоненты вектора х по пред­положению равны 0, а числа х_j ¹, x_j ² ≥ 0 и λ, (1 -λ)>0, то эти же компоненты в векторах x ₁ и х ₂ также равны 0. Поэтому, с учетом допустимости планов х ¹ и х ², можно утверждать, что

Вычитая из (1.15) (1.16), получим

Так как векторы а ¹, а ²,..., а^k — линейно независимы, то коэф­фициенты х ¹₁ – х ²₁ =0,..., х¹_k –х²_k =0, из чего следует, что x ¹ = х ². Это противоречит предположению, что х ¹ и х ² являются раз­личными угловыми точками множества D. Следовательно, х не может быть представлен в виде выпуклой комбинации двух точек D и по определению является угловой точкой данного множества. A

Интересно отметить, что справедливо и обратное утвержде­ние, которое приведем без доказательства:

Если х — угловая точка множества D, то она являет­ся допустимым базисным планом задачи (D, f).

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

СИМПЛЕКС-МЕТОД

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

Классическим методом решения ЗЛП стал симплекс-ме­тод, получивший также в литературе название метода по­следовательного улучшения плана, разработанный в 1947г. американским математиком Джорджем Данцигом.

Идея такого перехода от одного базисного плана к другому, при котором происходит «улучшение» значения целевой функ­ции, может быть продемонстрирована для случая m = 2 с помо­щью рис. 1.4. Если вектор ограничений b принадлежит конусу, натянутому на некоторые два базисных вектора условий {а^j1,а^j2}, то существует такой базисный план х с базисными компонентами х_j1, х_j2, что b= х_j1a^j1 + х_j2a^j2. Разумеется, таких планов может быть несколько в зависимости от выбора систе­мы базисных векторов. Чтобы различать их по соответствую­щей величине целевой функции f(x)=c_{j 1} x_{j 1} + с_{j 2} х_{j 2}, вводятся так называемые расширенные векторы условий и ограничений. В общем случае расширенный столбец условий ā^j получается соединением коэффициента целевой функции с^j и столбца а^j:

расширенный вектор ограничений определим как

В дальнейшем для удобства нумерации элементов будем счи­тать, что добавляемый коэффициент целевой функции с_j явля­ется нулевым элементом j -го расширенного столбца условий, т. е. ā_0,j = с_j. При изображении расширенных векторов нулевая координата откладывается вдоль вертикальной оси — оси апп­ликат.

Рассмотрим также вектор

=

Геометрически определение вектора b означает, что он при­надлежит конусу, натянутому на расширенные векторы, а век­тор служит его проекцией. Нулевая координата вектора b имеет вид:

т. е. равна значению целевой функции для выбранного базисно­го плана.

Из геометрической иллюстрации следует, что для решения задачи мы должны среди векторов а^j выбрать такой набор {а^j1,а^j2}, чтобы, прямая, проведенная через конец вектора параллельно оси аппликат, пересекала конус, натянутый на систему соответствующих расширенных столбцов { ā^j1, ā^j2}, в «наивысшей» точке.

На рис. 1.4 выделен конус, натянутый на систему расширен­ных столбцов ā² и ā³, отвечающих текущему допустимому ба­зису. Нетрудно заметить, что данный базис не является опти­мальным, например, для базиса { а³, а⁴ } точка пересечения соответствующего конуса и прямой будет находиться выше. Можно, наоборот, указать базис с «худшим» значением целе­вой функции: { а¹ а² }. Наконец, рассматриваемая геометричес­кая интерпретация КЗЛП иллюстрирует и общую идею крите­рия, который используется в симплекс-методе для определения оптимальности (или неоптимальности) текущего плана: если существуют векторы-столбцы, лежащие выше плоскости, проходящей через векторы текущего базиса, то он не явля­ется оптимальным и может быть «улучшен».

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

Для удобства дальнейшего изложения введем некоторые обозначения. Учитывая то, что симплекс-метод представляет собой некоторый итеративный вычислительный процесс, то че­рез q будем обозначать номер очередной (текущей) итерации. Соответственно, набор базисных столбцов, получаемых на q -й итерации, будет обозначаться как β ^{( q )}:

Для того чтобы было легче отличить номер итерации от номе­ров компонентов матриц и векторов, он заключен в круглые скобки. Номера столбцов, входящих в базис, обозначим через N (β^(q)), а именно

При этом N_r (β^(q)) = j_r — номер столбца, занимающего r -ю пози­цию в базисе. Тогда текущий базисный план х имеет вид:

Обозначим через Δ(ß^(q)) матрицу, составленную из столбцов {а^j1, а^j2,..., а^jm}, образующих базис, через Δ(ß^(q)) матрицу, об­разованную из соответствующих расширенных столбцов и до­полненную слева столбцом специального вида:

а через ∆^-1(β^(q)) и ∆^-1(β^(q)) — матрицы, обратные по отношению к ним. Также представляется удобным ввести отдельные обо­значения для элементов матрицы ∆^-1(β^(q)):

δ _i (β^(q)) — i -я строка матрицы ∆ˉ^-1(β^(q)), (i Î 0: m);

δ _ij (β^(q)) — элемент матрицы ∆^-1(β^(q)), находящийся в i -й строке j -го столбца (i Î 0: m, j Î 0: m).

Расширенный вектор ограничений b представляется в виде линейной комбинации расширенных векторов условий с коэф­фициентами, равными базисным компонентам текущего базис­ного плана:

Если интерпретировать компоненты векторов а ^j и b как ко­ординаты в ортогональном базисе, то их столбцы координат от­носительно произвольного базиса (β^(q)), дополненного единич­ным вектором (-1,0,..., 0), направленным противоположно оси аппликат примут вид:

а для расширенной матрицы задачи в целом можно записать

Нулевая строка данной матрицы a ₀(β^{( q )}) содержит координаты расширенных векторов условий по оси аппликат. Согласно по­строению, элементы данной строки имеют следующие знаки:

Ø Ø a _0,j (β^{( q )}) < 0 — для расширенных векторов условий, рас­положенных выше плоскости, натянутой на систему расширенных базисных векторов;

Ø Ø a _0,j (β^{( q )}) > 0 — для расширенных векторов условий, рас­положенных ниже плоскости, натянутой на систему расширенных базисных векторов;

Ø Ø a _0,j (β^{( q )}) = 0 — для расширенных базисных векторов.

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

F план является оптимальным, если для всех j Î1: n a _0,j (β^{( q )}) ≥ 0, и неоптимальным в противном

случае, т. е. если существует такое l Î l: n, что a _{0 l} (β^{( q )}) < 0.

Значения a _0,j (β^{( q )})также называют оценками столбцов мат­рицы А относительно текущего базиса, или симплекс-разнос­тями.

В случае неоптимальности текущего базиса в алгоритме сим­плекс-метода осуществляется переход к следующему базису. Это делается за счет вывода одного столбца из базиса и ввода другого. Для обеспечения улучшения значения целевой фун­кции в базис должен быть введен вектор-столбец, имеющий от­рицательную оценку. Если таких столбцов несколько, то для ввода рекомендуется выбирать столбец, имеющий макси­мальную по модулю оценку. Отметим, что данное правило но­сит относительный характер и не гарантирует наилучшего выбора вводимого столбца. Одновременно на этой стадии тре­буется принять решение о том, какой столбец следует вывести из базиса. Сделать это нужно таким образом, чтобы вновь формируемый базис оказался допустимым. Данное требование может быть легко проиллюстрировано для случая m = 2. Например, на рис. 1.3 векторы { а ², а ³} образуют допустимый ба­зис, а векторы { а ³, a ⁴} —недопустимый, т. к. разложение b по а ³ и а ⁴ содержит один отрицательный компонент плана, что противоречит условиям КЗЛП.

Можно доказать, что допустимость базиса, к которому осу­ществляется переход, обеспечивается следующим правилом вывода столбца из текущего базиса:

Рис.1.5

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

* Настоящая структура симплекс-таблиц строится на идеях и прин­ципах их организации, предложенных в [1].

Симплекс-таблица Т^{( q )}, изображенная на рис. 1.5, соответ­ствует допустимому базису КЗЛП β^{( q )}), получаемому на q -й ите­рации. Столбец N (β^{( q )}) содержит номера базисных столбцов (в той последовательности, в которой они входят в базис), стол­бец b (β^{( q )}) —компоненты вектора ограничений относительно текущего базиса β^{( q )}, A (β^{( q )}) — компоненты матрицы задачи относительно текущего базиса β^{( q )}. Наконец, в строке а ₀(β^{( q )}) находятся текущие оценки столбцов, а ячейка b ₀(β^{( q )}) содержит значение целевой функции, достигаемое для текущего плана.

Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное практическое значение не столько как удобная форма организации ручного счета, сколь­ко как основа для реализации данного алгоритма в рамках про­граммного обеспечения ЭВМ.

1.4.3. Пример решения ЗЛП симплекс-методом. Рас­смотрим на конкретном примере процесс решения КЗЛП таблич­ным симплекс-методом. Пусть дана каноническая задача ЛП:

Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по дан­ным столбцам вектора ограничений с положительными коэф­фициентами. Последнее означает, что столбцы {5, 2, 3} образу­ют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых эле­ментов формируется матрица Δ(β⁽¹⁾) и обратная по отношению к ней Δ^-1(β⁽¹⁾):

Используя их, по формуле (1.26) получаем

Используя полученные значения A (β⁽¹⁾) и b (β⁽¹⁾), заполняем симплекс-таблицу T ⁽¹⁾, соответствующую первой итерации (q =1).

Поскольку строка оценок a ₀(β⁽¹⁾) в первом и четвертом столбцах содержит отрицательные элементы (a _0,1(β⁽¹⁾) = -84, a _0,4(β⁽¹⁾) = -88), план х (β⁽¹⁾) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f (x (β⁽¹⁾)) = -226 может быть улучшено. Следуя рекомендации п.1˝ алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l = 4 (т.к. |-88| > |-84|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)

Он содержит два положительных элемента. Применяя рекомен­дацию п. 2" алгоритма, получаем λ₁= 4/(1/3) =12, λ₂=14/3, и, стало быть r = 2. Следовательно, столбец с номером N ₂(β⁽¹⁾) = 2 должен быть выведен из базиса. Таким образом, по­лучаем очередной допустимый базис задачи N (β⁽²⁾) = {5, 4, 3}. Элемент a _2,3(β⁽¹⁾) является ведущим (обведен кружком). При­менив формулы (1.28)-(1.31), переходим к симплекс-таблице, соответствующей второй итерации T ⁽²⁾, и полагаем индекс те­кущей итерации q = 2.

В ходе выполнения второй итерации опять-таки определяют­ся вводимый столбец а ¹, выводимый а ⁴ и ведущий элемент a _2,1(β⁽²⁾). Перейдя к итерации q = 3, имеем таблицу T ⁽³⁾.

Как видно из T ⁽³⁾, строка оценок содержит только неотрицатель­ные значения, поэтому достигнутый базис N (β⁽³⁾) = {5, 1, 3} яв­ляется оптимальным. В итоге мы получаем, что вектор х ^* = (7, 0, 31/3, 0, 5/3) является оптимальным планом (точ­кой максимума) задачи (1.34)-(1.35), максимальное значение целевой функции равно f * = f (х *)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362).

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

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

будут достигнуты для нескольких строк таблицы Т ^{( q )} одновре­менно. Тогда на следующей итерации столбец b (β^{( q +1)}) будет со­держать нулевые элементы. Напомним, что

F F допустимый базисный план канонической задачи ЛП, со­ответствующий базису β^{( q )}, называется вырожденным, если некоторые его базисные компоненты равны нулю, т. е. вектор b (β^{( q )}) содержит нулевые элементы.

Задача ЛП, имеющая вырожденные планы, называется вы­рожденной. При «выходе» на вырожденный план мы фактиче­ски получаем разложение столбца b по системе из меньшего, чем m, количества столбцов а^j и, следовательно, лишаемся воз­можности корректно определить, ввод какого столбца в базис приведет к росту значения целевой функции. Подобные ситуа­ции, в конечном счете, могут привести к зацикливанию вычис­лительного процесса, т. е. бесконечному перебору одних и тех же базисов.

С точки зрения первой геометрической интерпретации ЗЛП ситуация вырожденности означает, что через некоторую угло­вую точку многогранного множества допустимых планов зада­чи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи. Иными сло­вами, одно или несколько ограничений в данной точке являют­ся избыточными. Последнее предоставляет повод для размыш­лений об экономической стороне проблемы вырожденности как проблемы наличия избыточных ограничений и в некоторых случаях определяет пути ее решения.

С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро кону­са, натянутого на систему расширенных векторов текущего базиса. Так, в случае, изображенном на рис. 1.6, эта линия по­падает в ребро, определяемое вектором а^{j 2}, т. е., несмотря на то что текущий базис содержит столбцы а^{j 1} и а^{j 2}, для представле­ния вектора b достаточно только одного а^{j 2}.

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

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

1.4.5. Нахождение допустимого базисного плана. В рас­смотренном выше примере исходный базисный план, необходи­мый для начала вычислений по симплекс-методу, был подобран за счет особенностей матрицы условий. Действительно, данная матрица уже содержала необходимое количество «почти базис­ных» столбцов. Очевидно, что для подавляющего большинства задач ЛП невозможно подобным образом сразу и в явном виде указать исходный допустимый базисный план. Вообще говоря, существуют различные приемы решения данной задачи. Мы остановимся на одном из них, получившем название метода минимизации невязок. Его сильной стороной, безусловно, яв­ляется универсальность. Xотя, в некоторых частных случаях, он может оказаться слишком громоздким.

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

Не умаляя общности, можно считать, что вектор ограниче­ний в исходной задаче неотрицателен, т. е. bⁱ ≥ 0, i Î 1: m. Тогда для КЗЛП максимизации функции

на множестве, определяемом ограничениями

строится вспомогательная задача

Как видно из (1.36)-(1.39), задача ( , ) отличается от за­дачи (D, f) матрицей, получаемой в результате добавления к исходной матрице А единичной матрицы, которой соответ­ствуют дополнительные (фиктивные) переменные х_{n +1},..., х_n+m. Данным переменным (собственно говоря, их и называют не­вязками) в целевой функции отвечают коэффициенты (-1), а переменным х ₁,..., х_n, которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенно­стью ( , ) является наличие в ней очевидного исходного ба­зиса, образуемого добавленными столбцами, и соответствую­щего плана с базисными компонентами х _n+i = b_i ≥ 0, i Î 1: m. В силу структуры целевой функции f̃ в процесс поиска ее мак­симума процедурой симплекс-метода фиктивные переменные (невязки) х _n+i должны минимизироваться желательно до нуля, что может быть достигнуто за счет последовательного перевода их в небазисные компоненты плана. Если в оптималь­ном плане х̃, полученном в результате решения вспомогатель­ной задачи, последние m компонент (т. е. невязки) равны нулю, то его начальные n компонент удовлетворяют системе ограни­чений, определяющих область D, и легко (простым отбра­сыванием невязок) может быть преобразован в стартовый до­пустимый план основной задачи (D, f). При этом все строки симплекс-таблицы, полученной на последней итерации вспо­могательной задачи (за исключением нулевой), могут быть перенесены в первую таблицу основной задачи. Элементы же нулевой строки для вновь формируемой симплекс-таблицы вы­числяются по формулам:

где β^(*) — базис, полученный на последней итерации вспомога­тельной задачи.

В случае, когда оптимальный план вспомогательной задачи х̃ все же содержит не равные нулю фиктивные компоненты (т. е. ( )<0), мы приходим к заключению об отсутствии до­пустимых планов у исходной задачи (D, f), т. е. D = Ø.