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