Глава 10. НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПРИМЕНЕНИЕМ К ТЕОРИИ ЛЯПУНОВА ДЛЯ РАЗНОСТНЫХ УРАВНЕНИЙ

Общая задача НЛП может быть определена как нахождение

В этой главе мы разрабатываем алгоритмы для решения этой задачи. Первый алгоритм, названный методом центров, представляет собой прямое применение теоремы сходимости А с предварительным преобразованием задачи с ограничениями (10.1) в последовательность задач без ограничений. Вторая часть этой главы посвящена методу Лагранжа для задачи (10.1), который основан на разностных уравнениях и имеет интересную интерпретацию в терминах определенных динамических экономических процессов. В заключительной части мы анализируем более общие динамические процессы, которые описываются разностными уравнениями. Для этих задач теорема сходимости А становится аналогом теории устойчивости Ляпунова.

10.1. МЕТОД ЦЕНТРОВ

Метод центров принадлежит классу методов, которые решают задачу (10.1), сводя ее к последовательности задач без ограничений. Алгоритмическое отображение здесь весьма простое. Сначала определим функцию

Следует обратить внимание на то, что в том и только в том случае, если

Тогда алгоритмическое отображение А принимает вид

Словами это можно выразить так: при заданной точке последующей точкой является любая точка, которая дает максимум функции без ограничений. Мы предполагаем, что все максимумы в задаче существуют (упр. 4) и что исходная допустимая точка задается. Обратите внимание на то, что при этом все точки должны быть допустимыми.

Доказательство сходимости. Для установления сходимости будет использована теорема сходимости А. Все функции и предполагаются непрерывными и, кроме того, предполагается, что если —решение задачи (10.1), то в любой окрестности х имеются точки такие, что для всех

Из этого предположения вытекает, что вблизи имеются допустимые точки которые не попадают на границу допустимой области. Так что, если даже х находится на границе, то все же вблизи имеются точки которые находятся внутри допустимой области. Как обычно, мы предполагаем, что вырабатываемые точки принадлежат компактному множеству, поэтому условие 1 выполняется (упр. 4).

Условие 2. Подходящей точкой в данном случае является любая оптимальная точка х задачи (10.1). Положим также Рассмотрим теперь условие 26. Если оптимальная точка, то, значит, не существует допустимой точки для которой Тогда согласно (10.2)

Следовательно из условия вытекает, условие 26 выполняется.

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

Тогда для этого

Из уравнения (10.2) следует вывод, что соотношение влечет за собой неравенство

Условие 3. Остается только проверить условие 3. Пусть По определению

Переходя к пределу в (10.4), получаем

Но тогда максимизирует по всем и поэтому (Другое доказательство замкнутости см. в упр. 5.) Таким образом, метод центров сходится.

Обратите внимание на то, что последовательные точки геометрически находятся внутри, в «центре» допустимой области, поскольку . С этим связано и название алгоритма.