Методы оптимизации

с ситуацией, когда ему из некоторой совокупности возможных вариантов своего

поведения или принятия решения в какой-либо области деятельности необходимо выбрать один вариант. Наилучший вариант поведения (принятие наилучшего решения) можно выбирать по-разному. Если такой выбор предусматривает проведение количественного анализа ситуации путем сравнения различных вариантов с помощью какой-либо количественной оценки этих вариантов, то говорят о необходимости решения задачи оптимизации (по латыни optimus — наилучший). Ясно, что задача оптимизации имеет смысл, если есть несколько возможных вариантов ее решения. Эти варианты обычно называют альтернативами.
По содержанию задачи оптимизации весьма разнообразны. Они могут быть связаны с проектированием технических устройств и технологических процессов, с распределением ограниченных ресурсов и планированием работы предприятий, наконец, с решением проблем, возникающих в повседневной жизни человека. Всевозможные устройства, процессы и ситуации, применительно к которым предстоит решать задачу оптимизации, объединим общим названием объект оптимизации.
В этой главе сформулированы некоторые основные определения и понятия, играющие важную роль в дальнейшем изложении материала, даны постановки известных и достаточно простых задач поиска экстремума из геометрии, алгебры и других разделов математики, приведены примеры прикладных задач оптимального проектирования и планирования, а также перечислены классы задач оптимизации.

“как лучше”, но, чтобы не получить плохой результат при самых

хороших намерениях, для решения задачи оптимизации нужно прежде всего найти ответы на следующие вопросы:
- Что значит лучше"?
- Что конкретно нужно улучшить?
- За счет чего можно добиться улучшения, что можно изменить?
- В каких пределах можно производить изменения?
Отвечая на первый вопрос, необходимо сформулировать критерий оптимальности, т.е. определить те признаки и предпочтения, по которым следует провести сравнительную оценку альтернатив и выбрать среди них наилучшую с точки зрения поставленной цели оптимизации. Именно с этой точки зрения можно ответить на второй вопрос: что конкретно нужно улучшить? Это может быть повышение производительности станка или срока службы технического устройства, снижение массы конструкции летательного аппарата или затрат на его производство и т.п.
Для ответа на два последних вопроса необходимо располагать математической моделью объекта оптимизации. Эта модель описывает объект при помощи соотношений между величинами, характеризующими его свойства. Обычно хотя бы часть этих величин можно изменять в некоторых пределах, что и порождает множество альтернатив, среди которых и предстоит выбрать наилучшую. Изменяемые при оптимизации величины, входящие в математическую модель объекта оптимизации, называют параметрами оптимизации, а соотношения, устанавливающие пределы возможного изменения этих параметров, — ограничениями. Эти ограничения могут быть заданы в форме равенств или неравенств. Их называют соответственно ограничениями типа равенства или ограничениями типа неравенства.

линейного пространства, то говорят о конечномерной задаче оптимизации в отличие

от бесконечномерных задач, которые рассматривают в вариационном исчислении и оптимальном управлении. При этом критерием оптимальности может быть требование достижения наибольшего или наименьшего значения одной или несколькими действительными (скалярными) функциями параметров оптимизации, выражающими количественно меру достижения цели оптимизации рассматриваемого объекта. Каждую из таких функций принято называть целевой. Если целевая функция единственная, то задачу конечномерной оптимизации называют задачей математического программирования, а в противном случае — задачей многокритериальной (векторной) оптимизации. В дальнейшем ограничимся рассмотрением задач математического программирования и методов их решения.
Если целевая функция и ограничения являются линейными относительно параметров оптимизации, то говорят о задаче линейного программирования. Одну из первых таких задач сформулировал и решил Л.В. Канторович. Задача Канторовича была связана с выбором оптимальной производственной программы, что и объясняет появление в названии этого класса задач слова “программирование”. При нелинейной зависимости целевой функции или ограничений от параметров оптимизации говорят о задаче нелинейного программирования.

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

математики. Эти задачи обычно можно решить геометрическим или алгебраическим путем, а также при помощи необходимых и достаточных условий экстремума действительной (скалярной) функции одного переменного. Включение таких примеров в эту книгу важно по нескольким причинам. Во-первых, эти задачи тесно связаны с историей развития методов оптимизации и позволяют наглядно продемонстрировать многообразие объектов оптимизации. Во-вторых, на простой задаче можно более четко выявить особенности построения математических моделей таких объектов с точки зрения выбранного критерия оптимальности и проследить этапы процесса формулировки задачи математического программирования. В-третьих, знание способов и результатов решения многих из этих задач помогает при решении более сложных задач оптимизации, например задач оптимального проектирования
(см. 1.3).
Пример 1.1. Найдем стороны прямоугольника,
вписанного в окружность радиуса R и имеющего
наибольшую площадь S (рис. 1.1).

