熊伟运筹学第2版第二版课后习题答案前八章答案

运筹学习题答案1目录教材习题答案1习题一1习题二28习题三39习题四41习题五46习题六54习题七64习题八70部分有图形的答案附在各章PPT文档的后面，请留意。习题一11讨论下列问题（1）在例11中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为08,设备B有7台，利用率为085,其它条件不变，数学模型怎样变化（2）在例12中，如果设XJJ1，2，7为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化（3）在例13中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路（4）在例14中，若允许含有少量杂质，但杂质含量不超过1，模型如何变化（5）在例16中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化12工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表122所示表122产品资源ABC资源限量材料KG151242500设备台时316121400利润元/件101412根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130试建立该问题的数学模型,使每月利润最大【解】设X1、X2、X3分别为产品A、B、C的产量，则数学模型为123123312MAX0455060,ZXX13建筑公司需要用6M长的塑钢材料制作A、B两种型号的窗架两种窗架所需材料规格及数量如表123所示运筹学习题答案2表123窗架所需材料规格及数量型号A型号B长度（M）数量根长度M数量根A1172B1272每套窗架需要材料A2133B1203需要量（套）200150问怎样下料使得（1）用料最少；（2）余料最少【解】第一步求下料方案，见下表。方案一二三四五六七八九十十一十二十三十四需要量B127M21110000000000300B22M01003221110000450A117M00100102103210400A213M01120010130234600余料060030700307061010900408第二步建立线性规划数学模型设XJ（J1,2,，14）为第J种方案使用原材料的根数，则（1）用料最少数学模型为14123456789103891232414MIN5600,JJZXXXXX用单纯形法求解得到两个基本最优解X150,200,0,0,84,0,0,0,0,0,0,200,0,0Z534X20,200,100,0,84,0,0,0,0,0,0,150,0,0Z534（2）余料最少数学模型为134131412456789103891232414MIN085600,JZXXXXXXX用单纯形法求解得到两个基本最优解X10,300,0,0,50,0,0,0,0,0,0,200,0,0Z0，用料550根X20,450,0,0,0,0,0,0,0,0,0,200,0,0Z0，用料650根显然用料最少的方案最优。14A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时可供利用的前道工序有11小时，后道工序有17小时每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售赢利，其余的只能加以销毁出售单位产品A、B、C的利润分别为3、7、2元，每单位产品C的销毁费为1元预测表明，产品C最多只能售出13个单位试建立总利润最大的生产计划数学模型运筹学习题答案3【解】设X1,X2分别为产品A、B的产量，X3为副产品C的销售量,X4为副产品C的销毁量，有X3X42X2,Z为总利润，则数学模型为1231234MAZ70,JX15某投资人现有下列四种投资机会,三年内每年年初都有3万元（不计利息）可供投资方案一在三年内投资人应在每年年初投资，一年结算一次，年收益率是20，下一年可继续将本息投入获利；方案二在三年内投资人应在第一年年初投资，两年结算一次，收益率是50，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三在三年内投资人应在第二年年初投资，两年结算一次，收益率是60，这种投资最多不超过15万元；方案四在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30，这种投资最多不超过1万元投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型【解】是设XIJ为第I年投入第J项目的资金数，变量表如下项目一项目二项目三项目四第1年第2年第3年X11X21X31X12X23X34数学模型为1213123412123141234MA0050650,1,4IJZXXXXJ最优解X30000，0，66000，0，109200，0；Z8472016IV发展公司是商务房地产开发项目的投资商公司有机会在三个建设项目中投资高层办公楼、宾馆及购物中心，各项目不同年份所需资金和净现值见表124三个项目的投资方案是投资公司现在预付项目所需资金的百分比数，那么以后三年每年必须按此比例追加项目所需资金，也获得同样比例的净现值例如，公司按10投资项目1，现在必须支付400万，今后三年分别投入600万、900万和100万，获得净现值450万公司目前和预计今后三年可用于三个项目的投资金额是现有2500万，一年后2000万，两年后2000万，三年后1500万当年没有用完的资金可以转入下一年继续使用IV公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分比，使其投资获得的净现值最大表12410项目所需资金（万元）年份项目1项目2项目3运筹学习题答案40400800900160080050029008002003100700600净现值450700500【解】以1为单位，计算累计投资比例和可用累计投资额，见表（2）。表（2）每种活动单位资源使用量（每个百分点投资的累计数）年份项目1项目2项目3累计可用资金万元04080902500110016014045002190240160650032003102208000净现值457050设XJ为J项目投资比例，则数学模型123123MA45700895646080,JZXXX最优解X（0，165049，131067）；Z181068万元实际投资年份项目1比例0项目2比例165049项目3比例131067累计投资万元00132039211796032499995102640784183493844757222039611762097072605824830511651928834747999993净现值0115534365533517图解下列线性规划并指出解的形式1121212MAX3,0ZXX【解】最优解X（1/2，1/2）；最优值Z1/2运筹学习题答案521221MIN30,ZX【解】最优解X（3/4，7/2）；最优值Z45/4运筹学习题答案63121212MIN34073,ZXX【解】最优解X（4，1）；最优值Z1041212MAX38,0ZX【解】最优解X（3/2，1/4）；最优值Z7/4运筹学习题答案75【解】最优解X（3，0）；最优值Z30,632MIN211XXZ60,632MAX2111XXZ【解】无界解。运筹学习题答案871212MIN56,0ZX【解】无可行解。运筹学习题答案98121212MAX580,ZXX【解】最优解X（2，4）；最优值Z1318将下列线性规划化为标准形式1123123MAX4057065,ZXX无限制【解】（1）令为松驰变量，则标准形式为6543,XX12341253634MA0570,ZXX2123123IN9|67|0580,ZX【解】（2）将绝对值化为两个不等式，则标准形式为运筹学习题答案10123123456123456MAX9708,0ZXXX31212MAX350,ZX【解】方法112134213MAX5,0ZXX方法2令111,5XX有212MA34,0ZX则标准型为12132MAX40,ZX41213123123MAXIN4,04596,ZXXXX无约束、【解】令，线性规划模型变为1123114,YYX213213MA4041596,ZYXXX、标准型为运筹学习题答案11124356127383456MAX3019,0ZYXXX19设线性规划4,1,062453MAX121JXXZJ取基分别指出对应的基变量和非基变量，求出基本解，并320P041BB，、，B12和说明是不是可行基12、【解】B1X1，X3为基变量，X2，X4为非基变量,基本解为X（15，0，20，0）T，B1是可行基。B2X1,X4是基变量，X2,X3为非基变量，基本解X（25，0，0，40）T，B2不是可行基。110分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点11212MA3,0ZX【解】图解法运筹学习题答案12单纯形法CJ1300CIBASISX1X2X3X4BRATIO0X32110220X42301124CJZJ130003X221102M0X480316075CJZJ703063X2010250257/21X110037501253/4CJZJ00037508751125对应的顶点基可行解可行域的顶点X1（0，0，2，12）、X2（0，2，0，6，）、X3（、,743（0，0）（0，2）7,43最优解5,2Z运筹学习题答案132121212MIN35640,ZXX【解】图解法单纯形法CJ35000BASISCIX1X2X3X4X5BRATIOX301210063X40140101025X501100144CJZJ350000X30050105012X250251002502510X50075000251152CJZJ175001250125X13102102MX25010505024X50001505100CJZJ003505016X13101022X25011012X40003120CJZJ0020116对应的顶点基可行解可行域的顶点运筹学习题答案14X1（0，0，6，10，4）、X2（0，25，1，0，15，）、X3（2，2，0，0，0）X4（2，2，0，0，0）（0，0）（0，25）2，2（2，2）最优解X（2，2，0，0，0）；最优值Z16该题是退化基本可行解，5个基本可行解对应4个极点。111用单纯形法求解下列线性规划1123123MAX40,JZXX【解】单纯形表CJ34100BASISCIX1X2X3X4X5RHSRATIOX402311011/3X501220133/2CJZJ341000X242/311/31/301/31/2X501/304/32/317/3MCJZJ1/301/34/304/3X1313/21/21/201/2X5001/23/21/215/2CJZJ01/21/23/203/2最优解X（1/2，0，0，0，5/2）；最优值Z3/2212341234MAX557060,JZXX【解】单纯形表CJ2135000BASISCIX1X2X3X4X5X6X7RHSRATIOX50153710030MX6031110101010X702614001205CJZJ2135000X509/211/25/40107/465MX605/21/25/40011/4510X451/23/21/41001/45M运筹学习题答案15CJZJ1/217/27/40005/4X503201501111120MX21515/20021/21010X45807/21031/220MCJZJ4302300173因为730并且AI70,原问题无可行解。两阶段法第一阶段数学模型为7124567MIN53910,JZXXCJ000001RHSRATIOBASISCIX1X2X4X5X6X7X40531000918X5056010015MX71210011525CJZJ210010514X1013/51/50009/5X5009110024X7101/52/50117/5CJZJ01/52/5010因为X70,原问题无可行解。图解法如下运筹学习题答案2141234123413MAX950,4JZXXX【解】大M法。数学模型为1234910123456107813MAX0,2,JZXMXXXXCJ2311MMMRHSRATIOBASISCIX1X2X3X4X5X6X7X8X9X10X11X9M112111945X6211155X10M213111103333X11M111133CJZJ2311BIGM426111X9M1/31/316712/312/38335X62/32332/311/31/3467M运筹学习题答案22X312/31/311/31/31/31/3MX11M1/31/31/31/311/312678CJZJ2672672/31/31/31/3BIGM21112X411/51/513/5043/5045MX608220413/5043/5836364X313/50411/51/51/51/52MX11M04041/51/511/51/51125CJZJ2828043/5043/53BIGM04041/51/511212X41105050505050555MX6315105551505552504545X3111113MX231105052505052525MCJZJ12712710BIGM111X41027100064009045064045573MX8055027018009100027009100045MX3104510002701800902700934576X23036100018045027018027364MCJZJ3820911271360911361318BIGM111X413/51081/504080478MX8123/5041/513/51/5146MX121223/5041/53/51/576MX23108043/51/5041/564MCJZJ8432283/5323/5422BIGM111无界解。两阶段法。第一阶段CJ111BASISCIX1X2X3X4X5X6X7X8X9X10X11RHSRATIOX9111211199/2X6211155X10121311111/3X111111133CJZJ42611113X911/31/35/312/312/325/35X62/37/32/311/31/314/3MX32/31/311/31/31/31/3MX1111/31/31/31/311/318/38CJZJ2111211X41/51/513/52/53/52/55MX64/511/52/513/52/53/5840/11运筹学习题答案23X33/52/511/51/51/51/52MX1112/52/51/51/511/51/5115/2CJZJ2/52/51/51/516/56/51X411/21/21/21/21/21/211/2MX633/211/211/23/21/211/25/25/11X311113MX2111/21/25/21/21/25/25/2MCJZJ111第二阶段CJ2311BASISCIX1X2X3X4X5X6X7X8RHSRATIOX4111/21/21/211/2MX633/211/211/25/25/11X311113MX23111/21/25/25/2MCJZJ12710X413/1117/111/115/1163/11MX86/113/112/111/1115/11MX315/1113/112/111/1138/1138/5X234/1112/115/113/1140/11MCJZJ42/11114/1115/111318X413/514/51/52/539/5MX86/53/52/51/5123/5MX12111/53/52/51/538/5MX2314/52/53/51/532/5MCJZJ42/516/514/53/5422原问题无界解。113在第19题中，对于基求所有变量的检验数,并判断B是不是最优基B2140,J14【解】,14,2B10231045,1595,20,0,244BCAB不是最优基，可以证明B是可行基。950,24114已知线性规划运筹学习题答案2412341234MAX587030,JZXX的最优基为，试用矩阵公式求（1）最优解；2单纯形乘子；34B5N13及；13和。【解】则14234,82BCC11455,0,02TTTBXXBXZ最优解21C31132531244534412NBP4113345,8502347,87012BBCCNC注该题有多重解X10，5，0，5/2X20，10/3，10/3，0X310，0，0，0，X2是基变量，X3是退化基本可行解Z50115已知某线性规划的单纯形表125,求价值系数向量C及目标函数值Z表125CJC1C2C3C4C5C6C7CBXBX1X2X3X4X5X6X7B运筹学习题答案253X4012130244X1101020100X601404123/2J0110102【解】由有JJIJCAJJIJCCAC21（31400（1）2C31（324（1）04）1C51（3（3）420（4）0则4,2,1,3,0,0,0,，ZCBXB12116已知线性规划321MAXXCCZ0,321231BA的最优单纯形表如表126所示，求原线性规划矩阵C、A、及B，最优基B及1表126CJC1C2C3C4C5CBXBX1X2X3X4X5BC1X11041/61/156C2X201301/52J00123【解】，C4C50，166,050B仿照第15题方法可求出C112，C211，C314由1A得64600551B由1B得2310则有，6321,4,510CAB16265,50B117已知线性规划的单纯形表127表127CJ3A11CBXBX1X2X3X4B1X32210B1运筹学习题答案261X43101B2J1234当（）,（）,A（）时，为唯一最优解B12,021X当（）,（）,A（）时，有多重解，此时（）【解】1B10,B20,A5时X4进基X2出基，用单纯形法计算。参数变化与目标值变化的关系如下表所示。FROMTOFROMTOLEAVINGENTERINGRANGEVECTORVECTOROBJVALUEOBJVALUESLOPEVARIABLEVARIABLE10527525X2X425M52M83015271955X1X3415M195M3目标值变化如下图所示。（2）0,2183645MAX21121XXZ【解】0时最优解X4,3,0，Z27；最优表CJ35000BASISCIX1X2X3X4X5RHSX13101004X250100503X500031100,Z275,Z5215,Z1950运筹学习题答案36CJZJ0032502741682B1140352105BBB替换最优表的右端常数，得到下表。CJ35000BASISCIX1X2X3X4X5RHSX13101004X250100503X50003115CJZJ0032500时X5出基X3进基得到下表CJ35000BASISCIX1X2X3X4X5RHSX131001/31/342/3X250101/203X300011/31/35/3CJZJ0003/2106时为最优解。6时Z15。6时X1出基X4进基得到下表CJ35000BASISCIX1X2X3X4X5RHSX4030011122X253/21001/29X30101004CJZJ9时最优解X0，0，13，6，0，Z0；9时无可行解。综合分析如下表所示。FROMTOFROMTOLEAVINGENTERINGRANGEVECTORVECTOROBJVALUEOBJVALUESLOPEVARIABLEVARIABLE10027273X5X320627152X1X23691505X249INFINITYINFEASIBLE50427153X164INFINITYINFEASIBLE运筹学习题答案37目标值变化如下图所示。习题三1设项目，不投资项目投资JXJ0,1234512345MAX001054789680,JZXXXJ或最优解X1,1,1,0,1，Z110万元。2设XJ为投资第J个点的状态，XJ1或0，J1,2,1212312447712115588MA409090,1,3,42JJJJJJJZXXXXX或，最优解X1X5X120，其余XJ1,总收益Z3870万元，实际完成投资额8920万元。3设XJ为装载第J件货物的状态，XJ1表示装载第J件货物，XJ0表示不装载第J件货物，有运筹学习题答案38105626547307638MAX25454312431或JXXXZ4设XIJ（I1，2，5；J1，2，3，4）为第I人参赛J项目的状态，即项目人不参赛第项目人参赛第IJ记第I人参赛J项目的成绩为CIJ,，目标函数514MAXIJIJXZ每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件5,2134321IXXIIII每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条件435JJJJJJ0514IJIXXIJ1或0，I1，2，5；J1，2，3，453,21086241221JYMYXJ，或10821或MYX4,32108621JYXJ，或6）条件（）条件（）条件（）条件（，或4321,20,0220184185MIN211919876547654213212JYXYMYXYYXYXZJ71X1,2,Z32X5,0,Z581X3,3,Z152X5,2,Z169教材原题遗漏，请补上。运筹学习题答案39（1）（2）3,1072465MAX1321JXXZJ，或4,321073534MIN214321JXXZJ，或答案1X1,1,1,Z82X1,1,1,0,Z4101X1,0,1,1,Z82X1,1,0,0,0,Z2习题四41工厂生产甲、乙两种产品，由、二组人员来生产。组人员熟练工人比较多，工作效率高，成本也高；组人员新手较多工作效率比较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表421所示。表421产品甲产品乙效率件/小时成本元/件效率件/小时成本元/件A组1050845B组845540产品售价元/件8075二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以加班10小时，加班生产的产品每件增加成本5元。工厂根据市场需求、利润及生产能力确定了下列目标顺序P1每周供应市场甲产品400件，乙产品300件P2每周利润指标不低于500元P3两组都尽可能少加班，如必须加班由组优先加班建立此生产计划的数学模型。41【解】解法一设X1,X2分别为A组一周内正常时间生产产品甲、乙的产量，X3,X4分别为A组一周内加班时间生产产品甲、乙的产量；X5,X6分别为B组一周内正常时间生产产品甲、乙的产量，X7,X8分别为B组一周内加班时间生产产品甲、乙的产量。总利润为135713572468246823800073XXXX生产时间为A组123405015XB组678X数学模型为运筹学习题答案40123454673571246821234567835653MIN20030500ZPDPDPDXXXXXD467871012,2,8JIXDIJ解法二设X1,X2分别为A组一周内生产产品甲、乙的正常时间，X3,X4分别为A组一周内生产产品甲、乙的加班时间；X5,X6分别为B组一周内生产产品甲、乙的正常时间，X7,X8分别为B组一周内生产产品甲、乙的加班时间。数学模型请同学们建立。42设XIJ为AI到BJ的运量，数学模型为1234354657683311223314244351233MIN807805BZPDDPDDPDXADXST保证供应需求的需求的需求的对212216213132734813000,4,12IJIIJIBBXXDCDXJDI对与的平衡运费最小43双击下图，打开幻灯片。运筹学习题答案41习题4313,210,468MIN21312132IDXPZI3X11020304050102030405021D1DDX2A50/3,20/3B3,满意解在线段上AB44已知某实际问题的线性规划模型为2150MAXXZ0,31621X资源资源假定重新确定这个问题的目标为1的值应不低于19002资源必须全部利用将此问题转换为目标规划问题，列出数学模型。【解】数学模型为1221122MIN059063,JJZPDDXD45已知目标规划问题143215MINDPPDPZ运筹学习题答案424,10,24296214311IDXDXI（1）分别用图解法和单纯形法求解；2分析目标函数分别变为、两种情况时（中分析W1、W2的比例变动）解的变化。35MIN441321DPDDPZ12W【解】（1）图解法（双击下图，打开幻灯片）习题4513X1123451234211D2D3DX2满意解X13/2,5/464123411234MIN569,01,4IZPDPDPXI913/2,5/4（1）单纯形法CJ00P1P40P25P303P30CB基X1X2D1D1D2D2D3D3D4D4BP1D1121160D2121195P3D3121143P3D41112P1121P21P35753表（1）CJZJP41P1D11112220D21112255P3D3111228运筹学习题答案430X21112P11122P21P3575710表（2）CJZJP410X111/21/21/21/20013/2P4D1111133P3D41/41/41/41/4113/40X211/41/41/45/4P11P21P33/43/417/43/43表（5）CJZJP4111B42321MINDPWDDPZ单纯形法，利用上表（5）的结果，引入参数W1、W2进行灵敏度分析，得到下表。CJ00P1P40P2W1P30W2P30CB基X1X2D1D1D2D2D3D3D4D4B0X111/21/21/21/20013/2P4D111113W2P3D41/41/41/41/4113/40X211/41/41/45/4P11P21P3W2/4W2/4W1W2/4W2/4W2表（1）CJZJP41110X1111225P4D111113W1P3D311114430X21112P11P21P3W1W1W1W24W14W1表（2）CJZJP4111（1）由表（1）知，当W1W2/40，即时，满意解为X（13/2，5/4）22,04（2）由表（2）知，当W24W10，即时，满意解为X（5，2）11,（3）当时，表1和表2都是满意解。112,4运筹学习题答案44习题五52用元素差额法直接给出表553及表554下列两个运输问题的近似最优解表553B1B2B3B4B5AIA119161021918A21413524730A3253020112310A478610442BJ152535205表554B1B2B3B4AIA1538616A2107121524A31748930BJ20251015【解】表553。Z824表554Z495运筹学习题答案4553求表555及表556所示运输问题的最优方案（1）用闭回路法求检验数（表555）表555B1B2B3B4AIA11052370A2431280A3564430BJ60604020（2）用位势法求检验数（表556）表556B1B2B3B4AIA19154810A2317630A321013420A4458343BJ20155015【解】（1）运筹学习题答案46254求下列运输问题的最优解（1）C1目标函数求最小值；（2）C2目标函数求最大值13590648739036178514215452040603050403目标函数最小值,B1的需求为30B150,B2的需求为40，B3的需求为20B360,A1不可达A4，B4的需求为30运筹学习题答案475027194836【解】（1）（2）（3）先化为平衡表B11B12B2B31B32B4AIA144977M70A266533220A3885991050运筹学习题答案48A4M0MM0M40BJ302040204030180最优解55（1）建立数学模型设XIJI1,2,3J1,2为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则123121232123MAX408650504405,1,2IJZXXXXJ2写平衡运价表将第一、二等式两边同除以40，加入松驰变量X13,X23和X33将不等式化为等式，则平衡表为B1B2B3AI甲乙丙80605065504000051015BJ10155为了平衡表简单，故表中运价没有乘以40，最优解不变（3）最优调度方案运筹学习题答案49即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为Z40（5805605501040）54000（元）56（1）设XIJ为第I月生产的产品第J月交货的台数，则此生产计划问题的数学模型为11213142142341234234112323441MN0985068560,IJZXXMXXXXXXJ,（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。12345AI12341MMM115125MM1314087M145155102098000065656565BJ50406080303用表上作业法，最优生产方案如下表12345AI123450152560105653065656565BI5040608030上表表明一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小运筹学习题答案50费用Z235万元。57假设在例515中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案【解】将表535所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000产品1产品2产品3产品4工厂1581385401040工厂275100450920工厂3651405101000工厂4821106001120用匈牙利法得到最优表第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；总成本Z1000589205101101598000注结果与例515的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。58求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作（1）2015683609C【解】最优解1,43XZ（2）2053416701986C【解】虚拟一个人，其效率取4人中最好的，构造效率表为12345甲2638415227乙2533445921丙2030475625丁2231455320运筹学习题答案51戊2030415220最优解甲戊完成工作的顺序为3、5、1、2、4，最优值Z165最优分配方案甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。59求解下列最大值的指派问题（1）261869304570C【解】最优解1,64XZ（2）86917520469C【解】最优解1,41XZ第5人不安排工作。510学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表558所示如何从中选拔一个接力队，使预期的比赛成绩最好【解】设XIJ为第I人参加第J项目的状态，则数学模型为表558成绩表分钟游泳自行车长跑登山甲20433329乙15332826丙18423829丁19443227戊17343028运筹学习题答案5212134541234234124355151123242334MIN0928ZXXXXXXX50,1,4IJIJ或接力队最优组合乙长跑丙游泳丁登山戊自行车甲淘汰。预期时间为107分钟。习题六61如图639所示，建立求最小部分树的01整数规划数学模型。【解】边I，J的长度记为CIJ，设否则包含在最小部分树内边0,1JIXIJ数学模型为,0133,22,5MIN5621525623523444165635332412,JIXXXXXCZIJJIIJ所有边或62如图640所示，建立求V1到V6的最短路问题的01整数规划数学模型。【解】弧I，J的长度记为CIJ，设否则包含在最短路径中弧,JIXIJ数学模型为,MIN56456435243341,JIXCZIJJIIJ所有弧或63如图640所示，建立求V1到V6的最大流问题的线性规划数学模型。【解】设XIJ为弧（I,J）的流量，数学模型为,056435243122JICXXIJIJ所有弧图639图640运筹学习题答案5364求图641的最小部分树。图641（A）用破圈法,图641（B）用加边法。图641【解】图641（A），该题有4个解，最小树长为21，其中一个解如下图所示。图641（B），最小树长为20。最小树如下图所示。65某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表620所示。乡镇府如何选择修建公路的路线使总成本最低。表620两村庄之间修建公路的费用万元12345678910123456712810596857713812713112611413911286758314815785968980132124105938812714812713615898821171368910513414691105126运筹学习题答案548910978988【解】属于最小树问题。用加边法，得到下图所示的方案。最低总成本743万元。66在图642中，求A到H、I的最短路及最短路长，并对图A和B的结果进行比较。图642【解】图642AA到H的最短路PAHA,B,F,H,A,C,F,H最短路长22；A到I的最短路PAIA,B,F,I,A,C,F,I最短路长21。对于图642B运筹学习题答案55A到H的最短路PAHA,C,G,F,H,最短路长21；A到I的最短路PAIA,C,G,F,I,最短路长20；结果显示有向图与无向图的结果可能不一样。67已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为35、38、40、42和45万元。使用时间在15年内的维护费用分别为04、09、14、23和3万元。试确定一个设备更新策略，使5年的设备购置和维护总费用最小。【解】设点VJ为第J年年初购置新设备的状态，（I，J）为第I年年初购置新设备使用到第J年年初，弧的权为对应的费用（购置费维护费），绘制网络图并计算，结果见下图所示。总费用最小的设备更新方案为第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为115万元。68图643是世界某6大城市之间的航线，边上的数字为票价（百美元），用FLOYD算法设计任意两城市之间票价最便宜的路线表。【解】教师可利用模板求解DATACHPT6CH6XLSL1V1V2V3V4V5V6V108895686V28801051004V3910034814V45653012100V58100481209V6641410090L2V1V2V3V4V5V6图643运筹学习题答案56V1088865686V288085134V3868034814V456530789V5813487809V66414990L3V1V2V3V4V5V6V1088865686V288085134V3868034812V456530789V5813487809V66412990最优票价表V1V2V3V4V5V6V1088865686V2085134V3034812V40789V509V60V1、V2、V6到各点的最优路线图分别为69设图643是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离KM。现要在6个工厂中选一个建装配车间。（1）应选那个工厂使零配件的运输最方便。运筹学习题答案57（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是05、06、08、13、16和17吨，运价为2元/吨公里。应选那个工厂使总运费最小。【解】1利用习题68表L3的结果MINAX128IJJLV1V2V3V4V5V6MAXV108886568688V288085134128V386803481212V4565307899V5813487809128V6641299012选第1个工厂最好。2计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。V1V2V3V4V5V6单件产品运费V10888656868488V2880851348916V38680348128216V4565307897196V58134878098192V66412990822运价11216263234选第4个工厂最好。610如图644，（1）求V1到V10的最大流及最大流量；（2）求最小割集和最小割量。【解】给出初始流如下第一轮标号得到一条增广链，调整量等于5，如下图所示调整流量。第二轮标号得到一条增广链，调整量等于2，如下图所示图644运筹学习题答案58调整流量。第三轮标号得到一条增广链，调整量等于3，如下图所示调整流量。第四轮标号不存在增广链，最大流量等于45，如下图所示取，最小截集3,7,4,7,6,9,8,10，最小截量等于45。123456817910,VVVVV611将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图645所示。输气管道单位时间的最大通过量CIJ及单位流量的费用DIJ标在弧上CIJ,DIJ。求1流量为22的最小费用流；（2）最小费用最大流。运筹学习题答案59图645【解】虚拟一个发点和一个收点T6111得到流量V22的最小费用流，最小费用为271。求解过程参看第4章PPT文档习题答案。T61113最小费用最大流如下图，最大流量等于27，总费用等于351。612如图643所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。图643【解】（1）旅行售货员问题。距离表C运筹学习题答案6012345618895686288105439103481445653125848129664149在C中行列分别减除对应行列中的最小数，得到距离表C1。距离表C112345613234006042286103470011406207251207296001032由距离表C1，V1到V4，H1V1,V4,V3,V5,V6,V2,V1,CH1563489488352去掉第1行第四列，D41，得到距离表C2。得到距离表C2123562286034701142072512096001032距离表C2的每行每列都有零，H2H1V1,V4,V3,V5,V6,V2,V1就是总距离最小的HAMILTON回路，CH1352。2中国邮路问题。虚拟一条边取回路H1V1，V3，V4，CH195317,CV1，V39CH1/2，调整回路。所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边V1,V4和V4,V3各重复一次。运筹学习题答案61习题七721分别用节点法和箭线法绘制表716的项目网络图，并填写表中的紧前工序。2用箭线法绘制表717的项目网络图，并填写表中的紧后工序表716工序ABCDEFG紧前工序ACAF、D、B、E紧后工序D,EGEGGG表717工序ABCDEFGHIJKLM紧前工序