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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

план определяется системой
m
линейно независимых векторов,
содержащихся в данной системе из
n
векторов
n21
,,, AAA
. Существует
такая угловая точка многогранника решений, в которой линейная функция
достигает своего наименьшего значения.
Для отыскания оптимального плана необходимо исследовать только
опорные планы. Верхняя граница количества опорных планов,
содержащихся в данной задаче, определяется числом сочетаний
m
n
C . При
больших
m
и
n
найти оптимальный план, перебирая все опорные планы
задачи, очень трудно.
Симплексный метод предоставляет схему, позволяющую осуществлять
упорядоченный переход от одного опорного плана к другому. Этот метод
позволяет, исходя из известного опорного плана задачи, за конечное число шагов
получить ее оптимальный план. Каждый из шагов (или итераций) состоит в
нахождении нового плана, которому соответствует меньшее значение линейной
функции, чем значение этой же функции в предыдущем плане. Если задача не
обладает планами или ее линейная функция не ограничена на многограннике
решений, то симплексный метод позволяет установить это в процессе решения.
2.3 Построение опорных планов
Для построения первоначального опорного плана необходимо выделить в
системе ограничений (2.2)
m
линейно независимых векторов. Наиболее просто
это произвести, преобразовав систему ограничений таким образом, чтобы в ней
появилось
m
единичных векторов (единичная подматрица):
nnmn1m1m,mm
2nn21m1m,22
1nn11m1m,11
bxaxax
bxaxax
bxaxax
, 0b
i
m,,2,1j
. (2.7)
В векторной форме система (2.7) имеет следующий вид:
0nn1m1mmm2211
xxxxx AAAAAA
, (2.8)
где
1
0
0
0
,,
0
0
1
0
,
0
0
0
1
m21
AAA ;

Страницы