и ее нетрудно решить геометрическим путем. Диагональ вписанного в окружность

прямоугольника является диаметром окружности и имеет фиксированную длину. Площадь S прямоугольника равна половине произведения его диагоналей на синус угла φ между диагоналями, т.е. S = 2R2sinφ. Ясно, что эта площадь будет наибольшей при sinφ = 1, или при φ = π/2. В этом случае диагонали прямоугольника перпендикулярны, а сам прямоугольник представляет собой квадрат. Таким образом, прямоугольником наибольшей площади, вписанным в окружность, является квадрат со стороной и площадью 2R2.
Если в качестве параметров оптимизации выбрать длины а≥0 и b ≥0 сторон прямоугольника, то получим целевую функцию S = аb и ограничение типа равенства, нелинейные по отношению к этим параметрам. Поэтому рассматриваемую задачу оптимизации следует отнести к задачам нелинейного программирования. Ее математическую формулировку можно представить в виде


Эту задачу можно решить одним из известных стандартных путей: либо использовать формальную процедуру поиска условного экстремума функции S = ab двух переменных с одним уравнением связи, построив функцию Лагранжа, либо выразить при помощи ограничения одно переменное через другое и перейти к поиску экстремума функции одного переменного. Отметим, что в данном случае возможен и нестандартный способ решения, связанный с построением вспомогательного соотношения 4R2 - 2S = а2 + b2- 2аb = (a - b)2, или . Отсюда следует, что S достигает наибольшего значения S* = 2R2 при условии а = b, т.е. когда прямоугольник является квадратом, причем а = b = R .

треугольник ABC с высотой Н и основанием

b вписать параллелограмм наибольшей площади,
стороны которого параллельны двум сторонам
треугольника (рис. 1.2).
Критерием оптимальности в этой задаче является
достижение площадью параллелограмма
наибольшего значения, а ограничения связаны с
условиями параллельности сторон и размещения параллелограмма в пределах заданного треугольника.
Выберем прямоугольную систему координат, совместив ее начало с общей вершиной параллелограмма и треугольника(вершина А на рис. 1.2), а ось абсцисс — с одной из сторон треугольника. В качестве параметров оптимизации выберем основание х параллелограмма и его высоту h. Тогда площадь S параллелограмма можно записать в виде S = hx, а условие, что параллелограмм вписан в треугольник, — как ограничение типа равенства (H — h)/H = x/b, которое вытекает из подобия треугольников DBE и ABC. Итак, имеем задачу оптимизации



Эту задачу также можно решить стандартными способами (см. пример 1.1). Ее решением является параллелограмм с основанием x* = b/2 и высотой h* = (1 - x/b)H = H/2. Отметим, что выбор вершины треугольника, с которой совпадает вершина параллелограмма, не является существенным, так как в любом из трех вариантов выбора вершины треугольника площадь параллелограмма максимальной площади равна половине площади треугольника ABC.

устройства различного назначения обычно часть его параметров можно изменять в

определенных пределах. Это приводит к тому, что при проектировании появляется некоторое множество вариантов создаваемого устройства. В результате возникает проблема выбора из этого множества альтернатив наилучшей альтернативы с точки зрения критерия оптимальности. Соответствующие такому выбору задачи оптимизации часто называют задачами оптимального проектирования.
Пример 1.6. Одной из наиболее простых задач оптимального проектирования является выбор размеров емкости определенной формы, имеющей наибольший объем при заданной площади поверхности или же наименьшую площадь при заданном объеме.
Пусть требуется спроектировать бак горючего в виде прямого кругового цилиндра заданного объема V, на изготовление которого будет затрачено наименьшее количество листовой стали. В качестве параметров оптимизации выберем радиус R и высоту Н цилиндра. Тогда затраты материала на изготовление бака будет определять суммарная площадь S его боковой поверхности и двух плоских днищ. Таким образом, необходимо минимизировать целевую функцию S = 2πR(H + R) при ограничении типа равенства πR2H = V, т.е. решить задачу нелинейного программирования. Если из целевой функции при помощи ограничения исключить Н и записать ее в виде

то произведение слагаемых не будет зависеть от R, и для нахождения ее минимального значения удобно использовать то же неравенство между геометрическим и арифметическим средними, что и в примере 1.3:

т.е. при

Учитывая ограничение, получаем


