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

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

Задача 1

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

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

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

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

Х ≥ 0

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

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

≥ 0

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

maxj (X) =

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

х ≥ 0

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

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

Рисунок 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.

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

(X^,λ^)N	X₁^*	X₂^*	λ^*	φ (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

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

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

Рисунок 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) равна минимальному значению.

Рисунок 4

X^*N	X₁^*	X₂^*	φ (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.