Основы автоматизированного проектирования химических производств. Миронов В.М - 119 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

119
матрицу В
-1
, обратную матрице В. Получим эквивалентную систему уравне-
ний, в которой коэффициенты при переменных (х
1
,…,х
m
) образуют единич-
ную матрицу. Это каноническая форма представления системы уравнений
Базисные
переменные
Внебазисные
переменные
Постоянные
x
1
+a
1m+1
x
m+1
+ . . . +a
1n
x
n
=b
1
x
2
+a
2m+1
x
m+1
+ . . . +a
2n
x
n
=b
2
. . . . . . . . . . . . . . . .
x
m
+a
mm+1
x
m+1
+ . . . +a
mn
x
n
=b
m
Переменные (х
1
– х
m
) – базисные, или зависимые; а переменные
(x
m+1
- xx
n
) – внебазисные, или независимые. Если задать определенные зна-
чения внебазисным переменным, то, решив систему, можно найти значения
базисных переменных. В частности, если x
m+1
=0; x
m+2
=0; … ; x
n
=0, то
x
1
=b
1
; x
2
=b
2
; ... ; x
m
=b
m
.
Если при этом все b
i
≥0 (i=1..m), то базисное решение является допус-
тимым. Если же один или несколько коэффициентов меньше нуля, т.е. b
i
<0,
то допустимое базисное решение является вырожденным.
Для получения канонической системы уравнений и базисного решения
можно выбрать любые m переменных из n в качестве базисных. Тогда мак-
симальное число базисных решений задачи линейного программирования
конечно и выражается формулой
)!(!
!
mnm
n
C
n
m
−
=
.
Однако при решении задачи симплекс-методом анализируется только
часть допустимых базисных решений.
Алгоритм симплекс-метода включает следующие основные шаги:
а) выбор начального допустимого базисного решения;
б) переход к другому допустимому базовому решению. Здесь исключа-
ются из рассмотрения все допустимые базовые решения, которые хуже теку-
щего;
в) продолжение поиска допустимых
базовых решений, улучшающих
значение целевой функции. Если некоторое допустимое базовое решение
нельзя улучшить, то оно является оптимальным.
Решение задачи начинается с формирования расширенной системы ли-
нейных уравнений в канонической форме. Базисными переменными являют-
ся (x
1
,…,x
m
) и –z. Проблема заключается в нахождении значений x
i
>0 и ми-
нимизации функции z при выполнении условий:

Страницы