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

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

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 набуває найбільшого значення fmax = 52,2+10,8 = 11,8; Оскільки не вказано, що елементи розв’язку додатні, то т.D(-2;0) – точка мінімуму, тобто при х2=-2 та х2=0 функція f набуває найменшого значення fmin = 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,0,4,4,5,1) – початковий опорний план. f0 = 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, fmax = =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,0,6,15) – початковий опорний план. f0 = -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,0,60,380) – початковий опорний план. f0 = -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,
fmax=-970+42,5+0(-3)+ 10+30+60=-620.
  1   2   3


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации