Численные методы оптимизации. Рейзлин В.И. - 80 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

80
В качестве базисных переменных будем брать систему дополнительно
введенных переменных. Тогда симплексная таблица для преобразованной задачи
будет иметь следующий вид:
1
x
2
x
….
S
x
.…
n
x
1
0
1,2
a
….
1,S
a
….
1,n
a
1
b
….
….
.…
….
.…
.…
.…
.…
0
,1m
a
,2m
a
….
,mS
a
….
,mn
a
m
b
1m
x
1,1m
a
1,2m
a
….
1,ms
a
….
1,mn
a
1m
b
….
….
….
….
….
….
….
…
mp
x
,1mp
a
,2mp
a
….
,m p S
a
….
,m p n
a
mp
b
Qx
1
c
2
c
….
S
c
….
n
c
0
Правила выбора разрешающего элемента при поиске опорного плана
1. При условии отсутствия “0-строк” (ограничений-равенств) и “сво-
бодных” переменных (т.е. переменных, на которые не наложено требование не-
отрицательности).
Если в столбце свободных членов симплексной таблицы нет отрица-
тельных элементов, то опорный план найден.
Есть отрицательные элементы в столбце свободных членов, напри-
мер
0
i
b
. В такой строке ищем отрицательный коэффициент
il
a
, и этим самым
определяем разрешающий столбец
l
. Если не найдем отрицательный
il
a
, то си-
стема ограничений несовместна (противоречива).
В качестве разрешающей выбираем строку, которой соответствует
минимальное отношение:
min 0
r i i
i
rl il il
b b b
a a a






, где
r
– номер разрешающей
строки. Таким образом,
rl
a
– разрешающий элемент.
После того, как разрешающий элемент найден, делаем шаг модифи-
цированного жорданова исключения с направляющим элементом
rl
a
и перехо-
дим к следующей симплексной таблице.
2. В случае присутствия ограничений-равенств и “свободных” переменных
поступают следующим образом.
Выбирают разрешающий элемент в “0-строке” и делают шаг моди-
фицированного жорданова исключения, после чего вычеркивают этот разреша-
ющий столбец. Данную последовательность действий продолжают до тех пор,
пока в симплексной таблице остается хотя бы одна “0-строка” (при этом таблица
сокращается).

Страницы