|
|
Решение:
Целевая функция:
F= -2x12-x22-4x1x2+6x1+1,5x2→max
Ограничения g1(x) и g2(x): 2,5x1-x2³7 2,5x1-x2–7³0
3x1+2,5x2³13 3x1+2,5x2-13³0
1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20):
→
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции
F11 (х10, х20) = -4 < 0
F12 (х10, х20)=-4
F21 (х10, х20)=-4
F22 (х10, х20)=-2
F11 F12 -4 -4
F21 F22 -4 -2
Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F(x)+u1g1(x)+u2g2(x)=-2x12-x22-4x1x2+6x1+1,5x2+u1 (2,5x1-x2–7)+ u2 (3x1+2,5x2-13).
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
i=1;2
Объединим неравенства в систему А, а равенства в систему В:
Система А:
Система В:
Перепишем систему А:
6-4x1-4x2+2,5u1+3u2 <0
1,5-4x1-2x2-u1+2,5u2 <0
2,5x1-x2–7³0
3x1+2,5x2–13³0
4)Введем новые переменные
V={v1,v2}≥0; W={w1,w2}≥0
в систему А для того, чтобы неравенства превратить в равенства:
6-4x1-4x2+2,5u1+3u2 + v1=0
1,5-4x1-2x2-u1+2,5u2 + v2=0
2,5x1-x2–7- w1=0
3x1+2,5x2–13- w2=0
Тогда
- v1=6-4x1-4x2+2,5u1+3u2
- v2=1,5-4x1-2x2-u1+2,5u2
w1=2,5x1-x2–7
w2=3x1+2,5x2–13
Следовательно, система В примет вид:
- это условия дополняющей нежесткости.
5) Решим систему А с помощью метода искусственных переменных.
Введем переменные Y={y1; y2} в 1 и 2 уравнения системы
6-4x1-4x2+2,5u1+3u2 + v1 -y1=0
1,5-4x1-2x2-u1+2,5u2 + v2 -y2=0
2,5x1-x2–7- w1=0
3x1+2,5x2–13- w2=0
и создадим псевдоцелевую функцию Y=My1+My2→min
Y’=-Y= -My1-My2→max.
В качестве свободных выберем х1, х2, v1, v2, u1, u2;
а в качестве базисных y1, y2, w1, w2.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
y1=6-(4x1+4x2-2,5u1-3u2 - v1)
y2=1,5-(4x1+2x2+u1-2,5u2 -v2)
w1=-7-(-2,5x1+x2)
w2=-13-(-3x1-2,5x2)
Y’=-Y=-My1-My2=-7,5M-(-8x1-6x2+1,5u1+5,5u2+ v1+v2) M
Решим с помощью симплекс-таблицы. Найдем опорное решение:
|
|
|||||||
|
-7,5M 4,5M |
-8M 12M |
-6M 3M |
1,5M 3M |
5,5M -7,5M |
M 0 |
M -3M |
|
|
6 -3 |
4 -8 |
4 -2 |
-2,5 -2 |
-3 5 |
-1 0 |
0 2 |
|
|
1,5 3/4 |
4 2 |
2 0,5 |
1 0,5 |
-2,5 -5/4 |
0 0 |
-1 -0,5 |
|
|
-7 -3/4 |
-2,5 -2 |
1 -0,5 |
0 -0,5 |
0 5/4 |
0 0 |
0 0,5 |
|
|
-13 15/8 |
-3 5 |
-2,5 5/4 |
0 5/4 |
0 -25/16 |
0 0 |
0 -5/4 |
Меняем и
|
|
|||||||
|
-3M 3M |
4M -4M |
3M -2M |
4,5M -4,5M |
-2M M |
M -M |
-2M 2M |
|
|
3 3/2 |
-4 -2 |
-2 -1 |
-4,5 -9/4 |
2 0,5 |
-1 -0,5 |
2 1 |
|
|
3/4 15/8 |
2 -2,5 |
0,5 -5/4 |
0,5 -45/16 |
-5/4 5/8 |
0 -5/8 |
-0,5 5/4 |
|
|
-31/4 -15/8 |
-4,5 2,5 |
-0,5 5/4 |
-0,5 45/16 |
5/4 -5/8 |
0 5/8 |
0,5 -5/4 |
|
|
-89/8 75/32 |
2 -25/8 |
5/4 -25/16 |
5/4 -225/64 |
-25/16 25/32 |
0 -25/32 |
-5/4 25/16 |
Меняем и
|
|
|||||||
|
0 0 |
0 0 |
M 0 |
0 0 |
M 0 |
0 0 |
0 0 |
|
|
3/2 77/8 |
-2 -1 |
-1 -3/4 |
-9/4 -37/16 |
0,5 5/8 |
-0,5 -5/8 |
1 3/4 |
|
|
21/8 77/32 |
-0,5 -1/4 |
-3/4 -3/16 |
-37/16 -37/64 |
5/8 5/32 |
-5/8 -5/32 |
3/4 -3/16 |
|
|
-77/8 77/16 |
-2 -0,5 |
3/4 -3/8 |
37/16 -37/32 |
-5/8 5/16 |
5/8 -5/16 |
-3/4 3/8 |
|
|
-281/32 693/128 |
-9/8 -9/16 |
-5/16 -27/64 |
-145/64 -333/256 |
25/32 45/128 |
-25/32 -45/128 |
5/16 27/64 |
Меняем и
|
|
|||||||
|
0 0 |
0 0 |
M 0 |
0 0 |
M 0 |
0 0 |
0 0 |
|
|
89/8 431/18 |
-1 -16/9 |
-7/4 |
-73/16 |
9/8 |
-9/8 |
7/4 |
|
|
161/32 431/72 |
-1/4 -4/9 |
-15/16 |
-185/64 |
25/32 |
-25/32 |
9/16 |
|
|
77/16 431/36 |
-0,5 -8/9 |
-3/8 |
-37/32 |
5/16 |
-5/16 |
3/8 |
|
|
-431/32 431/18 |
-9/16 -16/9 |
-47/64 |
-913/256 |
145/128 |
-145/128 |
47/64 |
Меняем и
|
|
|||||||
|
0 |
0 |
M |
0 |
M |
0 |
0 |
|
|
2525/72 |
|
|
|
|
|
|
|
|
3173/288 |
|
|
|
|
|
|
|
|
2417/144 |
|
|
|
|
|
|
|
|
431/18 |
|
|
|
|
|
|
Итак, =====, =16,785, =11,017, =23,944, =35,07
6) Условия дополняющей нежесткости выполняются ,значит, решения исходной задачи квадратичного программирования существует.
Ответ: существует.
Литература.
1) Курс лекций Плотникова Н.В.
2) Пантелеев А.В., Летова Т.А. «Методы оптимизации в примерах и задачах».
При использовании материалов активная ссылка на источник обязательна.