Общая задача нелинейного программирования
Рассмотрение общей задачи нелинейного программирования с гладкими функциями. Определение допустимых точек. Теорема (обобщенное правило множителей Лагранжа). Условие регулярности в случае общей задачи. Достаточные условия, существование, единственость.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 28.03.2020 |
| Размер файла | 107,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Общая задача нелинейного программирования
Ибо самое странное, заставляющее быть настороже в этой среде, или мире, в котором мы вынуждены существовать, состоит в том, что мир - в пределах неумолимо очерченного горизонта - всегда представляет нам разнообразные возможности действия, и нам не остается ничего, кроме как выбирать из этого разнообразия, осуществляя таким образом на практике свою свободу.
Х. Ортега-и-Гассет. Человек и люди
Здесь в соответствии со схемой предыдущего параграфа рассматривается общая задача нелинейного программирования с гладкими функциями.
1. Постановка задачи.
Общей задачей нелинейной условной оптимизации мы будем называть условную задачу минимизации
|
f0(x) > min, x · Щ, |
(1) |
где Щ выделяется как ограничениями типа равенств
|
fi(x) = 0, i = 1, ..., k, |
(2) |
так и ограничениями типа неравенств
|
gj(x) ? 0, j = 1, ..., l |
(3) |
(см. рис. 1).
Рис. 1.
Определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из Rm в Rk и Rl, соответственно, определяемые координатами fi и gj. Поэтому задачу (1)-(3) можно записывать в виде
|
f0(x) > min, f(x) = И, g(x) ? И. |
(4) |
(напомним, что неравенство g(x) ? И означает покоординатные неравенства).
Нам также потребуется следующее обозначение: a+ = (a + |a|)/2; таким образом, a+ = a, если a ? 0 и a+ = 0, если a ? 0. Для векторов a ? Rm операция "+" определяется покоординатно: a+ = ((a1)+, ..., (am)+). Кроме того, через J(x) будет обозначаться множество индексов так называемых активных ограничений:J(x) = {j ? {1, ..., l}: gj(x) = 0} - это номера ограничений, которые в данной точке существенны. Например, на рис. 22 J(x1) = {2}, а J(x2) = ?.
2. Теорема (обобщенное правило множителей Лагранжа)
Пусть f0, f, g ? C1, а x* - локальное решение задачи (4). Тогда найдутся такие л*0 ? R, л* ? Rk, м* ? Rl, не равные одновременно нулю, такие, что м*j ? 0при j ? J(x*) и
|
л*0 f ?0(x*)+ k ? i = 1 л*i f ?i(x*)+ ? j?J(x*) м*j g?j(x*) = И. |
(5) |
Д о к а з а т е л ь с т в о. Возьмем r > 0 таким, чтобы x* = argminx?Щr f(x), где Щr = Щ ? B(x*, r). Для любого n ? N определим функцию f n: Rm > R равенством
|
f n(x) = f0(x) + n(||f(x)||2 + ||g+(x)||2) + ||x - x*||2. |
З а д а ч а 7.1. Докажите, что f n ? C1, в частности, покажите, что (||g+(x)||2)? = 2g+(x)g?(x).
Поскольку f n непрерывно дифференцируемы и поэтому непрерывны, функции f n на шаре B(x*, r) достигают минимума; обозначим его через xn. В частности,
|
f n(xn) ? f n(x*), |
(6) |
т. е.
|
f0(xn) + n(||f(xn)||2 + ||g+(xn)||2) + ||xn - x*||2 ? f n(x*). |
Отсюда, поскольку, как легко видеть, f n(x*) = f0(x*),
|
||f(xn)||2 + ||g+(xn)||2 ? 1 |
Размещено на http://www.allbest.ru/
|
n [f0(x*) - ||xn - x*||2 - f0(xn)], |
Выражение в квадратных скобках ограничено, так как xn ? B(x*, r). Поэтому
||f(xn)||2 + ||g+(xn)||2 > 0 при n > ? и,
следовательно,
f(xn) > И и g+(xn) > И приn > ?.
Пусть теперь {xni} - произвольная сходящаяся, скажем к y, подпоследовательность. Тогда, как легко видеть, во-первых, y ? Щ и, во-вторых, f ni(xni) > f0(y) +||y - x*||2 при n > ?. Поэтому, подставляя в (6) ni вместо n и переходя к пределу в получившемся неравенстве при i > ?, получим
|
f0(y) + ||y - x*||2 ? f0(x*). |
С другой стороны, так как x* = argmin f(x), f0(x*) ? f0(y). Отсюда ||y - x*||2 ? 0, т. е. y = x*. Таким образом, любая сходящаяся подпоследовательность последовательности {xn} сходится к x*. Последнее, учитывая компактность последовательности, гарантирует ее сходимость к тому же пределу.
Далее, в силу доказанного можно считать, что при всех n точка xn лежит внутри шара B(x*, r). Поэтому в силу теоремы Ферма (f n)?(xn) = И, т. е.
|
f ?0(xn)+ 2 k ? i = 1 fi(xn)f ?i(xn)+ 2 l ? j = 1 [gj(xn)]+g?j(xn)+ 2(xn - x*) = И. |
(7) |
Положим теперь
|
sn = ( 1 + 4n2 k ? i = 1 [fi(xn)]2 + 4n2 l ? j = 1 [gj(xn)]2 ) -1/2 , |
|
лn0 = sn, лni= 2nfi(xn)sn, мnj= 2n[gj(xn)]+sn. Поскольку лn0,лnj,мnj? [-1, 1] (n ? N; i = 1, ..., k; j = 1, ..., l), можно считать, не ограничивая общности, что найдутся такие л*0,л*iи м*j,что |
|
лn0> л*0, лni> л*i, мnj> м*j при n > ?. |
Умножив (7) на sn и переходя в получившемся равенстве к пределу при n > ?, получаем
|
л*0f ?0(x*)+ k ? i = 1 л*if ?i(x*)+ l ? j = 1 м*jg?j(x*)= И. |
(8) |
Остается заметить, что, во-первых, так как |лn0|2+ ?ki=1|лni |2+?lj=1|мnj|2=1, не все из л*0,л*i,м*jравны нулю, во-вторых, поскольку мnj= 2n[gj(xn)]+sn ? 0,неотрицательны и м*jи, наконец, в-третьих, если j ? J(x*) (т. е. gj(x*) < 0), то gj(xn) < 0 при больших n; поэтому [gj(x*)]+ = 0, что влечет равенство м*j= 0 и, следовательно, равенство
|
l ? j = 1 м*jg?j(x*)= ? j?J(x*) м*jg?j(x*). |
Таким образом (8) - это (5).
3. Регулярный случай
Так же, как и в случае ограничений-равенств в случае общей задачи нелинейной оптимизации, необходимый признак, задаваемый теоремой 2, информативен только в случае, если л*0? 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (5) на л*0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: RmЧRkЧRk > R (в регулярном случае) равенством
|
L(x, л, м) = f0(x) + (л, f(x)) + (м, g(x)). |
Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ?1(x),..., f ?k(x)линейно независимы и для некоторого ненулевого вектора h ? Rm
|
(f ?i(x),h) = 0 при i = 1, ..., k |
И
|
(g?j(x),h) < 0 при j ? J(x). |
|
Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е.ортогонален всем градиентам f ?i(x)),и, во-вторых, он образует с градиентами g?j(x)активных ограничений (указывающими, очевидно, вовне множества Щ) тупой угол (см. рис. 2). |
Рис. 2.
4. Теорема (обобщенное правило множителей Лагранжа в регулярном случае)
Пусть f0, f, g ? C1, а x* - регулярное локальное решение задачи (4). Тогда найдутся л* ? Rk, м* ? Rl не равные одновременно нулю, такие, что м*j ? 0 приj ? J(x*) и
|
L?x(x*,л*, м*) = 0, |
(9) |
|
(м*, g(x*)) = 0. |
(10) |
|
Д о к а з а т е л ь с т в о. Пусть л0**, л** и м** - величины, существование которых утверждается в теореме 7.2. Покажем, что л0** ? 0. В предположении противного умножим (5) скалярно на вектор h, фигурирующий в определении регулярности x*: |
|
k ? i = 1 лi**(f ?i(x*),h)+ ? j?J(x*) мj**(g?j(x*),h) = И. |
(11) |
|
В силу регулярности (f ?i(x*),h) = 0 и (g?j(x),h) < 0, а по теореме 7.2 мj**? 0 при j ? J(x*). Поэтому (11) влечет равенство м** = И. Но тогда (5) означает, что |
|
k ? i = 1 лi**f ?i(x*)= И, |
что вместе с линейной независимостью f ?i(x*)дает равенство л** = И. Противоречие.
Таким образом л0**? 0. Положим теперь л*i= лi**/л0**(i = 1, ..., k),
|
м*j= { мj**/л0**при j ? J(x*), 0 при j ? J(x*). |
Очевидно теперь, (10) выполняется автоматически, а (9) тривиально получается из (5).
5. Достаточные условия, существование, единственость
Ситуация с задачей (1)-(3) несколько отличается от изучавшихся ранее, поскольку минимумы здесь могут быть двух типов. В случае, когда в точке минимумаx* нет активных ограничений, т. е. J(x*) = ?, ситуация полностью аналогична описанной в предыдущем параграфе, поскольку ограничения-неравенства в окрестности точки x* можно опустить (см. рис. 3). В случае же, когда J(x*) ? ? минимум может достигаться на границе множества Щ и точка x* может не быть стационарной точкой (см. рис. 3).
Рис. 3.
Мы ограничимся лишь формулировками результатов, поскольку в идейном плане они не доставляют ничего нового. Аналогом теоремы 6.9 может служить следующая
Теорема (достаточные условия минимума). Пусть f0, f, g ? C2, а x* - допустимая точка такая, что для некоторых л* ? Rk и м* ? Rl, одновременно не равных нулю, выполнены условия (9)-(10) и при любых h ? Rm, h ? И таких, что
|
(f ?i(x*),h) = 0 при i = 1, ..., k; (g?j(x*),h) = 0 при j ? J(x*), м*j> 0; (g?j(x*),h) ? 0 при j ? J(x*), м*j= 0 |
|
выполнено неравенство (L??xx(x*,л*, м*)h, h) > 0. Тогда x* - локальное решение задачи (1)-(3). |
З а д а ч а 7.2. Докажите.
Что касается утверждений о существовании и единственности, то ситуация с результатами, которые могут быть доказаны изученными выше приемами, полностью аналогична.
З а д а ч а 7.3. Сформулируйте и докажите аналоги утверждений задач 6.7 и 6.8 для задачи (1)-(3).
6. Об ограничениях-равенствах
С целью упрощения изложения, начиная с этого момента, мы будем рассматривать задачу условной оптимизации, содержащую только ограничения-неравенства. Это, с одной стороны, не снижает общности изложения, поскольку ограничения-равенства сводятся к ограничениям-неравенствам: ограничение
|
f(x) = И |
эквивалентно ограничениям
|
f(x) ? И, -f(x) ? И. |
С другой стороны, задачи с ограничениями-равенствами мы уже достаточно подробно рассматривали выше.
Здесь, правда, следует помнить об одном важном обстоятельстве. При решении задач с ограничениями-неравенствами часто бывает важна (существенно используется) выпуклость функций, фигурирующих в задаче, вернее, выпуклость минимизируемой функции f0 и выпуклость множества Щ допустимых точек. Последнее гарантируется выпуклостью функций gj в ограничениях-неравенствах (см. задачу 7.4 ниже). Множества же, выделяемые ограничениями-равенствами, не бывают выпуклыми, за исключением случая аффинных функций fi. Поэтому методы решения задач условной оптимизации, существенно использующие "выпуклость задачи" могут применяться к задачам с ограничениями-равенствами с большой осторожностью.
Напомним, что множество Щ ? Rm называется выпуклым, если ?(x, y ? Щ, л ? [0, 1])[лx + (1 - л)y ? Щ].
З а д а ч а 7.4. Докажите, что если функции gi: Rm > R (i = 1, ..., l) выпуклы, то множество Щ = {x ? Rm: gi(x) ? 0, i = 1, ..., l} выпукло.
З а д а ч а 7.5. Докажите, что если функция g: Rm> R выпукла, вместе с функцией -g, то она аффинна: g(x) = (b, x) + c.
7.7. Еще один достаточный признак условного минимума.
Напомним, что точка (x*, л*) называется седловой точкой функции L: Щ1ЧЩ2 > R (Щ1 ? Rm, Щ2 ? Rl), если при всех (x, л) ? Щ1ЧЩ2 выполнены неравенства
|
L(x*, л) ? L(x*, л*) ? L(x, л*) |
|
Теорема. Пусть (x*, л*) - седловая точка функции Лагранжа L: RmЧRl+> R задачи (1), (3) (здесь Rl+= {л ? Rl: л ? И}), л* ? И, x* - допустимая точка. Тогда x* - глобальное решение этой задачи. |
Д о к а з а т е л ь с т в о. Пусть x - произвольная допустимая точка, т. е. gi(x) ? 0 (i = 1, ..., l). Тогда
|
f0(x*) + (л*, g(x*)) = L(x*, л*) ? L(x, л*) = f0(x) +(л*, g(x)). |
(12) |
Покажем, что
|
(л*, g(x*)) = 0. |
(13) |
Тогда из (12), поскольку л* ? И, а g(x) ? И, будет следовать нужное неравенство f0(x*) ? f0(x). Для доказательства (13) заметим, что по условию теоремыL(x*, И) ? L(x*, л*), т. е.
|
(л*, g(x*)) ? 0. |
(14) |
Равенство (13) вытекает теперь из (14), т.к. л* ? И, а g(x*) ? И.
Тот факт, что доказанная теорема дает лишь достаточный признак условного минимума демонстрируетсмя в следующей задаче.
З а д а ч а 7.6. Покажите, что одномерная задача минимизации функции f(x) = -x при ограничениях x ? 1, -x ? 0 разрешима, но ее функция Лагранжа не имеет седловых точек.
З а д а ч а 7.7. Если в предыдущей теореме (x*, л*) - локальная седловая точка, то можно ли утверждать, что x* - локальное решение задачи (1), (3)? (Ответ: нельзя).
Однако, если функции f0 и gi (i = 1, ..., l) выпуклы, а множество Щ содержит хотя бы одну внутреннюю точку, то условия доказанной теоремы являются необходимыми и достаточными (это утверждение называется теоремой Куна - Таккера; оно является центральным фактом теории выпуклого программирования).
Перейдем к описанию методов решения задач с ограничениями-неравенствами. Многие из описываемых ниже методов либо существенно используют выпуклость объектов, фигурирующих в задаче, либо вообще неработоспособны на невыпуклых задачах.
8. Методы возможных направлений
Эти методы основываются на следующем простом понятии. Вектор (направление) z в допустимой точке x назовем возможным для задачи (1), (3), если малое перемещение в этом неправлении уменьшает значение функции f0 и не выводит из множества допустимых точек, т. е. если при достаточно малых s точкаxs = x + sz допустима и f(xs) < f(x). Если теперь на каждом шаге сдвигаться в возможном направлении на достаточно малое расстояние, то мы очевидно получим релаксационную последовательность, которая во многих случаях будет сходиться к решению задачи. Методы этого типа называются методами возможных направлений.
З а д а ч а 7.8*. Докажите, что если (f0(x), z) < 0, то малое перемещение из точки x в направлении z уменьшает значение функции f0 (ср. с доказательством теоремы Ферма).
З а д а ч а 7.9*. Докажите, что если точка x допустима и (gi(x), z) < 0 при i ? J(x), то малое перемещение из точки x в направлении z не выводит из множества допустимых точек.
В силу этих задач возможное направление zn в очередной точке xn, в котором функция f0 будет убывать быстрее всего, можно искать, решая задачу линейного программирования (о методах решения линейных задач см. список литературы)
|
(f ?0(xn),z) > min, |
(15) |
|
(g?i(xn),z) ? 0, i ? J(xn), |
(16) |
|
zi - 1 ? 0, -zi - 1 ? 0, i = 1, ..., m. |
(17) |
Здесь "нормализующие" ограничения (16) введены для того, чтобы искать вектор возможных направлений на ограниченном множестве, т. е. для того, чтобы линейная задача (15)-(16) была разрешима. К сожалению, решение задачи (15)-(16) не всегда дает возможное направление (см. рис. 4). Причиной этого являются нестрогие неравенства в (16) (задачи же со строгими неравенствами часто оказываются неразрешимыми, поскольку точная нижняя грань значений функции f0 часто достигается на границе множества допустимых точек, которая в случае строгих ограничений-неравенств не принадлежит этому множеству). Эту трудность можно обойти разными способами. Например, на каждом шаге можно "возвращать" точку во множество Щ с помощью какой-либо процедуры "проектирования" см., например, следующий пункт). Можно также поступать следующим образом. Для любой допустимой точки x и произвольного е > 0определим множество Jе(x) индексов так называемых е-активных ограничений:
|
Jе(x) = {i ? {1, ..., m}: gi(x) ? -е}. |
Рис. 4.
Таким образом, если е малу и i ? Jе(x), то i-ое ограничение в точке x почти обращается в равенство. В одном из вариантов метода возможных направлений выбирают последовательность еn > 0 и из очередной точки xn следующий шаг совершют в направлении zn:
|
xn+1 = xn + бnzn, |
(18) |
где zn есть решение следующей линейной задачи
|
о> min |
с ограничениями
|
(f ?0(xn),z) - о ? 0, |
|
(g?i(xn),z) - о ? 0, i ? Jеn(xn) |
и нормализующими ограничениями (16). Подчеркнем, что в этой задаче неизвестными являются z и о. Длина шага в (18) выбирается таким образом, чтобы точка xn+1 не выходила из множества допустимых точек.
9. Методы проекции градиента
Проекцией PЩx точки x ? Rm на множество Щ ? Rm называется любая ближайшая к x точка множества Щ:
|
||x - PЩx|| ? ||x - y|| при всех y ? Щ. |
З а д а ч а 7.10. Докажите, что если Щ замкнуто и выпукло, то для любой точки проекция сужествует и единственна.
З а д а ч а 7.11. Приведите пример, когда проекция: а) не существует; б) не единственна.
В тех случаях, когда проекцию точки на множество допустимых точек задачи (1), (3) найти достаточно легко (например, когда Щ - линейное подпространство, полупространство, шар, Rm+и т. д.) используют метод проекции градиента:
|
xn+1 = PЩ(xn - бnf ?0(xn)) |
(см. рис. 5), являющийся прямым обобщением градиентного метода.
Рис. 5.
Можно доказать, например, что если функция f0 ? C1 сильно выпукла и f ? удовлетворяет условию Липшица, а множество Щ замкнуто и ограничено, то методпроекции градиента сходится со скоростью геометрической прогрессии.
10. Методы линеаризации
Суть этих методов, как следует из названия, состоит в линеаризации минимизируемой функции и ограничений в очередной точке xn строящейсярелаксационной последовательности и объявлении следующим значением xn+1 решения получающейся линейной задачи, т. е. задачи
|
(f ?0(xn),x - xn) > min, |
(19) |
|
gi(xn) + (g?i(xn),x - xn) ? 0, i = 1, ..., l. |
(20) |
Чтобы эта (линейная) задача была разрешима либо добавляют штраф в минимизируемую функцию, заменяя (19), например, задачей
|
(f ?0(xn), x- xn) + д||x - xn||2 > min, |
либо добавляя к (20) простые ограничения, которые делают множество допустимых точек этой задачи ограниченным, например, (линейные) ограничения
|
xi - xni- бn ? 0, -xi + xni- бn ? 0 (i = 1, ..., m). |
Часто для уменьшения объема вычислительной работы среди ограничений (20) оставляют только е-активные.
11. Методы штрафов
Основная идея здесь заключается в переходе от задачи (1), (3) к задаче безусловной оптимизации, в которой "наказывается" либо удаление от множества Щдопустимых точек (внешний штраф), либо приближение изнутри множества Щ к его границе (внутренний штраф). Например, это можно сделать так. Для любого s > 0 определим функцию Fsout:Rm > R равенством (индекс "out" станет понятен чуть ниже)
|
Fsout(x)= f0(x) + s l ? i = 1 (gi)2+(x). |
(21) |
З а д а ч а 7.12 (ср. с задачей 6.11). Пусть f0, g ? C1, а x* - единственное решение задачи (1), (3). Пусть, кроме того, множество {x ? Rm: ||gi(x)|| ? е, i = 1, ..., l} при некотором е ? 0непусто и ограничено. Докажите, что (безусловная) задача
|
F sout(x)> min |
(22) |
при всех s разрешима и ее решение xs сходится к x* при s> ?.
Геометрическая трактовка замены задачи (1), (3) задачей (22) изображена на рис. 6.
Рис. 6.
Задачу (22) решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности задачи (22) с ростом s.
Описанный класс методов называют методами внешних штрафов, поскольку минимизируемая функция изменяется вне множества Щ. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества Щ возводятся барьеры, не позволяющие приближаться к его границе. Например, вместо задачи (1), (3) можно рассмотреть задачу
|
Fsin(x)> min, |
(23) |
где функция Fsin: Щg >R определяется равенством (ср. с ((21))
|
Fsin(x)= f0(x) + s l ? i = 1 1 gi(x) . |
Сравнение геометрических интерпретаций задач (1), (3) и (23) изображено на рис. 7.
Рис. 7.
З а д а ч а 7.13. Сформулируйте и докажите аналог задачи 7.5 для метода барьеров.
Задача (23) решается методами, развитыми для безусловных задач; при этом "крутизна барьера" характеризуемая числом s, возрастает на каждом шаге.
З а д а ч а 7.14. Попытайтесь выписать аналоги штрафных функций Fsoutи Fsinдля общей задачи нелинейного программирования (1)-(3), содержащей как ограничения-неравенства, так и ограничения-равенства.
12. Двойственные методы
Суть методов из этого весьма обширного класса в применении к задачам с ограничениями-неравенствами, так же как и в задачах с ограничениями-равенствами, заключается в замене условной задачи (1), (3) задачей поиска стационарной (часто седловой) точки функции Лагранжа. В выпуклом случае задача (1), (3) и задача о поиске седловой точки функции Лагранжа в силе теоремы Куна - Таккера эквивалентны. Например, применение простейшего (градиентного) метода к последней задаче приводит к следующему методу Эрроу - Гурвица - Удзавы:
|
xn+1 = xn - бnL?x(xn,мn), мn+1 = [мn + бnL?м(xn,мn)]+. |
Для поиска седловой точки в двойственных методах применяют почти весь спектр описанных выше методов минимизации - методы Ньютона, квазиньютоновские методы, методы сопряженных направлений и т. д.
Размещено на Allbest.ru
...Подобные документы
Формулировка общей задачи математического программирования. Классификация задач нелинейного программирования. Понятие о функции Лагранжа. Задача теоремы Куна-Таккера. Экономическая интерпретация множителей Лагранжа, формулирование условий оптимальности.
презентация [669,1 K], добавлен 25.07.2014Решение задачи нелинейного программирования с определением экстремумов функции. Этапы процесса нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации. Определение гиперповерхности уровней функции.
курсовая работа [1,5 M], добавлен 25.09.2010Решение задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях. Компьютерная реализация выбранных задач нелинейного программирования в среде пакетов Excel и Matlab.
дипломная работа [2,9 M], добавлен 25.01.2013Постановка задачи нелинейного программирования. Определение стационарных точек и их типа. Построение линий уровней, трехмерного графика целевой функции и ограничения. Графическое и аналитическое решение задачи. Руководство пользователя и схема алгоритма.
курсовая работа [2,5 M], добавлен 17.12.2012Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013Особенности решения задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования. Общая характеристика классических и числовых методов решения.
дипломная работа [2,4 M], добавлен 20.01.2013Описание параметрических и непараметрических методов штрафных функций в области нелинейного программирования. Решение задачи с использованием множителей Лагранжа. Непрерывность, гладкость, выпуклость, простота вычисления значения функции и производных.
курсовая работа [114,8 K], добавлен 25.11.2011Число линейно независимых уравнений. Отрицательная базисная переменная. Симплекс-метод решения задач линейного программирования. Экстремальное значение целевой функции. Метод северо-западного угла. Задачи нелинейного программирования. Функция Лагранжа.
контрольная работа [257,5 K], добавлен 29.09.2008Понятие графика функции и его представление на ЭВМ. Алгоритм реализации, блок-схема и функциональные тесты графического метода решения частного случая задачи нелинейного программирования, его математическая модель. Диалог программы с пользователем.
курсовая работа [1,6 M], добавлен 15.05.2012Поиск верхних и нижних границ для оптимального значения на подобласти допустимых решений. Методы и проблемы решения задач нелинейного программирования. Написание и отладка программы. Создание программы для решения задачи "коммивояжёра" прямым алгоритмом.
курсовая работа [176,9 K], добавлен 22.01.2016Методы решения задачи оптимального резервирования технической системы. Решение задачи методами неопределенных множителей Лагранжа и динамического программирования. Построение оптимальной схемы системы при нагруженном резервировании ее элементов.
лабораторная работа [31,5 K], добавлен 10.06.2009Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Экстремальные комбинаторные задачи. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори.
курсовая работа [211,3 K], добавлен 22.05.2013Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Особенности технологии параллельного программирования, описание компилятора OpenMP (Open Multi-Processing) и MPI (Message Passing Interface). Постановка задачи о ранце и пример ее решения на С++. Решение задачи о ранце на OpenMP со многими потоками.
магистерская работа [1,8 M], добавлен 08.03.2012Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Постановка задачи нелинейного программирования. Критерии оптимальности в задачах с ограничениями. Задачи с ограничением в виде равенств. Метод исключения переменных. Интерпретация условий Куна-Таккера. Функции нескольких переменных. Методы прямого поиска.
реферат [330,0 K], добавлен 29.09.2008Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Понятие арифметического точечного пространства. Различные виды плоскостей в пространстве. Общая задача оптимизации. Геометрия задачи линейного программирования. Графический метод решения задачи линейного программирования при малом количестве переменных.
курсовая работа [756,9 K], добавлен 29.05.2014
