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

Решить графоаналитическим методом.
Задача 1
max j (X) = — 2×1 + x2 + 5×3
при 4×1 + 2×2 + 5×3³ 12
6×1 — 3×2 + 4×3 = 18
3×1 + 3×2 — 2×3£ 16
Х ≥ 0
Здесь число n = 3 и число m = 3.
Выразим из ограничений и х3:
/>≥ 0
Подставим его в целевую функцию
max j (X) = />
Получим новые ограничения:
/>
/>
/>
х ≥ 0
Получили задачу линейного программирования в основном виде для n = 2
Вычисляем градиент />:
/> = /> = />
/>/>/>/>/>/>/>/>/>/>/>
Рисунок 1
Прямые a, c, d и e пересекаются и образуют четырехугольник ACDE. Определим maxφ (Х), который удовлетворяет условию Х>=0:
Это точка D (0,7; 4,7; 0).
Функция φ (Х*) в точке D:
φ (Х*) = 38,3
Найти экстремумы методом множителей Лагранжа
Задача 2
extr φ(X) = 4×1— x22— 12
при x12 + x22 = 25
Составим функцию Лагранжа:
L (X,λ) = 4×1 — x22 — 12 + λ (x12 + x22 — 25)
h (X) = x12 + x22 — 25 = 0 — функция ограничения.
Составим систему уравнений из частных производных и приравняем их нулю.
/>
Решим данную систему уравнений:
2×2 (λ — 1) = 0
Предположим, что x2 ≠ 0, тогда λ = 1 подставим в первое уравнение системы.
4 — 2×1 = 0
2×1 = — 4
x1 = 2
Подставим x1 в третье уравнение системы.
4 +x22 — 25 = 0
x22 — 21 = 0
x22 = 21
x2 = ±4,5826
Параболоид вращения функции h (x).
/>
В двухмерной проекции график выглядит так:
/>/>/>
Рисунок 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= />
при 3×1 + 2×2 >= 12
x1— x2
Решим задачу на основе условий Куна-Таккера.
Составим функцию Лагранжа.
L (X,λ) = />+ λ1 (3×1 + 2×2 — 12) + λ2 (x1 — x2 — 6) =
Составим систему уравнений из частных производных и приравняем их нулю.
/>
Решим систему уравнений.
1) Предположим, что λ2 ≠ 0, тогда из уравнения (d) получим
x2 = х1 — 6
Пусть λ1 = 0 и x1 ≠ 0, тогда из уравнения (а) получим
18×1 — 90 — λ2 = 0, λ2 = 18х1 — 90
Пусть x2 ≠ 0, тогда из уравнения (b) получим
8×2 — 48 — λ2 = 0
Подставив в уравнение выражения для x2 и λ2, получим
x1 = 4
x2 = — 2
x1* = 4; x2* = — 2; φ (Х) * = 265
Трехмерный график целевой функции для данной задачи
/>
Двухмерная проекция
/>/>/>/>/>
Рисунок 3
На рис.3 видно, что в точке А функция b (X) = a (X), которые находятся в параболоиде вращения целевой функции.
В этой точке функция φ (X) равна максимальному значению.
2) Предположим, что λ2 = 0 и x2 ≠ 0, тогда из уравнения (b) получим
8×2 — 48 + 2λ1 = 0
x2 = />
x2 = 6 — />
Предположим, что x1 ≠ 0, тогда из уравнения (а) выразим x1.
18х1 — 90 + 3λ1 = 0–PAGE_BREAK–
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) равна минимальному значению.
/>/>/>/>/>
Рисунок 4
X*
N
X1*
X2*
φ (X*)
Примечание
1
5
6
Min
2
4
-2
265
Max
Получить выражение вектор-функции и матрицы Якоби системы и составить алгоритм численного решения задачи на основе условий Куна-Таккера.
Задача 4
max φ (X) = — x12 — x22 +2х2
при x1 + x2 >= 18
x1 + 2×2 >= 14
Х>=0
Найдем выражение вектор-функции системы.
Составим функцию Лагранжа.
L (X,λ) = — x12 — x22 + 2х2 + λ1 (x1 + x2 — 18) + λ2 (x1 + 2×2 — 14)
Вектор-функция системы:
/>
Составим матрицу Якоби.
/>
Составим алгоритм численного решения задачи:
/>

Рисунок 5.