运筹学课后习题答案名师优质课赛课一等奖市公开课获奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/10/10,1,3.1,与普通线性规划数学模型相比，运输问题数学模型含有什么特征？,答：与普通线性规划数学模型相比，运输问题数学模型含有以下特征：,1.,运输问题不象普通线性规划问题那样，线性规划问题有可能有没有穷多最优解，运输问题只有有限个最优。,2.,运输问题约束条件系数矩阵元素等于,0,或,1,；且每一列有两个非零元素。,3.,运输问题解个数不可能大于,(m+n-1),个。,3.2,运输问题基可行解应满足什么条件,?,试判断形表,3-26,和表,3-27,中给出调运方案是否作为表上作业法迭代时基可行解,?,为何,?,第1页,销地,产地,B1,B2,B3,B4,产量,A1,A2,A3,0,5,15,15,10,15,25,5,销量,5,15,15,10,/10/10,2,表,3-26,解：表,3-26,产地个数,m=3,，销地个数,n=4,，,m+n-1=3+4-1=6,个，而表,3-26,中非零个数分量为,5,个,6,个，所以表,3-26,不可作为表上作业法时基可行解。,第2页,销地,产地,B1,B2,B3,B4,B5,产量,A1,A2,A3,A4,A5,150,90,200,210,300,250,250,80,50,20,400,500,300,300,100,销量,240,410,550,330,70,/10/10,3,表,3-27,解：表,3-27,产地个数,m=5,，销地个数,n=5,，,m+n-1=5+5-1=9,个，而表,3-27,中非零个数分量为,10,个,9,个，也不可作为表上作业法时基可行解。,第3页,/10/10,4,3.3,试对给出运输问题初始基可行解最小元素法和,Vogel,法进行比较，分析给出解之质量不一样原因。,解：对于任意给出运输问题初始基可行解最小元素法和,Vogel,法进行比较，分析给出两种不一样方法求出解确有不一样原因。初看起来，最小元素法十分合理。不过，有时按某一最小单位运价优先安排物品调运时，却可能造成不得不采取运费很高其它供销点时，从而使整个运输费用增加。我们称各销售地或供给地单位运价中找出最小单位运价和次小单位运价之差为罚数，若罚数值不大，当不能按最小单位运价安排运输时造成运费损失不大；但假如罚数很大，不按最小运价组织运输就会造成很大损失，故应尽可能按最小运价安,第4页,销地,产地,B1,B2,B3,B4,产量,A1,4,1,4,6,8,A2,1,2,5,0,8,A3,3,7,5,1,4,销量,6,5,6,3,20,/10/10,5,排运输。这就是最小元素法和沃格尔法质量不一样原因。,3.7,表,3-28,和表,3-29,分别给出了各产地和各销地产量和销量，以及各产地至各销地单位运价，试用表上作业法求最优解。,表,3-28,第5页,/10/10,6,销地,产地,B1,B2,B3,B4,产量,A1,3,7,6,4,5,A2,2,4,3,2,2,A3,4,3,8,5,6,销量,3,3,3,2,表,3-29,解：（,1,）表,3-28,用三种方法计算，用闭回路法检验。,用最小元素法计算以下表所表示,销地,产地,B1,B2,B3,B4,产量,A1,3,7,6,4,5,A2,2,4,3,2,2,A3,4,3,8,5,6,销量,3,3,3,2,销地,产地,B1,B2,B3,B4,产量,A1,3,7,6,4,5,A2,2,4,3,2,2,A3,4,3,8,5,6,销量,3,3,3,2,第6页,/10/10,7,销地,产地,B1,B2,B3,B4,产量,A1,4,5,1,3,4,6,8,A2,5,1,2,5,3,0,8,A3,1,3,7,3,5,1,4,销量,6,5,6,3,20,最小元素法求解以下：,从上表计算知：,x,12,=5,，,x,13,=3,，,x,21,=5,，,x,24,=3,，,x,31,=1,，,x,33,=3,。总费用,=51,34,51,30,13,35=40,第7页,/10/10,8,销地,产地,B1,B2,B3,B4,产量,A1,6,4,2,1,4,6,8,A2,1,3,2,5,5,0,8,A3,3,7,1,5,3 1,4,销量,6,5,6,3,20,西北解法计算以下：,从上表计算知：,x,11,=6,，,x,12,=2,，,x,22,=3,，,x,23,=5,，,x,33,=1,，,x,34,=3,。总费用,=64,21,32,55,15,31=65,第8页,/10/10,9,销地,产地,B1,B2,B3,B4,产,量,u,i,1,2,3,4,A1,4,5,1,3,4,6,8,3,0,2,A2,3,1,2,2,5,3,0,8,1,1,5,A3,3,7,1,5,1,4,2,2,4,销量,6,5,6,3,用沃格尔法求解以下：,列,罚,数,v,j,1,2,1,1,1,2,2,1,1,3,1,1,4,1,第9页,/10/10,10,从上表计算知：,x,12,=5,，,x,13,=3,，,x,21,=3,，,x,23,=2,，,x,24,=3,，,x,33,=1,。总费用,=51,34,31,25,30,15=35,，在上述三种计算方法中，这种方法计算所需运输费用是最省。但还不知是否最优。现用闭回路法检验以下：,闭回路法检验以下：,第10页,产地,销地,B1,B2,B3,B4,产量,A1,4,5 1,3 4,6,8,A2,3 1,2,2 5,3 0,8,A3,3,7,1 5,1,4,销量,6,5,6,3,/10/10,11,第一个闭回路,11,，走,4154,线路,11,=4-1+5-4=4,第11页,产地,销地,B1,B2,B3,B4,产量,A1,4,5 1,3 4,6,8,A2,3 1,2,2 5,3 0,8,A3,3,7,1 5,1,4,销量,6,5,6,3,/10/10,12,第二闭回路,14,，走,6054,线路,14,=6-0+5-4=7,第12页,产地,销地,B1,B2,B3,B4,产量,A1,4,5 1,3 4,6,8,A2,3 1,2,2 5,3 0,8,A3,3,7,1 5,1,4,销量,6,5,6,3,/10/10,13,第三个闭回路,22,，走,2145,线路,22,=2-1+4-5=0,第13页,产地,销地,B1,B2,B3,B4,产量,A1,4,5 1,3 4,6,8,A2,3 1,2,2 5,3 0,8,A3,3,7,1 5,1,4,销量,6,5,6,3,/10/10,14,第四个闭回路,31,，走,3155,线路,31,=3-1+5-5=2,第14页,产地,销地,B1,B2,B3,B4,产量,A1,4,5 1,3 4,6,8,A2,3 1,2,2 5,3 0,8,A3,3,7,1 5,1,4,销量,6,5,6,3,/10/10,15,第五个闭回路,32,，走,7145,线路,32,=7-1+4-5=2,第15页,产地,销地,B1,B2,B3,B4,产量,A1,4,5 1,3 4,6,8,A2,3 1,2,2 5,3 0,8,A3,3,7,1 5,1,4,销量,6,5,6,3,/10/10,16,第六个闭回路,34,，走,1550,线路,34,=1-5+5-0=1,，至此，六个闭回路全部计算完，,11,=4,，,14,=2,，,22,=0,，,31,=2,，,32,=2,，,34,=1,，即全部检验数,均大于或等于,0,。即用上述三种方法计算中，用沃格尔法计算所得结果,z*=35,为最优解。,第16页,/10/10,17,解：（,2,）表,3-29,用三种方法计算，用位势法检验。因为总产量,=13,，总销量,=10,，所以该题总产量总销量，所以该题是产销不平衡问题，故假设一销地,B5,用最小元素法计算以下表所表示,销地,产地,B1,B2,B3,B4,产量,A1,3,7,6,4,5,A2,2,4,3,2,2,A3,4,3,8,5,6,销量,3,3,2,2,表,3-29,第17页,销地,产地,B1,B2,B3,B4,B5,产量,A1,1,3,7,6,1,4,3,0,5,A2,2,2,4,3,2,0,2,A3,4,3,3,2,8,1,5,0,6,销量,3,3,2,2,3,/10/10,18,最小元素法求解：,x,11,=1,，,x,14,=1,，,x,15,=3,，,x,21,=2,，,x,32,=3,，,x,33,=2,，,x,34,=1,，总费用,=13,14,30,22,33,28,15,41,第18页,销地,产地,B1,B2,B3,B4,B5,产量,A1,3,3,2,7,6,4,0,5,A2,2,1,4,1,3,2,0,2,A3,4,3,1,8,2,5,3,0,6,销量,3,3,2,2,3,/10/10,19,西北角法求解：,x,11,=3,，,x,12,=2,，,x,22,=1,，,x,23,=1,，,x,33,=2,，,x,34,=2,，,x,35,=2,，总费用,=33,27,14,13,18,25,30,48,第19页,销地,产地,B1,B2,B3,B4,B5,产,量,行罚数,ui,1,2,3,4,A1,2,3,7,6,4,3,0,5,3,1,1,1,A2,2,4,2,3,2,0,2,2,0,A3,1,4,3,3,0,8,2,5,0,6,3,1,1,1,销量,3,3,2,2,3,/10/10,20,沃格尔法求解：,列,罚,数,vj,1,1,1,3,2,0,2,1,1,3,2,3,1,4,2,1,4,1,2,1,第20页,/10/10,21,x11=2,，,x15=3,，,x23=2,，,x31=1,，,x32=3,，,X33=0,，,x34=2,，总费用,=23,06,30,23,14,33,25,35,。在最小元素法中，总费用,=41,，在用西北角法计算中，总费用,=56,，所以用沃格尔法计算所需费用,=35,是最小，但不知是否最优，还要用对偶变量法（位势法）加以检验。如表,3-30,所表示：,产地,销地,B1,B2,B3,B4,B5,Ui,A1,2,3,0,A2,2,A3,1,3,0,2,vj,表,3-30,位势法检验,表,3-30,位势法检验,表,3-30,位势法检验,表,3-30,位势法检验,表,3-30,位势法检验,表,3-30,位势法检验,第21页,产地,销地,B1,B2,B3,B4,B5,产,量,Ui,A1,2-1,3,7,12,=2,+1,6,13,=-1,4,14,=0,3,0,5,0,A2,2,21,=3,4,22,=2,2-1,3,+1,2,24,=2,0,25,=5,2,-4,A3,1+1,4,3,3,0,8,2-1,5,0,15,=0,6,1,销量,3,3,2,2,3,vj,3,2,7,4,-1,/10/10,22,表,3-30,位势法检验,由,13,=-1,，故知,z=35,还不是最优解。经上表调整后得：,x,11,=1,，,x,13,=1,，,x,15,=3,，,x,23,=1,，,x,24,=1,，,x,31,=2,，,x,32,=3,，,x,33,=0,，,x,34,=1,，,z*=13,16,30,13,12,24,33,15,36,第22页,/10/10,23,经过调整和检验，得到最终一表,3-30,才是本问题最优解即,z*=36,。,经检验，沃格尔法计算所得结果,z=35,即使不是最优解，不过比较靠近最优解。,第23页,