3.6. Модифицированный симплекс-метод

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

Последовательность подстановок приводит к следующей формуле:

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

Шаги алгоритма модифицированного симплекс-метода, по существу, такие же, как и в алгоритме обычного симплекс-метода.

3.7. Построение опорных планов

Рассмотрим каноническую форму задачи линейного программирования

(1)

при ограничениях

Пусть . Предположим, что система ограничений содержит m - единичных векторов. Пусть это первые n - векторов, тогда:

(2)

(3)

Запишем систему (2) в векторной форме

(4)

, , .

Векторы - единичные, линейно независимые векторы m - мерного пространства, они образуют базис. В (4) за базисные неизвестные выберем . Свободные неизвестные приравниваем нулю и учитывая, что (где ), а векторы - единичные. Получим первоначальный план

(5).

Плану (5) соответствует разложение (6), так как - линейно независимые, то первоначальный план является и опорным.

Рассмотрим, как исходя из опорного плана (5) можно построить другой опорный план - базис, поэтому . Предположим, что для некоторого вектора, не входящего в базис, например для , является положительным хотя бы один из коэффициентов , входящих в разложение (7). Зададимся величиной , пока неизвестной, умножим (7) на и почленно вычислим из (6),получаем

вектор является планом, если его компоненты положительны. (9).

Из (9) следует, что , план, если (10).

Чтобы план был опорным должно быть m - положительных компонентов.

Необходимо обратить в нуль хотя бы одну из компонентов

(11).

3.8. Условия оптимальности

Предположим, что задача линейного программирования (1) - (3) обладает планами и каждый ее опорный план невырожден. В этом случае для опорного плана (5) имеем (12) (13), где - это значение линейной формы, соответствующее плану . Разложение любого вектора по векторам базиса - единственно.

(14)

(15)

Теорема (для задачи на min): Если для некоторого вектора выполняются условия , то план не является оптимальным и можно построить такой план X: .

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

Умножим равенство (14) на и вычтем из равенства (12), получаем

.

Умножим равенство (15) на и вычтем из равенства (13), получаем

(16).

Следствие: Если для некоторого плана разложение всех векторов в данном базисе, удовлетворяющих условию (17), то план является оптимальным. Неравенство (17) это условие оптимальности задачи на минимум, а величины - оценки плана.

Теорема (для задачи на max): Если для некоторого вектора выполняются условия , то план не является оптимальным и можно построить такой план X: .

Следствие: Если для некоторого плана разложение всех векторов в данном базисе, удовлетворяющих условию (18), то план является оптимальным. Неравенство (18) это условие оптимальности задачи на минимум, а величины - оценки плана.

- формула Жордана-Гаусса.