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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

118
брать решения, соответствующие вершинам многогранника, удовлетворяю-
щего заданным ограничениям.
При этом возникает два вопроса:
а) как найти координаты вершин многогранника?
б) как организовать наиболее рациональный перебор решений, соответ-
ствующих вершинам?
Ответ на первый вопрос дает теория ЛП. Она говорит, что вектор
х=(х
1,
…,х
n
) является вершиной многогранника решений тогда, и только тогда,
когда х является допустимым базисным решением.
В теории ЛП существуют методы, которые позволяют целенаправленно
перебирать вершины так, чтобы в каждой последующей вершине значение
целевой функции было меньше, чем в предыдущей.
Рассмотрим систему m уравнений с n неизвестными (n>m).
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=+…++
=+…++
=+…++
.bxa xaxa
. . . . . . . . . . . . ..
,bxa xaxa
,bxa xaxa
mnmnmm
nn
nn
2211
22222121
11212111
. (7.7)
Решением этой системы является любой вектор х=(х
1
,…,х
n
), удовлетво-
ряющий всем ее уравнениям. Множество решений этой системы может быть
пустым, может состоять из одного или нескольких решений.
Определение: две системы уравнений эквивалентны, если они имеют
одно и то же множество решений.
Следующие основные операции над строками преобразуют одну систему
уравнений в другую, ей эквивалентную:
а) умножение любого уравнения
R
t
на постоянную величину k≠0;
б) замена уравнения R
t
на уравнение R
t
+ k R
i
, где R
i
– любое из осталь-
ных уравнений.
Представляет интерес последовательность основных операций, в ре-
зультате которых данная линейная система преобразуется в эквивалентную.
Коэффициенты эквивалентной системы при заданной переменной в одном
уравнении равны единице, а в остальных уравнениях – нулю. Это преобразо-
вание называется операцией ведущего элемента, или р-операцией (метод
Жордана-Гаусса). Операция
состоит из следующих шагов:
а) выбирается член a
rs
x
s
в уравнении R, где a
rs
≠0;
б) уравнение R умножается на 1/ a
rs
;
в) все уравнения R
i
(i=1,...,n), кроме i=r, заменяются уравнениями вида
r
rs
is
i
R
a
a
R − .
Систему линейных уравнений (7.7) бывает удобно использовать в ка-
нонической форме. Допустим, что первые m столбцов уравнений (7.7) обра-
зуют базисную матрицу В. Умножим каждый столбец уравнений (7.7) на

Страницы