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

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

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

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

Задание №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
А1 А2 А3 А4 А5 А6 А7 А8 А9
А5 500 7 6 5 21 1
А6 1402 9 13 17 16 1
А7 203 5 7 15 19 1
А8 600 17 5 24 23 1
А9 150 4 7 9 2 1
∆j F=0 -124 -125 -195 -274

Таблица 2

Базис Сб Опорное решение С1 С2 С3 С4 С5 С6 С7 С8 С9
124 125 195 274
А1 А2 А3 А4 А5 А6 А7 А8 А9
А5 275,6 1,5 -1,7 -11,6 1 -1,1
А6 1231,1 4,8 7,1 4,4 1 -0,8
А4 274 10,7 0,3 0,4 0,8 1 0,05
А8 354,3 10,9 -3,4 5,8 -1,2 1
А9 128,6 3,4 6,2 7,4 -0,1 1
∆j F=2927,47 -51,9 -24,1 21,3 14,4

Таблица 3

Базис Сб Опорное решение С1 С2 С3 С4 С5 С6 С7 С8 С9
124 125 195 274
А1 А2 А3 А4 А5 А6 А7 А8 А9
А5 227,9 -1,3 -12,4 1 -0,9 -0,1
А6 1076,1 8,6 1,8 1 -0,3 -0,4
А4 274 2,2 0,5 0,6 1 0,08 -0,02
А1 124 32,4 1 -0,3 0,5 -0,11 0,09
А9 16,2 7,4 5,6 0,28 -0,03 1
∆j F=4606,81 -40,5 49 8,7 4,7

Таблица 4

Базис Сб Опорное решение С1 С2 С3 С4 С5 С6 С7 С8 С9
124 125 195 274
А1 А2 А3 А4 А5 А6 А7 А8 А9
А5 230,7 -11,4 1 -0,89 -0,19 0,17
А6 1057,07 -4,71 1 -0,64 -0,07 -1,17
А4 274 1,173 0,307 1 0,065 -0,005 -0,061
А1 124 33,06 1 0,77 -0,1 0,08 0,04
А2 125 2,2 1 0,76 0,038 -0,04 0,14
∆j F=4696,05 79,64 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
А1 А2 А3 А4 А5 А6 А7 А8 А9
А4 -600 2,99 0,19 0,07 1 -0,08 0,04 0,005
А5 -150 5,5 -0,17 1,17 1 -0,04 -0,13 -0,06
А3 -203 10,2 0,9 0,6 1 0,01 -0,04 -0,06
А8 79,6 11,4 4,7 -0,8 -0,76 1 -0,3
∆j F=-4696,05 230,07 1057 33,6 2,2 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. Значит Db3 =10, Db4 =10 и Db5 =10. Остальные Db1 =Db2 =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 = 1523x 12 + 152321 + 863x 13 + 863x 31 + 1899x 14 + 1899x 41 + 1809x 15 + 1809x 51 + 1578x 16 + 1578x 61 + 2329x 32 + 2329x 23 + 1622x 24 +1622x 42 + 3275x 25 + 3275x 52 + 3044x 26 + 3044x 62 + 1801x 34 + 1801x 43 + 1208x 35 + 1208x 53 + 977x 36 + 977x 63 + 2023x 45 + 2023x 54 + 1792x 46 + 1792x 64 + 247x 56 + 247x 65min

x 12 + x 13 + x 14 + x 15 + x 16 = 1

x 21 + x 23 + x 24 + x 25 + x 26 = 1

x 31 + x 32 + x 34 + x 35 + x 36 = 1

x 41 + x 42 + x 43 + x 45 + x 46 = 1

x 51 + x 52 + x 53 + x 54 + x 56 = 1

x 61 + x 62 + x 63 + x 64 + x 65 = 1

x 21 + x 31 + x 41 + x 51 + x 61 = 1

x 12 + x 32 + x 42 + x 52 + x 62 = 1

x 13 + x 23 + x 43 + x 53 + x 63 = 1

x 14 + x 24 + x 34 + x 54 + x 64 = 1

x 15 + x 25 + x 35 + x 45 + x 65 = 1

x 16 + x 26 + x 36 + x 46 + x 56 = 1

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

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

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

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

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

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

Q13 = 660+179=839;

Q21 = 0;

Q24 = 839;

Q31 = 114;

Q42 =660+170=830;

Q56 = 170+961=1131;

Q65 = 345+730=1075

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

w= h1 +Q42= 5464 + 830 = 6294

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

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

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

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

Q13 = 715+730=1445;

Q21 = 0;

Q24 = 839;

Q31 = 114;

Q56 = 114+961=1075;

Q65 = 345+730=1075

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

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

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

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

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

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

Q13 = 212+730=942;

Q34 = 212;

Q36 = 0;

Q56 = 952;

Q65 = 231+721=952

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

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

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

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

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

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

Q34 = 721;

Q36 = 0;

Q56 = 952;

Q65 = 231

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

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

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

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

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

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

5464 6303 6303 7024

G04,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

Q13 = 660+9=669;

Q21 = 0;

Q24 = 839;

Q31 = 114;

Q46 =9;

Q56 = 961;

Q65 = 231+730=961

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

w= h6 +Q56= 5634 + 961 = 6595

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

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

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

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

Q12 = 806;

Q13 = 0;

Q21 = 0;

Q24 = 839;

Q31 = 345;

Q43 = 98;

Q65 = 730+345=1075

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

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

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

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

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

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

Q12 = 806;

Q13 = 0;

Q31 = 98+345=443;

Q43 = 98;

Q65 = 730+222=952

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

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

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

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

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

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

Q31 = 98+345=443;

Q43 = 730+98=828;

Q65 = 730+222=952

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

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

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

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

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

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

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

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

5634 5634 6303 6303 6303 6303

G05,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 = 10x 11 + 2x 12 + 3x 13 + 7x 14 + 7x 15 + 9x 16 + 10x 17 + 10x 18 + 10,5x 19 + 12x 110 + 14,5x 111 + 7x 112 + 12x 21 + x 22 + 5x 23 + 6,5x 24 + 8x 25 + 10,5x 26 + 8x 27 + 9x 28 + 12x 29 + 11x 210 + 15x 211 + 7,5x 212 + 11x 31 + x 32 + 3,5x 33 + 6,5x 34 + 8x 3,5 + 10,5x 36 + 8x 37 + 9x 38 + 12x 39 + 11x 310 + 15x 311 +17,5x 312 + 11x 41 + 2x 42 + 4x 43 + 6,5x 44 + 8x 45 + 11x 46 + 8x 47 + 9,5x 48 + 12x 49 + 12x 410 + 15,5x 411 + 7,5x 412 + 10x 51 + 2,5x 52 + 4x 53 + 5x 54 + 8x 55 + 11,5x 56 + 8,5x 57 + 8x 58 + 11x 59 + 12x 510 + 15,5x 511 + 6x 512 + 10x 61 + 2,5x 62 + 4,5x 63 + 5x 64 + 7,5x 65 + 10,5x 66 + 8,5x 67 + 8x 68 + 11x 69 + 12x 610 + 15x 611 + 6x 612 + 9,5x 71 + x 72 + 4x 73 + 5,5x 74 + 7,5x 75 + 10,5x 76 +8,5x 77 + 9x 78 + 11x 79 + 12x 710 + 15,5x 711 + 6x 712 + 9,5x 81 + 1x 82 + 3,5x 83 + 6,5x 84 + 7x 85 + 10,5x 86 + 10x 87 + 10,5x 88 + 12x 89 + 10x 810 + 15,5x 811 + 6x 812 + 9,5x 91 + 3x 92 + 3x 93 + 3,5x 94 + 6,5x 95 + 7x 96 + 11x 97 + 10,5x 98 + 10x 99 +12x 910 +15x 911 + 7x 912 + 8x 101 + 3x 102 + 3x 103 + 6,5x 104 + 7x 105 + 11x 106 + 10,5x 107 + 10x 108 + 9,5x 109 + 12x 1010 + 15,5x 1011 + 6,5x 1012 + 8x 111 + 3x 112 + 3x 113 + 6,5x 114 + 7,5x 115 + 10x 116 + 11x 117 + 10,5x 118 + 9,5x 119 + 12x 1110 + 15,5x 1111 + 6,5x 1112 + 8x 121 + 3x 122 + 3x 123 + 6,5x 124 + 7,5x 125 + 9x 126 + 11x 127 + 10,5x 128 + 9,5x 129 + 12x 1210 + 15x 1211 + 6,5x 1212 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 часов.

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

еще рефераты
Еще работы по информатике