Функции с легко вычисляемыми экстремальными значениями

Определенный интерес представляют также функции (р{х) , зна- че-ние минимума и максимума по всем переменным при ограничениях на переменные в виде х е Нs находится на основании простых вы- числе-ний. Приведём только несколько примеров таких функций.

1. Абсолютное значение функции - (р{х) = |/(х)|, где | • | - абсолютное значение функции, a f(x) - одна из сепарабельно квазимоно- тонных функций в сильном смысле по всем переменным

Здесь и в дальнейшем „if ‘ следует читать «если», а «&» - «и».

Тогда

Аналогичные выражения могут быть получены и для максимума функции

Для любых функций вида

где г - любой целый и четный показатель степени (положительный или отрицательный), a f(x) - любая одна из сепарабельно квазимоно- тонных функций в сильном смысле по всем переменным справедливы выражения:

а значения переменных в оптимальном решении определяются согласно выражениям (2.8), (2.9).

Выделение областей, не содержащих допустимых планов

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

2,4.1. Некоторые свойства систем неравенств

Пусть f(x) - некоторая функция SQMF, и условиями решаемой задачи предусмот-рено выполнение ограничения вида

Отметим, что все ограничения вида

легко могут быть сведены к ограничениям вида (2.27).

Обозначим соответственно Q1/^, - векторы аргументов

минимума и максимума функции f1 (х), вычисляемые в соответствии с выражениями (2.8), (2.9) и содержащие все переменные к = 1 к Ф j (кроме переменной /),

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

Если существует такое число t‘js

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

не содержит допустимых решений, удовлетворяющих неравенству (2.27), в условиях, что х е Н5.

Если задача (2.28) не имеет решения (t1- не существует), то подмножество Нs не содержит допустимых решений неравенства (2.27). Доказательство.

Из свойств SQMF(j) как следствие следует справедливость (2.9), (2.10) в случае

т.е. при подстановке в эти выражения компонент вектора Ql'^n ?

Предположим, что найдется такое значение pjs е Н jS, что Pjs > t'js» если / е JT»либо

Следовательно, должно выполняться неравенство

Но это противоречит паре условий (2.2),(2.3). Возникшие противоречия являются доказательством утверждения 2.1.

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

Если справедливо утверждение 1, то не существует никаких других значений tlb е Нь, к = 1 к Ф j , таких, что

при которых найдется некоторое другое значение pljs g Hjs, которое обеспечит выполнение неравенства

в том случае, если значения одной, некоторой группы или всех переменных к е J /{j} выбраны согласно (2.32).

Доказательство.

Из утверждения 2.1 следует справедливость неравенства

Замена в (2.34) одного, группы или всех значений q1^ на tlb, к=1,...,п, к Ф j, взятых из условий (2.32), может только усилить неравенство (2.33), что доказывает справедливость утверждения.

Следствие утверждений 2.1 и 2.2.

Подмножество значений переменных

не содержит допустимых решений, и дальнейшему рассмотрению подлежит подмно-жество

Рассмотрим систему неравенств

в условиях ограничений х е Нs, т.е. системы п -мерных параллелепипедов (2.4), где каждая из функций f'(x) являетяся SQMF(j) по каждой из переменных / = 1,..., п.

Принимая во внимания обозначения (2.1), (2.2), определим со- тветственно , ?2* пт

- векторы значений всех переменых к = 1,...,п, кФ j, компоненты которых соответственно равны ql? и ql?.

Вычислим

Подмножества Н р и Н jS определим следующим образом где

Определим

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

  • 1. Если для некоторого индекса /' е J справедливо неравенство tjs > tjS, то система неравенств (2.37) в условиях х е Нх не имеет допустимых решений.
  • 2. Подмножество Н jS = HJS U Hjs, определенное в соответствии с (2.33)-(2.35), не содержит допустимых планов, обеспечивающих ре-шение системы неравенств (2.31) в условиях xeHs.

Доказательство.

  • 1. Если tjs > tjs, то Hjs = 0, и, следовательно, не существует значе-ний Xj, удовлетворяющих системе ограничений (2.31), и первое по-ложение утверждения 2.3 доказано.
  • 2. Предположим, что Н /? содержит допустимые значения X-. Рассмо-трим сопутствующие этой посылке следующие два условия.
  • а) Пусть найдется такое значение pjs е Нjs, pjs < tjs, удовле- творя-ющее всем ограниче-ниям

Тогда найдется такое ограничение ix, для которого / е J‘1,+, а tljs = tjs > pjs. В соответствии с утверждениями 2.1 и 2.2 справедливо

т.е. z’j -е ограничение при значении Xj = pjs не выполняется ни при каких значениях других переменных хь е Hks, к = к Ф j.

в) Пусть найдется такое значение ljs е Hjs, ljs > tjs, удовлетворяющее всем ограничениям

В этом случае найдется такое ограничение i2, для которого / е J, +, для которого /е/‘ и tjs = tjs < ljs. В соответствии с утверждени-ями 2.1 и 2.2 справедливо

т.е. i2 -е ограничение при значении ху. = ljs не выполняется ни при каких значениях других переменных хь е Нь , к = к Ф j.

Но эти два условия противоречат исходной посылке, что под- множе-ство Н jS содержит допустимые планы. Два возникших противоречия доказывают второе положение утверждения 3.3.

Следствия утверждения 2.3.

1. Подмножество

где Н^определяется согласно выражениям (2.35), не содержит допустимых планов.

2. Допустимое решение системы неравенств (2.27) может искаться только в подмножестве переменных, Hs+l, которое определяется в соответствии с (2.36).

Подмножества Н j J+1 определяются согласно выражениям

2.4.2. Итеративный процесс исключения областей, не содержащих допустимых планов

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

Введем счетчик количества шагов М , в течение которых Hs+l = Hs, т.е. не происходит изменения п -мерного параллелепипеда ни по одной из переменной. В начале процесса положим

На каждом s -м шаге итеративного процесса в цикле для каждой переменной / = выполняем вычисления в соответствии с выра- же-ниями (2.36), (2.38)-(2.42).

Если на некотором s -м шаге для некоторого индекса переменной / g J выполняются условия утверждения 2.3, т.е. Нj J+] = 0 , то

си-стема ограничений задачи не содержит допустимых планов, и ите- ра-тивный процесс останавливается.

Если на некотором -м шаге справедливы условия Hs +1 =

(т.е. Н jSl = 0), то значение М увеличиваем на 1. Если М = п, то полу-ченное подмножество Hs +l не может быть подвергнуто дальнейшему изменению (сужению), и итеративный процесс останавливается, т.е дальнейшее исключение областей, не содержащих допустимых планов, на основе описанного алгоритма невозможно.

Если Н +l a Hs и при этом М > 0, то полагаем М — 0 и пе-

рехо-дим к следующему шагу процесса.

Ясно, что через конечное количество шагов процесса мы либо при-дем к факту о несовместности исходной системы ограничений,

либо получим п -мерный параллелепипед Н = Нs+x =? 0, который не мо-жет быть в дальнейшем подвергнут изменениям.

Отметим, что успешное завершение этого итеративного процесса и получение в результате этого п -мерного параллелепипеда

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

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

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

Пример 2.1:

Ниже показаны шаги итеративного процесса.

и итеративный процесс останавливается.

Рассмотрим выполнение этого итеративного процесса для случая нелинейной системы неравенств.

Пример 2.2.

Пусть задана система ограничений: х • > 0, / = 1,2,3;

Итеративный процесс выделения подмножества переменных, не со-держащего допустимых решений, состоит из нескольких шагов:

Итеративный процесс на этом останавливается.

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