после того как к выбрано, г выбирается однозначно. Построим набор векторов

Ал > , A r-i Dk, D8r+1 ,...,Dep.

Можно показать, что этот набор векторов является базисом некоторой вершины у, для которой справедливо соотношение L(y) > L(x).

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

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

Требуется найти (q + р)-мерный вектор ж, для которого значение функции

м(х) = - £

является максимальным. Координаты вектора ж должны быть неотрицательными и удовлетворять системе линейных алгебраических уравнений

Eij хз + ж<гН = di0, г = 1,2,...,р.

Через dij обозначены координаты векторов Dj из условия (10.2) при j = 0,1,2,... , q. Мы можем считать, что а\0 > 0 при г = 1,2,... ,р. (Этого всегда можно добиться, умножив некоторые из уравнений (10.2) на -1.) В качестве вершины,

с которой начинается перебор при решении вспомогательной задачи линейного программирования, берется точка с координатами

Xi = ж2 = ... = xq = 0, xq+i = сЦо при г = 1,2,...,р.

Решение вспомогательной задачи всегда может быть найдено, поскольку функция М(х) ограничена сверху нулем. Если найден (q + р)-мерный вектор ж, являющийся решением вспомогательной задачи, для которого М(х) = 0, то последние р координат этого вектора нулевые, а первые q координат удовлетворяют системе линейных алгебраических уравнений (10.2), и соответствующий с/-мерный вектор является вершиной множества Г исходной задачи линейного программирования. Если для найденного решения вспомогательной задачи М(х) < 0, то это означает, что система условий (10.2), (10.3) исходной задачи несовместна.

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

Мы искали вектор ж, при котором функция L(x), определенная в (10.1), принимает максимальное значение. Но может быть и так, что нам нужно найти вектор ж, при котором функция Ь(х) принимает минимальное значение. Чтобы найти такой вектор ж, можно воспользоваться уже полученными расчетными формулами. Вектор ж, при котором

410 решении задач линейного программирования при нарушении условия невырожденности см., например, [21], [27], [39].

достигает максимального значения функция - Т=1 cj xh ~ это тот вектор, при котором достигает минимального значения функция L(x).

2. Симплексный метод для решения задач квадратичного программирования. В §3 и 9 мы сталкивались с задачей квадратичного программирования. Сформулируем ее еще раз. Пусть даны iV-мерный вектор Р и матрица С размера N х N. Матрица С является симметричной, т. е. Сц = Cji при любых г и j. Кроме того, матрица С является неотрицательно определенной. Это означает, что для любого iV-мерного вектора х = (жь ж2,... ждг) справедливо неравенство

JV N

£ X Xi xi СН °-i=i j-i

Среди всех iV-мерных векторов, удовлетворяющих приводимым ниже условиям (10.6) и (10.7), требуется найти тот (или один из тех), для которого значение функции

N N N

F{x) = J> Д + Е> Ч °а (10-5)

j=l г=1 j=l

является минимальным. Условия, которым должны удовлетворять вектора ж, имеют следующий вид. Во-первых, существуют m-мерные вектора В, Ai, А2, .., An такие, что координаты вектора х удовлетворяют соотношению

£х;А, = £. (10.6)

Условие (10.6) - это система т линейных алгебраических уравнений относительно N неизвестных. Считается, что