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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

77
Теперь можно заметить, что при увеличении
2
x
значения переменных
1
x
и
3
x
также возрастают, то есть при
2
x 
в допустимой области
Qx 
(за-
дача не имеет решения).
Замечание. В процессе поиска допустимого плана может быть выявлена
противоречивость системы ограничений.
7.1. Алгоритм симплекс метода
Формализованный алгоритм симплекс метода состоит из двух основных
этапов:
1) построение опорного плана;
2) построение оптимального плана.
Проиллюстрируем алгоритм на рассмотренном ранее примере:
45
minQ x x x
,
1 4 5
2 4 5
3 4 5
2 1,
2 2,
3 3,
x x x
x x x
x x x
0x
.
В случае базисных переменных
1 2 3
,,x x x
начальная симплексная таблица
для данного примера будет выглядеть следующим образом:
4
x
5
x
1
1
x
1
–2
1
2
x
–2
1
2
3
x
3
1
3
Qx
–1
1
0
Она уже соответствует опорному плану
1
1 2 3 0 0x
(столбец
свободных членов).
Построение оптимального плана. Для того чтобы опорный план был оп-
тимален, при минимизации целевой функции необходимо, чтобы коэффициенты
в строке целевой функции были неположительными (в случае максимизации –
неотрицательными). Т.е. при поиске минимума мы должны освободиться от по-
ложительных коэффициентов в строке
Qx
.
Выбор разрешающего элемента. Если при поиске минимума в строке це-
левой функции есть коэффициенты больше нуля, то выбираем столбец с поло-

Страницы