Исследование операций 4 (стр. 2 из 2)

β1=45		β2=60		β3=40		β4=60		β5=70
α1=0	45	60	40	60	95	90
	15	30	45	0	+
α2= -30	35	30	55	30	40	50
	+	15	+	20	15
α3= -30	50	40	35	30	100	30
	+	+	+	30	+
15		45		45		50		15		170

Δ1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки.

Таким образом, решение верное, т.к. Δij ≥0.

ОТВЕТ:

B1		B2		B3		B4		B5		a
A1	45	60	40	60	95	90
	15	30	45
A2	35	30	55	30	40	50
	15	20	15
A3	50	40	35	30	100	30
	30
b	15		45		45		50		15		170

Задача 4

№59

Условие:

Определить экстремум целевой функции вида

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при условиях

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2 .

1. Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.

2. Составить функцию Лагранжа.

3. Получить систему неравенств в соответствии с теоремой Куна-Таккера.

4. Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.

5. Дать ответ с учетом условий дополняющей нежесткости.

№

b1

b2

c11

c12

c22

extr

a11

a12

a21

a22

p1

p2

Знаки огр.1 2

59

4.5

1.5

–5

–2

–1

max

2

–3

5

4

9

13

³

³

Решение:

Целевая функция: F=-5x12-x22-2x1x2+4.5x1+1.5x2

Ограничения g1(x) и g2(x):

→

1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20):

→ →

2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции

F11 (х10, х20) = -10 < 0

F12 (х10, х20) = -2

F21 (х10, х20) = -2

F22 (х10, х20) = -2

Т.к. условие выполняется, то целевая функция является строго вогнутой в окрестности стационарной точки

3) Составляем функцию Лагранжа:

L(x,u)=F(x)+u1g1(x)+u2g2(x)=

=-5x12-x22-2x1x2+4.5x1+1.5x2+u1(2x1-3x2-9)+u2(5x1+4x2-13)

Получим уравнения седловой точки, применяя теорему Куна-Таккера:

i=1;2

Объединим неравенства в систему А, а равенства в систему В:

Система А:

Система В:

Перепишем систему А:

4)Введем новые переменные

V={v1,v2}≥0; W={w1,w2}≥0

в систему А для того, чтобы неравенства превратить в равенства:

Тогда

.

Следовательно, система В примет вид:

- это условия дополняющей нежесткости.

5) Решим систему А с помощью метода искусственных переменных.

Введем переменные Y={y1; y2} в 1 и 2 уравнения системы

и создадим псевдоцелевую функцию Y=My1+My2→min

Y’=-Y= -My1-My2→max.

В качестве свободных выберем х1, х2, v1, v2, u1, u2;

а в качестве базисных y1, y2, w1, w2.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

Решим с помощью симплекс-таблицы. Найдем опорное решение:

Примечание: вычисления производились программно, см Приложение

b		x1		x2		u1		u2		v1		v2
Y'	-6M	-12M	-4M	-M	9M	M	M
	y1	4,5	10	2	-2	-5	-1	0
y2		1,5	2	2	3	-4	0	-1
	w1	-9	-2	3	0	0	0	0
w2		-13	-5	4	0	0	0	0
	b		w1		x2		u1		u2		v1		v2
Y'	48M	-6M	-22M	-1M	9M	1M	1M
	y1	-40,5	5	17	-2	-5	-1	0
y2		-7,5	1	5	3	-4	0	-1
	x1	4,5	-0,5	-1,5	0	0	0	0
w2		9,5	-2,5	-3,5	0	0	0	0
	b		w1		x2		y1		u2		v1		v2
Y'	68,25M		-8,5M	-30,5M		-0,5M	11,5M		1,5M	1M
	u1	20,25	-2,5	-8,5	-0,5	2,5	0,5	0
y2		-68,25	8,5	30,5	1,5	-11,5	-1,5	-1
	x1	4,5	-0,5	-1,5	0	0	0	0
w2		9,58	-2,5	-3,5	0	0	0	0
	b		w1		x2		y1		y2		v1		v2
Y'	0	0	0	M	M	0	0
	u1	5,413043
u2		5,934783
	x1	4,5
w2		9,5

Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413043; u2=5,934783; x1=4.5; w2=9.5.

б) Условия дополняющей нежесткости не выполняются (u2w2≠0), значит решения исходной задачи квадратичного программирования не существует.

ОТВЕТ: не существует.

Приложение

#include <math.h>

#include <stdio.h>

main()

{

int i,j,k,m;

double h,n,a[5][7],b[5][7];

clrscr();

printf ("Введите числа матрицы А ");

for (i=0; i<5; i++){for(j=0; j<7; j++) {scanf ("%lf",&n); a[i][j]=n;}}

printf ("Введите координаты разрешающего элемента&bsol;n");

scanf("%d",&k) ;

scanf ("%d",&m);

printf (" матрицa A &bsol;n");

for (i=0; i<5; i++)

{for(j=0; j<7; j++) printf (" %lf",a[i][j]);printf ("&bsol;n");}

printf (" координаты &bsol;n ");

printf("%d %d",k,m) ;

h=1/a[k][m];

b[k][m]=h;

printf ("&bsol;n h=%lf",h);

for (i=0; i<7; i++)

{ if (i!=m) b[k][i]=a[k][i]*b[k][m]; }

for (i=0;i<5; i++)

{ if (i!=k) b[i][m]=-a[i][m]*b[k][m];}

for (i=0;i<5;i++)

{

for (j=0;j<7;j++)

if ((i!=k)&&(j!=m)) b[i][j]=a[i][j]+a[k][j]*b[i][m];

}

printf ("&bsol;n результат ");

printf (" матрицa B &bsol;n");

for (i=0; i<5; i++)

{for(j=0; j<7; j++) printf (" %lf",b[i][j]);printf ("&bsol;n");}

getch();

}