XIV Аттетков и др. Методы оптимизации (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска), страница 3

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

Канторович'. Задача Канторовича была связана с выбором оптимальной производственной программы, что и объясняет появление в названии этого класса задач слова е программирование". При нелинейной зависимости целевой функции или ограничений от параметров оптимизации говорят о задаче нелинейноео проераммирования. 1.2. Некоторые простые примеры Начнем с рассмотрения достаточно простых задач оптимизации из геометрии, алгебры и некоторых других разделов математики. Эти задачи обычно можно решить геометрическим *Л.В.

Канторович (1912 1986) — отечественный математик и экономист, лауреат Нобелевской премии (197ог г.). 18 Ь ЗЛДЛПИ ОПТИМИЗАЦИИ или алгебраическим путем, а также при помощи необходимых и достаточных условий экстремума действительной (скалярной) функции одного переменного [П). Включение таких примеров в эту книгу важно по нескольким причинам. Во-первых, эти зада~и тесно связаны с историей развития методов оптимизации и позволяют наглядно продемонстрировать многообразие объектов оптимизаиии.

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

1.3). Пример 1.1. Найдем стороны прямоугольника, вписанного в окружность радиуса Л и имеющего наибольшую площадь Л (р '. 1.1). В Эта задача известна с глубокой древности, и ее нетрудно решить геометрическим путем. Диагональ вписанного в окружность прямоугольника является диаметром окружности и имеет фиксированную П длину. Площадь з' прямоугольника равна половине произведения его Рис. 1.1 диагоналей на синус угла у между диагоналями, т.е.

Л = 2Лз вшу. Ясно, что эта площадь будет наибольшей при в1п у = 1, или при у = х/2. В этом случае диагонали прямоугольника перпендикулярны, а сам прямоугольник представляет собой квадрат. Таким образом, прямоугольником наибольшей площади, вписанным в окружность, является квадрат со стороной ЛчГ2 и площадью 2Лз. Если в качестве параметров оптимизации выбрать длины а > О и 6 > О сторон прямоугольника, то получим целевую Ь2.

Некоторые простые примеры 19 функцию Я = аб и ограничение ъ'аз+ Ьз = 2Л типа равенства. нелинейные по отношению к этим параметрам. Поэтому рассматриваемую задачу оптимизации следует отнести к задачам нелинейного программирования. се математическую формулировку можно представить в виде < Я =аб — «шах; аз+ Ьз = 4Л2. а > 9, Ь > б. Эту задачу можно решить одним из известных стандартных путей: либо использовать формальную процедуру поиска условного экстремума функции Я = аб двух переменных с одним уравнением связи, построив функцию Лагранжа, либо выразить при помощи ограничения одно переменное через другое и перейти к поиску экстремума функции одного переменного.

Отметим, что в данном случае возможен и нестандартный способ решения, связанный с построением вспомогательного соот- и — ь~ ношения 4Л2 — 23 =аз+Ь~ — 2аб= (а — Ь)2, или Я = 2Л~ — ~~ ь) 2 Отсн«да <ледует, что Я достигает наибольшего значения Я* = = 2Лз при условии а = Ь, т.е. когда прямоугольник яавяется квадратом, причем а = Ь = Лх/2. Пример 1.2 (задача Евклида). В заданный треугольник АВС с высотой Н и основанием Ь вписать параллелограмм наибольшей площади, стороны которого параллельны двум сторонам Н ...Н треугольника (рис. 1.2). Критерием оптимальности в этой задаче является достижение Я площадью параллелограмма нан- и большего зна 1ения, а ог1«ани «ения связаны с условиями параллельности сторон и размещения параллелограмма в пределах заданного треугольника.

Выберем прямоугольную систему координат, совместив ее начало с общей вершиной параллелограмма и треугольника 20 1. ЗАДАЧИ ОПТИМИЗАЦИИ Я = 6х — > свах; Н вЂ” 6 х Н 6' — 6>0, х>0 Эту задачу также можно решить стандартными способами (см. пример 1.1). Ее решением является параллелограмм с основанием х„= 6/2 и высотой 6, = (1 — х„(Ь)Н = Н(2. Отметим, что выбор вершины треугольника, с которой совпадает вершина параллелограмма, не является существенным, так как в любом из трех вариантов выбора вершины треугольника площадь параллелограмма максимальной площади равна половине площади треугольника АВС.

Пример 1.3. В прямой круговой конус вписан прямой круговой цилиндр так, что основания конуса и цилиндра лежат в одной плоскости (рис. 1.3). Найдем наибольшую возможную часть объема конуса, занятук1 таким цилиндром. Как и зада та Евклида, зта задача известна тысячи лет. Ее можно решить, используя неравенство средних, известное еще Пифагору, согласно которому среднее геометрическое не превышает среднего арифметического, т.е. з — — а+6+с ъ'абс ( 3 ч'аб ( а+6 2 и т.п., причем среднее геометриче- ское равно среднему арифметическо- му только в том случае, когда все чи- сла равны между собой.

Рис. 1.3 (вершина А на рис. 1.2), а ось абсцисс — с одной из сторон треугольника. В качестве параметров оптимизации выберем основание х параллелограмма и его высоту 6. Тогда площадь Я параллелограмма можно записать в виде Я = 6х, а условие, что параллелограмм вписан в треугольник, как ограничение типа равенства (Н вЂ” 6) (Н = х/6, которое вытекает из подобия треугольников РВЕ и АВС. Итак., имеем задачу оптимизации 22 1.

ЗАДА'1И ОПТИМИЗАЦИИ Пример 1.4. Найдем значение параметра и, при котором 1 достигает максимума функция 1(а) = ехр( — — (игл+ тд), где ил., хг — корни квадратного уравнения ъг + ела + За — 1 = О. По теореме Виста* [1-4А) имеем х1+ юг = — а и т1тг = За — 1. Отсюда находим тг+игг (т +тг)г 2тьлг=аг — ба+2=(а — 3)г 7 и в итоге л" (сл) = ехр(3,5 — 0,5(а — 3)л). Так как (а — 3)г > О, а ехр( — 0,5(а — 3)г) убывает с возрастанием (а — 3)г, то функция 11а) достигает своего максимума при а, = 3 и этот максимум равен 1(а„) = ехр13,5) — 33,115.

Применение теоремы Виета позволило в данном случае упростить задачу и даже избежать использования дифференциального исчисления для поиска экстремума функции 11а), заданной как композиция функций. Пример 1.5. Луч света, переходя из одной однородной среды в другуял, падает на границу раздела этих сред под углом ол к направлению нормали и после преломления на этой грани- 1 це составляет с нормалью угол аг (рис. 1.4). Требуется найти соотношение между этими уг~г лами.

В к Из курса физики известно, что в соответствии с принципом Рис. 1.4 Ферма** геометрической оптики свет при прохождении через среду с различными свойствами выбирает такую траекторию, время прохождения которой минимально. Пусть 11 — время прохождения световым лучом отрезка АМ со скоростью сл в среде 1, т абсцисса точки М падения *Ф. Виет (1640- 1603) — французский математик и юрист. "*П. Ферма (1601 1666) . - французский математик. 23 1мт Задачи оптимального проектировании светового луча на границу двух сред, 12 — время прохождения световым лучом отрезка МВ со скоростью ся в среде 2. Тогда время прохождения света из точки А в точку В будет равно Лнь е Яе1:Г ь(т) =11+12 — + . (1.2) С1 сз Из необходимого условия экстремума функции е(и), который по физическому смыслу задачи является минимумом, получаем чСЬ~ '- Х- 8111ет1 с1 (1.3) с2 о — и ь1н;,2 чич ь — 'е Это равенство выражает закон преломления света, установлен- ный В.

Снеллиусом*. 1.3. Задачи оптимального проектирования При создании технического устройства различного назначения обычно часть его параметров можно изменять в определенных пределах. Это приводит к тому, что при проектировании появляется некоторое множество вариантов создаваемого устройства. В результате возникает проблема выбора из этого множества а,льтернатие наилучшей альтернативы с точки зрения критерия оптимальности. Соответствующие такому выбору задачи опгпимизииии часто называют задачами оптимального проектирования. Пример 1.6.

Одной из наиболее простых задач оптимального проектирования является выбор размеров емкости определенной формы, имеющей наибольший объем при заданной площади поверхности или же наименыпую площадь при заданном объеме. *В. Снеллиус (1580. 1626) -- нидерландский астроном и математик. К ЗАДАЧИ ОПТИМИЗАИИИ Пусть требуется спроектировать бак горючего в виде прямого кругового цилиндра заданного объема Г, на изготовление которого будет затрачено наименьшее количество листовой стали.

В качестве параметров оптимизации выберем радиус Л и высоту Н цилиндра. Тогда затраты материала на изготовление бака будет определять суммарная площадь Я его боковой поверхности и двух плоских днищ. Таким образом, необходимо минимизировать целевую функцию Ь' = 2«Л(Н+Л) при ограничении типа раеенстеа пЛ~Н = Ъ', т.е.

решить задачу нелинейного прогрвммнрооиння. Если из целевой функции при помощи ограничения ис«лючить й и записать ее в виде Я(Л) = — + — + 2«Л, 1' $' Л Л то произведение слагаемых не будет зависеть от Л., и для нахождения ее минимального значения удобно использовать то же неравенство между геометрическим и арифметическим средними, что и в примере 1.3: Я(Л) = — + — + 2«ЛЯ ) 3 ' — — 2«Лз = 3 ъ~2«'«" г = Я„.