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

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

Задача 1

max j (X) = - 2x₁ + x₂ + 5x₃

при 4x₁ + 2x₂ + 5x₃ ³ 12

6x₁ - 3x₂ + 4x₃ = 18

3x₁ + 3x₂ - 2x₃ £ 16

Х ≥ 0

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

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

≥ 0

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

max j (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) = 4x₁ - x₂² - 12

при x₁² + x₂² = 25

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

L (X,λ) = 4x₁ - x₂² - 12 + λ (x₁² + x₂² - 25)

h (X) = x₁² + x₂² - 25 = 0 - функция ограничения.

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

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

2x_{2 (}λ - 1) = 0

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

4 - 2x₁ = 0

2x₁ = - 4

x₁ = 2

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

4 +x₂² - 25 = 0

x₂² - 21 = 0

x₂² = 21

x₂ = ±4,5826

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

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

А2

А1

Рисунок 2.

На рис.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 (x₁ - 5) ² + 4 (x₂ - 6) ² =

при 3x₁ + 2x₂ >= 12

x₁ - x₂ <= 6

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

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

L (X,λ) = + λ₁ (3x₁ + 2x₂ - 12) + λ₂ (x₁ - x₂ - 6) =

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

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

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

x₂ = х₁ - 6

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

18x₁ - 90 - λ₂ = 0, λ₂ = 18х₁ - 90

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

8x₂ - 48 - λ₂ = 0

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

x₁ = 4

x₂ = - 2

x₁^* = 4; x₂^* = - 2; φ (Х) ^* = 265

 

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

 

 

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

 

b(x)

φ(x)

a(x)

А

Рисунок 3

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

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

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

8x_{2 -} 48 + 2λ₁ = 0

x₂ =

x₂ = 6 -

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

18х₁ - 90 + 3λ₁ = 0

18 = 90 - 3λ₁

х₁ =

х₁ = 5 -

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

а) = 0, x₁ = 5; x₂ = 6

б) = 15

x₁ = 2,5; x₂ = 2,25

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

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

x₁^*= 5; x₂^*= 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) = - x₁² - x₂² +2х₂

при x₁ + x₂ >= 18

x₁ + 2 x₂ >= 14

Х>=0

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

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

L (X,λ) = - x₁² - x₂² + 2х₂ + λ₁ (x₁ + x₂ - 18) + λ₂ (x₁ + 2x₂ - 14)

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

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

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

Рисунок 5.