模型决策法

无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台第六章模型决策法•线性规划等•时序与路径规划•分派问题•最短路问题•最大流问题无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台模型决策法优化模型max(min)目标函数s.t.约束条件无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台线性规划模型的建立实例1两种产品的生产。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，资源限制及市场价格如下表：ⅠⅡ资源限制设备11300台时原材料A21400千克原材料B01250千克市场价格50100•问题：如何安排生产，才能使工厂获利最多？无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策分析：（1）设x1—生产产品Ⅰ的数量；x2—生产产品Ⅱ的数量。（2）目标函数：MAX50x1+100x2（3）约束条件：subjectto(s.t.):x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策线性规划模型：max50x1+100x2s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策线性规划模型的一般形式maxc1x1+c2x2+…+cnxns.t.a11x1+…+a1nxn≤(≥,=)b1a21x1+…+a2nxn≤(≥,=)b2…am1x1+…+amnxn≤(≥,=)bmxij≥0i=1,…,n,j=1,…,m无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策线性规划应用领域：†合理利用板、线材问题；†配料问题；†投资问题；†生产计划问题、劳动力安排问题；†运输问题、电子商务配送问题；†企业决策问题；企业或商业竞争对策问题等。无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策一般线性规划建模过程Step1.理解及分析实际问题，资源状况，解决问题实现的目标；Step2.确定决策变量（x1,…，xn）—解决问题的具体方案（量化方案）；Step3.确定目标函数及约束条件；Step4.应用线性规划软件求解；Step5.检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转Step1或Step2修改模型。无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策案例2：（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工，亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策工时与成本甲乙丙总工时每件铸造工时（小时）51078000每件机加工工时（小时）64812000每件装配工时（小时）32210000自产铸件每件成本（元）354外协铸件每件成本（元）56-机加工每件成本（元）213装配每件成本（元）322每件产品售价（元）231816问题：如何安排生产计划，使公司获利最大？无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策分析：设xi—公司加工甲、乙、丙三种产品数量，i=1,2,3。x4、x5—由外协铸造后再由本公司机加工和装配的甲、乙两种产品数量；目标函数：每件产品利润分别是：每件x1产品利润:23-（3+2+3）=15元每件x2产品利润:18-（5+1+2）=10元每件x3产品利润:16-（4+3+2）=7元每件x4产品利润:23-（5+2+3）=13元每件x5产品利润:18-（6+1+2）=9元目标函数为：max15x1+10x2+7x3+13x4+9x5无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000xi≥0i=1,…,5无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策图解法:Step1.确定可行域D={x|x满足上述约束条件}如下图2-1：Step2.确定直线50x1+100x2=0如下图2-2：Step3.向上移动直线50x1+100x2=0如图2-2，z=50x1+100x2的值不断地增加，达到B点时，达到最大；Step4.最优解为B=(50,250),z最大=27500。无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策0100200300300200100D图2-1无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台规划与决策0100200300300200100DB(50,250)Z=50x1+100x2图2-2无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序与路径规划•讨论各种时序规划问题•介绍时序规划原则•分派问题•运输问题•网络的最短路径•网络的最大流无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题ABEFDC机器机器DEFCAB等待处理的一批工作按最优次序排队一台机器工作的时序规划无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题原则：(1)最紧迫的优先实例1：6种部件作为一批等待一台机器加工。每一部件的平均周需求量、当前的存货水平以及加工一批所需时间如下表，你将如何安排各种部件的生产次序？部件ABCDEF平均需求量104263473当前存货量722148922823加工时间2.01.50.50.51.01.5无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题1最紧迫的优先23数据4项目ABCDEF5当前存货7221489228236平均需求1042634737存货用完的时间7,205,251,852,714,007,6789经整理的数据10存货用完的时间1,852,714,005,257,207,6711项目CDEBAF12当前存货48922821722313平均需求2634741031415生产时间0,50,51,01,52,01,516开始生产时间0,00,51,02,03,55,517完成生产时间0,51,02,03,55,57,018容余时间1,41,72,01,81,70,7无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题23数据4项目ABCDEF5当前存货7221489228236平均需求1042634737存货用完的时间7,205,251,852,714,007,6789经整理的数据10存货用完的时间1,852,714,005,257,207,6711项目CDEBAF12当前存货48922821722313平均需求2634741031415生产时间0,50,51,01,52,01,516开始生产时间0,00,51,02,03,55,517完成生产时间0,51,02,03,55,57,018容余时间1,351,7121,751,70,67无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题ABCDEFGHI1加工时间最短者优先23数据4工作ABCDEFGH5加工时间2538472367整理后数据8工作AGCHEBFD9加工时间223345781011开始加工时间0,02,04,07,010,014,019,026,012完成加工时间2,04,07,010,014,019,026,034,0以“加工时间最短者优先”为原则无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题23数据4工作ABCDEFGH5加工时间2538472367整理后数据8工作AGCHEBFD9加工时间223345781011开始加工时间0,02,04,07,010,014,019,026,012完成加工时间2,04,07,010,014,019,026,034,0以“加工时间最短者优先”为原则无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题(3)到期日最近者原则BCDEFGHIABCDEFGH1378301420236GBCAEFDH2781314203036253247830,02,07,010,012,016,023,031,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题(3)到期日最近者原则BCDEFGHIABCDEFGH1378301420236GBCAEFDH2781314203036253247830,02,07,010,012,016,023,031,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0无忧资源：中国最大最全的资源下载网教育新天地：中国最大的学习培训咨询平台时序规划问题(4