Исключение областей, не содержащих оптимальных решений

Рассмотрим задачи поиска глобального экстремума в условиях ограничений вида

Здесь

f1 (xvx2,.......,Xj,...,хп), j = 0,1,...,га, - сепарабельно квазимо-

нотонные функции в сильном смысле по каждой из переменной задачи. Пусть для некоторой переменной Xj выполняются условия

и критерий оптимальности f°(xl,x2,...,xj,...,xn), как и все функции ограничений fl(xl,x2,...,Xj,...,xn), i = являются сепарабельно квазимонотонными функциями в сильном смысле по каждой из переменной задачи, т.е., если Xj е НJs, то hs < Xj < h2s j = 1,..., n. Вне зависимости от значения всех других переменных хк, к = ,

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

Если f°(xl,x2,...,Xj,...,xn) является неубывающей функцией по переменной Xj, т.е. q^ = h2s, то найдем

Если f°(xl,x2,...,xj,...,xn) является S+QMF(j) невозрастающей функцией по переменной Xj, т.е. q°jf = h}js, то найдем

Утверждение 2.4.

1. Если целевая функция f°(xl,x2,...,Xj,...,xn) является S+QMF(j) неубывающей функцией по переменной Xj, т.е.

~о,+ 1 2

qjs = hjS, то при условии

подмножество переменной

не содержит оптимальных планов.

2. Если f°(x,,x2,...,Xj,...,хп)является S~QMF(j)neB03рас-

тающей функцией по переменной Xj, т.е. q°^+ = hxjs, то подмножество переменной

не содержит оптимальных планов.

Следовательно, подмножество переменной Hjs = Hljs U H2js

может быть отброшено как неперспективное, и на дальнейших шагах итеративного процесса для неубывающей функции f°(xl,x2,...,Xj,...,xn) подлежит рассмотрению только подмножество

возможных значений переменной е Н ? ?+1, где

а в случае невозрастающей функции - значений переменной

хj е^,«1>где

Используя приведенные в утверждении 2.4 выражения, аналогично описанному в разделе 2.4 алгоритму, может быть построен ите- ратив-ный процесс исключения областей, не содержащих оптимальных реше-ний. Обозначим этот итеративный процесс ИР_2. На каждом s -м шаге итеративного процесса в цикле для каждой переменной / = 1,...,и вы-полняем вычисления в соответствии с выражениями (2.47) и (2.49) или (2.48) и (2.51), определяем новый параллелепипед Hs+l ci Нs. Если выполнено п шагов итеративного процесса и выполняются условия Hs+k = Hs, к — 1,...,п, то алгоритм завершает работу.

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

Проиллюстрируем работу операторов и алгоритма выделения областей, не содержащих оптимальных планов на простом числовом приме-ре.

Пример 2.3.

в условиях ограничений хх > 0, х2 ^ 0, а также

На основе выполнения итеративного процесса ItP_l получаем

Принимая во внимание, что f°(xl,x2) является монотонно возрастающей функцией по переменной х{ и монотонно убывающей функцией по переменной х2, положив в каждом из неравенств граничные значе-ния другой переменной, которые являются наиболее неблагоприятны-ми для их выполнения, получаем

Следовательно, х2 = 0.

Таким образом, подмножество Н = {х{ = 24, х2 =0} выражда- ется в точку. Т.е. только как результат применения операторов выделения областей, не содержащих допустимых и оптимальных планов, было получено решение этой нелинейной задачи математического программирования.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >