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

• Название: Задача нелинейного программирования отличается от задачи на условный экстремум наличием дополнительных ограничений, имеющих вид
• Дата: 30.01.2019
• Размер: 71.84 Kb.
• Имя файла: курсовая.docx
• Тип: Задача; #65807

Содержание.

Введение………………………………………………………………………..3

Глава1. Основы нелинейного программирования…………………………..4

1. 
   Теорема Каруша – Джона…………………………………………………5
   
2. 
   Условия дополняющей нежесткости…………………………………....11
   
3. 
   Условия регулярности…………………………………………………...13
   
4. 
   Существование и единственность минимума………………………….18
   

Глава 2. Решение задачи нелинейного програмирования………………....23

Заключение …………………………………………………………………..25

Список литературы…………………………………………………………..26

Введение

Данная работа направлена на исследование и решение задач нелинейного программирования.

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

Цель курсовой работы заключается в изучении одного из основополагающих разделов теории экстремальных задач – математическому программированию.

Для осуществления обозначенной цели служат следующие задачи:

1. 
   Ознакомится с теоремой Каруша – Джона.
   
2. 
   Изучить условия дополняющей нежесткости и условия регулярности.
   
3. 
   Исследовать существование и единственность минимума.
   

1.Основы нелинейного программирования

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

h(x) <0, (1)

где h: R^{n →}R^r- некоторая заданная функция, и называемых ограничениями типа неравенств. Поэтому ограничения

g(x) = 0, (2) гдеg: R^n→R^m, в задаче нелинейного программирования называются ограничениями типа равенства. Таким образом задача нелинейного программирования заключается в минимизации числовой функции ƒ:R^{n →}R при выполнении ограничений (1) и (2).

Задачу нелинейного программирования часто записывают в следующем виде:

ƒ(x) → min,

gⁱ (x) = 0, i = 1,…..,m, (3)

hⁱ (x) <0, I = 1,……,r,

объединяя тем самым функцию ƒ, подлежащую минимизация и ограничения (1) и (2), которые следует учитывать при выполнении минимизации. Как и в случае задачи на условный экстремум нелинейного программирования представляет интерес только в случае, когда n>m, что и предполагается в дальнейшем. При этом множество Q точек, для которых выполнены условия (1) и (2) замкнуто, т.е. если множество Q ограничено.

1.1Теорема Каруша – Джона

В качестве примера будем рассматривать данные задачи. Задача (1) о минимизации функции ƒ (x¹, x²) = - (x¹)² -(x²)² при ограничении x¹ + x² = 1. Задача (2) о минимизации функции ƒ (x¹, x²) =x¹при ограничении

(x¹)² + (x¹)² = 0.

Пусть

Q₁ = {x€ Rⁿ :gⁱ(x) = 0, i = 1,…., m}

– множество точек, для которых выполнены ограничения типа равенств (1), и пусть

Q₂ = {x€ Rⁿ:hⁱ(x) < 0, i = 1,…., r}

– множество точек, для которых выполнены ограничения типа неравенств (2). Пересечение

Q = Q₁ ∩Q₂

множествQ₁иQ₂дает точки x € Rⁿ, называемые допустимыми точками в задаче (1). Точкаx^*€Qназывается точкой минимума (или точкой локального минимума) в задаче (1), если для всех x€Q₁, достаточно близких к допустимой точке x^*₁выполнено неравенство

ƒ(x^*) < ƒ(x).

Необходимое условие минимума в задаче (3) дает следующая важнейшая для теории экстремальных задач.

Теорема (Каруш – Джон). Пусть x^*- точка минимума в задаче (2) и функции ƒ, g¹,….,g^mи h¹,….,h^rнепрерывно дифференцируемы в некоторой окрестности E точки х^*. Тогда найдутся такие действительные числа , ,….., , и ,….., , не все равные нулю одновременно, что

ƒ(х^*) +gⁱ(x^*) + hⁱ(x*) = 0,(4)

где > 0

и

> 0, i = 1,……,r.

Доказательство. Пусть ε – некоторое положительное число и пусть U – множество точек x€ Rⁿ, для которых

|x – x*| <ε.

Выберем число ε столь малым, чтобы все функции ƒ, g¹,……, g^mи h¹,…., h^r были непрерывно дифференцируемы на множестве Q ∩ U ⸦ E, причем каждая из функций h¹,….,h^r не меняла знак на множестве U∩(Rⁿ\Q). Далее, пустьM – подмножество множества индексов i = 1,….,r, таких, что

hⁱ (x) > 0

