Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

4.5. Методы отсечений. Искусственная линеаризация задачи

Методы отсечений имеют своей целью свести исходную нелинейную задачу математического программирования к более простой ее разновидности (например, к задаче линейного программирования). Это делается путем последовательной замены имеющейся области U рядом несложных по своей конфигурации областей. Существующие варианты методов отсечений характеризуются принятыми способами аппроксимации границ U, предполагаемыми свойствами функций f(X), φi(Х), i = 1,....,m и т. п.

Метод аппроксимации границ области

Пусть дана следующая нелинейная задача: найти Х→max {z = f (X)} при φi(Х)≥0 (i = 1,...,m). Вводя в рассмотрение скалярную величину 0, можно дать другую интерпретацию этих условий: найти X, ω→max ω при f(X)-ω≥0, φi(Х)≥0 (i = 1,....,m). Таким образом, добавлением одной переменной и одного ограничения можно заменить задачу с целевой функцией общего вида задачей с линейной целевой функцией.

Пусть теперь φ(Х, ω) = min{f(X)} - ω, φ1(Х),... ..., фm(Х)}. Требование φ(Х, ω)≥0 равносильно совокупности перечисленных ограничений, поэтому новая интерпретация исходных условий находит свое выражение в задаче: найти X, ω→max ω при φ(Х, ω) ≥ 0. Здесь область Uω допустимых X, ω определяется единственным неравенством φ>0, и легко предположить, что какая-то из внутренних точек (Х1, ω1) этой области известна (по крайней мере, ее можно найти методом штрафных функций, см. § 4.4). Формально параметр со может рассматриваться как (n+1)-я составляющая вектора Х = (x1, x2, ....,хn, хn+1), что еще более упростит принятую формулировку задачи и позволит сохранить неизменными используемые обозначения точек, множеств и т. п. (оптимальная величина ω, как и ранее, есть ω* ≡ x*n+1).

Погрузив множество Uω≡U в некоторый многогранник Q (для простоты - параллелепипед, заданный как aj≤xj≤bj, j = 1,...., n+1), обратимся к задаче: найти Х = (х1, х2, ...., хn+1)→max {xn+1}, X∈Q. Искомый максимум (если он существует) будет достигнут в одной из крайний точек Q (см. гл. 1) (обозначим ее X̃). Прямая, проходящая через X̃ и X1∈U0, определяется уравнением X = X1+a(X̃-X1) и пересекает границу U в тех точках ХΓ, которые удовлетворяют условиям XΓ = X1+а(Х̃-X1), φ(ХΓ) = 0, причем 0≤аΒ≤1 (рис. 4.2). Если в этой ситуации сравнить значения xn+1 относящиеся к ХΓ (здесь xn+1+1 = x(n+1)Γ) и X̃ (здесь xn+1=х̃n+1), с х*n+1 то окажется хn+1≥х*n+1≥x(n+1)Γ (замена U на Q означает расширение выбора допустимых X с перспективой улучшить достижимый экстремум целевой функции х̃n+1). В дальнейшем естественно стремиться к сближению величин х̃n+1 и x(n+1)Γ с тем, чтобы последовательно уточнять оценку х*n+1. Сделать это можно путем от сечений каких-то частей многогранника Q гиперплоскостью, касательной к поверхности φ(Х) = 0 в точке ХΓ (в результате Q будет все плотнее "охватывать" U, а погрешность определения x*n+1 уменьшаться).

Каждый шаг подобного процесса связан с необходимостью решать задачу линейного программирования с целевой функцией хn+1 и системой ограничений, включающей не только первоначальные неравенства aj≤xj≤bj (j = 1,....,n+1), но и ряд неравенств вида Δφ(ХΓ)×(X-ХΓ)≥0, учитывающих присутствие отсекающих гиперплоскостей (их число увеличивается на единицу после очередного шага). Получаемая невозрастающая последовательность значений хn+1 (верхние оценки x̃*n+1) сходится при определенных условиях к решению исходной задачи нелинейного программирования; то же относится и к последовательности {x(n+1)Γ}.

Рис. 4.2
Рис. 4.2

Строгое доказательство сходимости рассматриваемого метода связано с предположениями о гладкости функций f(X), φi(Х), выпуклости множества U и т. п., что может не всегда иметь место ка практике. Тем не менее несомненным достоинством метода являются достаточность решения на каждом шаге только линейной задачи и возможность вычислять верхнюю и нижнюю оценки ω* = x*n+1 (это позволяет ориентироваться в общей обстановке и довольствоваться во многих случаях приближенными результатами, не добиваясь сходимости вычислительного процесса к точному оптимуму).

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"