运筹学第3版熊伟编著习题答案

运筹学〔第3版〕习题答案第1章线性规划P36第2章线性规划的对偶理论P74第3章整数规划P88第4章目标规划P105第5章运输与指派问题P142第6章网络模型P173第7章网络计划P195第8章动态规划P218第9章排队论P248第10章存储论P277第11章决策论P304第12章多属性决策品P343第13章博弈论P371全书420页第1章线性规划1.1工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．表1－23ABC资源限量产品资源材料<kg>设备<台时>利润<元/件>1.531.21.6144250014001.21210根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．[解]设x1、x2、x3分别为产品A、B、C的产量,则数学模型为1.2建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：表1－24窗架所需材料规格及数量型号A长度〔m〕型号B数量<根>每套窗架需要材料长度<m>数量<根>A1：2A2：1.523B1：2.5B2：223需要量〔套〕300400问怎样下料使得〔1〕用料最少；〔2〕余料最少．[解]第一步：求下料方案,见下表.方案B1B2A1A2一2.5221.5二2000三1100四1010五六七八九十需要量10011020010110101020002010012000038001200600900余料<m>00.50.50.5第二步：建立线性规划数学模型设xj〔j=1,2,…,10〕为第j种方案使用原材料的根数,则〔1〕用料最少数学模型为〔2〕余料最少数学模型为1.3某企业需要制定1～6月份产品A的生产与销售计划.已知产品A每月底交货,市场需求没有限制,由于仓库容量有限,仓库最多库存产品A1000件,1月初仓库库存200件.1～6月份产品A的单件成本与售价如表1－25所示.表1－25月份123456产品成本<元/件300330320360360>300340350340350420410销售价格<元/件>〔1〕1～6月份产品A各生产与销售多少总利润最大,建立数学模型；〔2〕当1月初库存量为零并且要求6月底需要库存200件时,模型如何变化.[解]设xj、yj〔j＝1,2,…,6〕分别为1～6月份的生产量和销售量,则数学模型为〔1〕〔2〕目标函数不变,前6个约束右端常数800改为1000,第7～11个约束右端常数200改为0,第12个约束"≤200"改为"＝－200".1.4某投资人现有下列四种投资机会,三年内每年年初都有3万元〔不计利息〕可供投资：方案一：在三年内投资人应在每年年初投资,一年结算一次,年收益率是20％,下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资,两年结算一次,收益率是50％,下一年可继续将本息投入获利,这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资,两年结算一次,收益率是60％,这种投资最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资,一年结算一次,年收益率是30％,这种投资最多不超过1万元．投资人应采用怎样的投资决策使三年的总收益最大,建立数学模型.[解]是设xij为第i年投入第j项目的资金数,变量表如下项目一x11x21项目二x12项目三x23项目四x34第1年第2年第3年x31数学模型为最优解X=<30000,0,66000,0,109200,0>；Z＝847201.5炼油厂计划生产三种成品油,不同的成品油由半成品油混合而成,例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合,辛烷值不低于94,每桶利润5元,见表1－26.表1－26成品油高级汽油一般汽油航空煤油一般煤油轻油、裂化中石脑油中石脑油轻油、裂化油、重油、重整汽油重整汽油油、重油、残按10:4:3:1调合半成品油油裂化汽油裂化汽油残油而成辛烷值≥94≥84蒸汽压：公斤／平方厘米利润<元/桶>≤154.231.5半成品油的辛烷值、气压、及每天可供应数量见表1－27.表1－27半成品油辛烷值1中石脑油2重整汽油3裂化汽油4轻油5裂化油6重油7残油80115105蒸汽压：公斤／平方厘米每天供应数量<桶>1.01.50.60.05800200010001500120010001000问炼油厂每天生产多少桶成品油利润最大,建立数学模型.解设xij为第i〔i＝1,2,3,4〕种成品油配第j<j=1,2,…,7>种半成品油的数量〔桶〕.总利润：高级汽油和一般汽油的辛烷值约束航空煤油蒸气压约束一般煤油比例约束即半成品油供应量约束整理后得到1.6图解下列线性规划并指出解的形式：<1>[解]最优解X＝〔3,2〕；最优值Z=19<2>[解]有多重解.最优解X〔1〕＝〔0,5/4〕；X〔2〕＝〔3,1/2〕最优值Z=5<3>[解]最优解X＝〔4,1〕；最优值Z=－10,有唯一最优解<4>[解]最优解X＝〔2,3〕；最优值Z=26,有唯一最优解<5>[解]无界解.<6>[解]无可行解.1.7将下列线性规划化为标准形式<1>[解]〔1〕令为松驰变量,则标准形式为<2>[解]〔2〕将绝对值化为两个不等式,则标准形式为<3>[解]方法1：方法2：令则标准型为<4>[解]令,线性规划模型变为标准型为1.8设线性规划取基分别指出对应的基变量和非基变量,求出基本解,并说明是不是可行基．[解]B1：x1、x3为基变量,x2、x4为非基变量,基本解为X=〔15,0,10,0〕T,B1是可行基.B2：x2、x4是基变量,x1、x3为非基变量,基本解X=〔0,20,0,100〕T,B2是可行基.1.9分别用图解法和单纯形法求解下列线性规划,指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．<1>[解]图解法单纯形法：C<j>C<i>13X1-220X20X3bX4010RatioBasisX3X4100C<j>-Z<j>[1]3010021224330C<j>-Z<j>X2X47-2[8]010-31-3001626M0.7531C<j>-Z<j>X2X1001010-0.3750.25-0.375-0.8750.250.12545/47/23/4对应的顶点：基可行解X<1>=〔0,0,2,12〕X<2>=〔0,2,0,6,〕、可行域的顶点〔0,0〕〔0,2〕、X<3>=〔、最优解<2>[解]图解法单纯形法：C<j>BasisX3X4X5-3C<i>000-5X11110X22[4]10X31000X4010bX5001Ratio610432.54C<j>-Z<j>X3X2X5C<j>-Z<j>X1X2X5C<j>-Z<j>X1X2-30-50-1.75-3-50-5[0.5]0.250.750000001001001.252-0.5-1.5-0.5-11-0.50.25-0.250001-12.5001-162-1212.51.5210210000103.50102-1220M400.5[0.5]00-3-5010000011220X4C<j>-Z<j>-300-16对应的顶点：基可行解可行域的顶点X<1>=〔0,0,6,10,4〕、〔0,0〕〔0,2.5〕<2,2>X<2>=〔0,2.5,1,0,1.5,〕、X<3>=〔2,2,0,0,0〕X<4>=〔2,2,0,0,0〕〔2,2〕最优解：X=〔2,2,0,0,0〕；最优值Z＝－16该题是退化基本可行解,5个基本可行解对应4个极点.1.10用单纯形法求解下列线性规划<1>[解]单纯形表：C<j>BasisX43C<i>04X121X2[3]20X310X41R.H.S.X50Ratio434/33/2X501201C<j>-Z<j>X2X534100040[2/3]-1/30101/34/3-4/31/3-2/3001－16/34/32M1/3C<j>-Z<j>1/3-1/3X1X5C<j>-Z<j>30010-1/23/21/2-1/21/23/2-3/21/2-1/2001-621最优解：X=〔2,0,0,0,1〕；最优值Z＝6<2>[解]单纯形表：C<j>BasisX5X6X7C<j>-Z<j>X5X6X4C<j>-Z<j>X52C<i>0001X1132-3X25-1-6-35X33[1]-1500X51000X6010R.H.S.X7001RatioX4-71[4]0301020M1052100005-1/2015-439/25/21/217/2325-11/25/4[1/2]5/4-3/2-1/4-7/4010-2300101000010-5/4112337/4-1/41/46555M10M0155/27/200010100-17-1-1/2-1/21201020M10MX2X4C<j>-Z<j>80因为λ7＝3>0并且ai7<0<i=1,2,3>,故原问题具有无界解,即无最优解.<3>[解]C<j>Basis32-0.125X2000R.H.S.X6RatioC<i>X1X3X4X5X4X5X6C<j>-Z<j>X4X1X6C<j>-Z<j>X4X1X2000303000320-1[4]3208-1/820[8]11/80013-24100001000141210M310/3200001025/2-1/211/20100-3/4101/41/4-3/4000197313.5M1/801009/8-1/2[11/16]07/161/4-3/32-1/4-1/401/837/427/431/86M0.1818180-9/16C<j>-Z<j>0X3进基、X2出基,得到另一个基本最优解.C<j>3X10102X2-18/118/1116/110-0.125X30010X41000X513/222/11-3/22-1/40X6-5/111/112/1137/4R.H.S.RatioBasisX4X1X3C<j>-Z<j>072/1134/112/116M0.18183-0.125000-9/16原问题具有多重解.基本最优解,最优解的通解可表示为即〔4〕[解]单纯形表：C<j>Basis3C<i>2X15[8]21X24610X36300X4100R.H.S.X5010RatioX4X5C<j>-Z<j>X4X100303025245301-1/41/43/4-1/833/83/8010-3/8-5/81/89103C<j>-Z<j>最优解：X=〔3,0,0,10,0〕；最优值Z＝91.11分别用大M法和两阶段法求解下列线性规划：<1>[解]大M法.数学模型为C<j>BasisX510C<i>-M01051000-5X15-5-5310-1101X231113/54-100X31-100-MX4010001-2-1R.H.S.X510001/51200Ratio10152X4MC<j>-Z<j>*BigMX1X4C<j>-Z<j>*BigM01/5-9022500最优解X＝<2,0,0>；Z=20两阶段法.第一阶段：数学模型为C<j>BasisX5X4C<j>-Z<j>X10C<i>10-500X1[5]-5-310X230X31-1001X4010R.H.S.X51Ratio1015210M-13/541/5-900111/51225X4C<j>-Z<j>00000第二阶段C<j>BasisX110-5X111X23/540X31/5-90R.H.S.X40RatioC<i>10022X40125MC<j>-Z<j>0-11-1最优解X=<2,0,0>；Z=20<2>[解]大M法.数学模型为C<j>BasisA1S2A35C<i>M0M-6X1151-7X2[5]-60X3-31010S1-10MS2010MA1100R.H.S.A3001Ratio152053M510C<j>-Z<j>*BigMX25-2-6-6-7201000000-61/531/54/501-3/532/5[8/5]-6/5-1/5-1/5-6/51/5001/56/5-1/500013382M95/165/4S2A3C<j>-Z<j>*BigM0M31/5-4/500-53/5-8/5106/56/5000X2S2X3C<j>-Z<j>*BigM-60-723/201/231/20100000011/80-1/8-21/80010-1/811/82-1/853/813/8-45/815/4305/400两阶段法.第一阶段：数学模型为C<j>BasisA1S2A30C<i>1010X115100X3-31010S1-1001S20101A1100R.H.S.RatioA3X2[5]-61001152053M5C<j>-Z<j>X2S2A3C<j>-Z<j>X2-2001-4/50-62100-8/511000106/5001/531/54/501/23-3/532/5[8/5]-1/50-1/5-6/51/50-1/8-21/56/5-1/501/820013382M95/165/43/8-415/430S20001X3C<j>-Z<j>001/2000101/8001-1/815/85/4第二阶段：C<j>BasisX25C<i>-60-6-7X210X300S1-1/8-2R.H.S.S20RatioX11/2315/4303S2001MX3C<j>-Z<j>-723/21/200011/81/8005/45最优解：<3>[解]大M法.数学模型为C<j>BasisX3X4X6C<j>-Z<j>*BigMX110C<i>015X1[5]-5215110X2361003/590X3100001/510X40100-10-MX500-10000R.H.S.X60010000Ratio91551.8M2.50-M1021009/524X401X6C<j>-Z<j>*BigM-M0009-1/5-1/5-2-2/5-2/50000-1-10011807/5因为X6>0,原问题无可行解.两阶段法第一阶段：数学模型为C<j>BasisX3X4X6C<j>-Z<j>X1X4X6C<j>-Z<j>0C<i>001-200100X1[5]-52-1100X236103/59-1/52/50X310001/51-2/500X401010101X500-1000-10R.H.S.X60015001Ratio9155149/5247/51.8M2.501/51因为X6>0,原问题无可行解.图解法如下：<4>[解]大M法.X7是人工变量,数学模型为CjCB00－MC<j>-Z<j>－MR.H.S.Ratio4XBX4X5X72500X410X163X2-1-3X34-51X5X6X710811[2]－112010425*BigM00M2M13/29/2M－1-1/2-3/2-1/2X4X5X2[9/2]-7/21/211/23/21/22038101121/21C<j>-Z<j>*BigM50234-1-1-1/9-17/917/9482/9-4/9X3X5X213/986/9-2/912/97/9-1/91/940/9114/970/9C<j>-Z<j>*BigM-25/9-8/913/9-13/9-1无界解.两阶段法.第一阶段：Cj00X4101R.H.S.RatioCBXBX163X2-1-3X34-51X5X6X7108001X4X5X711[2]－112010C<j>-Z<j>002－1－2－111X4X5X213/29/21/2[9/2]-7/21/21-1/2-3/2-1/21/23/21/22038101C<j>-Z<j>1第二阶段：CjCB004XBX4X52500X410R.H.S.RatioX6X113/29/2X2X3[9/2]-7/2X5-1/2-3/2203811C<j>-Z<j>002X27/21/211/21-1/2-1/9-17/9482/9-4/9109/21/21X3X5X213/986/9-2/92/97/9-1/940/9170/9C<j>-Z<j>-3-11原问题无界解.1.12在第1.9题中,对于基求所有变量的检验数,并判断B是不是最优基．[解],B不是最优基,可以证明B是可行基.1.13已知线性规划的最优基为,试用矩阵公式求〔1〕最优解；<2>单纯形乘子；<3><4>[解]则<1><2><3><4>注：该题有多重解：X<1>X<2>=<0,5,0,5/2>=<0,10/3,10/3,0>X<3>=<10,0,0,0>,x2是基变量,X<3>是退化基本可行解Z＝501.14已知某线性规划的单纯形表1－28,求价值系数向量C及目标函数值Z．表1－28CjCB3c1XBx4c2x10c3x21c4x32c5x41c6x5－3c7x60bx72404x110－1020－10x60－140－4123/20－1－1010－2λj[解]由有c2＝－1＋〔3×1＋4×0＋0×〔－1〕〕＝2c3＝－1＋〔3×2＋4×〔－1〕＋0×4〕＝1c5＝1＋〔3×〔－3〕＋4×2＋0×〔－4〕〕＝0c7＝-2＋〔3×2＋4×<－1>＋0×2〕＝0则C＝<4,2,1,3,0,0,0,>,Z=CBXB=121.15已知线性规划的最优单纯形表如表1－29所示,求原线性规划矩阵C、A、及b,最优基B及表1－29．CjCBc1c1XBx1c2x11c3x20c4x34c5x41/60bx51/1562c2x201－31/5λj00－1－2－3[解]由c4＝c5＝0,由公式得由得由得1.16思考与简答〔1〕在例1.2中,如果设xj<j=1,2,…,7>为工作了5天后星期一到星期日开始休息的营业员,该模型如何变化.〔2〕在例1.3中,能否将约束条件改为等式；如果要求余料最少,数学模型如何变化；简述板材下料的思路.〔3〕在例1.4中,若允许含有少量杂质,但杂质含量不超过1％,模型如何变化.〔4〕在例1.6中,假定同种设备的加工时间均匀分配到各台设备上,要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时,模型如何变化.<5>在单纯形法中,为什么说当时线性规划具有无界解.<6>选择出基变量为什么要遵循最小比值规则,如果不遵循最小比值规则会是什么结果.〔7〕简述大M法计算的基本思路,说明在什么情形下线性规划无可行解.〔8〕设X<1>、X<2>、X<3>是线性规划的3个最优解,试说明也是线性规划的最优解.〔9〕什么是基本解、可行解、基本可行解、基本最优解,这四个解之间有何关系.〔10〕简述线性规划问题检验数的定义及其经济含义.返回顶部第2章线性规划的对偶理论2.1某人根据医嘱,每天需补充A、B、C三种营养,A不少于80单位,B不少于150单位,C不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．〔1〕试建立此人在满足健康需要的基础上花费最少的数学模型；〔2〕假定有一个厂商计划生产一中药丸,售给此人服用,药丸中包含有A,B,C三种营养成分．试为厂商制定一个药丸的合理价格,既使此人愿意购买,又使厂商能获得最大利益,建立数学模型．表2-22一二三四五六需要量含量食物营养成分ABC1324180.52591430210.84025340.9811150≥80≥150≥18012100.37食物单价0.40.2〔元/100g〕[解]〔1〕设xj为每天第j种食物的用量,数学模型为〔2〕设yi为第i种单位营养的价格,则数学模型为2.2写出下列线性规划的对偶问题〔1〕[解]〔2〕[解]〔3〕[解]〔4〕[解]对偶问题为：2.3考虑线性规划<1>说明原问题与对偶问题都有最优解；<2>通过解对偶问题由最优表中观察出原问题的最优解；<3>利用公式CBB－1求原问题的最优解；<4>利用互补松弛条件求原问题的最优解．[解]<1>原问题的对偶问题为容易看出原问题和对偶问题都有可行解,如X＝<2,1>、Y＝<1,0,1>,由定理2.4知都有最优解.<2>对偶问题最优单纯形表为C<j>Basisy3y1C<j>-Z<j>4C<i>7402y101-11/57y2-1/57/500y310-16/5-1/50y44/5-3/5R.H.S.y5-1/52/5w=42.428/54/5对偶问题的最优解Y＝<4/5,0,28/5>,由定理2.6,原问题的最优解为X=<16/5,1/5>,Z＝42.4〔3〕CB=<7,4>,,<4>由y1、y3不等于零知原问题第一、三个约束是紧的,解等式得到原问题的最优解为X=<16/5,1/5>.2.4证明下列线性规划问题无最优解证明：首先看到该问题存在可行解,例如x=<2,1,1>,而上述问题的对偶问题为由约束条件①②知y1≤0,由约束条件③当y2≥0知y1≥1,对偶问题无可行解,因此原问题也无最优解<无界解>.2.5已知线性规划的最优解,求对偶问题的最优解．[解]其对偶问题是：由原问题的最优解知,原问题约束③的松弛变量不等于零<①、约束③为等式,又由于知y3＝0；解方程>,x1、x3不等于零,则对偶问题的约束得到对偶问题的最优解Y=<5/2,5/2,0>；w＝55/2＝27.52.6用对偶单纯形法求解下列线性规划[解]将模型化为对偶单纯形表：cj34600CBXBX1X2X3X4X5b00X4X5－1[－2]－2－2－3－11001－10－12C<j>-Z<j>340600003X4[－1]1－5/21/210－1/2－4－1/2X10116C<j>-Z<j>9/203/2－18X2X10110425/2－2－111/2－153C<j>-Z<j>00211－22b列全为非负,最优解为x＝<2,4,0>；Z＝22[解]将模型化为5400bX40XBX3X4CB0X1[-1]2X2-11X31-62001Cj－Zj3400X1X4311-1201600[-1]-10Cj－ZjX1X2Cj－Zj03110030011-415-21-11040出基行系数全部非负,最小比值失效,原问题无可行解.[解]将模型化为cj24X120X230X310X40bX50XBX3X4X5CB0024-10-18-1-14-2[-3]00100001Cj－Zj200X3X4X20101016260-1/31/30001－2/3－1/34100Cj－Zj2/3004/3最优解X=<0,6>；Z＝24[解]将模型化为Cj235600bXBX5X6CB0X1X2[-2]1X3-3X4-4X51X60-1-23-2-30-1301Cj－Zj25600X2X6Cj－ZjX2X3Cj－ZjX1X3Cj－ZjX1X2Cj－Zj31/2-5/2013/22-1/21/2001100[-5/2]01-41/231/213/213/5-2/58/5-13/511/58/5-2/511/58/5[-1]10-1/5-1/51/51/5-2/51/5-1/5-2/51/53/5-7/58/5501-2/50001/5021-1[1]0-3/51/57/51/5501001/51210-2/51/58/51/530110001/5原问题有多重解：X<1>＝<7/5,0,1/5,>；最优解X<2>＝<8/5,1/5,0>；Z＝19/5如果第一张表X6出基,则有Cj235600bXBCBX1X2X3X4X5X6X5X60-1-2-3-410-2-30[-2]1-1301Cj－ZjX5X1Cj－ZjX2X1Cj－Zj202032030140105[-5/2]-1/246-5/21/29001-11/2-3/20-1/2-1/2-1/23/2011111/5-7/58/5-2/5-1/51/51/51/58/501-2/501/52．7某工厂利用原材料甲、乙、丙生产产品A、B、C,有关资料见表2-23．表2-23每月可供原材料〔Kg〕A2B1C1产品材料消耗原材料甲200乙丙12每件产品利润2243115006003〔1〕怎样安排生产,使利润最大．〔2〕若增加1kg原材料甲,总利润增加多少．〔3〕设原材料乙的市场价格为1.2元/Kg,若要转卖原材料乙,工厂应至少叫价多少,为什么？〔4〕单位产品利润分别在什么范围内变化时,原生产计划不变．〔5〕原材料分别单独在什么范围内波动时,仍只生产A和C两种产品．〔6〕由于市场的变化,产品B、C的单件利润变为3元和2元,这时应如何调整生产计划．〔7〕工厂计划生产新产品D,每件产品D消耗原材料甲、乙、丙分别为2kg,2kg及1kg,每件产品D应获利多少时才有利于投产．[解]〔1〕设x1、x2、x3分别为产品A、B、C的月生产量,数学模型为最优单纯形表：C<j>XBX1X3X6C<j>-Z<j>4CB43001X11003X21/53/500X301000X5-1/52/50R.H.S.X6001RatioX43/5-1/5-120160400-8/50-9/5-2/50Z=560最优解X=〔20,0,160〕,Z=560.工厂应生产产品A20件,产品C160种,总利润为560元.〔2〕由最优表可知,影子价格为,故增加利润1.8元.〔3〕因为y2=0.4,所以叫价应不少于1.6元.〔4〕依据最优表计算得〔5〕依据最优表计算得〔6〕变化后的检验数为λ2=1,λ4=-2,λ5=0.故x2进基x1出基,得到最最优解X=<0,200,0>,即只生产产品B200件,总利润为600元.C<j>XBX1X3X6C<j>-Z<j>X2X3X6C<j>-Z<j>X2X44CB4200230-5200-23X110015-3002X2[1/5]3/50010001000X3010-2010-510X43/5-1/5-100X5-1/52/50R.H.S.X600156000Ratio20160400100800/3M03-1[1]000100100100400M100M-2-1112-30100120010040010-3-2-10X6C<j>-Z<j>0-1<7>设产品D的产量为x7,单件产品利润为c7,只有当时才有利于投产.则当单位产品D的利润超过4.4元时才有利于投产.2．8对下列线性规划作参数分析〔1〕[解]μ＝0时最优解X=<4,3,0>；最优表：C<j>Basis3C<i>5X10X20X30X4R.H.S.X5X1X2X53500100001010-300.5-10001430C<j>-Z<j>-3-2.527将参数引入到上表：C<j>BasisX13＋2μC<i>3＋2μ5－μ005－μX110X200X310X40R.H.S.X50430X2X5C<j>-Z<j>00010－3－2μ-2.5＋0.5μ0-30.5-100127当－3－2μ≤0及-2.5＋0.5μ≤0时最优基不变,有－1.5≤μ≤5.当μ<－1.5时X3进基X1出基；μ>5时X4进基X2出基,用单纯形法计算.参数变化与目标值变化的关系如下表所示.EnterinFromToFromToLeavinggVariableOBJValue275227Range<Vector><Vector>OBJValueSlopeVariableX212340505M-1.5-M52M19.5M585X4X1X3-1.519.5-3目标值变化如下图所示.0<μ＝-1.5,Z=19.5><μ＝5,Z=52><μ＝0,Z=27>〔2〕[解]μ＝0时最优解X=<4,3,0>,Z＝27；最优表：C<j>BasisX1X2X53C<i>35005X11000X20100X310-30X400.5-10R.H.S.X5001430C<j>-Z<j>0-3-2.527替换最优表的右端常数,得到下表.C<j>BasisX1X2X53C<i>3505X11000X20100X310[-3]0X400.5-1R.H.S.X50014＋μ3－5μC<j>-Z<j>00-3-2.50①μ<－4时问题不可行,－4≤μ<0时最优基不变.μ＝－4时Z＝15.②μ>0时X5出基X3进基得到下表：C<j>BasisX1X2X33C<i>35005X11000X20100X30010R.H.S.X51/30-1/3X4-1/31/21/3-14-2/3μ35μ/3C<j>-Z<j>00-3/20≤μ≤6时为最优解.μ＝6时Z＝15.③μ>6时X1出基X4进基得到下表：C<j>BasisX4X2X33C<i>0505X1-33/210X20100X30010X4100R.H.S.X5-11/20-12+2μ9-μ4+μC<j>-Z<j>μ＝9时最优解X=<0,0,13,6,0>,Z=0；μ>9时无可行解.综合分析如下表所示.FromToFromToLeavingEnteringRange<Vector><Vector>OBJValueOBJValueSlopeVariableVariableX3X212345600690069Infinity-4-Infinity272715Infeasible27Infeasible271503-2-5X5X1X2153X1-4目标值变化如下图所示.2.9有三个决策单元的输入输出矩阵〔1〕建立C2R模型并求解,判断各决策单元的DEA有效性.<2>建立BC2模型并求解,判断各决策单元的DEA有效性.〔3〕指出哪些决策单元是技术有效又规模有效、是技术有效非规模有效、既不是技术有效又非规模有效.<4>分别求三个决策单元的整体效率、技术效率、规模效率及规模报酬[解]〔1〕对第一决策单元有最优解,Z1P=1对偶问题的最优解：,Z1D=1.DEA有效对第二决策单元有最优解,Z2P=0.7967对偶问题的最优解：,Z2D=0.7967非DEA有效对第三决策单元有最优解,Z3P=0.7465对偶问题的最优解：,Z3D=0.7465.非DEA有效〔2〕第一决策单元BC2模型最优解,W1P=1对偶问题的最优解：技术有效,W1D=1.第二决策单元BC2模型最优解,W2P=0.9346对偶问题的最优解：,W2D=0.9346非技术有效第三决策单元BC2模型最优解,W3P=1对偶问题的最优解：技术有效,W3D=1〔3〕第一决策单元DEA有效,从而既技术有效又规模有效；第二决策单元非DEA有效,由BC2模型知既不是技术有效又非规模有效；第三决策单元非DEA有效,由BC2模型知是技术有效非规模有效；〔4〕由定义及式〔2－12〕、〔2－13〕得到下表结果.决策单元kZkpWkp1ck0整体效率技术效率规模效率规模报酬DMU1DMU2DMU310.79670.934600.7465111110.79670.934610.85240.746510.451.22220.7465返回顶部第3章整数规划3.1某公司今后三年内有五项工程可以考虑投资.每项工程的期望收入和年度费用<万元>如表3-8所示.表3-8工程费用收入第一年第二年第三年123455457179568262930402015308资金拥有量302530每项工程都需要三年完成,应选择哪些项目使总收入最大,建立该问题的数学模型.[解]设,模型为最优解X＝<1,1,1,0,1>,Z=120万元,即选择项目1、2、3、5时总收入最大.3.2选址问题.以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇.某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行,如图3-8所示.每个点的投资额与一年的收益见表3－9.计划汉口投资2～3个支行,汉阳投资1～2个支行,武昌投资3～4个支行.如何投资使总收益最大,建立该问题的数学模型,说明是什么模型,可以用什么方法求解.表3-9地址i123456789101112投资额<万元>收益〔万元〕900120010007506808007201150120012508501000400500450350300400320460500510380400[解]设xj为投资第j个点的状态,xj=1或0,j=1,2,…,12最优解：x1＝x5=x12=0,其余xj=1,总收益Z=3870万元,实际完成投资额8920万元.3.3一辆货车的有效载重量是20吨,载货有效空间是8m×2m×1.5m.现有六件货物可供选择运输,每件货物的重量、体积及收入如表表3-10.另外,在货物4和5中优先运货物5,货物1和2不能混装,货物3和货物6要么都不装要么同时装.怎样安排货物运输使收入最大,建立数学模型.表3-10货物号1632573344455766重量〔T〕22体积〔m3〕收入〔百元〕372583[解]设xj为装载第j件货物的状态,xj=1表示装载第j件货物,xj=0表示不装载第j件货物,有3.4女子体操团体赛规定：〔1〕每个代表队由5名运动员组成,比赛项目是高低杠、平衡木、鞍马及自由体操.〔2〕每个运动员最多只能参加3个项目并且每个项目只能参赛一次；〔3〕每个项目至少要有人参赛一次,并且总的参赛人次数等于10；〔4〕每个项目采用10分制记分,将10次比赛的得分求和,按其得分高低排名,分数越高成绩越好.已知代表队5名运动员各单项的预赛成绩如表3-11所示.表3-11怎样安排运动员的参赛项目使团体总分最高,建立该问题的数学模型.[解]设xij〔i=1,2,…,5；j＝1,2,3,4〕为第i人参赛j项目的状态,即记第i人参赛j项目的成绩为Cij,,目标函数每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件：每个项目至少要有人参赛一次,并且总的参赛人次数等于10,约束条件：数学模型为3.5某电子系统由3种元件组成,为了使系统正常运转,每个元件都必须工作良好,如一个或多个元件安装几个备用件将提高系统的可靠性,已知系统运转可靠性为各元件可靠性的乘积,而每一元件的可靠性是备用件数量的函数,具体如表3－12所示.表3－12备用件数元件可靠性1230.60.700.50.80.91.01.00.91.01.01.012340.60.750.91.03种元件的价格分别为30、40和50元/件,重量分别为2、4和6kg/件.而全部备用件的费用预算限制为220元,重量限制为20kg,问每种元件各安装多少个备用件,使系统可靠性最大.试建立该问题的整数〔非线性〕规划数学模型.[解]设分别为元件1、2、3的备件数,由可靠性知设为元件1备件数的状态变量,〔备件数为j件,j＝0,1…,4〕或〔备件数为0件,i＝1,2,…,5〕设为元件2备件数0、1、2、3件时的状态变量,为元件3备件数0、1、2件时的状态变量,〔i＝6、7、8、9〕〔i＝10、11、12〕设数学模型为：注意：如果去掉第6、7、8个约束,因目标函数中没有x,则x与y之间就没有逻辑关系.3.6利用0－1变量对下列各题分别表示成一般线性约束条件〔1〕x1+2x2≤8、4x1+x2≥10及2x1+6x2≤18三个约束中至少两个满足〔2〕若x1≥5,则x2≥10,否则x2≤8〔3〕x1取值2,4,6,8中的一个[解]3.7考虑下列数学模型其中满足约束条件〔1〕x1≥8或x2≥6〔2〕|x1－x2|=0,4或8〔3〕x1+2x2≥20、2x1+x2≥20及x1+x2≥20三个约束中至少一个满足〔4〕x1≥0,x2≥0将此问题归结为混合整数规划的数学模型.[解]3.8用分枝定界法求解下列IP问题〔1〕〔2〕[解]<1>X=<4,0>,Z=4〔双击打开PPT〕<2>X<1>=<2,4>,X<2>＝<0,5>；Z=103.9用割平面法求解下列IP问题〔双击打开PPT〕〔1〕〔2〕[解]<1>加入松弛变量x3、x4,单纯形表如下：C<j>CB00C<j>-Z<j>2XBX3X421X14210X22100X3100bX4010141020X1X40101/20－1/21/4－1/2001－77/23C<j>-Z<j>0X1行为来源行,割平面方程为：,插入到最优表得到C<j>CB22XBX1X4S110X21/20[－2]－1/20010X31/4－1/2－100bS1X1X401100010004020001－7[1/4]07/203－200C<j>-Z<j>0020X1X4X20001331－1/21/20100－1/2－71C<j>-Z<j>－1/220S1X4X2000100100123－1/21/2001C<j>-Z<j>0－77－1/2从表中看出,有两个最优解：X<1>=<3,1>,X<2>＝<0,7>；Z=7<2>加入松弛变量x3、x4,单纯形表如下：C<j>CB002XBX3X4300X31bX40X1X2－1[－2]－2－1－9－1001C<j>-Z<j>0230120100[－3/2]1/200101－2/31/30X3X10－1/2－1/2－101/3－2/3－46/3－452C<j>-Z<j>3X2X1018/32011/3C<j>-Z<j>4/31/3以X1行为来源行,割平面方程为：,插入到最优表得到C<j>CB32XBX2X1S203X10000bS20X21X3X4－2/31/3－11/3－111/3－2/3[－1]08/311/3－221000001－46/31/3－2/3－1C<j>-Z<j>04/313X2X1X4000012522100001C<j>-Z<j>0101/3－16最优解X=<5,2>；最优值Z=163.10用隐枚举法求解下列BIP问题〔1〕〔2〕[解]<1>X=<1,0,1>,Z=8<2>X=<1,0,1,0>,Z=93.11思考与简答题〔1〕"整数规划的最优解是求其松弛问题最优解后取整得到"为什么不对.〔2〕解释"分支"与"定界"的含义.〔3〕简述分支定界法的基本步骤.〔4〕高莫雷方程是怎样得到的,在割平面法中起到什么作用.〔5〕割平面法计算过程中,什么时候可以去掉单纯形表中一行和一列.返回顶部第4章目标规划4.1已知某实际问题的线性规划模型为假定重新确定这个问题的目标为：Ｐ1：ｚ的值应不低于1900Ｐ2：资源１必须全部利用将此问题转换为目标规划问题,列出数学模型.[解]数学模型为4.2工厂生产甲、乙两种产品,由Ａ、Ｂ二组人员来生产.Ａ组人员熟练工人比较多,工作效率高,成本也高；Ｂ组人员新手较多工作效率比较低,成本也较低.例如,A组只生产甲产品时每小时生产10件,成本是50元有关资料如表4.21所示.表4.21产品甲产品乙效率<件/小时>成本<元/件>效率<件/小时>成本<元/件>A组B组1050458545408产品售价<元/件>8075二组人员每天正常工作时间都是8小时,每周5天.一周内每组最多可以加班10小时,加班生产的产品每件增加成本5元.工厂根据市场需求、利润及生产能力确定了下列目标顺序：P1：每周供应市场甲产品400件,乙产品300件P2：每周利润指标不低于500元P3：两组都尽可能少加班,如必须加班由Ａ组优先加班建立此生产计划的数学模型.[解]解法一：设x1,x2分别为A组一周内正常时间生产产品甲、乙的产量,x3,x4分别为A组一周内加班时间生产产品甲、乙的产量；x5,x6分别为B组一周内正常时间生产产品甲、乙的产量,x7,x8分别为B组一周内加班时间生产产品甲、乙的产量.总利润为生产时间为A组：B组：数学模型为：解法二：设x1,x2分别为A组一周内生产产品甲、乙的正常时间,x3,x4分别为A组一周内生产产品甲、乙的加班时间；x5,x6分别为B组一周内生产产品甲、乙的正常时间,x7,x8分别为B组一周内生产产品甲、乙的加班时间.总利润为数学模型为4.3[解]设xij为Ai到Bj的运量,数学模型为4.4用图解法求解下列目标规划问题〔1〕满意解X＝〔0,5〕〔2〕满意解X＝〔6,0〕〔3〕双击下图打开PPTA点：X＝<40/3,40/3>,B点：X＝<40,0><4>双击下图打开PPT4.5用单纯形法求解下列目标规划问题<1><2>[解]〔1〕初始表基变量为,单纯形法计算如下：CjP1x3P3d1－d1+d2－d2+d3－d3+P2P1P2P300x110x21bCBP1XBd1－d2－d3－P1[2]1－1406030－1P2P2－1111111－1Cj－ZjP2P3－2↑11－1－1－1－211111x31－1/2－1/21/201/23/21/23/21/22080d2－d3－P2－11/2P2－1[1/2]-1/2-1/2110Cj－ZjP2P3P1－2↑11－1111111x3d2－x11－1－21－10[1]313105020P2－1－3201－1－112－2Cj－ZjP2P114－3－221－3x2d2－x11－1[1]－10111102030－3P2－1－1111－10Cj－ZjP2P30111P111131－1111－1x2d1+x1－2－3－1111302030P3－1－111－10Cj－ZjP211P11111－1P3311满意解：X＝〔30,30,0〕〔2〕加入松弛变量x3,初始表基变量为x3、,单纯形法计算如下：Cj002P1x3d1－d1+d2－d2+d3－d3+1P1P20000bx22CB0XBx3x1162d1－d2－d3－P1－1011－1[2]P1P2－1－1124111－1Cj－ZjP21－2211－1[2]x3d1－x2d3－P1－1/2x1d1－－11/21/243130101/211－1－1/2－1/21/20－1/21/21P2－1/21－111Cj－ZjP221/2－1/2－1/2[1/2]011/2220-1/4－13/4－3/4x21－1/41/401/41/422d3－P1P2－1/41－1-1/411Cj－ZjP221/41/4－1/4d2+d1－x2d3－P1－10021143/21/21/21－1531101/2P2－1/2－1-1/211Cj－ZjP2211/21/2满意解：X＝〔0,3〕4.6已知目标规划问题<1>分别用图解法和单纯形法求解；<2>分析目标函数分别变为如下两种情况时解的变化.a>b>〔分析w1、w2的比例变动〕[解]〔1〕图解法〔双击下图,打开幻灯片〕〔1〕单纯形法CjP1x2d1－d1+d2－d2+d3－P4P25P33P3d3+00000bd4－d4+CBP1XBx1d1－d2－d3－111221－1694201－15P33P3－2－11d4－[1]1－1表〔1〕Cj－ZjP2P3P4P1－1－2111－5751311d1－d2－P1－1－2[1]1222505P30－1－22d3－x21－1－28211－1表〔2〕Cj－ZjP1－1－212P21P3P40－5－75101x1－1/21/2－1/213/211/2d4－x23P30－1/4－1/4－11/41/4133/4111/4－1/4－1/45/4表〔5〕P11C－ZjjP2P3P413/41－3/417/43/41满意解为：X＝〔13/2,5/4〕〔2〕a〕,利用上表〔5〕的结果,重新求检验数得到单纯形表如下：CjP1x2d1－d1+d2－d2+d3－P3P25P43P4d3+00000bd4－d4+CB0XBx1x1d1+－1/21/2－1/213/211/2[1]P3－1－113d4－x23P40表〔1〕Cj－ZjP2－1/4－1/4－11/41/413/45/4111/4－1/4－1/4P1111P3－1P4－3/43/417/43/43x1－1/21/2－1/25011/2d2－d4－x203P40表〔2〕Cj－ZjP2－1111－13－1/41/41/4－1/413－13/21/211/4－1/4－1/4P11P3P413/4－3/417/43/4满意解为：X＝〔5,1/2〕〔2〕b>单纯形法.利用问题〔1〕表〔5〕的结果,引入参数w1、w2进行灵敏度分析,得到下表.CjP1P4x1x2d1－d1+d2－P2w1P3d2+－1/2－1w2P3d3+00000bd3－1/2d4－0d4+0CB0基x1d1+－1/213/211/21P4－113d4－x2w2P30－1/4－1/4－11/4[1/4]13/45/411/4－1/4－1/4表〔1〕Cj－ZjP2P111w1-w2/4w2/4P3w2/4－w2/4w2P4011111x1d1+d3－x2－1－1－1－2532P4－111w1P30－1－1－4－1114132表〔2〕Cj－ZjP11P2P3P41－w11w2－4w1w1w14w11－1〔1〕由表〔1〕知,当w1－w2/4>0,即时,满意解为：X＝〔13/2,5/4〕〔2〕当时,表<1>和表<2>都是满意解.〔3〕由表〔2〕知,当w2－4w1>0,即时,满意解为：X＝〔5,2〕4.7思考与简答题〔1〕目标规划与线性规划模型有哪些相同与区别.〔2〕简述正负偏差变量的含义,在模型中起什么作用.〔3〕用单纯形法求解目标规划时,按什么规则选进基变量,在什么时候得到满意解停止计算；〔4〕当期望结果不低于目标值时,为什么目标函数不是求正偏差变量最大而是目标函数求负偏差变量最小.〔5〕图解法时,能否首先分别求各目标的最小值然后取解的交集得到满意解,为什么.返回顶部第5章运输与指派问题5.1用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解．表5-52B11914257B21613308B3105B42124111020B59Ai18301042A1A2A3A4Bj72062341525355表5-53B15B23B38B46Ai162430A1A2A3Bj10172071281594251015[解]双击演示过程→表5-52.Z=824表5-53结果如下,Z=495〔最优值Z=480〕5.2求表5-54及表5-55所示运输问题的最优方案．〔1〕用闭回路法求检验数〔表5-54〕表5-54B1104B25B32B43aiA1A2A3bj708030312564460604020〔2〕用位势法求检验数〔表5-55〕表5-55B19B2151B34B48aiA1A2A3A4bj10302040376210513844320155015解〔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〕〔2〕〔3〕先化为平衡表B11B12B2B31B32B4aiA146469573739M70A2A3A4bj22050884910M300M40M20040M304020180最优解如下表,最优值Z＝6405.4〔1〕建立数学模型设xij<I=1,2,3;j=1,2>为甲、乙、丙三种型号的客车每天发往B1,B2两城市的台班数,则<2>写平衡运价表将第一、二等式两边同除以40,加入松驰变量x13,x23和x33将不等式化为等式,则平衡表为：B1B2B3ai甲乙丙bj8060506550400005101510155为了平衡表简单,故表中运价没有乘以40,最优解不变〔3〕最优调度方案：即甲第天发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.12345ai1234bj11.151.25MM401.31.40.87M1.451.551.020.988000003065656565MMM5060<3>用表上作业法,最优生产方案如下表：12345ai123501525601056530656565465Bi5040608030上表表明：一月份生产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产品2产品3产品4工厂1工厂2工厂3工厂458138540104075658210014011045051060092010001120用匈牙利法得到最优表第一个工厂加工产品1,第二工厂加工产品4,第三个工厂加工产品3,第四个工厂加工产品2；总成本Z＝1000×<58＋920＋510＋110>＝1598000注：结果与例5.15的第2个方案相同,但并不意味着"某列〔行〕同乘以一个非负元素后最优解不变"结论成立.5.7求解下列最小值的指派问题,其中第〔2〕题某人要作两项工作,其余3人每人做一项工作．〔1〕[解]最优解〔2〕[解]虚拟一个人,其效率取4人中最好的,构造效率表为12345甲乙丙丁2625202238333031414447455259565327212520最优解：,最优值Z=165甲～戊完成工作的顺序为3、5、1、2、4,最优分配方案：甲完成第3、4两项工作,乙完成第5项工作,丙完成第1项工作,丁完成第2项工作.5.8求解下列最大值的指派问题：〔1〕[解]最优解〔2〕[解]最优解第5人不安排工作或第1人不安排工作.表5-57成绩表<分钟>游泳自行车长跑登山甲乙丙丁戊20151819174333424434332838323029262927285.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.返回顶部第6章网络模型6.1如图6－42所示,建立求最小部分树的0－1整数规划数学模型.[解]边[i,j]的长度记为cij,设数学模型为：6.2如图6－43所示,建立求v1到v6的最短路问题的0－1整数规划数学模型.[解]弧<i,j>的长度记为cij,设数学模型为：6.3如图6－43所示,建立求v1到v6的最大流问题的线性规划数学模型.[解]设xij为弧〔i,j〕的流量,数学模型为6.4求图6－41的最小部分树.图6-41〔a〕用破圈法,图6-41〔b〕用加边法.图6－44[解]图6-44〔a〕,该题有4个解,最小树长为22,其中一个解如下图所示.图6-44〔b〕,最小树长为20.最小树如下图所示.6.5某乡政府计划未来3年内,对所管辖的10个村要达到村与村之间都有水泥公路相通的目标.根据勘测,10个村之间修建公路的费用如表6-20所示.乡镇府如何选择修建公路的路线使总成本最低.表6-20两村庄之间修建公路的费用<万元>211234567891034567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.910.513.414.69.110.512.68.98.211.713.69.78.8[解]属于最小树问题.用加边法,得到下图所示的方案.最低总成本74.3万元.6.6在图6－45中,求A到H、I的最短路及最短路长,并对图<a>和<b>的结果进行比较.图6－45[解]图6－45<a>:A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路长22；A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路长21.对于图6－45<b>：A到H的最短路PAH={A,C,G,F,H},最短路长21；A到I的最短路PAI={A,C,G,F,I},最短路长20；结果显示有向图与无向图的结果可能不一样.6.7已知某设备可继续使用5年,也可以在每年年末卖掉重新购置新设备.已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元.使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元.试确定一个设备更新策略,使5年的设备购置和维护总费用最小.[解]设点vj为第j年年初购置新设备的状态,〔i,j〕为第i年年初购置新设备使用到第j年年初,弧的权为对应的费用〔购置费＋维护费〕,绘制网络图并计算,结果见下图所示.总费用最小的设备更新方案为：第一种方案,第1年购置一台设备使用到第5年年末；第二种方案,第1年购置一台设备使用到第2年年末,第3年年初更新后使用到第5年年末.总费用为11.5万元.6.8图6－46是世界某6大城市之间的航线,边上的数字为票价〔百美元〕,用Floyd算法设计任意两城市之间票价最便宜的路线表.[解]教师可利用模板求解：data\chpt6\ch6.xlsL1v1v2v3v4v5v6v108.895.686v28.801051004.841003530121001004.81204141009v39v45.6v5v6861490L2v1v2v3v4v5v6v108.80851348.68034.8145.65307.898134.87.806414990v28.8v38.6v45.6v5v6869L3v1v2v3v4v5v6v108.80851348.68034.8125.65307.898134.87.806412990v28.8v38.6v45.6v5v6869最优票价表：v1v2v3v4v5v6v1v2v3v4v5v608.808.6805.65386412990134.87.800v1、v2、…、v6到各点的最优路线图分别为：6.9设图6－46是某汽车公司的6个零配件加工厂,边上的数字为两点间的距离<km>.现要在6个工厂中选一个建装配车间.〔1〕应选那个工厂使零配件的运输最方便.〔2〕装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨,运价为2元/吨公里.应选那个工厂使总运费最小.[解]<1>利用习题6.8表L3的结果v10v28.8085v38.6803v45.6530v58134.87.80v664129Max8.812.812912.812v1v28.8v38.6v45.686v5v61344.8127.89909选第1个工厂最好.<2>计算单件产品的运价,见下表最后一行.计算单件产品的运费,见下表最后一列.单件产品运费v1v2v3v4v5v6v1v2v3v4v5v608.80851348.6805.65307.898684.8889.1682.1671.9681.9282.28.88.65.6861134.87.8093.241299034.8121.6运价1.22.63.4选第4个工厂最好.6.10如图6－47,〔1〕求v1到v10的最大流及最大流量；〔2〕求最小割集和最小割量.[解]给出初始流如下第一轮标号：得到一条增广链,调整量等于5,如下图所示调整流量.第二轮标号：得到一条增广链,调整量等于2,如下图所示调整流量.第三轮标号：得到一条增广链,调整量等于3,如下图所示调整流量.第四轮标号：不存在增广链,最大流量等于45,如下图所示取,最小截集{<3,7>,<4,7>,<6,9>,<8,10>,最小截量等于45.6.11将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2,中途有2个加压站B1、B2,天然气管线如图6－48所示.输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上<cij,dij>.求<1>流量为22的最小费用流；〔2〕最小费用最大流.图6－48[解]虚拟一个发点和一个收点T6.11－1得到流量v＝22的最小费用流,最小费用为271.求解过程参看习题部分答案PPT文档.T6.11－13最小费用最大流如下图,最大流量等于27,总费用等于351.6.12如图6－46所示,〔1〕求解旅行售货员问题；〔2〕求解中国邮路问题.图6-46[解]〔1〕旅行售货员问题.距离表C1∞8.895.68628.8∞1053910∞34.81445.653∞58∞4.812∞66414∞9123456∞412∞9∞在C中行列分别减除对应行列中的最小数,得到距离表C1.距离表C11∞2.840.61.2023.2∞72∞033.46∞040150.6∞07.2∞60.4011∞1234560∞7.2∞0109∞3.2由距离表C1,v1到v4,H1={v1,v4,v3,v5,v6,v2,v1},C<H1>=5.6+3+4.8+9+4+8.8=35.2去掉第1行第四列,d41=∞,得到距离表C2.得到距离表C212.84∞1.202∞72∞036∞00105∞07.2∞3.26011∞923456∞距离表C2的每行每列都有零,H2=H1={v1,v4,v3,v5,v6,v2,v1}就是总距离最小的Hamilton回路,C<H1>=35.2.<2>中国邮路问题.虚拟一条边取回路H1＝{v1,v3,v4},C<H1>=9+5+3=17,C<v1,v3>=9>C<H1>/2,调整回路.所有回路满足最短回路的准则,上图是最短的欧拉回路,其中边<v1,v4>和<v4,v3>各重复一次.6.13思考与简答题〔1〕运筹学研究的图有哪些特征.〔2〕什么是树形图.〔3〕简述求有向图最短路的Dijkstra算法的基本步骤.〔4〕Dijkstra算法在求有向图与无向图最短路时有什么不同.〔5〕什么是网络最大流问题？最大流与最大流量有何区别.〔6〕简述最大流问题Ford-Fulkerson标号算法的基本思路.〔7〕求最小树有哪几种方法,分别简述各种方法的求解思路.〔8〕简述增广链的含义.〔9〕什么是最小割集,最小割集的经济含义是什么.返回顶部第7章网络计划7.1<1>分别用节点法和箭线法绘制表7-16的项目网络图,并填写表中的紧前工序.<2>用箭线法绘制表7-17的项目网络图,并填写表中的紧后工序表7-16工序ABCDEFG紧前工序－－－AA、C－B、D、E、F紧后工序D,EGEGGG－表7-17工序紧前工序A-B-C-DBEBA,BFGBHD,GC,E,F,HD,GC,EIJ,K,LIJKLM紧后工序FE,D,F,GI,KH,JI,KIH,JILMMM－[解]〔1〕节点图：箭线图：〔2〕节点图：箭线图：7.2根据项目工序明细表7-18：〔1〕画出网络图.〔2〕计算工序的最早开始、最迟开始时间和总时差.〔3〕找出关键路线和关键工序.表7-18工序A-BACADECFG紧前工序工序时间〔周〕B,CD,ED,E961219678[解]<1>网络图<2>网络参数工序A00B9156C990D21210EF40411G40400最早开始最迟开始总时差2134130<3>关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A、C、D、G；完工期：48周.7.3表7-19给出了项目的工序明细表.表7-19工序ABCDEFGHIJKLMN紧前工序---A,BBB,CED,GEEHF,JI,K,LF,J,L工序时间<天8571281716814510231512>〔1〕绘制项目网络图.〔2〕在网络图上求工序的最早开始、最迟开始时间.〔3〕用表格表示工序的最早最迟开始和完成时间、总时差和自由时差.〔4〕找出所有关键路线及对应的关键工序.〔5〕求项目的完工期.[解]<1>网络图〔2〕工序最早开始、最迟开始时间〔3〕用表格表示工序的最早最迟开始和完成时间、总时差和自由时差工序tTESTEFTLSTLF总时差S自由时差FA8571281716800085713291313857201324293727189071757132933191757291324293747249009000020600090000BCDEFGHI145206JKLMN102315123724474747476259372447504747626200030003<4>关键路线及对应的关键工序关键路线有两条,第一条：①→②→⑤→⑥→⑦→→；关键工序：B,E,G,H,K,M第二条：①→④→⑧→⑨→〔5〕项目的完工期为62天.→；关键工序：C,F,L,M7.4已知项目各工序的三种估计时间如表7-20所示.求：表7-20工序的三种时间〔小时〕工序紧前工序ambABCDEF－AABB,CD,E961381591081591712121016112014〔1〕绘制网络图并计算各工序的期望时间和方差.〔2〕关键工序和关键路线.〔3〕项目完工时间的期望值.〔4〕假设完工期服从正态分布,项目在56小时内完工的概率是多少.〔5〕使完工的概率为0.98,最少需要多长时间.[解]〔1〕网络图紧前工序工序的三种时间〔小时〕工序期望值方差ambABCDEF－AABB,CD,E96138159108159171212101611201410.1780.444414.839.16717.170.694411.830.69440.250.250.25<2>关键工序：A,C,E,F；关键路线：①→②→④→⑤→⑥<3>项目完工时间的期望值：10.17+14.83+17.17+11.83＝54<小时>完工期的方差为0.25+0.25+0.6944+0.6944＝1.8889<4>X0=56,56天内完工的概率为0.927<5>p=0.98,要使完工期的概率达到0.98,则至少需要56.82小时.7.5表7-21给出了工序的正常、应急的时间和成本.表7-21时间的最大应急增加成本缩量<天>〔万元/天〕工序紧前工序应急时间<天>成本正常正常1512713141610应急121041110138ABCDEF5010080651208932324325103153AAB,