Файл: Е.В. Буйная Симплексный метод решения оптимизационных задач.pdf

3

1. Основные понятия и алгоритм стандартного симплекс-метода

Пусть стоит задача максимизации (минимизации)

где Aj (j=1,...,n) , B – m-мерные векторы.

Напомним несколько ключевых определений и свойств задачи.

Вектор X=(X1,X2,..,Xn) , удовлетворяющий условиям (1.2) и (1.3), называется планом. Множество планов в геометрической интерпретации представляет собой выпуклый многогранник.

План, который обращает в равенство хотя бы n независимых ограничений задачи, называется опорным планом. Опорный план соответствует некоторой вершине многогранника планов.

Опорный план содержит не свыше m положительных компонент (m – число независимых ограничений задачи). Опорный план, содержащий менее m положительных компонент, называют вырожденным.

Оптимальный план является опорным (если оптимум достигается на двух опорных планах, то оптимальны все планы, соответствующие отрезку, соединяющему соответствующие вершины).

Система m векторов Aj при положительных компонентах опорного плана называется базисом этого плана.

Симплексметод - это метод упорядоченного перебора опор-

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

В теоретическом обосновании симплексного метода [1] обнаруживается, что в случае единичного базиса (векторы образуют единичную матрицу) коэффициенты разложения некоторого вектора по векторам базиса, используемые в симплексной процедуре, совпадают с компонентами самого вектора (в общем же случае придется решать систему

4

уравнений). Поэтому на практике стремятся иметь дело с единичным базисом.

Предположим, что исходная задача приведена к канонической форме (1.1)-(1.3) при В ≥ 0 и первые m векторов начального базиса образуют единичную матрицу (их можно принять за базис).

Для единообразия описания вычислительной процедуры в дальнейшем будем пользоваться т. н. симплексными таблицами вида:

В первом столбце таблицы (С баз) записывают коэффициенты целевой функции (С1, С2 …Сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу, как в нашем случае А1 Аm). Во втором столбце (Базис плана) должны находиться базисные векторы данного опорного плана, а в третьем столбце (План Х) – правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы первого столбца таблицы со столбцом – «План Х», и суммируя эти произведения, мы получаем значение целевой функции (ячейка – L(X)=С1 В1 + С2 В2+…+

+Сm Bm).

Первая строка симплексной таблицы содержит коэффициенты линейной функции нашей задачи и остается неизменной на протяжении всего решения (С1, С2, …, Сn).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи (Z11,…, Z1n,…, Zm1,…, Zmn). При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу.

6

Критерий 3 . Если обнаруживается некоторое ∆ k < 0, но все Zjk≤ 0, то линейная форма задачи не ограничена по максимуму (неограниченность по минимуму устанавливается аналогично при ∆ k>0 и всех Zjk

≤ 0).

Переход к очередной симплексной таблице сводится к тому, чтобы

выразить Xk из уравнения, соответствующего минимуму для Θ , и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компоненте и тем самым сохраняется единичная подматрица при базисных векторах):

1.Строку, соответствующую вектору, выводимому из базиса (главная строка), делим на коэффициент (главный элемент), находящийся на пересечении этой строки и столбца, соответствующего вектору, вводимому в базис (главный столбец).

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

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

2.Приведение задачи к канонической форме

Как мы уже отмечали, изложенный алгоритм стандартного сим- плекс-метода применим к задачам, представленным в каноническом виде.

Для приведения задачи к такому виду используют следующие приемы.

1. Если на некоторую переменную Xk отсутствует условие неотрицательности, то ее всегда можно заменить разностью двух неотрицательных переменных, т.е.

7

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

ляющую (свободную, дополнительную), переменную, уравновешиваю-

щую разность между левой и правой частями ограничения.

3. Если среди основных ограничений присутствует ограничение с отрицательной правой частью, из соображений удобства последующего поиска начального опорного плана его умножают на (-1).

Рассмотрим несколько примеров:

Пример 1.

Пусть стоит задача максимизации

L(X) = 3X1+4X2-5X3

при условиях

3X1 - 4X2 + X3 ≤ 5

X1 - 10X2 + X3 = 10 5X2 - 3X3 ≥ 0 X1, X2 ≥ 0, X3 ≤ 0.

Так как X3 ≤ 0, произведем замену X3 = - X3’, где X3’≥ 0.

Так как первое и третье ограничения записаны в форме неравенства, необходимо ввести ослабляющие переменные. В первое ограничение вводим переменную Х4 = 5 - 3X1 - 4X2 + X3 , Х4 ≥ 0, а в третье - переменную Х5 = 0 - 5X2 - 3X3 , Х5 ≥ 0. В итоге исходная задача примет вид:

Максимизировать

L(X) = 3X1 + 4X2 + 5X3’

5X2 - 3X3’ - Х5 = 0 X1, X2, X3’, X4 , X5 ≥ 0.