Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

§ 4. Задачи с сепарабельными функциями

Будем, например, искать решение задачи следующего вида:


(2.9)

которое обращает в минимум (максимум) целевую функцию


(2.10)

Здесь все функции в ограничениях и целевая функция являются сепарабельными.

Решение этой задачи может быть получено приближенными методами, в основу которых положена кусочно-линейная аппроксимация функций gij (xj) и fj (Xj) (см. [8]). В результате мы приходим к приближенной задаче, которая может быть решена симплексным методом. В случае, когда функции gij (Xj) обладают соответствующими свойствами выпуклости или вогнутости и fj (Xj) являются выпуклыми (вогнутыми), решение приближенной задачи дает абсолютный минимум (максимум), который в принципе может быть сделан сколь угодно близким к абсолютному минимуму (максимуму) исходной задачи. Множество М допустимых решений, определяемое выражением (2.9), является выпуклым в следующих случаях: 1) в ограничениях со знаком "≥" все gij (xJ) - вогнутые функции; 2) в ограничениях со знаком "≤" все gij (xj) - выпуклые функции; 3) в ограничениях, входящих только со знаком "=", все gij (xj) - линейные функции. Эти правила следуют из определений выпуклого множества (см. п. 2, гл. I, § 3), выпуклой и вогнутой функций (§ 3, гл. II).

Существует ряд практических приемов сведения исходной задачи к виду (2.9) - (2.10), основанных на введении новых переменных.

Пусть, например, в качестве слагаемого в ограничениях или в функции цели имеется произведение xixj, в результате чего эти функции не являются сепарабельными. Введем новые переменные yi и yj следующим образом:


(2.11)

(2.11)

Тогда xixj = yi2 - yj2, и в новых переменных соответствующая функция приобретает сепарабельную форму. При этом в условие задачи включаются два дополнительных ограничения вида (2.11). Таким образом, каждый раз при исключении произведения xixj приходится расширять задачу включением дополнительных ограничений.

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

y = xixj(2.12)

и прологарифмируем это выражение:

lg y = lg xi + lg xj.(2.13)

Далее вводим новую переменную (2.12) и выражение (2.13) в задачу. Очевидно, требование строгой положительности переменных xi и xj позволяет избежать трудностей, которые возникнут из-за того, что lg 0 = -∞.

Можно, однако, модифицировать этот прием таким образом, чтобы он стал пригоден для любых неотрицательных xi и xj. Введем новые переменные zi и zj и некоторые фиксированные положительные числа di и dj таким образом, чтобы

zi = xi + di, zj = xj + dj.(2.14)

Тогда zi≥di>0, zj≥dj>0 и xixj = zizj - dizj - djzj + didj.

Теперь можно ввести переменную y = zizj и записать

lg y = lg zi + lg zj.(2.15)

Вместо произведения xi*xj вводим в задачу новые переменные y, zi, zj и добавляем три новых ограничения (2.14) и (2.15). Этот метод в принципе может быть обобщен на случай произведения любого числа переменных.

С помощью логарифмирования легко преобразовать к сепарабельному виду выражения, содержащие экспоненты, например, e(axi2+bxj), введя новую переменную y:


(2.16)

Аналогично при наличии в задаче членов вида xixj производим замену следующих переменных (при xi>1, xj≤0):


(2.17)

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

предыдущая главасодержаниеследующая глава


Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2016
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru