2015-08-21
183
Основная идея симплекса-метода состоит в переходе от одного допустимого базисного решения к другому таким образом, что значения целевой функции при этом непрерывно возрастают (для задач максимизации).
Предположим, что ограничения задачи сведены к такому виду, что в матрице А имеется единичная подматрица и все свободные члены положительные. Иными словами, пусть матрица ограничений имеет вид
A 1 x 1+…+ A nxn + e 1 xn + e 1 xn +1+…+ e mxn + m = A 0=[ ai 0],
где
… 
— единичный базис, ai 0³0
для всех i = 1, 2,…, n.
Применим одну итерацию метода полного исключения к расширенной матрице ограничений A p=[ A 1, …, A n, e 1, …, e m, A 0].
Пусть aij – направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (2.2.18) получим новые значения свободных членов:
. (2.2.19)
Исследуем выражения (2.2.19). и выясним условия, при которых al 0(k+ 1) >0 для всех l, то есть новое базисное решение будет также допустимым.
По предположению al0 (k)>0; l= 1,…, m,
aij (k)>0,
тогда
Если alj (k)<0, тогда al 0(k+ 1)> 0,поскольку ai 0(k)> 0, aij (k)> 0.
|
|
|
Если alj (k)>0, то
будет больше нуля при всех l =1, 2...., m тогда и только тогда, когда
(2.2.20)
Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:
a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;
б) направляющую строку i выбирают так, чтобы отношение 
было минимально при условии, что aij >0.
При таком преобразовании в базис вводится вектор A j и выводится вектор А i. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.
Для этого используют так называемые оценки векторов D j:
(2.2.21)
где Iб – множество индексов базисных векторов; xij – определяют из условия
(2.2.22)
Величины {D j } равны симплекс-разницам для переменных { xj } с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец А j с наибольшей по модулю отрицательной оценкой, то есть
.
Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.2.
Таблица 2.2.
| c | c1 | c2 | c3 | … | c j | … | c n | ||
| B x | a00 | A1 | A2 | A3 | … | A j | … | An | |
| c1 | x1 | a1o | a11 | a12 | a13 | … | a1j | … | a1n |
| c2 | x2 | a2o | a21 | a22 | a23 | … | a2j | … | a2n |
| … | … | … | … | … | … | … | … | … | … |
 c i
| x i | aio | ai1 | ai2 | ai3 | … | aij | … | ain |
| … | … | … | … | … | … | … | … | … | … |
| c m | x m | amo | am1 | am2 | am3 | … | amj | … | amn |
| D | D1 | D2 | D3 | … | D j | … | D n |
Последняя сторока таблицы — индексная —служит для определения направляющего столбца. Ее элементы Dj определяют по формуле (2.2.21). Очевидно, для всех базисных векторов { A i } i =1,…, m оценки D и=a 0 и = 0.
|
|
|
Значение целевой функции a 00 определяется из соотношения
.
В столбце B x записываем базисные переменные { xi } i = 1,..., т. Их значения определяются столбиком свободных членов ai 0, то есть
xi = ai 0, i =1, 2,…, m.
Направляющие строка A i и столбец A j указываются стрелками. Если в качестве направляющего элемента выбран aij, то переход от данной симплекс таблицы к следующей определяется соотношениями (2.2.16) - (2.2.18).
