Математические методы исследования операций в экономике (стр. 6 из 37)

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

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

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

Теорема 1.3. Каждый допустимый базисный план является угловой точкой множества допустимых планов D.

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

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

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

чтоx₁a¹ +х₂а² +...+x_ka^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 и по определению является угловой точкой данного множества. -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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