管理运筹学课后答案

第一章线性规划及单纯形法1用XJ（J125）分别代表5中饲料的采购数，线性规划模型123453412MIN070086751,0JZXXXSTX582解设123456XX表示在第I个时期初开始工作的护士人数，Z表示所需的总人数，则34561623456MIN0701,23IZXSTXX3解设用I1，2，3分别表示商品A，B，C，J1，2，3分别代表前，中，后舱，XIJ表示装于J舱的I种商品的数量，Z表示总运费收入则12132131231233123131231MAX070606805740586ZXXXSTXX31231312321305860586,IJXXXXXJ5（1）Z4（2）1212MAX607538ZSTX解如图由图可得0,66TZ；即该问题具有唯一最优解10,TX（3）无可行解41212MAX563,0ZXST如图由图知，该问题具有无界解。6（1）“123456“123456“12345MAX0214ZXXXSTXX，0（2）“1234“1234“1234MA06ZXXSTXX，071）系数矩阵A36120C2345630812（PP种组合123181450BPB；可构成基。求的基本解，（B，B）4069810116/3307Y1（0，16/3，7/6，0，0，0）T同理Y2（0，10，0，7，0，0）TY3（0，3，0，0，7/2，0）TY4（7/4，4，0，0，0，21/4）TY5（0，0，5/2，8，0，0）TY6（0，0，3/2，0，8，0）TY7（1，0，1/2，0，0，3）TY8（0，0，0，3，5，0）TY9（5/4，0，0，2，0，15/4）TY10（0，3，7/6，0，0，0）TY11（0，0，5/2，8，0，0）TY12（0，0，5/2，3，5，0）TY13（4/3，0，0，0，2，3/4）TY14（0，10，0，7，0，0）TY15（0，3，0，0，7/3，0）TY16（0，0，3/2，0，8，0）T基可行解（每个X值都大于0），（Y3，Y6，Y8，Y12，Y13，Y15，Y16）最优解（Y3，Y6，Y15，Y16）ZMAX3P2P3P4，P2P3P5，P3P4P5，P2P4P5为奇异，只有16个基。解（2）该线性问题最多有2C个基本解。基本解Z基本可行解最优解1X1X2X3X42411/20032/5011/5031/30011/6401/220501/202600118基的定义6235014BX1X2X3所对应的列向量可以构成基B由X1X2X3列向量构成6234N由非基变量对应的向量构成5120（B，B）106234/37/51B对应的基解（13/5，37/5，0，0，3/5）9解（1）由图知1,3/235/2TXZ；单纯形法化为标准形如下1234MA0958,IZXSTC10500CBXBX1X2X3XRB0X3341090XR52018检验数1050000X3014/513/521/510X112/501/58/5检验数0102165X2015/143/143/210X1101/73/70检验数005/1425/1435/2所以,3/35/2TXZ；其中0,8/,132ABC对应对应T对应（,98（/5021/,（,392）A点最大Z8化为标准形1234MAX03515,IZXST460点（0，0，15，24）A点（4，0，3，0）ZMAX810解1）要使A（0，0）成为最优解则需C0且D0；2）要使B（8/5，0）成为最优解则C0且D0或C0且D0；3）要使C（1，3/2）成为最优解则5/2C/D3/4且CD0；即5/2C/D3/4且CD0；4）要使D（0，9/4）成为最优解则C0或C0，D0111化为标准型1234123MAX6012,5,JZXSTXIC211000CBXBX1X2X3X4X5X6B0X4311100600X5112010100X611100120检验数21100000X4045130302X1112010100X602301110检验数013020200X4001112102X1101/201/21/2151X2013/201/21/25检验数003/203/21/225,TXZ5，；5C2100CBXBX1X2X3X4B0X33510150X4620124检验数21000X30411/23X111/301/64检验数0101/38（2）1234567132MAX12864,70IZXXSTXX6700C2350000CBXBX1X2X3X4X5X6X7B0X42231000120X5122010080X64060010160X7043000112检验数235000000X4020101/2040X51/320011/303/85X32/301001/603/80X7240001/214检验数4/330005/6040/30X4100101/41/220X52/300011/121/22/35X32/301001/608/33X21/210001/81/41检验数1/6000011/243/449/30X400012/31/81/412X110002/31/83/415X3001011/41/223X201003/43/161/83/2检验数00001/47/165/833/2,/3/TXZ，；（3）标准型12312MA548,35,0IZXSTXC35000BCBXBX1X2X3X4X50X31010040X402010120X53200118检验数350000X3101004X20101/206X5300116检验数3005/2030X30011/31/32X20101/206X11001/31/32检验数0003/2136TXZ，6；（4）标准型“12345678910“467“12368“592310“145MA2ZXXXMXXSTXXX，“678910X，C111111111MMM0CBXBX1X2X3X4X4“X5X5“X6X6“X7X8X9X10BMX710011001110009MX831400002201002MX912001122001060X10043000000000112检验数5M1M112MM11MM11M5M115M000017MMX701/34/311001/31/311/30028/31X111/34/300002/32/301/3002/3MX901/310/300114/34/301/31016/30X10043000000000112检验数04/32/3M14/5M7/3M11MM1M15/3M1/35/3M1/305/3M1/30041/3M2/3MX701/50112/52/51/51/511/52/5031/51X111/50002/52/56/56/501/52/5014/51X301/101003/103/102/52/501/103/1008/50X10043/100009/109/106/56/503/109/10136/5检验数01/5M11/100M11M2/5M17/102/5M17/103/51/5M1/5M3/506/5M7/5M031M/522/5（5）1234123MAX60851,40JZXXSTX解标准化1234561237MA685210,4,JZXSTXC62108000CBXBX1X2X3X4X5X6X7B0X55644100200X63328010250X7421300110检验数6210800000X521208114600X65102002510X3421300110检验数342202200101000X5110012120702X25102012510X3601702320检验数76006602234210由表可得，7KP且因此问题的解无界。（6）化为标准形ZZ1234623MAX51,0IZXSTX6（I）CX11000CBXBX1X2X3X4X5X6BXX110040251X201023131X30012565检验数00044X872X5X8401727/23XX如图11X7/2时，检验数0，最优解（5，3，5，0，0）T221X0由（I）得CX11000CBXBX1X2X3X4X5X6BXX1101/310/35/3020/31X2011/65/313/6013/60X6001/61/35/615/6检验数00X/37/610X/35/35X/313/6020X/313/6/365/2/36TXZX，；3X2X70CX11000CBXBX1X2X3X4X5X6BXX1120060111X201/2013/21/23/21X30110252检验数02X2006X2511X2检验数0，列系数0，所以解无界。43/2X44X0CX11000CBXBX1X2X3X4X5X6BXX110010/35/3020/31X20105/313/6013/61X60011/35/615/6检验数X/37/610X/35/35X/313/620X/313/6判断检验数的符号10/3501/2630/316XXX11/2X0又X5列的系数0，又X5的列的系数第二章线性规划的对偶理论1解设123X，分别表示A、B、C各产品的数量，Z表示总产值则23123MA05046,0IZXSTXMIN6042035WYYSTYY原问题的对偶问题为320，经济解释Y1，Y2，Y3分别表示给别人代工时所得收入，对厂方而言，W越大越好，但定价不能太高，要对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理，厂方不会吃亏，对方也容易接受。21MIN02YSTY0，2AX3524760WYSTYY50，3MIN3845760WSTYY2自由，AX325740WSTYYY30，3证明0X是线性问题的可行解，即该问题存在可行解；又其对偶问题为MIN210,21WYSTYY，这与约束条件（）不符该对偶问题无可行解原问题无最优解。4证明该线性问题的对偶问题为0MIN21012,MAXTWYSTYYYCYBZ，自由，易知（，）是对偶问题的一个可行解，由对偶问题的对偶定理可得即最大值不超过115证明对偶问题IN432023WYYSTT0，由题易知X（，）是原问题的一个可行解，Y（，1，）是对偶问题的一个可行解由对偶问题的推论可得它们都有最优解。即得证。771）对偶问题MIN534WYSTY20，无符号限制2）由题知原问题的最优解为320TX，；由互补松弛定理得在对偶问题中对应第一，二个约束为紧，第三个约束条件为松，即，121212434YY对偶规划问题的最优解1（，）3）影子价格为Y148解先写出其对偶问题。MIN2018324WSTYY0，对偶规划问题的最优解1121200XY，代入约束条件，知第，约束条件成立严格不等式，由互补松弛定理，原规划最优解中相应变量又，不为，则在原问题规划中对应的约束条件为紧，得3344XX原对偶规划问题的最优解0,4（）91MIN362860WYYSTYY442344（）0，567821032216102TZXXXYYYYYWT488（）（，）；把（1，2，）代入约束条件可得，；（，）；10解1212/2061/2002063131/XNBBANB0（）由表知；3令则131322025/2506/4634ACC1；B（，）（，）（，）1233MAX0,IZXST原线性问题为652N513620WYSTY（），45353/4024TXZYYY24T（），；6即10（，）W；11解（1）设123X，分别表示甲、乙、丙各产品的数量，Z表示总产值则123MA405,IZSTX化为标准形12345MAX0,IZXST，C32100CBXBX1X2X3X4X5B0X4121104000X521201500检验数321000X403/2011/21503X111/2101/2250检验数01/2203/22502X20102/31/31003X11011/32/3200检验数0021/34/3800,8TXZ；2MIN45321WYSTY（）原问题的对偶问题为0，此时，Y1，Y2分别表示出租A，B设备所得利润，由（1）中的最优表得1Y1/3，即如出租A设备可获得1000/3元，而1000/320/3最优解将发生变化。C251300CBXBX1X2X3X4X5B5X211310200X514124120检验数002501005X211310200X51505510检验数00250100C1064000CBXBX1X2X3X4X5X6B6X2015/65/31/60200/310X1101/62/31/60100/30X60044/501100检验数008/310/32/3010/3,020/3TXZ，2/；1MAX4IN56,C（）（4）新产品的生产数量为7X77718,1,43810/3,2405/6024/139/5TCP则有C10640008CBXBX1X2X3X4X5X6X7B6X2015/65/31/601200/310X1101/62/31/600100/30X60044/50119/5100检验数008/310/32/3022200/36X20125/11483/571/65/1902300/5710X1101/62/31/600100/38X70020/94/1905/191500/19检验数00544/114214/572/310/19027700/571/3,5/927/5TXZ，2/7；值得安排生产；（5）设生产I产品X1件，生产II产品X2件，III产品10X1件3213MA06405,IZXSTX3124536MAX0902,IZXSTXC1064000B6X20103/21/65/24275/610X11007/101/31/24175/650/6X30011/501/42500011/32/35/122350/3CBXBX1X2X3X4X5X60X4111100900X510450105500X6226001240检验数10640000X403/51/211/1003510X112/51/201/100550X606/5501/51130检验数0210106X2015/65/31/602175/310X1101/62/31/6095/30X600420160检验数008/310/32/302000/395/3,2/314TXZ，7/；即当，1；满足合同规定19解设生产ABC产品的数量分别为X1X2X3则123MA46540,IZXST3312MAX56440,IZXSTC41500CBXBX1X2X3X4X5B0X463510450X53450130检验数415000X421011155X33/54/5101/56检验数130014X111/301/31/355X30111/32/53检验数08/301/32/335,TXZ，；112MAIN236C（），6666325,3,251/,1/602/31/152TCPP（）设新产品D的数量为X则有C32100BCBXBX1X2X3X4X5X64X111/301/31/31/355X30111/52/51/53检验数08/301/32/31/6355/2X36310111155X33/56/512/53/500检验数1/25/201/21/207/20,575/2TXZ，；即该计划值得投产且，只生产D产品15件最有利。第三章运输问题1初始解的个数为MN1表336初始解个数5；MN16所以不能。表337初始解个数10；MN19所以不能。3（340）用最大差额法销地产地甲乙丙丁行差额1376411422432002343851111132112列差额21得初始解，并计算位势和检验数检验数IJR不全非负，没达到最优解,用闭回路法VJ3754UI销地产地甲乙丙丁产量013025222024333销量3322销地产地甲乙丙丁112113575VJ3754检验数最优解Z337042042333323（341）最小元素法，初始方案，闭回路法得，再用闭回路法得，所有检验数非负ZMIN1036271539662130（342）表中供大于求，虚设一销售点销地产地甲乙丙丁戊己产量11020591005UI销地产地甲乙丙丁013370642222403224343385销地产地甲乙丙丁102213565VJ108812UI销地产地甲乙丙丁产量011036271121432169105549594362421061024销量5246VJUI106812010362711213169107549546242106102VJUI1068120103627112216105396462410102210830603120710404863750629销量446242最大差额法销地产地甲乙丙丁戊己行差110205910022108306031207104048637505221135列差142210得VJ285960UI销地产地甲乙丙丁戊己011082012539010020224101283302162002311201470103420224886433725102检验数非负，ZMIN53022462004264337241）最优调运方案不变，则检验数还非负。VJ13C22110C2211UI销地产地B1B2B3B40A110C2231520C22101110C221A2120C22109152010C22C2211A3251429C2216171818C22解不等式21IJR2）非基变量检验数有一个为0，基变量检验数都为0112243122331406479UUVVU令非基变量检验数为132424340671638RCR（）（）（）（）（）（）240,172令R即，AB当的单位运价变为时，有无穷多最优调运方案。闭回路法进行调整1以（A2B4）点为起点，销地产地B1B2B3B4A110115201110A2120791517A3251016182以A3B2点为起点，销地产地B1B2B3B4A11015201110A21257591517A321051618第五章整数规划1、用图解法求解下列整数规划2156MAXXZST921X3572且为整数0,解作图得如图最优解为（4,1），最优值为29。2、使用分枝定界法求解下列整数规划1215MAXXZST3且为整数0,21解计算结果见图52，由分枝定界法可知该整数规划的最优解为X14，X20，Z20。22154MAXZST73且为整数0,21X且为整数解计算结果见图53，由分枝定界法可知该整数规划的最优解为X10，X23，Z15。45795X1X2LP（1）X135X225Z1205LP（2）X1367X21Z2203LP（3）X13X22Z319LP（5）X14X20Z520LP（4）X13X21Z417X21X22X13X14剪去剪去不再分枝0320ZZ205剪去图52不再分枝图533、一公司考虑在四个城市北京、上海、广州和表512华北华中华南北京上海广州武汉20030060030040025040015050045025035015ZLP（1）X104X229Z1163LP（2）X10X23Z215LP（3）X11X22Z314X10X11剪去Z163武汉设立库房这些库房负责向三个地区华北、华中和华南地区发运货物，每个库房每月可处理货物1000件，在北京设库房每月的成本为45万元，上海为5万元，广州为7万元，武汉为4万元每个地区的月平均需求量为华北为每月600件，华中每月700件，华南每月800件发运货物的费用（元/件）见表512公司希望在满足地区需求的前提下使平均月成本最小，且还要满足以下条件1如果在上海设库房，则必须也在武汉设库房；2最多设立三个库房；3武汉和广州不能同时设立库房请写一个满足上述要求的整数规划模型解设XIJ为从第I个库房发运到第J个地区的货物量，其中I1、2、3、4分别代表北京、上海、广州和武汉，J1、2、3分别代表华北、华中和华南，CIJ表示从第I个库房发运到第J个地区的货物的单位费用。、I01IY则该问题的数学模型为MINZ41413CIIJIJIYXST1、231234I0,0Y432108760423143124、IIJIJIIIIIYXXX4、考虑资金分配问题，在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用（千元）如表513假定每一项已经批准的工程要在整个3个内完成，目标是要选出使总收入达到最大的那些工程把这个问题表示成一个01整数规划模型解设、I01IX（I1、2、3、4、5）则该问题的数学模型为MIN20X140X220X315X430X5ST1、2345I0086978521、IXXX5、用割平面法求解下列整数规划12197MAXXZST635且为整数0,21解先化成标准形并用单纯形法求得CJ7900CBXBX1X2X3X4B0X3131060X4710135检验数790009X21/311/3020X422/301/3133检验数10030189X2017/221/227/2表513工程费用（千元）收入（千元）12312345543781794681021102040201530最大的可用基金数（千元）2525257X1101/223/229/2检验数0028/1115/1163由于松弛问题的最优解不是整数故构造源于X2所在行的割平面并加入到最优单纯形表中迭代得CJ79000BCBXBX1X2X3X4X59X2017/221/2207/27X1101/223/2209/20X5007/221/2211/2检验数0028/1115/110639X20100137X11001/71/732/70X30011/722/711/7检验数0001861构造源于X1所在行的割平面并加入到上表进行迭代得CJ790000BCBXBX1X2X3X4X5X69X201001037X11001/71/7032/70X30011/722/7011/70X60001/76/714/7检验数000180619X201001037X110001140X300104110X40001674检验数00002755由此得原IP问题的最优解为X14,X23,最优值为55。23216MAXZST54321X且为整数0,解先化成标准形并用单纯形法求得CJ462000CBXBX1X2X3X4X5X6B0X444010050X516001052X31110015检验数640002104X11101/4005/40X50501/41025/42X30011/40125/4检验数01003/20235/2CJ462000CBXBX1X2X3X4X5X6BJ4X11003/101/505/26X20101/201/505/42X30011/40125/4检验数00022230由于松弛问题的最优解不是整数故构造源于X1所在行的割平面并加入到最优单纯形表中迭代得CJ4620000BJCBXBX1X2X3X4X5X6X74X11003/101/5005/26X20101/201/5005/42X30011/401025/40X70003/101/5011/2检验数0002220304X1100000126X201001/601/67/62X300101/615/635/60X400012/3010/35/3检验数00002/3220/380/3构造源于X3所在行的割平面并加入到最优单纯形表中迭代得CJ46200000BJCBXBX1X2X3X4X5X6X7X84X1100000105/26X201001/601/605/42X300101/615/6025/40X400012/3010/301/20X800005/605/615/6检验数00002/3220/380/34X11000001026X201000001/512X300100111/560X400010044/510X500001016/51检验数00000264/526由此得原IP问题的最优解为X12,X21，X36,最优值为26。6、用完全枚举法求解下列01规划问题53MAZST2314X26310,1或解列表得由表可知原01规划的最优解为（1,0,1）,最优值为8。7、用隐枚举法求解下列01规划问题1324MAXXZST451032,或X解化成标准形令X11X1,X21X2,X31X3得94MAZST5约束条件X1,X2,X3过滤条件约束1约束2约束3约束4目标值Z（0,0,0）（0,0,1）（0,1,0）（0,1,1）（1,0,0）（1,0,1）（1,1,0）（1,1,1）058表5453421XX0,3、经检验零点（0，0，0）是可行解，因此该01规划的最优解为（X1,X2,X3）1,1,1,最优解为9。2543215MAXZST673X0X,0JJ或解化成标准形令X11X1,X31X3,X51X5得142AZST87X254321,0JXJ、改变变量的顺序得145MA2453XZST837152X,0JJ、经检验零点（21453,）（0,0,0,0,0）不是可行解，但目标函数值Z的上界为Z11选择3X为固定变量，则原问题分成两枝，一枝为问题1（3X1），另一枝为问题2（0）问题116234MAX145XZST214532XX5,104,210JXJXJJ、问题2301234MAX45XZST815012Z113X13X0图54542215XX,10,0JJJJ、得两试点（1,0,0,0,0）和（0,0,0,0,0），如图54但试点、都不是可行解选上界大的未探明分枝先分枝选5X为固定变量，则从点分出两枝问题3和问题4，得两试点（0,1,0,0,0）和试点（0,0,0,0,0），如图55问题351723MAX14XZST1420,01、JJ问题（4）5X03A214XZST850,01、JXJ分别对分枝、进行检查经检查点都不是可行解。选上界大的未探明分枝先分枝选4X为固定变量，则从点分出两枝问题5和问题6，得两试点（0,0,1,0,0）和试点（0,0,0,0,0），如图56问题54X182MAX1XZST31201、问题64X0A2XZST83215102、X别对分枝进行检查经