ВУЗ:
Составители:
Рубрика:
140
Примем в качестве начального приближения координаты некоторой вер-
шины многогранника допустимых решений и найдем все ребра, выходящие из
этой вершины. Двигаемся вдоль того ребра, по которому линейная целевая
функция убывает. Приходим в новую вершину, находим все выходящие из нее
ребра, двигаемся по одному из них и т. д. В конце концов мы придем в такую
вершину, движение из которой вдоль любого ребра приводит к возрастанию
целевой функции. Следовательно, минимум достигнут, и координаты этой по-
следней вершины принимаются в качестве оптимальных значений рассматри-
ваемых проектных параметров.
Поскольку f – линейная функция, а многогранник выпуклый, то данный
вычислительный процесс сходится к решению задачи, причем за конечное чис-
ло шагов k. В данном случае их число имеет порядок n, т. е. значительно мень-
ше количества шагов в методе простого перебора вершин, где k может быть по-
рядка 2
n
(рис. 7.11, б).
Пусть нужно найти такие неотрицательные значения проектных парамет-
ров х
1
, х
2
, …, х
n
, которые минимизируют линейную целевую функцию
f = с
0
+ с
1
х
1
+ с
2
х
2
+ … + с
n
х
n
(108)
при заданных ограничениях в виде системы линейных уравнений
=++
−−−−−−−−−−−−−−−
=
+
+
.bxахаха
,
,bxахаха
mnmn22m11m
1nn1212111
(109)
Если в качестве ограничений заданы неравенства, то их можно преобразо-
вать в равенства путем введения дополнительных неотрицательных перемен-
ных, называемых
балансовыми
.
Например, имея некоторое неравенство bxа...хаха
nn2211
≤
+
+
+
,
можно
всегда ввести новую переменную х
n+1
> 0, такую, что после ее прибавления к
левой части данного неравенства получим равенство
bхxа...хаха
1nnn2211
=
+
+
+
+
+
.
Будем считать, что все уравнения системы (109) линейно независимы, т. е.
ни одно из них нельзя получить как линейную комбинацию других. В против-
ном случае линейно зависимые уравнения можно отбросить. И, кроме того, эта
система совместна, т. е. среди уравнений системы нет противоречивых.
При этих предположениях число уравнений m меньше числа переменных
n, поскольку при m = n система (109) имеет единственное значение, что исклю-
чает всякую оптимизацию; при m > n не выполняется сделанные выше предпо-
ложения.
Выразим первые m переменных х
1
, х
2
, …, х
m
через остальные с помощью
уравнений (109):
