第5章运输与指派问题5.1用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解．表5-52表5-53【解】双击演示过程→表5-52。Z=824M 1 C r O S O f 、-|||-P( werPoint y,()表5-53结果如下，Z=495（最优值Z=480）M 1 C r O S O f 、-|||-P( werPoint y,()5.2求表5-54及表5-55所示运输问题的最优方案．（1）用闭回路法求检验数（表5-54）表5-54（2）用位势法求检验数（表5-55）表5-55解（1）最优表如下，最优值Z＝610(2)解最优表如下，最优值Z＝4455.3求下列运输问题的最优解（1）C1目标函数求最小值；（2）C2目标函数求最大值(3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达B4，B4的需求为30．【解】（1）M 1 C r O S O f 、-|||-P( werPoint y,()（2）M 1 C r O S O f 、-|||-P( werPoint y,()（3）先化为平衡表最优解如下表，最优值Z＝6405.4（1）建立数学模型设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则(2)写平衡运价表将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为：为了平衡表简单，故表中运价没有乘以40，最优解不变（3）最优调度方案：M 1 C r O S O f 、-|||-P( werPoint y,()即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为Z=40（5×80+5×60+5×50+10×40）=54000（元）5.5（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。(3)用表上作业法，最优生产方案如下表：上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。5.6假设在例5－16中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．用匈牙利法得到最优表第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；总成本Z＝1000×(58＋920＋510＋110)＝1598000注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。5.7求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．（1）【解】最优解（2）M 1 C r O S O f 、-|||-P( werPoint y,()【解】虚拟一个人，其效率取4人中最好的，构造效率表为最优解：，最优值Z=165甲～戊完成工作的顺序为3、5、1、2、4，最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。5.8求解下列最大值的指派问题：（1）M 1 C r O S O f 、-|||-P( werPoint y,()【解】最优解（2）【解】M 1 C r O S O f 、-|||-P( werPoint y,()最优解第5人不安排工作或第1人不安排工作。5.9学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-57所示．如何从中选拔一个接力队，使预期的比赛成绩最好．【解】设xij为第i人参加第j项目的状态，则数学模型为接力队最优组合甲淘汰。预期时间为107分钟。5.10思考与简答题（1）如何运用Vogel近似法求极大化运输问题的初始解。（2）运输问题和指派问题的数学模型有哪些相同和区别。（3）简述运输单纯形法中非基变量检验数的经济含义。（4）位势法求非基变量检验数的公式：，试说明与对偶问题的对应关系（5）运输问题中，为什么一组基变量不包含有任何闭回路，如果包含闭回路会怎样。（6）例5－11讨论的模型是不是指派问题模型，为什么。（7）匈牙利算法的条件是什么，不满足条件时如何求解。（8）如果将指派问题的效率矩阵每行（列）乘以一个大于零的数ki，最优解是否变化。（9）指派问题求最大值时，能否采用将目标函数乘以“－1”的方法转化为求最小值用匈牙利法求解，为什么。（10）证明定理5.4。________