XIV Аттетков и др. Методы оптимизации (1081420), страница 7
Текст из файла (страница 7)
В частном случае, когда заданы линейные оераничения тииа равенства Вх = е1, х Е К", (1.21) где д е Кв, В матрица размера в х п, а параметры оптимизации могут принимать лишь неотрицательные значения, т.е. х,>0, )=1,п, (1.22) соотношения (1.20)- (1.22) составляют сгпандартпную задачу линейноео проераммирования, или задачу линейного прозрамммрованил в стандартной форме (в литературе ее часто называют канонической задачей линейного программирования, или задачей линейного программирования в канонической форме). Условия (1.22) можно представить в виде х Е К"„', где К", декартово произведение п множеств К„неотрицательных действительных чисел, называемое иногда неотприцагпельным оргпонтом размерности и. Если к (1.20) — (1.22) добавить т 1.5.
Классы задач оптимизации оерониченнй пита нераеенстпеи а Е а11ай < йт; 1=1 (1.23) 1 (с, а) + — Я:в.,,в) — т ппп, (1.24) где (~1 — положительно определенная матрица порядка и., то говорят о задаче нвадратпичноео проераммирован я, а функцию вида (1.24) называют нвадратичнои. В случае, когда целевая функция является отношением двух линейных функций, а ограничения линейны, имеем задачу дробнолинейноео проераммирования. Ее формулировка включает ограничения (1.21) — (1.23) и условие минимума функции (д, х)+о (т, и) +Д (1 25) где а,.
Е 2, г = 1, т, то соотношения (1.20) -(1.23) приведут к формулировке общей задачи линейноео проера мирования. При этом ограничения (1.22) могут относиться не ко всем и параметрам оптимизации, а лишь к некоторым из них. При отсутствии ограничений типа равенства соотношения (1.20), (1.22) и (1.23) составляют формулировку основной задачи линейноео проераммирования (иногда ее называют естпестпвенной задачей линейноео проераммирования). Неравенства а ) а, ай < о, и а: < т < 61, 1 =1, и, называют прямыми оераничениями на переменные задачи, причем последнее относят к двустпоронним, а первые два к одностпоронним.
Таким образом, ограничения (1.22) являются прямыми односторонними. Методы решения задач линейного программирования подробно рассмотрены и обоснованы в [ХХ). Если при линейных ограничениях минимизируемая целевая функция помимо линейной комбинации вида 11.20) включает положительно определенную квадратичную форму., т.е. 46 ь 3АдАни ОптиАтизАции где т7 б К"', т б Б'.", о б К и,д е К заданы. Соотношения Д(а) = ~6 (л ) — ~ тпш; 1=-1 в Ы ') =,~,д.т('1) <Ъ; т=.т тт>0, 1=1,п,. (1.26) г = 1, тп; где чт Е К заданы, определяют задачу сепарабельноео проераммирования. В этой задаче целевая функция 1е(а) и функции д,(а) в левой части ограничений являются суммой функций, каждая из которых зависит только от одного параметра оптимизации.
В этом случае функции 1о(а) и д,(ж) называют сепарабельными. В прикладных задачах целевая функция нередко имеет вид т у(ж) = ~~ стр,(а), 1=-1 (1.27) (1. 28) где а,. Е Я. Требование положительности коэффициентов ст, г = 1, т,, послужило причиной того, что такой вид целевой функции стали называть позиномом в отличие от полинома (многочлена), в котором коэффициенты могут быть и неположительными. Кроме того, в многочлене показатели степени аргументов являются целыми неотрицательными числами, а в позиноме благодаря положительности параметров оптимизации где а = (хт, ..., х„) б Б'.", с; Е К+, а В" декартово произведение и множеств Я.е положительных действительных чисел, называемое иногда полоэтсиптельным орптанптом. При этом функции р,(ж) имеют вид 1.5. Классы задач оптимизации 47 выражение х " определено для любых действительных чисел а, Если целевая функция и левые части ограничений типа равенства и (или) неравенства в задаче минимизации являются позиномами, то такую задачу называют задачей ееометричесноео проераммирования.
В задаче нелинейного программирования ограничения могут быть заданы в неявном видс. Тогда множество Н возможных альтернатив приходится строить путем количественного анализа математической модели объекта оптимизации (см. пример 1.10). Если ограничения принадлежат к типам равенства и (или) неравенства Ц,х) = О, 1 = 1, Й; 91(х) ( О, 1 = 1,тп, (1 29) но хотя бы одна из функций 11(х), д,(х) или целевая функция нс является линейной. то говорят об общей задаче неяинейноео проераммирования. Ясно, что такая формулировка включает задачи квадратичного, дробно-линейного, сепарабельного и геометрического программирования. Среди целевых функций достаточно широкий класс составляют вьтуклые функции.
Во многих прикладных задачах оптимизации область допустимых значений параметров оптимизации оказывается выпуклым множеством. В такой области целевая функция может сохранять одно и то же направление выпуклости, т.е. выпукла либо вниз (выпукла), либо вверх (вогнута). Например, зависимость эффективности технического устройства от параметров оптимизации является вогнутой функцией. Дело в том, что чем выше технические характеристики устройства, тем труднее добиться его дальнейшего совершенствования и существенного приращения эффективности.
Наоборот, целевые функции, выражающие массу, габариты или стоимость технического устройства, по тем же причинам обычно выпуклы. Аналогичная ситуация характерна и для функций, описывающих зкономические системы. Например, рост объема выпускаемой продукции происходит не прямо пропорционально 48 Ь ЗАДА ЧИ ОПТИМИЗАЦИИ капиталовложениям или количеству используемых ресурсов, а с замедлением, причем это замедление часто тем больше, чем больше объем производства. Это приводит к вогнутости так называемых производственных функций, выражающих зависимость объема выпускаемой продукции от израсходованных ресурсов.
Наоборот, при фиксированном объеме производства дальнейшее снижение производственных затрат и стоимости единицы продукции по сравнению с достигнутым уровнем также происходит с замедлением, что приводит к выпуклости целевых функций, описывающих стоимостные характеристики производства. Ясно, что любую вогнутую целевую функцию, изменив знак, можно сделать выпуклой. Задачи оптимизации, в которых необходимо найти наименьшее значение выпуклой целевой функции, рассматриваемой на выпуклом множестве, относят к задачам выпуклого программирования. Частными случаями таких задач являются задачи квадратичного и линейного программирования. Задачи геометрического программирования при некоторых дополнительных условиях также являются задачами выпуклого программирования.
Если множество й допустимых решений оказывается конечным множеством, то мы имеем задачу дискретного программирования, а если к тому же координаты этих точек целые числа, то — — задачу целочисленного программирования. Такие задачи (в том числе для линейной целевой функции) рассмотрены в ~ ХХ ) . Вопросы и задачи 1.1. Решите задачи, рассмотренные в примерах 1.1 и 1.2, как путем построения функции Лагранжа, так и исключением из целевой функции одного из параметров оптимизации. 1.2. Получите (1.3) из необходимого условия экстремума функции (1.2). Вопросы и задачи 1.3. Найдите решение задач, рассмотренных в примерах 1.6 и 1.7, как путем построения функции Лагранжа, так и исключением из целевой функции одного из параметров оптимизации.
1.4. Классифицируйте рассмотренные в 1.2 — 1.4 задачи, отнеся каждую из них к тому или иному (или нескольким сразу) классу задач оптимизации и к одному или нескольким вариантам формулировок, рассмотренных в 1.5. 1.5. Найдите максимальное и минимальное значения функции ь~(6/О) (1.1) при )ь(Н Е [О, 1] и сравните результат с полученным в примере 1.3. 1.6.
Используя необходимые и достаточные условия экстремума функции одного переменного, убедитесь, что функция 7'(а), рассмотренная в примере 1.4, достигает максимума в точке а„= 3. 1.7. Решите задачу оптимального проектирования бака горючего, аналогичную рассмотренной в примере 1.6, но при заданной площади Я расходуемого листового материала максимизируйте объем бака. 1.8. Как из прямоугольной листовой заготовки с отношением сторон 1: 2 вырезать круговой сектор, из которого можно было бы изготовить коническую воронку наибольшего объема? 1.9.
Покажите, что геометрический момент инерции квадратного сечения относительно любой оси, лежащей в плоскости квадрата со стороной Ль/2 и проходящей через его центр, постоянен и равен 7 = Ль/3 (см. пример 1.7). 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 2.1. Предварительные замечания В некоторых случаях оераничения в задаче огнпимизаннаи позволяют через один из параметров оптимизации выразить остаяьные и исключить их из целевой функции.
В результате задача будет сведена к поиску наибольшего или наименьшего (в зависимости от цели оптимизации) значения скалярной действительной функции 1 (ж), л е РЦ) С К, выражающей критерий оптимальности. Выбирая тот или иной знак перед этой функцией, всегда можно ограничиться лишь поиском се наименьшего значения в области определения РЦ), заданной с учетом ограничений на параметр оптимизации ас Поэтому далее в этой главе будем рассматривать задачу 1[и) -+ шш, т Е РЦ) С Ж, (2.1) поиска наименьшего значения у„= 1(ж,) функции 1(оо) и точки х, Е РЦ), в которой 1 (л) принимает это значение. Для краткости будем говорить об одномерной минимизации, имея в виду нахождение наименьшего значения функции 1[я) на множестве РЦ) и точек, в которых это значение достигается. Изучение методов одномерной минимизации важно не только для решения задачи (2.1), имеющей самостоятельное значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