т.е. высота оптимального бака равна его диаметру.
При изготовлении одного бака нужно учитывать, что для заготовки круглого днища площадью πR2 придется взять квадратный лист площадью 4R2, причем после раскроя оставшуюся часть листа использовать будет практически невозможно. Поэтому более обоснованно в качестве целевой минимизировать функцию при прежнем ограничении πR2H = V.
Тогда в результате процедуры, аналогичной рассмотренной, получим

Если предстоит изготовить крупную партию баков, то раскрой листовой стали при заготовке днищ можно провести более рационально, располагая соседние центры днищ в вершинах правильных треугольников со стороной 2R. Тогда расход листа на каждое днище будет соответствовать площади правильного шестиугольника, описанного около окружности радиуса Д. При этом следует минимизировать целевую функцию при том же ограничении. В итоге получим



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

часто возникают в экономике, при планировании производственных процессов и количественной

оценке альтернатив, связанных с принятием управленческих решений. Постановка этих задач обычно основана на анализе и сопоставлении расходуемых ресурсов и полученного результата. Такой подход принято называть методом “затраты — эффективность”. Применение этого подхода приводит, как правило, к двум связанным между собой типам задач: либо максимизировать эффективность при ограниченных затратах, либо обеспечивать эффективность не ниже заданной при минимальных затратах. Таким образом, критерием оптимальности может быть количественное выражение затрат или эффективности. Рассмотрим несколько примеров такого подхода.
Пример 1.11. Предположим, что предприятие может выпускать продукцию п наименований, для производства которой требуется т видов ресурсов (сырья, энергии, оборудования и т.п.). Обозначим через aij затраты i-го вида ресурсов, на производство единицы продукции j-гo наименования, , а через bi и xj полные объемы располагаемых ресурсов и планируемые объемы выпуска продукции соответственно. Если к тому же по каждому наименованию продукции заданы нижняя aj и верхняя Aj границы объема выпуска продукции, то можно записать ограничения типа неравенства

