Контрольная работа по математическому программированию - файл n1.doc

Контрольная работа по математическому программированию
скачать (914 kb.)
Доступные файлы (1):

n1.doc

914kb.

10.06.2012 06:34

скачать

Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление (Документ)
Лекции по математическому программированию (Лекция)
Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию (Документ)
Шапкин А.С., Шапкин В.А. Задачи по высшей математике, теории вероятностей, математической статистике, математическому программированию с решениями (Документ)
Меньшиков Ф.В. Олимпиадные задачи по программированию (Документ)
Контрольная работа №3 Вариант №1(Чертов) (Документ)
Златопольский Д.М. Дидактические материалы по программированию.Целочисленная арифметика. Логические величины. Условия (Документ)
Контрольная работа по Дискретной математике (Лабораторная работа)
Контрольная работа - Миграция, как проблема современного общества (Лабораторная работа)
Контрольная работа - Инженерное благоустройство (Лабораторная работа)
Юркин А.Г. Задачник по программированию (Документ)
Конспект по математическому моделированию (Лекция)

n1.doc

1 2 3

Завдання 1

f=5x1+x2max/min

Запишемо обмеження у вигляді рівностей, для чого введемо базисні невідомі у1, у2, у3, у4 у вигляді

Побудуємо прямі, що відповідають обмежувальним рівнянням при нульових значеннях базисних змінних. На кожній прямій відзначено стрілочками ту півплощину, що відтинає область із значеннями у_і при

Отже, т.В(2,2;0,8) – точка максимуму, тобто при х1=2,2 та х2=0,8 функція f набуває найбільшого значення f_max = 52,2+10,8 = 11,8; Оскільки не вказано, що елементи розв’язку додатні, то т.D(-2;0) – точка мінімуму, тобто при х2=-2 та х2=0 функція f набуває найменшого значення f_min = 5 (-2)+10 = -10.

Завдання 2

f=2x1+x2max

х_і

Запишемо систему обмежень у канонічній формі:

f=2x1+x2+0х3+0х4+0х5+0х6.

х3, х4, х5, х6 – базисні змінні, х1, х2 – вільні змінні.

Якщо х1=х2=0, то х3=4, х4=4, х5=5, х6=1. Х₀ = (0,0,4,4,5,1) – початковий опорний план. f₀ = 20+x20+04+04+05+01=0.

Наявну інформацію розташуємо у симплекс-таблиці та виконаємо необхідні обчислення для поліпшення початкового опорного плану.

Крок 1
Базис	С_баз	План	2	1	0	0	0	0
Базис	С_баз	План	x 1	x 2	x 3	x 4	x 5	x 6	
x3	0	4	-1	1	1	0	0	0	-
x4	0	4	1	0	0	1	0	0	4
x5	0	5	0	1	0	0	1	0	-
 x6	0	1	1	-1	0	0	0	1	1
_j0		0	-2	-1	0	0	0	0

Крок 2
Базис	С_баз	План	x 1	x 2	x 3	x 4	x 5	x 6	
x3	0	5	0	0	1	0	0	1	-
 x4	0	3	0	1	0	1	0	-1	3
x5	0	5	0	1	0	0	1	0	5
x1	2	1	1	-1	0	0	0	1	1
_j0		2	0	-3	0	0	0	2



Крок3
Базис	С_баз	План	x 1	x 2	x 3	x 4	x 5	x 6	
x3	0	5	0	0	1	0	0	1	5
x2	1	3	0	1	0	1	0	-1	-
 x5	0	2	0	0	0	-1	1	1	2
x1	2	4	1	0	0	1	0	0	-
_j0		11	0	0	0	3	0	-1

Крок 4
Базис	С_баз	План	x 1	x 2	x 3	x 4	x 5	x 6	
x3	0	3	0	0	1	1	-1	0
x2	1	5	0	1	0	0	1	0
x6	0	2	0	0	0	-1	1	1
x1	2	4	1	0	0	1	0	0
_j0		13	0	0	0	2	1	0

Оскільки всі елементи індексного рядка останньої таблиці невід’ємні, то отримано оптимальний план: х1=4, х2=5, х3=3, х4=0, х5=0, х6=2, f_max = =24+15+03+00+00+02=13.
Завдання 3

f=-12x1-x2+4х3min

х_і

Запишемо систему обмежень у канонічній формі:

f=-12x1-x2+4х3+0х4

Для одержання першого опорного плану до лівих частин рівнянь додаємо деякі невід’ємні штучні змінні z1, z2. Система матиме вигляд:

f=-12x1-x2+4х3+0х4+Мz1+Mz2min,

де М – додатне і дуже велике число.

z1, z2 – базисні змінні, х1, х2, х3, х4, – вільні змінні.

Якщо х1=х2=х3=x4=0, то z1=6, z2=15, Х₀ = (0,0,0,0,6,15) – початковий опорний план. f₀ = -120-10+40+00+М6+М15=21М.

Наявну інформацію розташуємо у симплекс-таблиці та виконаємо необхідні обчислення для поліпшення початкового опорного плану.

Крок 1

Базис

С_баз

План

-12

-1



x 1

x 2

x 3

x 4

z 1

z 2

-1

 z2

-1

15/8

_j0

21M

10M+12

5M-4

-M

Крок 2

Базис

С_баз

План

x 1

x 2

x 3

x 4

z 1

z 2



 z1

9/4

-5/4

1/4

-1/4

9/20

-12

15/8

1/8

-1/8

1/8

_j0

9/4M-45/2

-24

-5/4M-1/2

5M-4

1/4M+3/2

-5/4M-3/2

Крок 3

Базис

С_баз

План

x 1

x 2

x 3

x 4

z 1

z 2



 x3

9/20

-1/4

1/20

1/5

-1/20

-12

15/8

1/8

-1/8

1/8

_j0

-207/10

-24

-3/2

17/10

-M+4/5

-M-17/10

Крок 4

Базис

С_баз

План

x 1

x 2

x 3

x 4

z 1

z 2



-5

-1

-12

-1/2

5/2

1/2

_j0

-36

-24

-34

-M-6

-M

Оскільки в останній симплекс-таблиці в розв’язувальному стовпчику (зміна х2) немає додатних елементів (-5; -1/2), тобто неможливо вибрати зміну, яка має бути виведена з базису, то цільова функція задачі є необмеженою і оптимального плану не існує.

Завдання 4

4.а) f=-9x1+4x2-3х3+х4+3х5+6х6min

х_і

.

Оскільки система обмежень вже подана у канонічній формі, то для одержання першого опорного плану до лівих частин рівнянь додаємо деякі невід’ємні штучні змінні z1, z2. Система матиме вигляд:

f=-9x1+4x2-3х3+х4+3х5+6х6+Мz1+Mz2min,

де М – додатне і дуже велике число.

z1, z2 – базисні змінні, х1, х2, х3, х4, x5, x6 – вільні змінні.

Якщо х1=х2=х3=x4=x5=x6=0, то z1=60, z2=380, Х₀ = (0,0,0,0,0,0,60,380) – початковий опорний план. f₀ = -90+40-30+10+30+60+М60+М380=440М.

Наявну інформацію розташуємо у симплекс-таблиці та виконаємо необхідні обчислення для поліпшення початкового опорного плану.

Крок 1

Базис

C_баз

План

-9

-3



x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2

-4

-6

 z2

380

-16

-10

380/33

_j0

440M

7M+9

-20M-4

31M+3

38M-1

-16M-3

7M-6

Крок 2

Базис

C_баз

План

x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2



 z1

80/33

1/11

-52/33

-1/11

-148/33

1/11

-5/33

80/3

380/33

2/11

-16/33

9/11

-10/33

2/11

1/33

380/6

_j0

80/33M+

380/33

1/11M+

101/11

-52/33M

-148/33

-1/11M+

42/11

-148/33M

-109/33

1/11M-64/11

-38/33M

+1/33

Крок 3

Базис

C_баз

План

x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2



-9

80/3

-52/3

-1

-148/3

-5/3

 x4

20/3

8/3

26/3

-2

1/3

10/13

_j0

-700/3

464/3

1349/3

-15

-M-102

-M+46/3

Крок 4

Базис

C_баз

План

x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2



-9

840/13

-28/13

61/13

74/13

-5/13

3/13

 x5

10/13

4/13

3/26

-3/13

1/26

5/2

_j0

-7530/13

212/13

-1011/26

-1427/26

-15

-M+36/13

-M-51/26

Крок 5

Базис

C_баз

План

x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2



-9

11/2

13/2

-2

1/2

5/2

3/8

13/4

-3/4

1/8

_j0

-620

-45

-61

-53

-15

-M+15

-M-4

Оскільки всі елементи індексного рядка останньої таблиці не додатні, то отримано оптимальний план: х1=70, х2=2,5, х3=0, х4=0, х5=0, х6=0,
f_max=-970+42,5+0(-3)+ 10+30+60=-620.

1 2 3