на замыканииR множестваU ∩ (Rⁿ\Q). Если множество M пусто, то теорема 3 справедлива, поскольку здесь можно принять

= 0, i = 1,…,r.

Исключив этот тривиальный случай, наряду с задачей (1) введем в рассмотрение задачу о минимизации функции ƒ_k :Rⁿ→R, задаваемой равенством




(5)

где k – некоторое натуральное число, а a₁,…., a_r– действительные числа, задаваемые равенством

_i=

Функция ƒ_k, очевидно, непрерывна, а множества R – компактно. Поэтому ƒ_k для всех значений kимеет на множестве Rрешение x_k, т.е. существует такоеx_k∈R, что

ƒ_k(x_k) ≤ ƒ_k(x^*).

Отсюда в силу равенства (5) имеем




или, что эквивалентно,



Поскольку для всех значений k = 1, 2,3,…….

|x_k -x^*| < ε,

то

.

Следовательно,



т. е.

, i = 1,…..,m

и

= 0, I = 1,……,r.

Выберем некоторую неограниченно возрастающую последовательность

k₁, k₂,….., k_i,….., k_i=

натуральных чисел. Легко видеть, что последовательность

x_k1, x_k2,.., x_ki,..(6)

ограничена. При этом

gⁱ() = 0, i = 1,..,m,

a_ihⁱ () = 0, i = 1,..,r

и

ƒ () +< ƒ (x^*). (7)

Поскольку х^* - точка минимума на Q, то

ƒ (x^*) <ƒ ().

Поэтому из неравенства следует, что

() = x^*,

т. е. предельная точка всякой последовательности вида (3) совпадает с точкой х^*. Следовательно,

х_k= х^*,

т. е. для всех достаточно больших значений k точка х_k лежит внутри множества U. Но на множествоU

= 0

или, что эквивалентно,



(8)

Положим

,


,

i= 1,…..,m

и


,

i= 1,….,r.

Тогда равенство (4) можно переписать в следующем эквивалентном виде:
+(x_k–x^*)= 0. (5) (9)

Поскольку, очевидно




Для всех значений k = 1,2,3,……, то существует такая неограниченно возрастающая последовательность

k₁, k₂,……, k_j…., (10)

Натуральных чисел, что

= , i = 1,…., m

и

= , i = 1,…., r,

где



Поэтому, переходя в равенстве (5) к пределу при k вдоль множества (1), в котором по построению



и

i = 1,….., r.

1.2Условия дополняющей нежесткости

При доказательстве теоремы 1 использовался тот факт, что в точке х^* минимума некоторые из ограничений типа неравенств обращаются в равенства, а некоторые другие – в строгие неравенства. Чтобы ясно различать указанные два возможных случая, введем следующие определение.

Предположим, что при некотором значении i =1,…., rимеет место равенство

hⁱ(x^*) = 0.

Тогда будем говорить, что ограничение hⁱ активно. Аналогичным образом, если при некотором значении j = 1,….,r имеет место не равенство

hⁱ(x^*)< 0,

то будем говорить, что ограничение hⁱ активно.

Обозначим через I^* - множество активных ограничений в задаче (1)

I^*={i: hⁱ(x^*) = 0, i = 1,...,r}

Просматривая доказательства теоремы 1, несложно заметить, что если i I, то

= 0.

Если же i∈I^*, то по определению

hⁱ(x^*) = 0,

т. е. в любом случае

hⁱ(x^*) = 0, i = 1,…., r.(11)

Равенство (11) называется условиями дополняющей нежесткости и используются следующем образом.

Легко видеть, что условие (4) дает n уравнений относительно n + m + r + 1 неизвестного x^*, ,….., ….., . Дополнив условие (4) уравнениями

gⁱ (x^*) = 0 i = 1,……., m

и (11), получим систему n + m + rуравнений относительно n + m + r + 1 неизвестного x^*, ,….., ….., . При этом по прежнему велик соблазн принять

= 1(12)

и, таким образом, замкнуть систему. Последнее, как и в случае задачи на условный экстремум, можно делать далеко не всегда, даже если ограничения типа равенств отсутствуют.

Таким образом, условия дополняющей нежескости позволяют привести необходимое условие минимума в задаче (1). Чтобы замкнуть эту систему, нужно получить условия, позволяющие, например, наверняка принять равенство (12).

Замечание. Необходимо отметить, что в условиях теоремы 3 принципиальным является следующий момент: либо

0, (13)

либо = 0.

Последнее, конечно, объясняется тем, что множители ,….., ….., определены с точностью до неотрицательного множителя и потому при выполнении условия (13) без какой-либо потери общности можно принять равенство (12).

