运筹学答案熊伟

运筹学习题答案119设线性规划4,1,062453MAX121JXXZJ取基分别指出对应的基变量3210P041BB，、，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分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点11212MAX3,0Z【解】图解法单纯形法CJ1300CIBASISX1X2X3X4BRATIO0X32110220X42301124CJZJ130003X221102M运筹学习题答案20X480316075CJZJ703063X2010250257/21X110037501253/4CJZJ00037508751125对应的顶点基可行解可行域的顶点X1（0，0，2，12）、X2（0，2，0，6，）、X3（、,743（0，0）（0，2）7,43最优解52,Z2121212MIN35640,XX【解】图解法单纯形法CJ35000BASISCIX1X2X3X4X5BRATIOX301210063运筹学习题答案3X40140101025X501100144CJZJ350000X30050105012X250251002502510X50075000251152CJZJ175001250125X13102102MX25010505024X50001505100CJZJ003505016X13101022X25011012X40003120CJZJ0020116对应的顶点基可行解可行域的顶点X1（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）运筹学习题答案4最优解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/2运筹学习题答案5212341234MAX557060,JZXX【解】单纯形表CJ2135000BASISCIX1X2X3X4X5X6X7RHSRATIOX50153710030MX6031110101010X702614001205CJZJ2135000X509/211/25/40107/465MX605/21/25/40011/4510X451/23/21/41001/45MCJZJ1/217/27/40005/4运筹学习题答案6X503201501111120MX21515/20021/21010X45807/21031/220MCJZJ4302300173因为730并且AI70,原问题无可行解。两阶段法第一阶段数学模型为7124567MIN53910,JZXXCJ000001RHSRATIOBASISCIX1X2X4X5X6X7X40531000918X5056010015MX71210011525运筹学习题答案17CJZJ210010514X1013/51/50009/5X5009110024X7101/52/50117/5CJZJ01/52/5010因为X70,原问题无可行解。图解法如下41234123413MAX950,4JZXXX【解】大M法。数学模型为运筹学习题答案181234910123456107813MAX0,2,JZXMXXXXCJ2311MMMRHSRATIOBASISCIX1X2X3X4X5X6X7X8X9X10X11X9M112111945X6211155X10M213111103333X11M111133CJZJ2311BIGM426111X9M1/31/316712/312/38335X62/32332/311/31/3467M运筹学习题答案19X312/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/511212X41105050505050555M运筹学习题答案20X6315105551505552504545X3111113MX231105052505052525MCJZJ12712710BIGM111X41027100064009045064045573MX8055027018009100027009100045MX3104510002701800902700934576X23036100018045027018027364MCJ38091313运筹学习题答案21ZJ21127136091618BIGM111X413/51081/504080478MX8123/5041/513/51/5146MX121223/5041/53/51/576MX23108043/51/5041/564MCJZJ8432283/5323/5422BIGM111无界解。两阶段法。第一阶段CJ111BASISCIX1X2X3X4X5X6X7X8X9X10X11RHSRATIOX9111211199/2运筹学习题答案22X6211155X10121311111/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/11X33/52/511/51/51/51/52M运筹学习题答案23X1112/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/11运筹学习题答案24X311113MX23111/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/5M运筹学习题答案25X86/53/52/51/5123/5MX12111/53/52/51/538/5MX2314/52/53/51/532/5MCJZJ42/516/514/53/5422原问题无界解。113在第19题中，对于基求所有变量的检验数B2140,并判断B是不是最优基J14【解】,104,2B10231045,1595,20,0,424BCAB不是最优基，可以证明B是可行基。950,24114已知线性规划运筹学习题答案2612341234MAX587030,JZXX的最优基为，试用矩阵公式求（1）最优解；2单B5纯形乘子；34N3及；13和。【解】则142534,82BBCC11455,0,02TTTBXXBXZ最优解2,1C31132531244534412NBP4113345,8502347,87012BBCCNC注该题有多重解X10，5，0，5/2运筹学习题答案27X20，10/3，10/3，0X310，0，0，0，X2是基变量，X3是退化基本可行解Z50115已知某线性规划的单纯形表125,求价值系数向量C及目标函数值Z表125CJC1C2C3C4C5C6C7CBXBX1X2X3X4X5X6X7B3X4012130244X1101020100X601404123/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及表126CJC1C2C3C4C5CBXBX1X2X3X4X5BC1X11041/61/156C2X201301/52运筹学习题答案28J00123【解】，C4C50，16265,5B仿照第15题方法可求出C112，C211，C314由1A得6204605351B由1B得0210则有，623022,14,51CAB16265,050B117已知线性规划的单纯形表127表127CJ3A11CBXBX1X2X3X4B1X32210B11X43101B2J1234当（）,（）,A（）时，BB为唯一最优解,021X当（）,（）,A（）时，有多重解，2此时（）【解】1B10,B20,A5时X4进基X2出基，用单纯形法计算。参数变化与目标值变化的关系如下表所示。FROMTOFROMTOLEAVINGENTERINGRANGEVECTORVECTOROBJVALUEOBJVALUESLOPEVARIABLEVARIABLE10527525X2X425M52M83015271955X1X3415M195M3目标值变化如下图所示。运筹学习题答案44（2）0,2183645MAX21121XXZ【解】0时最优解X4,3,0，Z27；最优表CJ35000BASISCIX1X2X3X4X5RHSX13101004X250100503X50003110CJZJ0032502746182B0,Z275,Z5215,Z1950运筹学习题答案451140352105BBBB替换最优表的右端常数，得到下表。CJ35000BASISCIX1X2X3X4X5RHSX13101004X250100503X50003115CJZJ0032500时X5出基X3进基得到下表CJ35000BASISCIX1X2X3X4X5RHSX131001/31/342/3X250101/203X300011/31/35/3CJZJ0003/2106时为最优解。6时Z15。6时X1出基X4进基得到下表运筹学习题答案46CJ35000BASISCIX1X2X3X4X5RHSX4030011122X253/21001/29X30101004CJZJ9时最优解X0，0，13，6，0，Z0；9时无可行解。综合分析如下表所示。FROMTOFROMTOLEAVINGENTERINGRANGEVECTORVECTOROBJVALUEOBJVALUESLOPEVARIABLEVARIABLE10027273X5X320627152X1X23691505X249INFINITYINFEASIBLE50427153X164INFINITYINFEASIBLE运筹学习题答案47目标值变化如下图所示。习题四41工厂生产甲、乙两种产品，由、二组人员来生产。组人员熟练工人比较多，工作效率高，成本也高；组人员新手较多工作效率比较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表421所示。表421产品甲产品乙效率件/小时成本元/件效率件/小时成本元/件A组1050845B组845540产品售价元/件8075二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以加班10小时，加班生产的产品每件增加成运筹学习题答案48本5元。工厂根据市场需求、利润及生产能力确定了下列目标顺序P1每周供应市场甲产品400件，乙产品300件P2每周利润指标不低于500元P3两组都尽可能少加班，如必须加班由组优先加班建立此生产计划的数学模型。41【解】解法一设X1,X2分别为A组一周内正常时间生产产品甲、乙的产量，X3,X4分别为A组一周内加班时间生产产品甲、乙的产量；X5,X6分别为B组一周内正常时间生产产品甲、乙的产量，X7,X8分别为B组一周内加班时间生产产品甲、乙的产量。总利润为135713572468246823800073XXXX生产时间为A组123405015XXB组678数学模型为123454673571246821234567835653MIN20030500ZPDPDPDXXXXXD467871012,2,8JIXDIJ解法二设X1,X2分别为A组一周内生产产品甲、乙的正常时间，X3,X4分别为A组一周内生产产品甲、乙的加班时间；X5,X6分别为B组一周内生产产品甲、乙的正常时间，X7,X8分别为B组一周内生产产品甲、乙的加班时间。运筹学习题答案49数学模型请同学们建立。42设XIJ为AI到BJ的运量，数学模型为1234354657683311223314244351233MIN807805ZPDDPDDPDXBADXST保证供应需求的需求的需求的对212216213132734813000,4,12IJIIJIBXXDCDXJDI对与的平衡运费最小43双击下图，打开幻灯片。习题4313,210,468MIN21312132IDXPZI3X11020304050102030405021D1DDX2A50/3,20/3B3,满意解在线段上AB44已知某实际问题的线性规划模型为运筹学习题答案502150MAXXZ,316021X资源资源假定重新确定这个问题的目标为1的值应不低于19002资源必须全部利用将此问题转换为目标规划问题，列出数学模型。【解】数学模型为1221122MIN059063,JJZPDDXD45已知目标规划问题143215MINDPDPDPZ4,10,24296214311IDXXI（1）分别用图解法和单纯形法求解；2分析目标函数分别变为、两种情况时（中分析W1、W2的比例变动）解的变化。35MIN441321DPDDPZ12W运筹学习题答案51【解】（1）图解法（双击下图，打开幻灯片）习题4513X1123451234211D2D3DX2满意解X13/2,5/464123411234MIN569,01,4IZPDPDPXI913/2,5/4（1）单纯形法CJ00P1P40P25P303P30CB基X1X2D1D1D2D2D3D3D4D4BP1D1121160D2121195P3D3121143P3D41112运筹学习题答案52P1121P21P35753表（1）CJZJP41P1D11112220D21112255P3D31112280X21112P11122P21P3575710表（2）CJZJP41运筹学习题答案530X111/21/21/21/20013/2P4D1111133P3D41/41/41/41/4113/40X211/41/41/45/4P11P21P33/43/417/43/43表（5）CJZJP4111B1423121MINDPWDPDPZ单纯形法，利用上表（5）的结果，引入参数W1、W2进行灵敏度分析，得到下表。CJ00P1P40P2W1P30W2P30B运筹学习题答案54CB基X1X2D1D1D2D2D3D3D4D40X111/21/21/21/20013/2P4D111113W2P3D41/41/41/41/4113/40X211/41/41/45/4P11P21P3W2/4W2/4W1W2/4W2/4W2表（1）CJZJP41110X1111225P4D111113W1P3D31111443运筹学习题答案550X21112P11P21P3W1W1W1W24W14W1表（2）CJZJP4111（1）由表（1）知，当W1W2/40，即时，1122,04W满意解为X（13/2，5/4）（2）由表（2）知，当W24W10，即时，1122,满意解为X（5，2）（3）当时，表1和表2都是满意解。1122,04W习题五52用元素差额法直接给出表553及表554下列两个运输问题的近似最优解表553B1B2B3B4B5AIA119161021918A21413524730A3253020112310运筹学习题答案56A478610442BJ152535205表554B1B2B3B4AIA1538616A2107121524A31748930BJ20251015【解】表553。Z824表554Z495运筹学习题答案5753求表555及表556所示运输问题的最优方案（1）用闭回路法求检验数（表555）表555B1B2B3B4AIA11052370A2431280A3564430BJ60604020（2）用位势法求检验数（表556）表556B1B2B3B4AIA19154810A2317630A321013420A4458343运筹学习题答案58BJ20155015【解】（1）254求下列运输问题的最优解（1）C1目标函数求最小值；（2）C2目标函数求最大值运筹学习题答案5913592064873C90361785142C15452040603050403目标函数最小值,B1的需求为30B150,B2的需求为40，B3的需求为20B360,A1不可达A4，B4的需求为305027194836【解】（1）（2）运筹学习题答案60（3）先化为平衡表B11B12B2B31B32B4AIA144977M70A266533220A3885991050A4M0MM0M40BJ302040204030180最优解运筹学习题答案6155（1）建立数学模型设XIJI1,2,3J1,2为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则12123121232123MAX408650504405,1,2IJZXXXXJ2写平衡运价表将第一、二等式两边同除以40，加入松驰变量X13,X23和X33将不等式化为等式，则平衡表为B1B2B3AI甲乙丙80605065504000051015BJ10155为了平衡表简单，故表中运价没有乘以40，最优解不变（3）最优调度方案运筹学习题答案62即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为Z40（5805605501040）54000（元）56（1）设XIJ为第I月生产的产品第J月交货的台数，则此生产计划问题的数学模型为11213142142341234234112323441MIN55098068560,IJZXXMXXXXXXJ,（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。12345AI121M1151251314145155006565运筹学习题答案6334MMMM087M102098006565BJ50406080303用表上作业法，最优生产方案如下表12345AI123450152560105653065656565BI5040608030上表表明一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z235万元。57假设在例515中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案【解】将表535所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000产品1产品2产品3产品4工厂1581385401040工厂275100450920工厂3651405101000工厂4821106001120用匈牙利法得到最优表运筹学习题答案64第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；总成本Z1000589205101101598000注结果与例515的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。58求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作（1）2015686209C【解】最优解1,43XZ（2）20534126701986C【解】虚拟一个人，其效率取4人中最好的，构造效率表运筹学习题答案65为12345甲2638415227乙2533445921丙2030475625丁2231455320戊2030415220最优解甲戊完成工作的顺序为3、5、1、2、4，最优值Z165最优分配方案甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。59求解下列最大值的指派问题（1）261869304570C【解】最优解1,64XZ（2）86917520469C运筹学习题答案66【解】最优解1,41XZ第5人不安排工作。510学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表558所示如何从中选拔一个接力队，使预期的比赛成绩最好【解】设XIJ为第I人参加第J项目的状态，则数学模型为12134541234234124355151123242334MIN0928ZXXXXXXX50,1,4IJIJ或接力队最优组合乙长跑丙游泳表558成绩表分钟游泳自行车长跑登山甲20433329乙15332826丙18423829丁19443227戊17343028运筹学习题答案67丁登山戊自行车甲淘汰。预期时间为107分钟。习题六61如图639所示，建立求最小部分树的01整数规划数学模型。【解】边I，J的长度记为CIJ，设否则包含在最小部分树内边0,1JIXIJ数学模型为,0133,22,5MIN5621525623523444165635332412,JIXXXXXXCZIJJIIJ所有边或62如图640所示，建立求V1到V6的最短路问题的01整数规划数学模型。【解】弧I，J的长度记为CIJ，设否则包含在最短路径中弧0,1JIXIJ图639图640运筹学习题答案68数学模型为,011,MIN5645643524632325412312,JIXXXXCZIJJIIJ所有弧或63如图640所示，建立求V1到V6的最大流问题的线性规划数学模型。【解】设XIJ为弧（I,J）的流量，数学模型为,0MIN5643524312542361JICXXXXZIJIJ所有弧64求图641的最小部分树。图641（A）用破圈法,图641（B）用加边法。图641【解】图641（A），该题有4个解，最小树长为21，其中一个解如下图所示。运筹学习题答案69图641（B），最小树长为20。最小树如下图所示。65某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表620所示。乡镇府如何选择修建公路的路线使总成本最低。表620两村庄之间修建公路的费用万元123456789101231281059857127131391114815132121271389105运筹学习题答案70456789106713811261142867583785968980410593881271486158988211713697134146911051268988【解】属于最小树问题。用加边法，得到下图所示的方案。运筹学习题答案71最低总成本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运筹学习题答案72A到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年年初，弧的权为对应的费用（购置费维护费），绘制网络图并计算，结果见下图所示。运筹学习题答案73总费用最小的设备更新方案为第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为115万元。68图643是世界某6大城市之间的航线，边上的数字为票价（百美元），用FLOYD算法设计任意两城市之间票价最便宜的路线表。【解】教师可利用模板求解DATACHPT6CH6XLSL1V1V2V3V4V5V6V108895686V28801051004V3910034814图643运筹学习题答案74V45653012100V58100481209V6641410090L2V1V2V3V4V5V6V1088865686V288085134V3868034814V456530789V5813487809V66414990L3V1V2V3V4V5V6V1088865686V288085134V3868034812V456530789V5813487809V66412990最优票价表V1V2V3V4V5V6V1088865686运筹学习题答案75V2085134V3034812V40789V509V60V1、V2、V6到各点的最优路线图分别为69设图643是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离KM。现要在6个工厂中选一个建装配车间。（1）应选那个工厂使零配件的运输最方便。（2）装配一辆汽车6个零配件加工厂所提供零件重量分别运筹学习题答案76是05、06、08、13、16和17吨，运价为2元/吨公里。应选那个工厂使总运费最小。【解】1利用习题68表L3的结果MINAX