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

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

Задача 1

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

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

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

3x₁ + 3x₂ — 2x₃ 16

Х? 0

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

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

? 0

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

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

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

Задача 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

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

Задача 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.