Алгоритмы численного решения задач

2



Решить графоаналитическим методом.



Задача 1



max  (X) = - 2x1 + x2 + 5x3

при 4x1 + 2x2 + 5x3  12

6x1 - 3x2 + 4x3 = 18

3x1 + 3x2 - 2x3  16

Х ≥ 0



Здесь число n = 3 и число m = 3.

Выразим из ограничений и х3:



≥ 0



Подставим его в целевую функцию



max  (X) = 



Получим новые ограничения:









х ≥ 0



Получили задачу линейного программирования в основном виде для n = 2

Вычисляем градиент :



 =  = 







х2=2х1-4,7

х2=

х 2=6-2х1

х2=2х1-6

D

E

C

A

Рисунок 1



Прямые a, c, d и e пересекаются и образуют четырехугольник ACDE. Определим max φ (Х), который удовлетворяет условию Х>=0:

Это точка D (0,7; 4,7; 0).

Функция φ (Х*) в точке D:

φ (Х*) = 38,3

Найти экстремумы методом множителей Лагранжа


Задача 2



extr φ (X) = 4x1 - x22 - 12

при x12 + x22 = 25



Составим функцию Лагранжа:



L (X,λ) = 4x1 - x22 - 12 + λ (x12 + x22 - 25)

h (X) = x12 + x22 - 25 = 0 - функция ограничения.



Составим систему уравнений из частных производных и приравняем их нулю.







Решим данную систему уравнений:



2x2 (λ - 1) = 0



Предположим, что x2 ≠ 0, тогда λ = 1 подставим в первое уравнение системы.



4 - 2x1 = 0

2x1 = - 4

x1 = 2



Подставим x1 в третье уравнение системы.



4 +x22 - 25 = 0

x22 - 21 = 0

x22 = 21

x2 = ±4,5826



Параболоид вращения функции h (x).







В двухмерной проекции график выглядит так:





А2

А1

Рисунок 2.



На рис.2 видно, что в точках А1 и А2 функция φ (X) = h (X). В этих точках функция φ (X) равна минимальному значению. 



 (X*,λ*)

N

X1*

X2*

λ*

φ (X*) 

Примечание

1

2

4,5826

1

-24,25

Min

2

2

-4,5826

1

-24,25

Min



Решить обобщенным методом множителей Лагранжа или на основе условий Куна-Таккера.



Задача 3



extr φ (X) = 9 (x1 - 5) 2 + 4 (x2 - 6) 2 = 

при 3x1 + 2x2 >= 12

x1 - x2 <= 6



Решим задачу на основе условий Куна-Таккера.

Составим функцию Лагранжа.



L (X,λ) = + λ1 (3x1 + 2x2 - 12) + λ2 (x1 - x2 - 6) =



Составим систему уравнений из частных производных и приравняем их нулю.







Решим систему уравнений.

1) Предположим, что λ2 ≠ 0, тогда из уравнения (d) получим



x2 = х1 - 6



Пусть λ1 = 0 и x1 ≠ 0, тогда из уравнения (а) получим



18x1 - 90 - λ2 = 0, λ2 = 18х1 - 90



Пусть x2 ≠ 0, тогда из уравнения (b) получим



8x2 - 48 - λ2 = 0



Подставив в уравнение выражения для x2 и λ2, получим



x1 = 4

x2 = - 2

x1* = 4; x2* = - 2; φ (Х) * = 265



Трехмерный график целевой функции для данной задачи







Двухмерная проекция





b(x)

φ(x)

a(x)

А

Рисунок 3



На рис.3 видно, что в точке А функция b (X) = a (X), которые находятся в параболоиде вращения целевой функции.

В этой точке функция φ (X) равна максимальному значению.

2) Предположим, что λ2 = 0 и x2 ≠ 0, тогда из уравнения (b) получим



8x2 - 48 + 2λ1 = 0

x2 = 

x2 = 6 - 



Предположим, что x1 ≠ 0, тогда из уравнения (а) выразим x1.



18х1 - 90 + 3λ1 = 0

18 = 90 - 3λ1

х1 = 

х1 = 5 - 



Подставим выражения для x1 и x2 в уравнение (с) системы.















а) = 0, x1 = 5; x2 = 6

б) = 15

x1 = 2,5; x2 = 2,25



Подставив корни x1 = 5; x2 = 6 в целевую функцию получим φ (Х) = 0, а корни x1 = 2,5; x2 = 2,25 - получим φ (Х) = 112,49

Таким образом:



x1* = 5; x2* = 6; φ* (Х) = 0



На рис.4 видно, что в точке В функция φ (X) = a (X). В этой точке функция φ (X) равна минимальному значению.





В

a(X)

b(X)

φ(X) 

Рисунок 4



X*

N

X1*

X2*

φ (X*) 

Примечание

1

5

6

0

Min

2

4

-2

265

Max



Получить выражение вектор-функции и матрицы Якоби системы и составить алгоритм численного решения задачи на основе условий Куна-Таккера.



Задача 4



max φ (X) = - x12 - x22 +2х2

при x1 + x2 >= 18

x1 + 2 x2 >= 14

Х>=0



Найдем выражение вектор-функции системы.

Составим функцию Лагранжа.



L (X,λ) = - x12 - x22 + 2х2 + λ1 (x1 + x2 - 18) + λ2 (x1 + 2x2 - 14)



Вектор-функция системы:







Составим матрицу Якоби.







Составим алгоритм численного решения задачи:



начало

{i ; xi >=0}

ε , μ

Х| = Х0| 

max = φ(Х|)

К = 0

Outputing



K, max, X*

Новый

расчет

Да

Нет

конец

1

1

2

2

Да

Нет

VecFunction F(Хк|)

Yacobian W(Хк|)

Inversion W-1(Хк|)

Хк+1|= Хк|- μ W-1(Хк|) F(Хк|)



φ(Хk+1|)- φ(Хk|)< ε 



max φ(Хk+1|)

X* = Хk+1|

Цикл итерации

Цикл задания

К = К +1

Result.txt

Data.txt

Рисунок 5.