3.3 Преобразование нелинейной модели к сепарабельному виду. Аппроксимация нелинейной сепарабельной функции кусочно-линейной функцией

Максимизировать целевую функцию:

Y=21x₁+5x₂+7x₃--2x₁x₂--→ max

При ограничениях:

x₁+3x₂ ≤ 2

3x₁+x₃ ≤ 0

x_1,2,3 ≥ 0

Преобразуем нелинейную модель к сепарабельному виду, введя подстановки

,

где y и z новые переменные.

В задачу также добавятся новые ограничения:

и ограничения для обеспечения неотрицательности:

Определим верхние и нижние границы переменных x₁, x₂, x_3, z, y. Для этого решаем соответствующие задачи линейного программирования c ограничениями:

x₁+3x₂ ≤ 2

3x₁+x₃ ≤ 0

x_1,2,3 ≥ 0

Границы х₁:

Y=x₁ → min, Y=0;

Y=x₁ → max, Y=0;

Границы х₂:

Y=x₂ → min, Y=0;

Y=x₂ → max, Y=2/3;

Границы х₃:

Y=x₃ → min, Y=0;

Y=x₃ → max, Y=0;

Границы y:

Y=y → min, Y=0;

Y=y → max, Y=1/3;

Границы z:

Y=z → min, Y=-1/3;

Y=z → max, Y=0;

Для выбора точек аппроксимации построим графики линеаризуемых функций.

Рисунок 3.1 - График функции F(x)=5x₂-

Рисунок 3.2 - График функции F(x)=y²

Рисунок 3.3 - График функции F(x)=z²

Точки следует выбрать в соответствии со следующим правилом: чем менее линейна функция на определенном участке, тем выше должна быть плотность точек аппроксимации. Разбиения, принятые при решении данной задачи, приведены в таблице 3.8.

Таблица 3.8 – Сетка аппроксимации

Переменная	Номера точек
	1	2	3	4	5	6	7	8	9	10
x1	0	0	0	0	0	0	0	0	0	0
x2	0	2/27	4/27	2/9	8/27	10/27	4/9	14/27	16/27	2/3
x3	0	0	0	0	0	0	0	0	0	0
y1	0	1/27	2/27	1/9	4/27	5/27	2/9	7/27	8/27	1/3
z1	-1/3	-8/27	7/27	-2/9	-5/27	-4/27	-1/9	-2/27	-1/27	0

3.4 Решение задачи сепарабельным симплекс-методом

Используя выбранные точки можно преобразовать нелинейные ограничения и нелинейную ЦФ к кусочно-линейному виду. К ограничениям также добавятся ограничения, обеспечивающие свойство весов смежных точек. В итоге получим задачу линейного программирования.

Таблица 3.9. – Целевая функция для сепарабельного симплекс-метода

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

X11

x12

x13

x14

Y=

0

0

0

0

0

0

0

0

0

0

0

266/729

524/729

86/81

x15	x16	x17	x18	x19	x20	x21	x22	x23	x24	x25
1016/729	1250/729	164/81	1694/729	1904/729	26/9	0	0	0	0	0

x26	x27	x28	x29	x30	x31	x32	x33	x34	x35	x36
0	0	0	0	0	0	-2/729	-8/729	-2/81	-32/729	-50/729

x37	x38	x39	x40	x41	x42	x43	x44	x45	x46	x47
-8/81	-98/729	-128/729	-2/9	2/9	128/729	98/729	8/81	50/729	32/729	2/81

x48	x49	x50	x51	x52	СЧ
8/729	2/729	0	0	0	0

Таблица 3.10. – Ограничения для сепарабельного симплекс-метода

x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15	x16	x17
0	0	0	0	0	0	0	0	0	0	0	2/9	4/9	2/3	8/9	10/9	4/3
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	1/27	2/27	1/9	4/27	5/27	2/9
0	0	0	0	0	0	0	0	0	0	0	-1/27	-2/27	-1/9	-4/27	-5/27	-2/9

x18	x19	x20	x21	x22	x23	x24	x25	x26	x27	x28	x29	x30	x31	x32
14/9	16/9	2	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	1	1	1	1	1	1	1	1	1	1	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
7/27	8/27	1/3	0	0	0	0	0	0	0	0	0	0	0	-1/27
-7/27	-8/27	-1/3	0	0	0	0	0	0	0	0	0	0	0	0

x33	x34	x35	x36	x37	x38	x39	x40	x41	x42	x43	x44	x45
0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	0	0	0	0	0
0	0	0	0	0	0	0	0	1	1	1	1	1
-2/27	-1/9	-4/27	-5/27	-2/9	-7/27	-8/27	-1/3	0	0	0	0	0
0	0	0	0	0	0	0	0	1/3	8/27	7/27	2/9	5/27

x46	x47	x48	x49	x50	x51	x52
0	0	0	0	0	1	0	=	2
0	0	0	0	0	0	1	=	0
0	0	0	0	0	0	0	=	1
0	0	0	0	0	0	0	=	1
0	0	0	0	0	0	0	=	1
0	0	0	0	0	0	0	=	1
1	1	1	1	1	0	0	=	1
0	0	0	0	0	0	0	=	0
4/27	1/9	2/27	1/27	0	0	0	=	0

Введем необходимые свободные и искусственные переменные и выразим все ограничения в форме Таккера. Теперь решим задачу линейного программирования: минимизировать ЦФ вида:

Y = x₅₃+x₅₄ → max

Сепарабельный симплексный алгоритм аналогичен обычному симплекс методу, за исключением необходимости соблюдения правила ограниченного ввода в базис, суть которого заключается в том, что оптимальное решение, полученное с использованием аппроксимирующей модели, содержит либо один вес , либо два соседних.

Оптимизируем искусственную целевую функцию с соблюдением этого правила. Получив оптимальное решение, осуществим стандартную процедуру перехода от искусственной целевой функции к исходной. Теперь решим полученную задачу с помощью сепарабельного симплекс-метода. Все этапы решения приведены в приложении В. Полученные результаты удовлетворяют ограничениям.

Ответ: Y = 26/9, X = ( 0; 2/3; 0).