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

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

n1.doc

914kb.

10.06.2012 06:34

скачать

---

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

n1.doc

Завдання 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



х_і 0,

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

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



х_і 0,

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

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

4

0

М

М



x 1

x 2

x 3

x 4

z 1

z 2

z1

М

6

2

-1

5

0

1

0

3

 z2

М

15

8

1

0

-1

0

1

15/8

j0

21M

10M+12

1

5M-4

-M

0

0

Крок 2

Базис

Сбаз

План

x 1

x 2

x 3

x 4

z 1

z 2



 z1

М

9/4

0

-5/4

5

1/4

1

-1/4

9/20

x1

-12

15/8

1

1/8

0

-1/8

0

1/8

-

j0

9/4M-45/2

-24

-5/4M-1/2

5M-4

1/4M+3/2

0

-5/4M-3/2

Крок 3

Базис

Сбаз

План

x 1

x 2

x 3

x 4

z 1

z 2



 x3

4

9/20

0

-1/4

1

1/20

1/5

-1/20

9

x1

-12

15/8

1

1/8

0

-1/8

0

1/8

-

j0

-207/10

-24

-3/2

0

17/10

-M+4/5

-M-17/10

Крок 4

Базис

Сбаз

План

x 1

x 2

x 3

x 4

z 1

z 2



x4

0

9

0

-5

20

1

4

-1

x1

-12

3

1

-1/2

5/2

0

1/2

0

j0

-36

-24

7

-34

0

-M-6

-M

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

Завдання 4

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



х_і 0, .

Оскільки система обмежень вже подана у канонічній формі, то для одержання першого опорного плану до лівих частин рівнянь додаємо деякі невід’ємні штучні змінні 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

4

-3

1

3

6

М

М



x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2

z1

М

60

1

-4

4

5

-6

1

1

0

12

 z2

М

380

6

-16

27

33

-10

6

0

1

380/33

j0

440M

7M+9

-20M-4

31M+3

38M-1

-16M-3

7M-6

0

0

Крок 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

0

-148/33

1/11

1

-5/33

80/3

x4

1

380/33

2/11

-16/33

9/11

1

-10/33

2/11

0

1/33

380/6

j0

80/33M+ 380/33

1/11M+ 101/11

-52/33M -148/33

-1/11M+ 42/11

0

-148/33M -109/33

1/11M-64/11

0

-38/33M +1/33

Крок 3

Базис

Cбаз

План

x 1

x 2

x 3

x 4

x 5

x 6

z 1

z 2



x1

-9

80/3

1

-52/3

-1

0

-148/3

1

11

-5/3

-

 x4

1

20/3

0

8/3

1

1

26/3

0

-2

1/3

10/13

j0

-700/3

0

464/3

13

0

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



x1

-9

840/13

1

-28/13

61/13

74/13

0

1

-5/13

3/13

-

 x5

3

10/13

0

4/13

3/26

3/26

1

0

-3/13

1/26

5/2

j0

-7530/13

0

212/13

-1011/26

-1427/26

0

-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



x1

-9

70

1

0

11/2

13/2

7

1

-2

1/2

x2

4

5/2

0

1

3/8

3/8

13/4

0

-3/4

1/8

j0

-620

0

0

-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.

---