Контрольная работа по предмету "Прикладная математика"

Автор работы: Пользователь скрыл имя, 09 Марта 2014 в 20:41, контрольная работа

Краткое описание

№1 Задача ЛП
Предприятие может производить 4 вида продукции (продукция 1,2,3,4) при использовании 3-х видов ресурсов (ресурс I,II,III).
Известен вектор объемов ресурсов:
128
В= 130
142
Известна техническая матрица затрат ресурсов:
2 4 5 3
А= 3 0 4 1
3 5 0 2
Известна удельная прибыль для каждого вида продукции:
С= (34 32 28 36)
Требуется составить план производства, который обеспечит максимальную прибыль.
№2 Двойственная задача и задача о расшивке «узких мест».

Прикрепленные файлы: 1 файл

1 Задача ЛП.doc

— 152.50 Кб (Скачать документ)

№1 Задача ЛП

Предприятие может производить 4 вида продукции (продукция 1,2,3,4) при использовании 3-х видов ресурсов (ресурс I,II,III).

Известен вектор объемов ресурсов:

      128


В=  130

      142

 

Известна техническая матрица затрат ресурсов:

 


         2 4 5 3

А=     3 0 4 1

         3 5 0 2 

 

Известна удельная прибыль для каждого вида продукции:

 

С= (34 32 28 36)

 

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

 

 

Пусть х1, х2, х3, х4 – количество продукции 1,2,3,4.

Очевидно, что х1,2,3,4≥0

Затраты ресурсов не должны превышать имеющихся объемов:

Для ресурса I:

2х1+4х2+5х3+3х4 ≤ 128

Для ресурса II:

3x1+…+4x3+x4 ≤ 130

Для ресурса III:

3х1+5х2+…+2х4 ≤ 142

Условие максимальности прибыли

Z= 34x1+32x2+28x3+36x4 → max

 

 

Математическая модель имеет вид:

Z= 34x1+32x2+28x3+36x4 → max

2х1+4х2+5х3+3х4 ≤ 128


3x1+…+4x3+x4 ≤ 130

3х1+5х2+…+2х4 ≤ 142

х1,2,3,4 ≥ 0

х1,2,3,4 - ?

Это задача Линейного программирования, приведем ее к основному виду, для этого добавим к каждому неравенству балансовую переменную х5, х6, х7. Модель примет вид:


Z= 34x1+32x2+28x3+36x4 → max

2х1+4х2+5х3+3х4+х5 = 128

3x1+…+4x3+x4+х6 = 130

3х1+5х2+…+2х4+х7 = 142

х1,2,3,4,5,6,7  ≥ 0

х1,2,3,4,5,6,7 - ?

 

 

 

 

 

 

 

 

 

 

 

 

 

Эта задача решается методом симплекс-таблицы

хб

 h

   x1     x2    x3    x4     x5       x6      x7 

Примечание

x5

x6

x7

128

130

142

   2       4       5       3       1         0        0

   3       0       4       1       0         1        0

   3       5       0       2       0         0        1

х4 - в базис

min(128/3, 130/1, 142/2), min 128/3

 Z

0

-34     -32    -28     -36    0         0        0

x5 – из базиса

x4

x6

x7

128/3

262/3

170/3

2/3    4/3     5/3     1     1/3        0        0

7/3   -4/3     7/3     0    -1/3        1        0

5/3    7/3   -10/3    0    -2/3        0        1

х1 – в базис

min(128/3:2/3,262/3:7/3,170/3:5/3) min 34(170/3:5/3)

 Z

1536

-10     16     32       0     12         0         0

x7 – из базиса

x4

x6

x1

20

8

34

  0      2/5      3       1     3/5        0     -2/5

  0    -23/5     7       0     3/5        1     -7/5

  1      7/5     -2       0    -2/5        0      3/5

 

Z

1876

  0     30       12      0        8        0         6

 

 

Оптимальный план найдет, т.к. все числа в нижней строке не отрицательны.

Оптимальная производственная программа

х1* = 34, х2* = 0, х3* = 0, х4* = 20

Максимальная прибыль

Z= 1876

Остатки ресурсов х5*=0, х6*=8, х7*=0

Узкие места – ресурс I и ресурс II

 

 

 

 

 

 

Проверка

h=Q-1В


             3/5  0  -2/5       128

Q-1В =  3/5   1  -7/5   *  130

           -2/5   0   3/5       142

 

3/5*128+0*130+(-2/5)*142=20

3/5*128+1*130+(-7/5)*142=8

-2/5*128+0*130+3/5*142=34

Проверка выполнена успешно.

 

Графическое решение 

Продукция х2, х3 не производится по оптимальному плану, вычеркнем из таблицы соответствующие два столбца:

 

34  32  28  36


2    4    5    3  128

3    0    4    1  130

3    5    0    2   142

 

Модель примет вид:

Z= 34x1+36x4 → max

2х1+3х4 ≤ 128


3x1+x4 ≤ 130

3х1+2х4 ≤ 142

х1,4  ≥ 0

х1,4 - ?

 

 

 

1)2х1+3х4=128

х1=0       х4=42 2/3

х1=64     х4=0

 

2) 3х1+х4=130

х1=0             х4=130

х1=43 1/3     х4=0

 

3) 3х1+2х4=142

х1=0       х4=71

х1=47 1/3     х4=0

 

 

 

 

 

 

 

 

График 1

 

 

 

 

 

 

Точка В – крайняя (образована прямыми 1 и 3)


  1. 2х1+3х4=128 │*3
  2. 3х1+2х4=142 │*2

6х1+9х4=384


