Расчётно-графическое задание

Цель и назначение работы

Целью выполнения расчетно-графической работы является закрепление знаний, умения и навыков, необходимых для математического моделирования социально-экономических процессов. А также, приобретение навыков работы с программными пакетами.



Задание на выполнение РГР

Задание №1



На фабрике с помощью 5 видов красителей (А1-А5) создается 4 разновидности рисунков для тканей (Р1-Р4). При известной отпускной стоимости 1 м ткани каждого рисунка (руб.), известном расходе каждого красителя на окраску 1 м ткани (г) и известном запасе каждого красителя (кг):

2.1.1 определить план выпуска ткани каждого рисунка, обеспечивающий максимальную прибыль от реализации тканей;

2.1.2 составить двойственную задачу и найти ее решение;

2.1.3 определить теневые цены на каждый краситель; указать дефицитные и недефицитные красители;

2.1.4. указать на сколько недоиспользуются недефицитные красители;

2.1.5 показать прибыль, план выпуска тканей каждого рисунка и недоиспользование недефицитных красителей при увеличении запасов дефицитных красителей на 1 ед.;

2.1.6 показать допустимые пределы изменения запасов красителей;

2.1.7 показать допустимые пределы изменения цен на выпускаемые виды тканей. 

2.1.8 оценить целесообразность введения в план производства выпуск ткани с разновидностью рисунка Р5, если нормы затрат красителей на 1 единицу ткани соответственно равны: 6; 2; 1; 4; 4; и доход, ожидаемый от реализации новой ткани равен 5000 руб;

2.1.9 показать, допустимо ли увеличение всех дефицитных красителей одновременно на 10 кг.



	



Номер варианта

Вид красителей

Разновидность рисунка.

Расход красителей на окраску 1 м ткани (г). 

Запасы красителей (кг).





Р1

Р2

Р3

Р4



8

А1

7

6

5

21

500



А2

9

13

17

16

1402



А3

5

7

15

19

203



А4

17

5

24

23

600



А5

4

7

9

2

150



Стоимость одного  метра ткани (руб.)

124

125

195

274



Составляем экономико – математическую модель задачи.

Обозначим:

Х1 – план выпуска продукции вида Р1;

Х2 – план выпуска продукции вида Р2;

Х3 – план выпуска продукции вида Р3;

Х4 – план выпуска продукции вида Р4.

















Приведем задачу к каноническому виду:















Решаем задачу с помощью симплекс –таблицы.

Таблица 1

Базис          

     Сб  

 Опорное решение

С1

С2

С3

С4

С5

С6

С7

С8

С9







124

125

195

274

0

0

0

0

0







А1

А2

А3

А4

А5

А6

А7

А8

А9

А5

0

500

7

6

5

21

1

0

0

0

0

А6

0

1402

9

13

17

16

0

1

0

0

0

А7

0

203

5

7

15

19

0

0

1

0

0

А8

0

600

17

5

24

23

0

0

0

1

0

А9

0

150

4

7

9

2

0

0

0

0

1

  ∆j

       F=0

-124

-125

-195

-274

0

0

0

0

0



Таблица 2

Базис          

     Сб  

 Опорное решение

С1

С2

С3

С4

С5

С6

С7

С8

С9







124

125

195

274

0

0

0

0

0







А1

А2

А3

А4

А5

А6

А7

А8

А9

А5

0

275,6

1,5

-1,7

-11,6

0

1

0

-1,1

0

0

А6

0

1231,1

4,8

7,1

4,4

0

0

1

-0,8

0

0

А4

274

10,7

0,3

0,4

0,8

1

0

0

0,05

0

0

А8

0

354,3

10,9

-3,4

5,8

0

0

0

-1,2

1

0

А9

0

128,6

3,4

6,2

7,4

0

0

0

-0,1

0

1

∆j

F=2927,47

-51,9

-24,1

21,3

0

0

0

14,4

0

0

Таблица 3

