即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为
Z=40（5×80+5×60+5×50+10×40）=54000（元）
5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为
minZ?x11?1.15x12?1.3x13?1.45x14?Mx21???0.98x44?x11?x21?x31?x41?50??x12?x22?x32?x42?40?x13?x23?x33?x43?60??x14?x24?x34?x44?80??x11?x12?x13?x14?65?x?x?x?x?65?21222324?x31?x32?x33?x34?65??x41?x42?x43?x44?65?xij?0,(i,j?1,?,4)?
（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。 1 2 3 4 5 ai 1 1 1.15 1.3 1.45 0 65 2 M 1.25 1.4 1.55 0 65 3 M M 0.87 1.02 0 65 4 M M M 0.98 0 65 bj 50 40 60 80 30 (3)用表上作业法，最优生产方案如下表： 1 2 3 4 5 ai 1 50 15 65 2 25 10 30 65 3 60 5 65 4 65 65 Bi 50 40 60 80 30 上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。
5.7 假设在例5－16中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．
【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．
工厂1 工厂2 工厂3 工厂4 用匈牙利法得到最优表
产品1 58 75 65 82 产品2 138 100 140 110 产品3 540 450 510 600 产品4 1040 920 1000 1120
第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 总成本
Z＝1000×(58＋920＋510＋110)＝1598000
注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。
5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．
?126915??20121826?? （1）C＝??35181025???6101520??【解】最优解
1???1??,Z?43 X???1????1??26?25（2）C＝??20??2238333031414447455259565327?21?? 25??20?【解】虚拟一个人，其效率取4人中最好的，构造效率表为
甲 乙 丙 丁 戊 1 26 25 20 22 20 2 38 33 30 31 30 3 41 44 47 45 41 4 52 59 56 53 52 5 27 21 25 20 20 1????1???，最优值Z=165 最优解：X??1??1???1???
甲～戊完成工作的顺序为3、5、1、2、4，
最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9 求解下列最大值的指派问题：
?109617??15141020?? （1）C＝??18131319???1681226??1??109617???15141020??1?? 最优解X???,Z?64 【解】 C＝??18131319??1?????1???1681226?（2）【解】
?96510??96?4－85??40???C＝?710912???710???615716???615??9868????98?7101160??0?12168110??5?????96740???2???101900???3??781080????0
51016?8516??91216??71616?6816??
9460?151110??5040??0200?7380???09460??08350??5151110??5140100???????25040???35041? ????3020040201??????07380????06270???0?5??3??8??01?01006??0100?1
?020?5225??0431??1??????11????1?或X??1?；Z?44 最优解X??????11???????1????1?第5人不安排工作或第1人不安排工作。
5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-57所示．如何从中选拔一个接力队，使预期的比赛成绩最好．
【解】设xij为第i人参加第j项目的状态，则数学模型为
表5-57 成绩表(分钟) 甲 乙 丙 丁 戊 游泳 自行车 长跑 登山 20 15 18 19 17 43 33 42 44 34 33 28 38 32 30 29 26 29 27 28 minZ?20x11?43x12?33x13?29x14??28x54?x11?x12?x13?x14?1?x?x?x?x?1?21222324?x31?x32?x33?x34?1??x41?x42?x43?x44?1?x?x?x?x?1?51525354??x11?x21?x31?x41?x51?1?x12?x22?x32?x42?x52?1??x13?x23?x33?x43?x53?1?x?x?x?x?x?1?1424344454??xij?0或1,i?1,2,?,5;j?1,2,3,4接力队最优组合 乙 长跑 丙 游泳 丁 登山 戊 自行车
甲淘汰。预期时间为107分钟。
习题六
6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。
【解】边[i，j]的长度记为cij，设
图6－42
?1边[i,j]包含在最小部分树内 xij???0否则
数学模型为：
minZ?cijxij??xij?5?i,j?x?x?x?2,x?x?x?2232434?121323?x34?x36?x46?2,x35?x36?x56?2??x12?x13?x24?x34?3 ?x?x?x?x?334354656??x23?x24?x46?x36?3??x12?x13?x24?x46?x36?4?x23?x35?x24?x46?x56?4,??x12?x13?x24?x35?x46?x56?5?x?1或0,所有边[i,j]?ij
6.2如图6－43所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。 【解】弧(i，j)的长度记为cij，设
?1弧(i,j)包含在最短路径中 xij???0否则数学模型为：
minZ??cijxiji,j?x12?x13?1??x12?x23?x24?x25?0?x?x?x?x?013233435 ???,x24?x34?x45?x46?0?x?x?x?x?0?25354556?x46?x56?1???xij?1或0,所有弧(i,j)图6－43
6.3如图6－43所示，建立求v1到v6的最大流问题的线性规划数学模型。
【解】 设xij为弧（i,j）的流量，数学模型为