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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

3 Алгоритм симплексного метода
3.1 Построение симплексной таблицы
Следующим шагом после того, как задача приведена к стандартной форме,
в системе ограничений выделена единичная подматрица и получен
первоначальный опорный план в виде (2.10), необходимо исследовать этот план
на оптимальность. Для этого необходимо векторы
j
A
n,,2,1j
системы
разложить по векторам базиса
m21
,,, AAA
и подсчитать значения оценок
jj
CZ
. Базис является единичным, поэтому коэффициентами разложения
вектора
j
A по базису служат его компоненты, т.е.
ijij
ax
n,,2,1j;m,,2,1i
. Это означает, что в столбцы
j
A
n,,2,1j
таблицы
нужно записать матрицу ограничений вида (2.7). Дальнейшие вычисления
удобнее проводить, если условия задачи и первоначальные данные, полученные
после определения первого опорного плана, записать в симплексную таблицу
(табл.1).
Таблица 1
C
1
C
2
…
C
l
…
C
m
C
m+1
…
C
j
…
C
k
…
C
n
I
Базис
C
Базиса
A
0
A
1
A
2
…
A
l
…
A
m
A
m+1
…
A
j
…
A
k
…
A
n
1 A
1
C
1
X
1
1 0 …
0 …
0 x
1,m+1
…
x
1j
…
x
1k
…
x
1n
2 A
2
C
2
X
2
0 1 …
0 …
0 x
2,m+1
…
x
2j
…
x
2k
…
x
2n
… … … …
…
…
…
…
…
…
… …
… …
… …
…
l A
l
C
l
x
l
0 0 …
1 …
0 x
l,m+1
…
x
lj
…
x
lk
…
x
ln
… … … …
…
…
…
…
…
…
… …
… …
… …
…
m A
m
C
m
x
m
0 0 …
0 …
1 x
m,m+1
…
x
mj
…
x
mk
…
x
mn
M+1
Z
j
-C
j
Z
0
0 0 …
0 …
0 Z
m+1
-C
m+1
…
Z
j
-C
j
…
Z
k
-C
k
…
Z
n
-C
n
В столбце
C
базиса записываются коэффициенты линейной функции,
соответствующие векторам базиса. В столбце
0
A – первоначальный опорный
план
0
X , в нем же в результате вычислений получается оптимальный план, а
столбцах
j
A
n,,2,1j
записываются коэффициенты разложения
j
-го вектора
по базису, обозначаемые в дальнейшем через
j
X

Страницы