выручкой от продажи продукции, то оптимальный план х = (х1,

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


где dj — цена единицы продукции j-го наименования. В данном случае и целевая функция, и ограничения линейны относительно параметров оптимизации xj, . Поэтому рассмотренная задача оптимального планирования выпуска продукции является задачей линейного программирования.
Пример 1.12 (транспортная задача). Пусть необходимо составить план перевозок некоторого товара с m складов в п магазинов так, чтобы затраты на эти перевозки были минимальными. Предположим, что на i -м складе, имеется ai единиц товара, a j-й магазин, п, сделал заказ на bj единиц этого товара, причем стоимость его перевозки с i-го склада в j-й магазин равна сij. Обозначим через xij планируемое количество товара, перевозимое с i-го склада в j-й магазин, тогда стоимость его перевозки составит сij xij. Общие затраты на перевозки — это сумма затрат на перевозки со всех складов во все магазины. Поэтому оптимальный план перевозок соответствует минимуму целевой функции


что должно быть достигнуто выбором mn значений xij ≥0, которые в данном случае являются параметрами оптимизации. Но при этом необходимо обеспечить потребности магазинов, т.е.должны быть выполнены ограничения типа равенства

больше, чем там его находится. Следовательно, должны быть выполнены ограничения

типа неравенств


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

Пример 1.13 (задача о диете). Рассмотрим задачу построения оптимального рациона питания. Обозначим: п — число видов пищевых продуктов; т — число видов питательных веществ; aij — число единиц i-го питательного вещества в единице j-го продукта; bj — ежегодная потребность в i-м питательном веществе; cj — стоимость единицы j-го продукта. Выясним, сколько единиц каждого пищевого продукта нужно употребить за рассматриваемый период (в данном случае за год) таким образом, чтобы, обеспечив потребности в каждом питательном веществе, затратить минимальное количество денег.
Назовем рационом вектор х=(х1 x2 ... хп)T , где xj — ежегодное потребление j-гo пищевого продукта. Речь идет, таким образом, о построении рациона минимальной стоимости. Математически эта задача может быть сформулирована следующим образом: минимизировать целевую функцию


при ограничениях

п изделий, причем затраты на производство x единиц i-го изделия

составляют , где — затраты на производство одного i-го изделия (при мелкосерийном или индивидуальном производстве обычно кi ≥1, а при крупносерийном — кi < 1). Предположим также, что должно быть выполнено так называемое условие на ассортимент: предприятие должно выпустить не менее bi единиц i-го изделия, т.е. имеем п ограничений типа неравенства Если эффективность производства изделий определить как суммарную выручку от их продажи, то получим еще одно ограничение типа неравенства



где di, — цена единицы i-го изделия, а b — заданный нижний уровень эффективности. При этих ограничениях необходимо минимизировать нелинейную целевую функцию



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

собой m месторождений Аi,

газа и п пунктов Bj, его потребления с известными значениями p0≥0 расхода газа в единицу времени. Производительность i-го месторождения, ограничена заданным значением Gi, т.е. заданы ограничения типа неравенства . Затраты на добычу газа на i-м месторождении, являются функцией производительности . Сеть состоит из К участков, причем стоимость подачи газа по k-му участку, , является функцией расхода через этот участок. В пунктах потребления газа имеем ограничения типа равенства


где — множества участков сети с входящими в j-й пункт и выходящими из него потоками газа соответственно. Аналогично для месторождений газа получаем ограничения типа равенства


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


на добычу и подачу газа. Все ограничения в сформулированной задаче линейные. Поэтому в частном случае линейных функций и и на будет задачей линейного программирования, но в общем случае — задачей нелинейного программирования.

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

Отметим, что одна и та же прикладная задача может приводить к разным задачам оптимизации в зависимости от того, какая математическая модель используется при рассмотрении реального объекта оптимизации. Ясно, что желательно применять более простые модели, но в то же время достаточно полно отражающие свойства объекта, существенные с точки зрения поставленной цели, выраженной в критерии оптимальности. Поэтому при выборе либо разработке математической модели или же при обосновании ее упрощения необходимо достаточно четко представлять, к какому классу будет относиться поставленная задача оптимизации и какие методы применимы для ее решения.
Пусть f0(x) — целевая функция, количественно выражающая некоторый критерий оптимальности и зависящая от координат . Эти координаты являются параметрами оптимизации (иногда их называют также переменными задачи оптимизации или просто переменными задачи).
При математической формулировке задачи оптимизации целевую функцию выбирают с таким знаком, чтобы решение задачи соответствовало поиску минимума этой функции. Поэтому формулировку общей задачи математического программирования, обычно записывают так:
f0(x) → min, x ∈ Ω, (1.18)
где Ω ⊂ Rn множество возможных альтернатив, рассматриваемых при поиске решения задачи

допустимым решением задачи математического программирования, а само множество — множеством

допустимых решений или, короче, допустимым множеством. Точку x* ∈ Ω, в которой функция f0(x) достигает своего наименьшего значения, называют оптимальным решением задачи.
При отсутствии ограничений множество Ω совпадает с областью определения D(f0) ⊂ Rn целевой функции. Если же рассматриваемые альтернативы должны удовлетворять некоторым ограничениям, то множество допустимых решений сужается.
Задачу (1.18) в дальнейшем будем называть задачей минимизации целевой функции на множестве Ω, понимая под этим нахождение наименьшего значения функции f0(x) на Ω и точек x ∈ Ω, в которых оно достигается. Но целевая функция может и не достигать на Ω наименьшего значения. Тогда говорят о точной нижней грани infx∈Ω f0(x) функции f0(x) на этом множестве и вместо (1.18) используют запись
f0(x) → inf, x ∈ Ω. (1.19)
Отличие (1.18) от (1.19) в том, что в первом случае предполагают существование точки x* ∈ Ω, в которой целевая функция достигает своего наименьшего значения на множестве Ω, а во втором случае такая точка может и не существовать. Поэтому решение общей задачи математического программирования состоит в том, чтобы в первом случае найти точные (или с некоторой заданной точностью) значения координат точки x* ∈ Ω и значение целевой функции f0(x*) = minx∈Ω f0(x), а во втором случае построить такую последовательность {хп} точек xn ∈ Ω, которой бы соответствовала последовательность {f0(xn)}, сходящаяся к значению infx∈Ω f0(x), и вычислить это значение с заданной точностью. Отметим, что в большинстве прикладных задач имеет место первый случай, поэтому использование записи вида (1.19) будем оговаривать особо.

область определения совпадает с Rn. В Rn такую функцию с

помощью стандартного скалярного произведения можно представить в виде f0(x) = (c, x), где c = (c1, …, cn) ∈ Rn — известный вектор. Ясно, что целевая функция



может достигать наименьшего значения на множестве лишь в точках границы этого множества. Если в задаче нет ограничений, то и точная нижняя грань линейной функции равна - . Поэтому в случае линейной целевой функции задача оптимизации
(c, x) → min, x ∈ Rn, (1.20)
имеет смысл лишь при наличии ограничений.
В частном случае, когда заданы линейные ограничения типа равенства
Bx = d, x ∈ Rn (1.21)
где d ∈ Rk, В — матрица размера k × п, а параметры оптимизации могут принимать лишь неотрицательные значения, т.е.

(1.22)
соотношения (1.20)-(1.22) составляют стандартную задачу линейного программирования, или задачу линейного программирования в стандартной форме (в литературе ее часто называют канонической задачей линейного программирования, или задачей линейного программирования в канонической форме).

— декартово произведение п множеств неотрицательных действительных чисел, называемое иногда неотрицательным ортантом размерности п. Если к (1.20)-(1.22) добавить т ограничений типа неравенства


то соотношения (1.20) - (1.23) приведут к формулировке общей задачи линейного программирования. При этом ограничения (1.22) могут относиться не ко всем п параметрам оптимизации, а лишь к некоторым из них. При отсутствии ограничений типа равенства соотношения (1.20), (1.22) и (1.23) составляют формулировку основной задачи линейного программирования (иногда ее называют естественной задачей линейного программирования).
Неравенства называют прямыми ограничениями на переменные задачи, причем последнее относят к двусторонним, а первые два — к односторонним. Таким образом, ограничения (1.22) являются прямыми односторонними. Методы решения задач линейного программирования подробно рассмотрены и обоснованы далее.
Если при линейных ограничениях минимизируемая целевая функция помимо линейной комбинации вида (1.20) включает положительно определенную квадратичную форму, т.е.

(1.24)
где Q — положительно определенная матрица порядка п, то говорят о задаче квадратичного программирования, а функцию вида (1.24) называют квадратичной. В случае, когда целевая функция является отношением двух линейных функций, а ограничения линейны, имеем задачу дробно-линейного программирования. Ее формулировка включает ограничения (1.21) - (1.23) и условие минимума функции
  (1.25)

где заданы.

(1.26)


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


где — декартово произведение n множеств положительных действительных чисел, называемое иногда положительным ортантом. При этом функции pi (ж) имеют вид


Требование положительности коэффициентов ci, послужило причиной того, что такой вид целевой функции стали называть позиномом в отличие от полинома (многочлена), в котором коэффициенты могут быть и неположительными. Кроме того, в многочлене показатели степени аргументов являются целыми неотрицательными числами, а в позиноме благодаря положительности параметров оптимизации выражение определено для любых действительных чисел аij. Если целевая функция и левые части ограничений типа равенства и (или) неравенства в задаче минимизации являются позиномами, то такую задачу называют задачей геометрического программирования.

заданы в неявном виде. Тогда множество Ω возможных альтернатив приходится

строить путем количественного анализа математической модели объекта оптимизации (см. пример 1.10). Если ограничения принадлежат к типам равенства и (или) неравенства

(1.29)

но хотя бы одна из функций f1(x), или целевая функция не является линейной, то говорят об общей задаче нелинейного программирования. Ясно, что такая формулировка включает задачи квадратичного, дробно-линейного, сепарабельного и геометрического программирования.
Среди целевых функций достаточно широкий класс составляют выпуклые функции. Во многих прикладных задачах оптимизации область допустимых значений параметров оптимизации оказывается выпуклым множеством. В такой области целевая функция может сохранять одно и то же направление выпуклости, т.е. выпукла либо вниз (выпукла), либо вверх (вогнута). Например, зависимость эффективности технического устройства от параметров оптимизации является вогнутой функцией. Дело в том, что чем выше технические характеристики устройства, тем труднее добиться его дальнейшего совершенствования и существенного приращения эффективности. Наоборот, целевые функции, выражающие массу, габариты или стоимость технического устройства, по тем же причинам обычно выпуклы.

экономические системы. Например, рост объема выпускаемой продукции происходит не прямо

пропорционально капиталовложениям или количеству используемых ресурсов, а с замедлением, причем это замедление часто тем больше, чем больше объем производства. Это приводит к вогнутости так называемых производственных функций, выражающих зависимость объема выпускаемой продукции от израсходованных ресурсов. Наоборот, при фиксированном объеме производства дальнейшее снижение производственных затрат и стоимости единицы продукции по сравнению с достигнутым уровнем также происходит с замедлением, что приводит к выпуклости целевых функций, описывающих стоимостные характеристики производства.
Ясно, что любую вогнутую целевую функцию, изменив знак, можно сделать выпуклой. Задачи оптимизации, в которых необходимо найти наименьшее значение выпуклой целевой функции, рассматриваемой на выпуклом множестве, относят к задачам выпуклого программирования. Частными случаями таких задач являются задачи квадратичного и линейного программирования. Задачи геометрического программирования при некоторых дополнительных условиях также являются задачами выпуклого программирования.
Если множество Q допустимых решений оказывается конечным множеством, то мы имеем задачу дискретного программирования.