1.3Условие регулярности

Для получения некоторых условий, гарантирующих справедливость условия (13) или, что эквивалентно, (12), введем в рассмотрение функцию



(14)

которую будем называть функцией Лагранжа.При этом множители λ₁,…..,λ_m, μ₁,……., μ_r будем называть множителями Лагранжа.

Принимая очевидные обозначения, перепишем равенство (14) в следующем эквивалентном виде:

L(x,λ,μ) = ƒ(x) + + .

Если условие (14) выполняется, то в силу теоремы 3 необходимое условие минимума в задаче дает равенство

= 0, i = 1,……,n,

которое совместно с условиями

g(x) = 0

и

= 0, i = 1,……..,r

образуют замкнутую систему, решение которой дает искомые значения переменны.

Условия, при которых справедливо равенство (12), принято называть условием регулярности. Простейшее из условий регулярности, которое будем называть первым условием регулярности, выглядит следующим образом: если х^* - точка минимума в задаче (1), то функция ƒ,g^mμhⁱ,…..,h^r непрерывно дифференцируемые в некоторой ее окрестности, а вектора

(15)

линейно независимым.

Теорема 4. Пусть в некоторой точке х^* выполнено первое условие регулярности. Тогда найдутся такие λ^*∈ ℝ^mиμ^* ∈ ℝ^r, что

= 0, i = 1,…..,n(16)

и

= 0, i = 1,…..,r, (17)

где 0.

Доказательство. Прежде всего, заметим, что условие (17) есть условие дополняющей нежесткости и выполняется в точке х^* всегда. Далее, для всех i∉I^* запишем

= 0.

Тогда, поскольку вектора (15) линейно независимы, то в силу теоремы 3 следует принять



например,

= 1,

откуда и следует равенство (16).

Замечание. Легко видеть, что первое условие регулярности полностью аналогично условию регулярного минимума в задаче на условный экстремум. Другими словами, теорема 4 является очевидным аналогом теоремы 2. При этом следует иметь ввиду, что проверку линейной независимость векторов (15) необходимо проделывать в точке минимума (заранее неизвестной) со всеми вытекающими отсюда последствиями. Все это, однако, не снижает исторической ценности теорем 2 и 4, поскольку именно с них собственно и начиналось математическое программирование.

Сформулируем теперь более тонкое условие, которое будем называть вторым условием регулярности: если х^* - точка минимума в задаче (1), то функции ƒ, gⁱ,…..,g^mиhⁱ,…..,h^rнепрерывно дифференцируемы в некоторой ее окрестности, вектора ……., линейно независимы и существует такой вектор s∈ℝⁿ, что

= 0, i = 1,……,m

и

<0, i∈I^*.

Замечание. Легко видеть, что геометрически второе условие

регулярности означает следующие. В точке х^* найдется элемент s

касательного пространства к ограничениям типа равенств, который

направлен внутрь каждого из множеств

h^*(x^*) <0, i∈ I^*

активных в этой точки ограничений.

Теорема 5. Пусть в некоторой точке х^* выполнено второе условие

регулярности. Тогда найдутся такие λ^*∈ ℝ^m и μ^* ∈ ℝ^r, что

= 0, i = 1,…..,n (18)

и

= 0, i = 1,…..,r, (19)

где 0.

Доказательство. Как и в случае теоремы 4, заметим, что условие (19) выполняется в точке х^* всегда. Далее, для всех положим

= 0.

Тогда, предположим, что

= 0.

и умножаем равенство




скалярно на s, получим



Отсюда в силу условий 0. и

<0, i∈I^*

имеем

= 0. i = 1,…..,r.

Поэтому равенство (20) принимает вид



где в силу теоремы 3 не все одновременно равны нулю. Это, однако, противоречит принятой линейной независимости векторов

g¹(x^*),….,

g^m(x^*) и, значит,

= 1,

откуда и следует равенство (18).

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

1.4Существование и единственность минимума.

В отличии от задачи на условный экстремум, в задаче нелинейного программирования (1) достаточно просто устанавливаются условия существования решения. Объясняется это следующим.

Легко видеть, что множества ограничений как в задаче на условный экстремум, так и в задаче (1) замкнуты. При этом в случае задачи на условный экстремум даже в простейших ситуациях множества Q допустимых точек не ограничено. Это приводит к тому, что вопрос о существовании решения задачи на условный экстремум часто остается открытым. В случае задачи нелинейного программирования (1) дело обстоит несколько иначе: добавление к ограничению (1) ограничения (2) часто приводит к тому, что множество Q допустимых точек становится ограниченным и, следовательно, компактным. Поэтому задача (1) обычно находится в условиях применяемости теоремы Вейерштрасса и, значит, вопрос о существовании ее решения часто снимается.

Часто касается единственности решения задачи (1), то этот вопрос является гораздо более тонким. Как уже отмечалось ранее, в силу теоремы 4 и 5 точкой минимума может быть только точка х ∈Q, удовлетворяющая системе

где неизвестным наряду с х является и μ, причем

µ_i ≥0.(22)

Тогда, если система (21) имеет единственное решение, удовлетворяющее условию (22), то в силу теорем 4 и 5 это решение будет единственной точкой минимума в задаче (1). На практике, однако, единственность решений системы (21) имеет место далеко не всегда, даже если минимум единственный. Последнее, например, объясняется тем, что решение системы (21) не обязано удовлетворять условию (22).

Замечание. Необходимо отметить, что непосредственное применение к системе (21) какой-либо классической теоремы существования и единственности, очевидно, затруднено условием (22).

Пример. Рассмотрим задачу о минимизации функции

ƒ(х¹, х²) = (х¹)² + (х²)²(23)

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

х¹ + х² = 1, (24)

х¹> 0 (25)

x²> 0. (26)

Положим

g(x¹,x²) = x¹ + x² – 1, h¹(x¹, x²) = -x¹

и

h²(x¹, x²) = -x^2.

Тогда, поскольку для всех значений х¹ и х²

g(x¹, x²) = (1,1),

h¹(x¹, x²) = (-1, 0)

и

h²(x¹, x²) = (0, -1),

то заметив, что только одно из ограничений (25) или (26) может быть активным, видим, что для задачи (13) - (26) будет выполнятся первое условие регулярности. Поэтому без какой-либо потери общности можно принять

L(x¹, x², λ, μ₁, μ₂) = (x¹)² + (x²)² + λ(x¹ + x² -1) + μ₁(-x¹) + μ₂(-x²).

В силу теоремы 4 уравнения (21) для рассматриваемой задачи примут вид

(27)

где

μ₁>0, μ₂>0. (28)

Легко видеть, что при выполнении условия (28) система (27) имеет единственное решение





При этом, как несложно заметить, множество, задаваемое соотношениями

(24) – (26), компактно, поскольку представляет собой отрезок прямой (24),

заключенный между точками (0,1) и (1,0). Следовательно, точка (29) является

точкой минимума в задаче (23) – (26).

Пример. Рассмотрим задачу о минимизации функции



при ограничениях (24) – (26). Действуя, как и в примере 5, положим



и



Тогда, поскольку для всех значений х¹ и х²





и



то заметив, что только одно из ограничений (25) или (26) может быть

активным, видим, что для задачи о минимизации функции (30) при

ограничениях (24) – (26) будет выполнятся первое условие регулярности.

Поэтому без какой-либо потери общности можно принять



В силу теоремы 4 уравнения (21) для рассматриваемой задачи примут вид



где

μ₁>0, μ₂>0. (32)

Легко видеть, что при выполнении условия (32) система (31) имеет решения

x^*1 = 0, x^*2 = 1, λ^* = 2,

x^*1 = 1, x^*2 = 0, λ^* = 2,

и



При этом, как уже отмечалось в примере 5, множество (24) – (26)

Представляет собой отрезок прямой (24), заключенный между точками



Следовательно, задача о минимизации функции (30) при ограничениях

(24)-(26) имеет по крайней мере одно решение, т. е. по крайней мере одна из

точек (33), (34) или



является точкой минимума. На самом же деле несложно заметить, что каждая

из точек (33) и (34) является точкой локального минимума, а точка (35) –

точкой локального максимума.

2.Решение задачи нелинейного программирования

x² + (y-11)²

x + y = 1 x + y – 1 = 0

x ≥ 0 - x < 0

y > 0 - y < 0







x + y – 1 = 0



x

₀ =

x	y
a	а
а	н
н	а
н	н

x + y – 1 = 0





1. x = 0, y = 0

x + y = 0, невозможный случай

2. 
   x = 0, y> 0, = 0
   

3. 
   x > 0, y = 0, = 0
   

4. 
   x > 0, y > 0, = 0, = 0
   

x+y=1





x =-





2

И так

Ответ:

Заключение.

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

Список литературы

1.Элементарное введение в теорию экстремальных задач. А.П. Афанасьев, С.М. Дзюба М.: Наука, 1982.