Составители:
Рубрика:
20
Найти максимум (минимум) ее
12
11 2 2
, ,...,
max ( ...
)
n
nn
xx x
ax ax a x
+++
при
условии, что удовлетворяются следующие m неравенств:
11 2 2
...
ii
bx bx
++
{}
,,,, ,
in n i
bx b
+<≤=≥>
1, ..., .im
=
Решение заключается в поиске оптимальных переменных, удовлет-
воряющих решению задачи. Неравенства определяют в пространстве
переменных выпуклый многогранник, называемый симплексом, а до-
пустимые значения переменных – точку внутри или на краю симплек-
са. Оптимальная точка находится в одной из вершин симплекса.
Симплекс-метод заключается в последовательном обходе вершин сим-
плекса до тех пор, пока не попадется оптимальная вершина. Для сокра-
щения пути обхода в текущей вершине делается пробный шаг движе-
ния точки по каждому исходящему из этой вершины ребру и выбирает-
ся ребро, максимально увеличивающее значение целевой функции при
перемещении точки на единицу длины этого ребра. По этому ребру
перемещаются в следующую вершину. Проверяется ее оптимальность
и, если она не оптимальна, повторяется переход в следующую вершину.
Вершина оптимальна, если при движении точки по любому исходяще-
му из нее ребру значение целевой функции уменьшается (при поиске
максимума) или, наоборот, увеличивается, если ищется минимум целе-
вой функции.
Опишем методику решения на следующем примере.
Дано:
1
2
2yx
x
=+
. (24)
Найти
ma
x
y
при условии, что
1
12
12
2
7;
9;
31
5;
4.
x
xx
xx
x
≤
+≤
+≤
≤
(25)
На рис. 4 показан симплекс, соответствующий условиям (25), и пря-
мая GH, соответствующая уравнению целевой функции (24), если ее
значение равно двум. Оптимальной будет вершина D, так как она явля-
ется точкой касания прямой GH к симплексу при наибольшем удалении
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