Базис          

     Сб  

 Опорное решение

С1

С2

С3

С4

С5

С6

С7

С8

С9







124

125

195

274

0

0

0

0

0







А1

А2

А3

А4

А5

А6

А7

А8

А9

А5

0

227,9

0

-1,3

-12,4

0

1

0

-0,9

-0,1

0

А6

0

1076,1

0

8,6

1,8

0

0

1

-0,3

-0,4

0

А4

274

2,2

0

0,5

0,6

1

0

0

0,08

-0,02

0

А1

124

32,4

1

-0,3

0,5

0

0

0

-0,11

0,09

0

А9

0

16,2

0

7,4

5,6

0

0

0

0,28

-0,03

1

  ∆j

       F=4606,81

0

-40,5

49

0

0

0

8,7

4,7

0

Таблица 4

Базис          

     Сб  

 Опорное решение

С1

С2

С3

С4

С5

С6

С7

С8

С9







124

125

195

274

0

0

0

0

0







А1

А2

А3

А4

А5

А6

А7

А8

А9

А5

0

230,7

0

0

-11,4

0

1

0

-0,89

-0,19

0,17

А6

0

1057,07

0

0

-4,71

0

0

1

-0,64

-0,07

-1,17

А4

274

1,173

0

0

0,307

1

0

0

0,065

-0,005

-0,061

А1

124

33,06

1

0

0,77

0

0

0

-0,1

0,08

0,04

А2

125

2,2

0

1

0,76

0

0

0

0,038

-0,04

0,14

  ∆j

       F=4696,05

0

0

79,64

0

0

0

10,22

2,99

5,5

Отрицательных  оценок  в  оценочной  строке  нет;  решение  оптимально.  Оптимальный  опорный  план:

 

Хопт=(33,06; 2,2; 0; 1,173; 0; 0; 0; 0; 0)Т



Fmax=4696,05 руб.



             Для  получения  максимальной  прибыли  4696,05 руб.  необходимо  выпустить  продукции  вида Р1  33,06 м ткани,  Р2 2,2 м и Р4 1,173 м.

             Продукция  видов  Р3 является   убыточным; его  производство  является  нерентабельным.

составим двойственную задачу.

 - теневая цена ресурса   I

 - теневая цена ресурса II

 - теневая цена ресурса Ш

- теневая цена ресурса IV

 - теневая цена ресурса V

→min







    

≥

Т.к. в прямой задаче все неравенства в системе сильных ограничений вида “≤”, найдем решение двойственной задачи по результатам решения прямой задачи.



=4696,05 руб.

y1=0

y2=0

y3=10,22

y4=2,99

y5=5,5

Дефицитным являются ресурсы III, IV и V.

Недефицитными являются ресурсы I, II.

Недефицитные ресурсы недоиспользуются:

I ресурс на 230,7 кг;

II  ресурс на 1057,07 кг

При увеличении запаса III ресурса на 1 ед. (204 кг) можно получить увеличение прибыли на 10,22 руб. она составит F=4706,27 руб. При этом план выпуска продукции 4 надо увеличить на 0,065 т.е. x4=1,238, продукции 1 надо увеличить на -0,1 т.е. x1=2,1, продукции 2 надо увеличить на 0,038 т.е. x2=33,098. В этом случае недефицитные ресурсы  будут недоиспользоваться:

1 ресурс на 0,89; его недоиспользование составит 231,69 кг;

2 ресурс на 0,64; его недоиспользование составит 1057,71 кг

Покажем допустимые пределы изменения запасов ресурсов.

                          

Составим матрицу Р



 



и вектор столбец



  



Найдем матрицу P







Р-1(b+∆b)= =







Покажем допустимые пределы изменения цен на выпускаемые виды продукции. 

p-1(c+∆c)



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

Приводим задачу к каноническому виду

F*= - 500y1-1402y2-203y3-600y4-150y5+0y6+0y7+0y8+0y9→max

7y1+9y2+5y3+17y4+4y5-y6=124

6y1+13y2+7y3+5y4+7y5-y7=125

5y1+17y2+15y3+24y4+23y5-y8=195

21y1+16y2+19y3+23y4+2y5-y9=274

 i=

	

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

G=0y1+0y2+0y3+0y4+0y5+0y6+0y7+0y8+0y9-y10-y11-y12-y13→min

7y1+9y2+5y3+17y4+4y5-y6+y10=124

6y1+13y2+7y3+5y4+7y5-y7+y11=125

5y1+17y2+15y3+24y4+9y5-y8+y12=195

21y1+16y2+19y3+23y4+2y5-y9+y13=274

 

  i=



Базис

Сб

Опорное решение

С1

С2

С3

С4

С5

С6

С7

С8

С9







500

1402

203

600

150

0

0

0

0







А1

А2

А3

А4

А5

А6

А7

А8

А9

А4

-600

2,99

0,19

0,07

0

1

0

-0,08

0,04

0

0,005

А5

-150

5,5

-0,17

1,17

0

0

1

-0,04

-0,13

0

-0,06

А3

-203

10,2

0,9

0,6

1

0

0

0,01

-0,04

0

-0,06

А8

0

79,6

11,4

4,7

0

0

0

-0,8

-0,76

1

-0,3

∆j

F=-4696,05

230,07

1057

0

0

0

33,6

2,2

0

1,17

Заключительная симплекс-таблиц



Составим матрицу P и вектор-столбец 



P = ;



 = 



Найдём матрицу 



 = 



∆c)= *=

Покажем целесообразность введения в план производства выпуск ткани с разновидностью рисунка Р5:

∆p5=6*0+2*0+1*10,22+4*2,99+4*5,5-5000=-4955,82

Т.к. ∆р5<0, то есть смысл ввести в план производства выпуск ткани с разновидностью рисунка р5.

Определяем, допустимо ли одновременное увеличение запасов дефицитных красителей на 10 кг каждого. Пределы изменения запасов красителей определяются из условия



Дефицитным является краситель А3, А4 и А5. Значит b3=10,  b4=10 и b5=10. Остальные b1=b2 =0, тогда



Увеличение дефицитных красителей не приводит к изменению плана производства тканей.









Задание №2



Коммивояжер выезжает из одного из городов (все равно какого) и должен объехать все города, преодолев минимальное расстояние. При этом в каждый город он может только 1 раз въехать и только 1 раз выехать. Составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.





Дон.

Ерев.

Жит.

Казань

Калин.

Каун.

Донецк



1523

863

1899

1809

1578

Ереван

1523



2329

1622

3275

3044

Житомир

863

2329



1801

1208

977

Казань

1899

1622

1801



2023

1792

Калининград

1809

3275

1208

2023



247

Каунас

1578

3044

977

1792

247





F= 1523x12 + 152321 + 863x13 + 863x31 + 1899x14 + 1899x41 + 1809x15 + 1809x51 + 1578x16 + 1578x61 + 2329x32 + 2329x23 + 1622x24 +1622x42 + 3275x25 + 3275x52 + 3044x26 + 3044x62 + 1801x34 + 1801x43 + 1208x35 + 1208x53 + 977x36 + 977x63 + 2023x45 + 2023x54 + 1792x46 + 1792x64 + 247x56 + 247x65 min



x12 + x13 + x14 + x15 + x16 = 1

x21 + x23 + x24 + x25 + x26 = 1

x31 + x32 + x34 + x35 + x36 = 1

x41 + x42 + x43 + x45 + x46 = 1

x51 + x52 + x53 + x54 + x56 = 1

x61 + x62 + x63 + x64 + x65 = 1



x21 + x31 + x41 + x51 + x61 = 1

x12 + x32 + x42 + x52 + x62 = 1

x13 + x23 + x43 + x53 + x63 = 1

x14 + x24 + x34 + x54 + x64 = 1

x15 + x25 + x35 + x45 + x65 = 1

x16 + x26 + x36 + x46 + x56 = 1





Решение задачи методом ветвей и границ.

  Преобразуем матрицу s















Определяем сумму приводимых элементов

h1=863+1523+863+1622+247+247+99=5464

Определяем претендентов для ветвления в множестве Y

Претендентами на ветвление могут быть S13, S21, S24, S31, S42, S56, S65

13 = 660+179=839;

21 = 0;

24 = 839;

31 = 114;

42 =660+170=830;

56 = 170+961=1131;

65 = 345+730=1075

Максимальную оценку имеет маршрут: 42=830 

w  = h1+42= 5464 + 830 = 6294

Преобразуем матрицу:



Определяем h2= 0;

Оценка по  {4,2}=5464       

Определяем пару для ветвления

13 = 715+730=1445;

21 = 0;

24 = 839;

31 = 114;

56 = 114+961=1075;

65 = 345+730=1075

Подходящую оценку имеет маршрут: 21=0

w  = w(4;2)+ 21= 6294

Преобразуем матрицу:



Определяем h3= 114+725=839;

Оценка по  {2,1}=5464+839=6303 

Определяем пару для ветвления

13 = 212+730=942;

34 = 212;

36 = 0;

56 = 952;

65 = 231+721=952

Подходящую оценку имеет маршрут: 13=942

w  = w(2;1)+ 13= 6294+942=7236

Преобразуем матрицу:





Определяем h4= 0;

Оценка по {1,3}= 6303

Определяем пару для ветвления

34 = 721;

36 = 0;

56 = 952;

65 = 231

Подходящую оценку имеет маршрут: 36=0

w  = w(1;3)+ 36= 7236

Преобразуем матрицу:

  Матрица приведена 





Определяем h5=952;

Оценка w{3,6}=6303+721=7024







               5464        6303       6303       7024            



G0           4,2		2,1	      1,3	 3,6			





    6294       6294        7236       7236           



4,2	     2,1 	 1,3	      3,6 		      





Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград.

Т.к. оценка последнего маршрута больше оценки одного из тупиковых ветвей, а именно , то необходимо доисследовать процесс ветвления этой ветви.

Возвращаемся к исходной матрице расстояний и полагаем в ней 









Определяем сумму приводимых элементов

h6=5634

Определяем претендентов для ветвления в множестве Y

Претендентами на ветвление могут быть S13, S21, S24, S31, S46, S56, S65

13 = 660+9=669;

21 = 0;

24 = 839;

31 = 114;

46 =9;

56 = 961;

65 = 231+730=961

Максимальную оценку имеет маршрут: 56=961 

w  = h6+56= 5634 + 961 = 6595

Преобразуем матрицу:





Определяем h7= 669;

Оценка по  {5,6}=5634+669=6303    

Определяем пару для ветвления

12 = 806;

13 = 0;

21 = 0;

24 = 839;

31 = 345;

43 = 98;

65 = 730+345=1075

Подходящую оценку имеет маршрут: 24=839

w  = w(5;6)+ 24= 6595+839=7434

Преобразуем матрицу:



Определяем h8= 0;

Оценка по  {2,4}=6303

Определяем пару для ветвления

12 = 806;

13 = 0;

31 = 98+345=443;

43 = 98;

65 = 730+222=952

Подходящую оценку имеет маршрут: 12=806

w  = w(2;4)+ 12= 7434+806=8240

Преобразуем матрицу:





Определяем h9= 0;

Оценка по {1,2}= 6303

Определяем пару для ветвления

31 = 98+345=443;

43 = 730+98=828;

65 = 730+222=952

Подходящую оценку имеет маршрут: 43=828

w  = w(4;3)+ 12= 8240+828=9068

Преобразуем матрицу:

  Матрица приведена 

Определяем h10=0;

Оценка w{4,3}=6303

Т.к. получена матрица 2x2 и оценка последнего маршрута не больше всех тупиковых ветвей, то решение оптимально. Маршрутами для завершения могут быть пары (3,1), (6,5).

Составим геометрическую интерпретацию найденного маршрута

            

5634	      5634      6303         6303       6303        6303 



G0           5,6		 2,4	      1,2	 4,3	      3,1	

	                                                                             6,5



    6595       7434       8240        9068        	           

							10744

5,6	     2,4 	 1,2	      4,3 	 3,1	10744      

	                                                              6,5



Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград; x42=1, x21=1, x13=1, x36=1, x65=1, F=5232 км.













Задание №3



На предприятии необходимо выполнить последовательно 12 видов работ (R1÷R12). 12 сотрудников предприятия (S1÷S12) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения.

Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.

№ варианта

Сотрудник



Виды работ

Время, затрачиваемое каждым сотрудником на выполнение каждого вида работ





R1

R2

R3

R4

R5

R6

R7

R8

R9

R10

R11

R12

8

   S1

10

2

3

7

7

9

10

10

10,5

12

14,5

7



S2

12

1

5

6,5

7,5

10

8

9

10

11

14

7,5



S3

11

1

3,5

6,5

8

10,5

8

9

12

11

15

7,5



S4

11

2

4

6,5

8

11

8

9,5

12

12

15,5

7,5



S5

10

2,5

4

5

8

11,5

8,5

8

11

12

15,5

6



S6

10

2,5

4,5

5

7,5

10,5

8,5

8

11

12

15

6



S7

9,5

1

4

5,5

7,5

10,5

8,5

9

11

12

15,5

6



S8

9,5

1

3,5

6,5

7

10,5

10

10,5

12

10

15,5

6



S9

9,8

3

3,5

6,5

7

11

10,5

10

12

10

15

7



S10

8

3

3

6,5

7

11

10,5

10

9,5

12

15

6,5



S11

8

3

3

6,5

7,5

10

11

10,5

9,5

12

15,5

6,5



S12

8

3

3

6,5

7,5

9

11

10,5

9,5

12

15

6,5



Составляем экономико-математическую модель задачи

F = 10x11 + 2x12 + 3x13 + 7x14 + 7x15 + 9x16 + 10x17 + 10x18 + 10,5x19 + 12x110 + 14,5x111 + 7x112 + 12x21 + x22 + 5x23 + 6,5x24 + 8x25 + 10,5x26 + 8x27 + 9x28 + 12x29 + 11x210 + 15x211 + 7,5x212 + 11x31 + x32 + 3,5x33 + 6,5x34 + 8x3,5 + 10,5x36 + 8x37 + 9x38 + 12x39 + 11x310 + 15x311 +17,5x312 + 11x41 + 2x42 + 4x43 + 6,5x44 + 8x45 + 11x46 + 8x47 + 9,5x48 + 12x49 + 12x410 + 15,5x411 + 7,5x412 + 10x51 + 2,5x52 + 4x53 + 5x54 + 8x55 + 11,5x56 + 8,5x57 + 8x58 + 11x59 + 12x510 + 15,5x511 + 6x512 + 10x61 + 2,5x62 + 4,5x63 + 5x64 + 7,5x65 + 10,5x66 + 8,5x67 + 8x68 + 11x69 + 12x610 + 15x611 + 6x612 + 9,5x71 + x72 + 4x73 + 5,5x74 + 7,5x75 + 10,5x76 +8,5x77 + 9x78 + 11x79 + 12x710 + 15,5x711 + 6x712 + 9,5x81 + 1x82 + 3,5x83 + 6,5x84 + 7x85 + 10,5x86 + 10x87 + 10,5x88 + 12x89 + 10x810 + 15,5x811 + 6x812 + 9,5x91 + 3x92 + 3x93 + 3,5x94 + 6,5x95 + 7x96 + 11x97 + 10,5x98 + 10x99 +12x910 +15x911 + 7x912 + 8x101 + 3x102 + 3x103 + 6,5x104 + 7x105 + 11x106 + 10,5x107 + 10x108 + 9,5x109 + 12x1010 + 15,5x1011 + 6,5x1012 + 8x111 + 3x112 + 3x113 + 6,5x114 + 7,5x115 + 10x116 + 11x117 + 10,5x118 + 9,5x119 + 12x1110 + 15,5x1111 + 6,5x1112 + 8x121 + 3x122 + 3x123 + 6,5x124 + 7,5x125 + 9x126 + 11x127 + 10,5x128 + 9,5x129 + 12x1210 + 15x1211 + 6,5x1212 min

























По исходным данным составляем таблицу



R1

R2

R3

R4

R5

R6

R7

R8

R9

R10

R11

R12

S1

10

2

3

7

7

9

10

10

10,5

12

14,5

7

S2

12

1

5

6,5

7,5

10

8

9

10

11

14

7,5

S3

11

1

3,5

6,5

8

10,5

8

9

12

11

15

7,5

S4

11

2

4

6,5

8

11

8

9,5

12

12

15,5

7,5

S5

10

2,5

4

5

8

11,5

8,5

8

11

12

15,5

6

S6

10

2,5

4,5

5

7,5

10,5

8,5

8

11

12

15

6

S7

9,5

1

4

5,5

7,5

10,5

8,5

9

11

12

15,5

6

S8

9,5

1

3,5

6,5

7

10,5

10

10,5

12

10

15,5

6

S9

9,8

3

3,5

6,5

7

11

10,5

10

12

10

15

7

S10

8

3

3

6,5

7

11

10,5

10

9,5

12

15

6,5

S11

8

3

3

6,5

7,5

10

11

10,5

9,5

12

15,5

6,5

S12

8

3

3

6,5

7,5

9

11

10,5

9,5

12

15

6,5



 Преобразуем составляемую таблицу

 1     2     3       4      5      6       7      8       9     10     11     12

	

	      

	

	

	

	

	

	

	

	

	

	

	

	

	       1     2     3      4       5      6      7      8       9     10     11    12

	

Произведем назначение каждого сотрудника на один из видов работ:

S1→R2; S2→?; S3→?; S4→R7; S5→R4; S6→R8; S7→?; S8→?; S9→R5; S10→R1; S11→R3; S12→R9

	 Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

	             1       2      3       4      5       6       7      8       9     10     11    12

	       

Произведем назначение каждого сотрудника на один из видов работ: 

S1→R11; S2→R2; S3→?; S4→R7; S5→R4; S6→R8; S7→?; S8→?; S9→R5; S10→R1; S11→R3; S12→R9

	    Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

	

	      

	

	

	      1       2      3      4      5      6      7      8       9      10     11     12

	 

Произведем назначение каждого сотрудника на один из видов работ: 

S1→R11; S2→R2; S3→?; S4→R7; S5→R4; S6→R8; S7→?; S8→?; S9→R5; S10→R1; S11→R3; S12→R9

	    Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

	       1      2       3      4       5      6       7      8      9     10     11    12



Произведем назначение каждого сотрудника на один из видов работ: 

S1→R6; S2→R11; S3→R2; S4→R7; S5→R4; S6→R8; S7→R12; S8→?; S9→R10; S10→R5; S11→R3; S12→R1

	    Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5





	       1     2     3      4       5      6      7      8      9     10     11     12



Произведем назначение каждого сотрудника на один из видов работ: 

S1→R6; S2→R11; S3→R2; S4→R7; S5→R4; S6→R8; S7→R12; S8→R10; S9→R5; S10→R3; S11→R1; S12→R9

	    Решение оптимально; можем назначить  всех сотрудников на выполнение работ.

И окончательно:

 1   2    3    4   5    6    7    8   9   10 11 12



При этом время, затрачиваемое на  выполнение всех работ, составит:

88,5 часов.

Альтернативных решений нет, решение единственное.