Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Глава 8. НЕКОТОРЫЕ МЕТОДЫ ДЛЯ ЗАДАЧ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИЗадача нелинейного программирования (НЛП) с линейными ограничениями может быть сформулирована в виде
где А — матрица размера задачи с линейными ограничениями встречаются часто и, вообще говоря, решить их легче, чем задачи с нелинейными ограничениями. В этой главе приведено несколько методов решения задачи (8.1). Первый метод основан на линейной аппроксимации. Второй, выпуклый симплексный метод, распространяет линейный симплексный метод на нелинейные целевые функции. Наконец, мы обсуждаем метод субоптимизации на многообразиях, с помощью которого рассматриваются на каждой стадии лишь некоторые ограничения, и решение задачи (8.1) сводится к решению подзадач меньшего размера. 8.1. МЕТОД ЛИНЕЙНОЙ АППРОКСИМАЦИИВозможно, наиболее прямой подход к решению задачи (8.1) заключается в линейной аппроксимации. Для данной допустимой точки В любой допустимой точке
Алгоритм при данном
при Но так как некоторые члены целевой функции постоянны, то алгоритм фактически решает более простую, но эквивалентную подзадачу ЛП
где х — фиксированная допустимая точка, а у — переменная. Далее с помощью направления
допустима, так что Алгоритмическое отображение. Алгоритм представляется в виде
где Назовем допустимую точку х подходящей, если для решения у подзадачи (8.3) при
Остается доказать, что в подходящей точке выполняются условия Куна — Таккера (см. упр. 1). Если Доказательство сходимости. Чтобы доказать сходимость, предположим, что Условие 2. Пусть
и поскольку
Условие 3. Наконец, нужно доказать замкнутость отображения А. Сначала исследуем Чтобы доказать замкнутость
Рис. 8.1. Алгоритм линейной аппроксимации: для любого допустимого у. Функция
Но тогда, так как точка Вследствие того, что все Графическое изображение поведения этого алгоритма представлено на рис. 8.1. Точка а представляет собой абсолютный максимум
|
1 |
Оглавление
|