6х1+4х4=284


                 5х4=100

                  х4=20

         2х1+3*20=128

          х1=34

    z=34*34+36*20=1876

Ответ:  х1*=34, х4*=20, z=1876

 

 

 

 

 

 

 

 

№2 Двойственная задача и задача о расшивке «узких мест»

 

Исходные данные

34  32  28  36

2    4    5    3  128

3    0    4    1  130

3    5    0    2  142

 

  1. Задача двойственная задаче №1 имеет вид:

2y1+3y2+3y3 ≥ 34


4y1+…+5y3 ≥ 32

5y1+4y2+… ≥ 28

3y1+y2+2y3 ≥ 36

 

При этом

f=128y1+130y2+142y3 при условии что

y1,2,3 ≥ 0

y1,2,3  - ?

 

Из второй теоремы двойственности следует, что


х1(2y1+3y2+3y3 - 34)=0        y1(2x1+4x2+5x3+3x4-128)=0

х2(4y1+…+5y3 – 32)=0         y2(3x1+…+4x3+x4-130)=0

х3(5y1+4y2+… - 28)=0          y3(3x1+5x2+…+2x4-142)=0

х4(3y1+y2+2y3 – 36)=0

 

Из первой задачи известно, что х1>0 и х2>0, тогда

2y1+3y2+3y3 - 34=0

3y1+y2+2y3 – 36=0

 

Также известно, что ресурс II избыточен, тогда y2=0. Получаем систему:

2y1+3y3 - 34=0


3y1+2y3 – 36=0

 

2y1+3y3 - 34=0│*3


3y1+2y3 – 36=0│*2

6y1+9y3 - 102=0


6y1+4y3 – 72=0


       5y3 – 30=0

        y3=6

2y1+3*6 - 34=0

y1=8

Двойственные оценки ресурсов

y1*=8   y2*=0   y3*=6

 

  1. Задача о расшивке «узких мест»

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

Задача состоит в том, чтобы найти вектор Т максимизирующий прирост прибыли

W=8t1+6t3

Вектор Т (t1,0,t3), t2=0 т.к. y2=0


20          3/5  0  -2/5            t1          0

8       *    3/5  1  -7/5     *      0     *    0

34         -2/5  0   3/5            t3          0

 

При условии что можно получить только 1/3 объема ресурса каждого вида:

 

t1             128


0    ≤ 1/3  130

t3             142  , причем t1 ≥ 0, t3 ≥ 0

 

 

 

-3/5t1+2/5t3 ≤ 20


-3/5t1+7/5t3 ≤ 8

2/5t1-3/5t3 ≤ 34

t1 ≤ 128/3   t3 ≤ 142/3

 

Задача решается графически

1) -3/5t1+2/5t3 = 20

t1=0     t3=50

t1= -33 1/3     t3=0

 

2) -3/5t1+7/5t3 = 8

t1=0     t3=5 5/7

t1= -13 1/3     t3=0

 

3) 2/5t1-3/5t3 = 34

t1=0     t3= -56 2/3

t1= 85     t3=0

 

График 2

 

 

Точка В – крайняя

t1=128/3=42 2/3


 -3/5*128/3+7/5t3 = 8

t3=24

 

 

Программа расшивки имеет вид:

t1=42 2/3; t2=0; t3 = 24

Прирост прибыли W=8*128/3+6*24=485 1/3

 

 

 

 

 

 

Сводка результатов

cj

34

32

28

36

bi

x4+i

yi

ti

 

2

4

5

3

128

0

8

42 2/3

aij

3

0

4

1

130

8

0

0

 

3

5

0

2

142

0

6

24

xj

34

0

0

20

1876

   

485 1/3

Dj

0

30

12

0

       

 

 

 

№4 Задача распределения капитальных вложений

 

Производственное объединение состоит из 4-х предприятий (n=4), общая сумма капитальных вложений равно 700 тыс. руб. (b=700), выделяемые предприятиям суммы кратны 100 тыс. руб. Значение функции fj(xj) приведены в таблице 1.

Табл. 1.

хj

0

100

200

300

400

500

600

700

f1(xj)

0

12

20

26

37

41

44

45

f2(xj)

0

16

27

37

44

48

50

56

f3(xj)

0

10

16

21

24

27

29

30

f4(xj)

0

11

19

25

29

32

33

33   


 

 

 

 

 

 

 

 

 

 

 

 

Таб. 2

            x - x2

0

100

200

300

400

500

600

700

x2

          F1(x-x2)

F2(x2)

0

12

20

26

37

41

44

45

0

0

0

12

20

26

37

41

44

45

100

16

16*

28*

36

42

53

57

60

 

200

27

27

39*

47

53

64

68

   

300

37

37

49*

57*

63

74

     

400

44

44

56

64*

70*

       

500

48

48

60

68

         

600

50

50

62

           

700

56

56

             

 

 

Табл. 3.

x

0

100

200

300

400

500

600

700

F2(x)

0

16

28

39

49

57

64

70

x2(x)

0

100

100

200

300

300

400

400


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Табл. 4

                x - x3

0

100

200

300

400

500

600

700

х3

          F2(x-x3)

F3(x3)

0

16

28

39

49

57

64

70

0

0

0

16*

28*

39*

49

57

64

70

100

10

10

26

38

49*

59*

67*

74*

 

200

16

16

32

44

55

65

73

   

300

21

21

37

49

60

70

     

400

24

24

40

52

63

       

500

27

27

43

55

         

600

29

29

45

           

700

30

30

             

Информация о работе Контрольная работа по предмету "Прикладная математика"