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

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

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

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

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

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

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

(1)

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

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

(2)

(3)

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

(4)

, , .

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

(5).

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

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

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

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

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

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

(11).

Поиск по сайту: