Реферат: Расчётно-графическое задание
Название: Расчётно-графическое задание Раздел: Рефераты по информатике Тип: реферат | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Цель и назначение работы Целью выполнения расчетно-графической работы является закрепление знаний, умения и навыков, необходимых для математического моделирования социально-экономических процессов. А также, приобретение навыков работы с программными пакетами. Задание на выполнение РГР Задание №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 – план выпуска продукции вида Р2 ; Х3 – план выпуска продукции вида Р3 ; Х4 – план выпуска продукции вида Р4 . Приведем задачу к каноническому виду: Решаем задачу с помощью симплекс –таблицы. Таблица 1
Таблица 2
Таблица 3
Таблица 4
Отрицательных оценок в оценочной строке нет; решение оптимально. Оптимальный опорный план: Хопт =(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=
Заключительная симплекс-таблиц Составим матрицу 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 раз выехать. Составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.
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 65 min 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 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 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 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) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения. Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.
Составляем экономико-математическую модель задачи 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 По исходным данным составляем таблицу
Преобразуем составляемую таблицу 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 часов. Альтернативных решений нет, решение единственное. |