Eng | Rus | Ukr
Исследование операций
24.12.2008

<< prev | ^up^ | next >>

6.4. МЕТОД АППРОКСИМИРУЮЩЕГО ПРОГРАММИРОВАНИЯ

Метод аппроксимирующего программирования (МАП) основан на линеаризации исходной задачи НП и  замене ее последовательностью промежуточных задач ЛП. Его называют также градиентным методом с малой длиной шага в отличие от обычных градиентных методов [50].

Итак, пусть задача НП задана в виде:

минимизировать                                  (6.4.1)

при условиях

                                  (6.4.2)

                            (6.4.3)

После линеаризации в окрестности точки  задача формулируется следующим образом:

минимизировать       (6.4.4)

при условии, что имеют место ограничения в виде равенств

                   (6.4.5)

и неравенств

             (6.4.6)

где                                                                  (6.4.7)

Пусть  - допустимая точка в . Произведем замену в (6.4.2), (6.4.3) нелинейных функций их аппроксимациями в окрестности точки . В результате получим соотношения (6.4.5), (6.4.6). Далее решаем задачу ЛП, представляемую этими соотношениями при следующем добавочном условии:

                  (6.4.8)

где  - абсолютное приращение , а  - маленькая величина, ограничивающая длину шага при перемещении в произвольном направлении и не позволяющая выходить вектору    за пределы допустимой области задачи (6.4.4).

Решение задачи (6.4.4) с учетом (6.4.5), (6.4.6) для разности  дает . Вычислив , повторяем выше указанную процедуру при постепенном уменьшении , чтобы довести отклонение элементов  до величины, определяемой принятым допуском, и стремимся достичь такой ситуации, когда минимизирующая поправка к найденному на предыдущей итерации значению  оказывается меньше некоторого наперед заданного числа.

В задаче (6.4.4) дополнительные ограничения для  можно ввести и другим способом. Обозначим  при  через , а при  через . Тогда прежде чем реализовать очередную аппроксимирующую процедуру, необходимо учесть ограничения для допустимых перемещений в пространстве решений, которые задаются следующими соотношениями:

 ,     

где                                                       (6.4.9)

                        (6.4.10)

 - максимальное допустимое перемещение вдоль -й оси координат на -м шаге;  - нижняя и верхняя границы для переменной . Если , то . Когда значение  близко к своему верхнему пределу, т.е. , то

                       (6.4.11)

и, следовательно ,

                    (6.4.12)

или , что гарантирует не превышение переменной  своего верхнего предела. Аналогичные рассуждения для случая, когда , показывают, что в этом случае . Соотношения (6.4.5), (6.4.6), (6.4.12) образуют систему линейных неравенств и уравнений, которые подлежат решению методами линейного программирования. Для этого решения можно использовать симплекс-метод, но сначала необходимо привести все ограничения к каноническому виду, введя свободные переменные, а затем и искусственные. Пока на каждом шаге (итерации) полученные решения являются допустимыми, МАП работает весьма быстро. Однако в случае, когда на каком-то шаге вектор  выходит за пределы допустимой области, процесс поиска в значительной мере замедляется. В процессе решения задач ЛП вначале стремятся удовлетворить ограничениям, которые не позволяют вектору  выходить за пределы допустимой области, а затем пытаются улучшить значения ц.ф., и именно этим

МАП отличается от других методов.


Отметим следующие трудности, которые возникают при решении задач НП методом МАП [50].

1. Оптимизация происходит очень медленно, если стремиться сделать векторы ,  и  допустимыми или очень близкими к допустимым. На рис. 6.10 представлен случай, когда малый допуск при учете ограничений приводит к тому, что поиск оптимального решения оказывается слишком малошаговым и протекает медленно.

При увеличении допуска решение задачи НП может остаться недопустимым, если возникает потребность остановки ЭВМ из-за ограничения ресурса машинного времени.

2. Трудно сравнивать между собой следующие один за другим два вектора  та , которые приводят к различным значениям и в различной степени нарушают множество ограничений.

Например, необходимо сравнить векторы  и . Пусть , но ограничение  для  нарушается сильнее, чем для . Ответить на вопрос, какой из векторов ,  будет предпочтительнее, дать весьма трудно.

3. Если целевая функция характеризуется высокой степенью нелинейности, то направление поиска оптимальной точки, получаемое путем решения линеаризованной задачи, может быть вычислено слишком неточно.

4. При использовании метода МАП трудно придумать такую процедуру учета исходных данных, которая  ускоряла бы процесс оптимизации.

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004