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

/10/1013.1与普通线性规划数学模型相比，运送问题数学模型含有什么特性？答：与普通线性规划数学模型相比，运送问题数学模型含有下列特性：1.运送问题不象普通线性规划问题那样，线性规划问题有也许有无穷多最优解，运送问题只有有限个最优。2.运送问题约束条件系数矩阵元素等于0或1；且每一列有两个非零元素。3.运送问题解个数不也许不小于(m+n-1)个。3.2运送问题基可行解应满足什么条件?试判断形表3-26和表3-27中给出调运方案是否作为表上作业法迭代时基可行解?为何?第1页第1页销地产地B1B2B3B4产量A1A2A30515151015255销量5151510/10/102表表3-26解：表解：表3-26产地个数产地个数m=3，销地个数，销地个数n=4，m+n-1=3+4-1=6个，而表个，而表3-26中非零个数分量为中非零个数分量为5个个6个，因此表个，因此表3-26不可不可作为表上作业法时基可行解。作为表上作业法时基可行解。第2页第2页销地产地B1B2B3B4B5产量A1A2A3A4A515090200210300250250805020400500300300100销量24041055033070/10/103表表3-27解：表解：表3-27产地个数产地个数m=5，销地个数，销地个数n=5，m+n-1=5+5-1=9个，而表个，而表3-27中非零个数分量为中非零个数分量为10个个9个，也不可作为表上个，也不可作为表上作业法时基可行解。作业法时基可行解。第3页第3页/10/1043.3试对给出运输问题初始基可行解最小元素法和Vogel法进行比较，分析给出解之质量不同原因。解：对于任意给出运输问题初始基可行解最小元素法和Vogel法进行比较，分析给出两种不同方法求出解确有不同原因。初看起来，最小元素法十分合理。不过，有时按某一最小单位运价优先安排物品调运时，却可能造成不得不采取运费很高其它供销点时，从而使整个运输费用增加。我们称各销售地或供应地单位运价中找出最小单位运价和次小单位运价之差为罚数，若罚数值不大，当不能按最小单位运价安排运输时造成运费损失不大；但假如罚数很大，不按最小运价组织运输就会造成很大损失，故应尽可能按最小运价安第4页第4页销地产地B1B2B3B4产量A141468A212508A337514销量656320/10/105排运输。这就是最小元素法和沃格尔法质量不同原因。3.7 表表3-28和表和表3-29分别给出了各产地和各销地产量和分别给出了各产地和各销地产量和销量，以及各产地至各销地单位运价，试用表上作业法求销量，以及各产地至各销地单位运价，试用表上作业法求最优解。最优解。表3-28第5页第5页/10/106销地产地B1B2B3B4产量A137645A224322A343856销量3332表3-29解：（解：（1）表）表3-28用三种办法计算，用闭回路法检查。用三种办法计算，用闭回路法检查。用最小元素法计算下列表所表示用最小元素法计算下列表所表示销地产地B1B2B3B4产量A137645A224322A343856销量3332销地产地B1B2B3B4产量A137645A224322A343856销量3332第6页第6页/10/107销地产地B1B2B3B4产量A14513468A25125308A31373514销量656320 最小元素法求解下列：最小元素法求解下列：从上表计算知：从上表计算知：x12=5，x13=3，x21=5，x24=3，x31=1，x33=3。总费用。总费用=513451301335=40第7页第7页/10/108销地产地B1B2B3B4产量A16421468A21325508A33715314销量656320西北解法计算下列：西北解法计算下列：从上表计算知：从上表计算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3。总费用。总费用=642132551531=65第8页第8页/10/109销地产地B1B2B3B4产量ui1234A14 513468302A231225308115A3371514224销量6563 用沃格尔法求解下列：用沃格尔法求解下列：列罚数vj12111221131141第9页第9页/10/1010从上表计算知：从上表计算知：x12=5，x13=3，x21=3，x23=2，x24=3，x33=1。总费用。总费用=513431253015=35，在上述三种计算办法中，这种办法计算所需运送费用是在上述三种计算办法中，这种办法计算所需运送费用是最省。但还不知是否最优。现用闭回路法检查下列：最省。但还不知是否最优。现用闭回路法检查下列：闭回路法检查下列：闭回路法检查下列：第10页第10页产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563/10/1011第一个闭回路第一个闭回路11，走，走4154线路线路11=4-1+5-4=4第11页第11页产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563/10/1012第二闭回路第二闭回路14，走，走6054线路线路14=6-0+5-4=7第12页第12页产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563/10/1013第三个闭回路第三个闭回路22，走，走2145线路线路22=2-1+4-5=0第13页第13页产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563/10/1014第四个闭回路31，走3155线路31=3-1+5-5=2第14页第14页产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563/10/1015第五个闭回路32，走7145线路32=7-1+4-5=2第15页第15页产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563/10/1016第六个闭回路第六个闭回路34，走，走1550线路线路34=1-5+5-0=1，至此，六个闭回路所有计算完，至此，六个闭回路所有计算完，11=4，14=2，22=0，31=2，32=2，34=1，即所有检查数，即所有检查数均不小于或等于均不小于或等于0。即用上述三种办法计算中，用沃格尔。即用上述三种办法计算中，用沃格尔法计算所得结果法计算所得结果z*=35为最优解。为最优解。第16页第16页/10/1017解：（解：（2）表）表3-29用三种办法计算，用位势法检查。由用三种办法计算，用位势法检查。由于总产量于总产量=13，总销量，总销量=10，因此该题总产量总销量，因此该题总产量总销量，因此该题是产销不平衡问题，故假设一销地因此该题是产销不平衡问题，故假设一销地B5用最小元素法计算下列表所表示用最小元素法计算下列表所表示销地产地B1B2B3B4产量A137645A224322A343856销量3322表3-29第17页第17页销地产地B1B2B3B4B5产量A1137614305A22243202A3433281506销量33223/10/1018最小元素法求解：最小元素法求解：x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，总费，总费用用=1314302233281541第18页第18页销地产地B1B2B3B4B5产量A133276405A221413202A3431825306销量33223/10/1019西北角法求解：西北角法求解：x11=3，x12=2，x22=1，x23=1，x33=2，x34=2，x35=2，总费，总费用用=3327141318253048第19页第19页销地产地B1B2B3B4B5产量行罚数ui1234A1237643053111A2242320220A314330825063111销量33223/10/1020沃格尔法求解：沃格尔法求解：列罚数vj11132021132314214121第20页第20页/10/1021x11=2，x15=3，x23=2，x31=1，x32=3，X33=0，x34=2，总费用，总费用=2306302314332535。在最小元素法中，总费用。在最小元素法中，总费用=41，在用西北角，在用西北角法计算中，总费用法计算中，总费用=56，因此用沃格尔法计算所需费用，因此用沃格尔法计算所需费用=35是最小，但不知是否最优，还要用对偶变量法（位是最小，但不知是否最优，还要用对偶变量法（位势法）加以检查。如表势法）加以检查。如表3-30所表示：所表示：产地销地B1B2B3B4B5UiA1230A22A31302vj表3-30位势法检查表3-30位势法检查表3-30位势法检查表3-30位势法检查表3-30位势法检查表3-30位势法检查第21页第21页产地销地B1B2B3B4B5产量UiA12-13712=2+1613=-1414=03050A2221=3422=22-13+1224=2025=52-4A31+1433082-15015=061销量33223vj3274-1/10/1022表表3-30 位势法检查位势法检查由13=-1，故知z=35还不是最优解。经上表调整后得：x11=1，x13=1，x15=3，x23=1，x24=1，x31=2，x32=3，x33=0，x34=1，z*=131630131224331536第22页第22页/10/1023通过调整和检查，得到最后一表通过调整和检查，得到最后一表3-30才是本问题最优解即才是本问题最优解即z*=36。经检查，沃格尔法计算所得结果经检查，沃格尔法计算所得结果z=35即使不是最优解，即使不是最优解，但是比较靠近最优解。但是比较靠近最优解。第23页第23页