02 АЗЭ Лекционный материал / лекция 16
точное оптимальное решение может быть получено за конечное число шагов. Для задач нелинейного программирования вычислительный метод, дающий точное оптимальное решение в конечное число шагов, удается построить не всегда. Здесь часто приходится соглашаться на использование методов, даю- щих только приближенное решение или требующих для сходимости беско- нечного числа шагов. Один из наиболее мощных методов решения задач нелинейного програм- мирования состоит в преобразовании задачи каким-либо образом к виду, до- пускающему применение симплексного алгоритма. Таким образом, оказыва- ется, что симплексный алгоритм служит хорошим средством для решения не только линейных, но и нелинейных задач. Другим полезным вычислитель- ным методом для решения некоторых типов задач нелинейного программи- рования является динамическое программирование. Достоинства и недостатки динамического программирования . Основное достоинство метода том, что он позволяет решать задачи в си- туациях, при которых многие другие метода просто неприемлемы, а именно: неединственность экстремума, недифференцируемость целевой функции, дискретное изменение переменных, многошаговый характер решения. Дру- гим важным свойством ДП является возможность получения многовариант- ного решения задач. Однако возможности ДП далеко не исчерпываются этим. Аппарат динамического программирования дает универсальные мето- ды решения как детерминированных, так и стохастических задач. Использо- вание ДП позволяет резко уменьшить объем комбинаторных задач. При большем числе переменных число комбинаций эффект существенно возрастает. Причина столь значительного эффекта в том что, для каждого шага планируемого процесса рассматриваются лишь их оптимальные про- должения. В результате область применения ДП резко расширилась. ДП ис- пользуется для решения большого числа разнообразных задач в науке , тех- нике и экономике.
В электроэнергетике с помощью этого метода решается задачи выбора структуры генерирующих мощностей и состава работающего оборудования в энергосистеме, оптимизация параметров электрические сетей, их развития и другие задачи. Недостаток метода ДП — так называемое «проклятие размерности», свя- занное с большим объемом накапливаемой информации в памяти ЭВМ. По- явление современных быстродействующих ЭВМ третьего и четвертого поко- лений с большими размерами памяти и имеющими «прямой доступ» к ней при решении одномерных задач практически снимает это ограничение. Вычислительный метод ДП является весьма своеобразным по сравнению с методами линейного и нелинейного программирования. Формулировка той или иной задачи в терминах ДП, не является стандартной, а требует творче- ского подхода. Поэтому, используя идеи ДП в каждом отдельном случае, необходимо разрабатывать такие алгоритмы, которые бы обеспечивали пра- вомерное применение этого математического аппарата и давали приемлемые инженерные решения, учитывая возможности современных ЭВМ. Трудности, порождаемые нелинейностями. Для задач линейного программирования характерно следующее: a) множество допустимых решений (т. е. множество всех точек [x 1 , х 2 . x n ]. б) множество всех точек [x 1 , х 2 . x n ] n -мерного пространства, в которых целевая функция принимает заданное значение, есть гиперплоскость. Кроме того, гиперплоскости, соответствующие разным значениям целевой функции, параллельны. в) локальный максимум или минимум является также глобальным макси- мумом или минимумом целевой функции на множестве допустимых реше- ний, т. е. не существует локального оптимума целевой функции, отличного от глобального оптимума.
г) если оптимальное значение целевой функции ограничено, то по край- ней мере одна крайняя точка множества допустимых решений является оп- тимальным решением. Кроме того, начав с произвольной вершины множества допустимых ре- шений, можно достичь оптимальной крайней точки в конечное число шагов, причем на каждом шаге совершается переход только в соседнюю вершину. Окончательно, данная вершина является оптимальной тогда и только тогда, когда значение целевой функции в ней по крайней мере не меньше, чем зна- чения целевой функции во всех примыкающих вершинах. Задачи, содержащие только две переменные, легко могут быть решены графически. Приведем несколько графических примеров:
| x 1 | x 2 | 6, | ||
| x 1 | x 2 | 1, | (16.6) | |
| 2 x 1 x 2 | 4, | |||
| x 1 | 1, x 2 | 0 | ||
найти max z = 0,5x 1 + 2х 2 . Графическое решение показано на рис. 16.1. Область допустимых реше- ний заштрихована. Оптимум достигается в вершине. Значения переменных, доставляющих максимум целевой функции, единственны и являются коор- динатами точки пересечения линий x 1 +х 2 = 6, 0,5,х 1 -х 2 =-4. Оптимальные зна-
| чения переменных есть x * 4 / 3, | x * 14 / 3 . Максимальное значение целе- |
| 1 | 2 |
| вой функции z * 10 . |
Рассмотрим теперь задачу нелинейного программирования, которая отли- чается от предыдущей только тем, что целевая функция имеет вид z =10( x 1 -3.5) 2 +20( x 2 — 4) 2 . (16.7) Пусть решается задача на минимум. Заметим, что здесь мы имеем сепара- бельную целевую функцию. Графическое решение задачи дано на рис. 16.2. Область допустимых решении, конечно, та же самая, что и в предыдущем примере. Здесь, однако, линии уровня функции z являются эллипсами с цен- трами в точке x 1 = 3,5, x 2 = 4.
Оптимальное решение есть точка, в которой эллипс касается границы вы- пуклого множества. Если обозначить оптимальные значения переменных че-
| рез x * и | x * , а минимальное значение целевой функции через z *, то из рис. | |
| 1 | 2 | |
| 16.2 следует, что x * x * 6 и z*=10(x 1 * — 3,5) 2 + 20(x 2 * — 4) 2 . | ||
| 1 | 2 | |
Рис.16.1. Кроме того, тангенс угла наклона касательной к кривой z* = 10(x 1 — 3,5) 2 +20(x 2 — 4) 2 в точке ( x 1 * , x 2 * ) должен равняться — 1, так как таков он у пря- мой x 1 x 2 6 . Таким образом, мы получаем дополнительное уравнение x 2 * — 4=0.5(x 1 * -3.5). Всего же, следовательно, имеется 3 уравнения относительно x 1 * , x 2 * и z * . Их единственное решение есть x 1 * =2,5, х 2 * = 3,5, z *= 15. Точка, в которой целевая функция принимает наименьшее значение, ле- жит на границе множества допустимых решений, но не в крайней точке этого множества. Следовательно, не существует вычислительной процедуры для задач такого типа, которая ограничивалась бы перебором только вершин множества допустимых решений.
Небольшая модификация уже рассмотренной целевой функции может привести к тому, что минимальное значение достигается во внутренней точке этого множества. Пусть, например, целевая функция имеет вид z*=10(x 1 — 2 ) 2 + 20(x 2 — 3) 2 (16.8) а множество допустимых решений то же, что и раньше (рис. 16.3). Опти- мальные значения x 1 , x 2 и z есть х 1 * = 2, x 2 * = 3, z * = 0. Рис. 16.2. Таким образом, оптимизирующая точка не обязательно лежит на границе. Отметим, что в рассмотренном случае минимум целевой функции при нали- чии ограничений и условий неотрицательности тот же, что и без них. В таких случаях мы будем говорить, что ограничения несущественны. В каждом из рассмотренных примеров локальный оптимум совпадал с глобальным. Легко, однако, привести примеры, где это будет не так. Рас- смотрим следующую задачу с линейными ограничениями и сепарабельной целевой функцией (рис. 16.4):
| x 1 | x 2 | 2, | |
| x 1 | x 2 | 2, | |
| x 1 | x 2 | 6 | (16.9) |
| x 1 | 3 x 2 2 | ||
x 1 , x 2 0 найти max z = 25( x 1 – 2) 2 +( x 2 – 2) 2 . Нетрудно понять, что в вершине 4 достигается глобальный максимум це- левой функции. Рис. 16.3.
Следует отметить, что в задачах такого типа глобальный экстремум до- стигается в вершине, однако нет возможности использовать вычислительную процедуру симплексного типа (основанную на переходе от одной вершины к соседней, которая оканчивалась бы при достижении вершины), доставляю- щей относительный экстремум целевой функции по сравнению со всеми со- седними вершинами. Рис.16.5. Если задача содержит нелинейные ограничения, то не сохраняет силу утверждение о выпуклости области допустимых решений. Более того, она может даже состоять из нескольких несвязанных областей.
| ( x 1 1) x 2 | 1, | (16.10) |
| x 1 x 2 | 3.5 |
Пусть, например, ограничения имеют вид и переменные должны быть не- отрицательны. Множество допустимых решений в этом случае состоит из двух отдельных частей, ни одна из которых не выпукла (рис. 5.5). Если мно- жество допустимых решений не выпукло, то может существовать отличный от глобального локальный оптимум даже при линейной целевой функции. Для задач нелинейного программирования, имеющих отличные от гло- бального локальные оптимумы, большинство вычислительных методов, поз-
воляет найти точку именно локального оптимума. В общем случае они не позволяют установить, совпадает ли она с точкой глобального оптимума. Тем не менее эти методы отыскания локального оптимума часто оказываются очень полезными на практике. Единственный вычислительный метод, приводящий к глобальному опти- муму независимо от числа локальных экстремумов,- это метод динамическо- го программирования. Следовательно, если задача может быть решена с по- мощью динамического программирования, мы всегда получаем возможность отыскать глобальный оптимум. Последней мы рассмотрим следующую задачу целочисленного програм- мирования: 0,5 x 1 x 2 1.75; x 1 0.30 x 2 1.50, x 1 , x 2 0, x 1 ,x 2 — целые; найти max z = 0,25x 1 +x 2 Заштрихованная область была бы выпуклым множеством допустимых решений при отсутствии целочисленных ограничений. При учете требования целочисленности переменных x j имеется лишь че- тыре допустимых решения Если игнорировать требования целочисленности, то решение соответствующей задачи линейного программирования есть х 1 * = 0, x 2 :* =1,75, z *= 1,75. Однако при учете целочисленности оптимальным ре- шением будет х 1 * = 1, x 2 *= 1, z*= 1.25. Отметим, что это решение не совпадает с тем, которое было бы получено путем решения задачи линейного программирования с последующим округ- лением результатов до ближайших целых, удовлетворяющих ограничениям (таким путем мы получили бы , x 1 *=0, x 2 * = 1 и z =1).