5. Учет ограничений в задаче оптимального планирования

В гл. 5, 4 было показано, что с помощью R-конъюнкции система неравенств, определяющая область допустимых решений может быть свернута в одно неравенство Семейство гиперповерхностей при включает границу области значениям соответствуют гиперповерхности, расположенные в области а значениям гиперповерхности, расположенные вне области Задача оптимального планирования состоит в отыскании в области точки, которой соответствует наименьшее значение функции цели

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

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

точек. Область может быть определена с помощью неравенства

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

Имеется довольно обширный класс задач, к которому, в частности, можно отнести задачи линейного и выпуклого программирования, где функция имеет единственный для каждого локальный максимум Этот максимум может быть найден одним из градиентных методов или методов случайного поиска, как бы ни выбиралась начальная точка. Следовательно, функция может быть найдена в любой точке интервала Заметим, что функция является неубывающей функцией и Оптимальное значение функции цели является единственным нулем функции на интервале Наиболее простым способом нахождения этого корня является способ последовательного деления отрезка Вначале берется значение функции в средине отрезка т. е. в точке Если то делится пополам отрезок если же то делится пополам отрезок Процесс деления продолжается до тех пор, пока длина отрезка, подлежащего дальнейшему делению, не станет меньше Тогда средина этого отрезка с точностью до является корнем уравнения Точка в которой достигается максимум функции является оптимальным решением задачи (оптимальным планом).

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

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

В общем случае функция может иметь не единственный локальный максимум и в этом случае мы сталкиваемся с многоэкстремальной задачей на отыскание глобального максимума. Для решения такой задачи вряд ли может быть предложен какой-либо эффективный общий метод, не основанный в том или ином виде на методе полного перебора. На практике чаще идут по пути многократного изменения (обычно, случайного) начальных условий. Если, например, начальная точка выбиралась раз, было найдено точек максимума и то мало вероятно, что добавление новых начальных точек позволит найти новый локальный максимум. В таком случае из точек локального максимума выбирается такая, которой соответствует наибольшее значение функции и принимается за точку глобального экстремума.

Сделаем одно замечание к изложенному выше методу поиска оптимального плана. Пусть в процессе поиска максимума функции найдена точка принадлежащая области значение функции цели в которой равно В этом случае оказывается выгодным изменить направление поиска максимума, заменив в функции значение на Точка может рассматриваться как начальный для отыскания максимума

функции Очевидно, что в области выполняется неравенство

Поэтому в процессе поиска максимума функции будет найдена точка в которой значение функции цели В этом случае также изменяем процесс, заменяя значение значением Процесс прекратится лишь тогда, когда область не будет содержать внутренних точек, т. е. когда

В таком варианте метод поиска оптимального решения был применен Е. Л. Ющенко [49] для решения задачи линейного программирования.