ВУЗ:
Составители:
Рубрика:
139
Если нас интересует максимум целевой функции, то параллельный перенос
прямой (107) осуществляется в направлении, противоположном
n
r
, пока она не
станет опорной. Тогда вершина многоугольника G, через которую проходит
прямая, будет соответствовать максимуму функции f. При дальнейшем перено-
се прямой целевая функция будет убывать.
Таким образом, оптимизация линейной целевой функции на многоуголь-
нике допустимых решений происходит в точках пересечения этого многоуголь-
ника с опорными прямыми, соответствующими данной целевой функции. При
этом пересечение может быть в одной точке (в вершине многоугольника) или в
бесконечном множестве точек (на ребре многоугольника).
Рассмотренный геометрический метод решения задач линейного програм-
мирования достаточно прост и нагляден для случая двух или трех переменных.
Для большего числа переменных его применение становится невозможным из-
за большого объема вычислений, связанных с перебором вершин и вычисле-
ниями в них значений целевой функции.
Поэтому для эффективного метода решений сложных задач линейного
программирования с гораздо меньшим числом операций используют
симплекс-
метод
.
Симплексом
(от лат. «простой») называется выпуклая оболочка m, со-
стоящая из n + 1 точек n-мерного метрического пространства: нольмерный
симплекс – точка, одномерный – отрезок, двумерный – треугольник, трехмер-
ный – тетраэдр.
Идея симплекс-метода заключается в следующем (рис. 7.11, а).
а) б)
Рис. 7.11. Геометрическая интерпретация решения задач линейного программирования
симплекс-методом (а) и методом перебора (б)
2
3
4
1
(решение найдено за 4 шага = 2
2
)
>
<
<<
>
>
1 шаг
(начальное
приближение)
2 шаг
(оптимальное решение –
найдено за 2 шага)
Страницы
- « первая
- ‹ предыдущая
- …
- 139
- 140
- 141
- 142
- 143
- …
- следующая ›
- последняя »
