Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

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

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

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

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

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

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

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

=

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

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

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

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

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

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

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

При этом Nr(q)) =jr — номер столбца, занимающего 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), направленным противоположно оси аппликат примут вид:

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

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

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

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

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