Симлекс-метод (стр. 2 из 4)
Второй столбец - базисные переменные.
Третий столбец - свободные члены (hi00).
Самая верхняя строка - коэффициенты при целевой функции.
Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».
Индексная строка позволяет нам судить об оптимальности плана:
1. При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
2. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.
Переход ко второй итерации:
Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.
Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.
Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца.
На пересечении строки и столбца находится разрешающий элемент.
На этом этапе осуществляется к переходу к последующим итерациям.
Переход к итерациям:
1. Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
2. Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
3. Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
4. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
5. Остальные элементы переносятся по формуле:
2. Решение различных задач симплекс методом.
Е
Алгоритмы симплекса-метода позволяют также установить, является ли задача линейного программирования разрешимой.
Запишем ограничения задачи ЛП в таком виде:
A1x1 + A2x2 + . + Anxn +An+1xn+1 +.+ An+mxn+m = A0.
Пусть A1,.,Am-множество линейно независимых векторов.
Тогда уравнение
A1x1*+ A2x2* + . + Anxn* +An+1xn+1* +.+ An+mxn+m* = A0, (2...2.1)
определяет базисное решение x1*, x2*,.,xm*,
Предположим, что это решение допустимо, то есть x1*³0, x2*³0,.,xm*³0. Базис {A1,.,Am}образует m-мерное пространство, а потому каждый из векторов Am+1,.,Am+n единственным образом выражается через этот базис. Если Ar не входит в базис, то
A1x1r + A2x2r + . + Amxmr = Ar, (2...2.2)
где xir- соответствующие коэффициенты (i = 1, 2, ..., m).
Предположим, что хотя бы одна из величин xir больше нуля.
Решение уравнения
A1x1 + A2x2 + . + Amxm + Arxr = A0 (2...2.3)
обозначим как
Тогда ,очевидно:
. (2.2.4)Умножив уравнение (2.2.2) на xr и вычтя полученное уравнение из уравнения (2.2.1), получим
A1(x1*-xrx1r) + A2(x2*-xrx2r) +.+Am(xm*-xrxmr)=A0-xrAr. (2.2.5)
Сравнив уравнения (2.2.5) и (2.2.4), находим связь нового решения
1,., m , xr со старым базисным решением x*1,.,x*m: 1=x1*-xrx1r, 2=x2*-xrx2r,., m=xm*-xrxmr , xr. (2.2.6)Решение (2.2.6), во-первых, не будет базисным, так как содержит
m + 1 переменную, а во-вторых, будет допустимым не для всех значений xr.
Чтобы новое решение оставалось допустимым, нужно выбрать значение xr таким, чтобы ни одна из величин
i = xi* - xrxir (i=1, 2, ..., m) не стала меньше нуля. Следовательно, максимальное значение переменной xr определяется соотношениемxr max =
, (2.2.7)где xir > 0.
Чтобы сделать новое допустимое решение базисным, нужно одну переменную xi вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов.
Для этого выбираем значения в соответствии с (2.2.7). Тогда новое базисное решение имеет вид
x1* - xr maxx1r;
x2* - xr maxx2r;
xj (опущен)
xr max,
ановыйбазис - (A1, A2, ., Aj-1, Aj+1, ., Am, Ar).
Такой переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению, которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность).
Новому ДБР { x1* - xrx1r, x2* - xrx2r, ., xm* - xrxmr, xr}
соответствует следующее значение целевой функции
z1 = с1(x1*-xrx1r) + с2(x2*-xrx2r) +.+сrxr =
= (с1x1*+с2x2*+.+сmxm*)+xr(сr-с1x1r-.-сmxmr)=
=z0+xr(сr-с1x1r-.-сmxmr), (2.2.8)
где z0 - значение целевой функции для начального ДБР;
сr-с1x1r -с2x2r - . - сmxmr - симплекс-разность для переменной хr.
Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение, и выбирают такую небазисную переменную хr, для которой симплекс-разность положительна и максимальна.
Таким образом, алгоритм симплекса-метода состоит из следующих этапов:
1) находят начальный базис и связанное с ним допустимое базисное решение;
2) вычисляют симплекс-разность для каждой переменной, не входящей в базисное решение;
3) вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплексом-разностью; ее значение xrmax определяют из соотношения
для всех xir > 0,
4) выводят из базисного решения переменную xj, соответствующую
а из базиса - вектор A j;
5) переходят к этапу 2 новой итерации.
Этапы 2) - 4) повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными.
Это и есть признак оптимальности текущего базисного решения.
Пример 2.2. Решить симплексом-методом такую задачу:
максимизировать (2x1+5x2)
при ограничениях
x1£400, x2£300, x1+x2£500 .
Расширенная форма задачи имеет вид
Ограничения задачи запишем в виде табл. 2.1.
Первая итерация. 1. Выбрав в качестве начального базиса векторы { A3, A4, A5}, находим первое допустимое базисное решение:
A3x3*+A4x4*+A5x5*=A0,
откуда x3*=400, x4*=300, x5*=500,
2. Записываем каждый из небазисных векторов A1, A2 в виде линейной комбинации базисных {A3, A4, A5}
A3x31+A4x41+A5x51=A1;
A3x32+A4x42+A5x52=A2.
Таблица 2.1
| А1 | A2 | A3 | А4 | А5 | а0 |
| 1 | 0 | 1 | 0 | 0 | 400 |
| 0 | 1 | 0 | 1 | 0 | 300 |
| 1 | 1 | 0 | 0 | 1 | 500 |
Решая эти уравнения, получим
х31=1; x41=0; х51=1; x32=0; х42=1; х52=1.
3. Находим симплекс-разности для небазисных переменных x1 и x2:
с1-с3х31-с4х41- с 5х51= с 1=2;
с 2- с 3х32- с 4х42- с 5х52= с 2=5.
Поскольку с 2> с 1, вводим в базис вектор x2.
4. Определяем, какая переменная выводится из базиса. Для этого находим
х3= х3* - х2х32=х3*;
х4= х4* - х2х42=300-1х2;
х5= х5* - х2х52=500-1х2;
Итак переменная х2 вводится в базис со значением x2*= 300, переменная x4 выводится из базисного решения, а вектор A4- из базиса.
Вторая итерация. 1. Раскладываем каждый из небазисных векторов через базисные {A2,A3,A5}. Базисное решение
x2*=300, х3*=400, х5*=500-300*1=200
Представим каждый из векторов A1, A4 ,не вошедших в базис, в виде линейной комбинации A2,A3,A5 .Так как вектор A4 был выведен из базиса, рассмотрим только вектор A1.
Уравнение будет иметь вид
A2х21+A3х31+A5х51=A1,
откуда х21=0; х31=1; х51=1.
2. Находим симплекс-разность для переменной x1:
с 1- с 2х21- с 3х31- с 5х51= с 1-0-0-0= с 1=2>0.
Итак, переменную х1 можно ввести в базис.
3. Определяем, какую переменную (вектор) следует вывести из базиса. Для этого вычисляем
х2= х2* - х1х21=300-0х1;
х3= х3* - х1х31=400-1х1;
х5= х5* - х1х51=200-1х1;
Следовательно, из базиса выводится вектор х5 , из базисного решения - A5.
4. Вычисляем новый ДБР.
Переходим к третьей итерации. Следующие итерации проводятся аналогично.
x1*=200; x2*=300.
Метод полного исключения
Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ. Потребовалась его рационализация как по форме представления информации, так и в способе организации вычислений, чтобы сделать его пригодным для реализации на ЭВМ. С этой целью был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана - Гаусса.
Пусть задана система линейных алгебраических уравнений
j=1, 2, ., m.В матричной форме данная система имеет следующий вид: