- •Введение
- •1. Линейное программирование
- •1.1 Решение задачи 1.1
- •1.2 Решение задачи 1.2
- •1.3 Решение задачи 1.3
- •1.4 Выводы к Главе 1
- •2. Целочисленное программирование
- •2.1 Решение полностью целочисленных задач Решение задачи методом отсекающих плоскостей
- •Решение задачи методом ветвей и границ
- •2.2 Решение частично целочисленной задачи
- •Глава 3. Нелинейное программирование
- •1) Критерий Сильвестра.
- •2) Метод характеристических чисел.
- •3.2Квадратичный симплекс метод (метод Била)
- •3.3 Преобразование нелинейной модели к сепарабельному виду. Аппроксимация нелинейной сепарабельной функции кусочно-линейной функцией
- •3.4 Решение задачи сепарабельным симплекс-методом
- •3.5 Определение погрешности решения
- •3.6. Выводы к главе 3
3.3 Преобразование нелинейной модели к сепарабельному виду. Аппроксимация нелинейной сепарабельной функции кусочно-линейной функцией
Y=36x2-5x12+4x1x2-5x22 → max
При ограничениях:
x1+x2 ≤ 2
x1 ≤ 1/2
x1,2 ≥ 0
Функция является сепарабельной, если ее можно представить как сумму функций, каждая из которых зависит от одной переменной. Целевая функция данной задачи не является сепарабельной, т.к. содержит произведение двух переменных . Для приведения ее к сепарабельному виду необходимо ввести подстановку
В задачу также добавятся ограничения:
y1=1/2*x1+1/2*x2
z2=1/2*x1+1/2*x2
y2-z2≥0
Тогда задача примет вид:
Определим верхние и нижние границы переменных х1, х2, z, y. Для этого решаем соответствующие задачи линейного программирования. В итоге получим:
/4
Для осуществления линеаризации выберем некоторую «сетку» значений x, построенную так:
Затем любое значение x будем выражать в виде некоторой средневзвешенной xk по правилу:
где веса k удовлетворяют условиям:
Для выбора точек аппроксимации построим графики линеаризуемых функций.
Рисунок 3.1 -
Рисунок 3.2 -
Рисунок 3.3 -
Рисунок 3.4 -
Точки следует выбрать в соответствии со следующим правилом: чем менее линейна функция на определенном участке, тем выше должна быть плотность точек аппроксимации. Разбиения, принятые при решении данной задачи, приведены в таблице 3.3.1.
Таблица 3.3.1 – Сетка аппроксимации
Переменная |
Номера точек | |||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
x1 |
0 |
1/18 |
1/9 |
1/6 |
2/9 |
5/18 |
1/3 |
7/18 |
4/9 |
1/2 |
x2 |
0 |
2/9 |
4/9 |
2/3 |
8/9 |
10/9 |
4/3 |
14/9 |
16/9 |
2 |
y1 |
0 |
1/9 |
2/9 |
1/3 |
4/9 |
5/9 |
2/3 |
7/9 |
8/9 |
1 |
z1 |
-1 |
-7/8 |
-3/4 |
-5/8 |
-1/2 |
-3/8 |
-1/4 |
-1/8 |
0 |
1/4 |
Выразим переменные
Таблица 3.3.2
|
U1 |
U2 |
U3 |
U4 |
U5 |
U6 |
U7 |
U8 |
U9 |
U10 | |
x1 |
0 |
1/18 |
1/9 |
1/6 |
2/9 |
5/18 |
1/3 |
7/18 |
4/9 |
1/2 | |
f(x1) |
0 |
-5/324 |
-5/81 |
-5/36 |
-20/81 |
-125/32 |
-5/9 |
-245/32 |
-80/81 |
-5/4 | |
| |||||||||||
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
V7 |
V8 |
V9 |
V10 | |
x2 |
0 |
2/9 |
4/9 |
2/3 |
8/9 |
10/9 |
4/3 |
14/9 |
16/9 |
2 | |
f(x2) |
0 |
628/81 |
1216/81 |
196/9 |
2272/81 |
2740/81 |
352/9 |
3556/81 |
3904/86 |
52 | |
| |||||||||||
|
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
S8 |
S9 |
S10 | |
y |
0 |
1/9 |
2/9 |
1/3 |
4/9 |
5/9 |
2/3 |
7/9 |
8/9 |
1 | |
f(y) |
0 |
1/81 |
4/81 |
1/9 |
16/81 |
25/81 |
4/9 |
49/81 |
64/81 |
1 | |
| |||||||||||
|
T1 |
T2 |
T3 |
T4 |
T5 |
T6 |
T7 |
T8 |
T9 |
T10 | |
z |
-1 |
-7/8 |
-3/4 |
-5/8 |
-1/2 |
-3/8 |
-1/4 |
-1/8 |
0 |
1/4 | |
f(z) |
1 |
49/64 |
9/16 |
25/64 |
1/4 |
9/64 |
1/16 |
1/64 |
0 |
1/16 |
3.4 Решение задачи сепарабельным симплекс-методом
Теперь, используя выбранные точки можно преобразовать нелинейные ограничения и нелинейную ЦФ к кусочно-линейному виду. К ограничениям также добавятся ограничения, обеспечивающие свойство весов смежных точек. В итоге получим задачу линейного программирования.
Максимизировать целевую функцию вида:
При ограничениях:
k = 1, 2, …, 10.
Полученную задачу решаем с помощью сепарабельного симплекс-метода. Сепарабельный симплексный алгоритм аналогичен обычному симплекс методу, за исключением необходимости соблюдения правила ограниченного ввода в базис, суть которого заключается в том, что оптимальное решение, полученное с использованием аппроксимирующей модели, содержит либо один вес k, либо два соседних k, k+1.
Оптимизация исходной целевой функции и ее решение, с учетом правила ограниченного ввода в базис, приведены в приложении B.
Полученследующийрезультат:
Подставим полученные значения в исходную функцию и ограничения, получим:
Y = 52
Ответ:X = (0; 2); Y = 52