运筹学课后习题答案

第一章 线性规划及单纯形法1用Xj（j=1.25）分别代表5中饲料的采购数，线性规划模型：2.解：设x表示在第i个时期初开始工作的护士人数，z表示所需的总人数，则3解：设用i=1，2，3分别表示商品A，B，C，j=1，2，3分别代表前，中，后舱，Xij表示装于j舱的i种商品的数量，Z表示总运费收入则：5. （1） Z = 4 （2）解：如图：由图可得：即该问题具有唯一最优解（3）无可行解(4)如图：由图知，该问题具有无界解。6（1）（2）71）系数矩阵A： （B，b）= y1=（0，16/3，-7/6，0，0，0）T同理y2=（0，10，0，-7，0，0）T y3=（0， 3，0，0，7/2，0）T y4=（7/4，-4，0，0，0，21/4）T y5=（0，0，-5/2，8，0，0）T y6=（0，0，3/2，0，8，0）T y7=（1，0，-1/2，0，0，3）T y8=（0，0，0，3，5，0）T y9=（5/4，0，0，-2，0，15/4）T y10=（0， 3，-7/6，0，0，0）T y11=（0，0，-5/2，8，0，0）T y12=（0，0，-5/2，3，5，0）T y13=（4/3，0，0，0，2，3/4）T y14=（0，10，0，-7，0，0）T y15=（0， 3，0，0，7/3，0）T y16=（0，0，3/2，0，8，0）T 基可行解：（每个x值都大于0），（y3，y6，y8，y12，y13，y15，y16） 最优解：（y3，y6， y15，y16） Zmax=3p2 p3 p4，p2 p3 p5，p3 p4 p5，p2 p4 p5为奇异，只有16个基。解：（2）该线性问题最多有个基本解。基本解 Z基本可行解最优解1X1X2X3X42-411/20032/5011/503-1/30011/6401/22050-1/202600118.基的定义 X1 X2 X3所对应的列向量可以构成基 B 由 X1 X2 X3 列向量构成 = N 由 非基变量对应的向量构成 = （B，b）= B对应的基解：（-13/5，37/5，0，0，3/5）9解：（1）由图知： 单纯形法：化为标准形如下：C10500bCBXBX1X2X3XR0X3341090XR52018检验数1050000X3014/51-3/521/510X112/50-1/58/5检验数010-2-165X2015/14-3/143/210X110-1/73/70检验数00-5/14-25/14-35/2所以：其中： 9.2） A点最大 Z= 8 化为标准形：C2-100bCBXBX1X2X3X40X33510150X4620124检验数2-1000X3041-1/23X111/301/64检验数0-10-1/3-8 0点（0，0，15，24） A点（4，0，3，0） Zmax=810.解1）要使A（0，0）成为最优解则需C0且d0； 2）要使B（8/5，0）成为最优解则 C0且d=0或C0且d0； 3）要使C（1，3/2）成为最优解则 -5/2-C/d-3/4且Cd0；即5/2C/d3/4且Cd0；4）要使D（0，9/4）成为最优解则C0或C=0，d011.(1)化为标准型： C2-11000bCBXBX1X2X3X4X5X60X4311100600X51-12010100X611-100120检验数2-1100000X404-51-30302X11-12010100X602-30-1110检验数01-30-20-200X40011-1-2102X1101/201/21/215-1X201-3/20-1/21/25检验数00-3/20-3/2-1/2-25（2）C2350000bCBXBX1X2X3X4X5X6X70X42231000120X5122010080X64060010160X7043000112检验数235000000X402010-1/2040X5-1/32001-1/303/85X32/301001/603/80X7-24000-1/214检验数-4/33000-5/60-40/30X410010-1/4-1/220X52/30001-1/12-1/22/35X32/301001/608/33X2-1/21000-1/81/41检验数1/60000-11/24-3/4-49/30X40001-2/3-1/81/412X110002/3-1/8-3/415X30010-11/41/223X201003/4-3/16-1/83/2检验数0000-1/4-7/16-5/8-33/2（3）标准型：C35000bCBXBX1X2X3X4X50X31010040X402010120X53200118检验数350000X3101004X20101/206X5300-116检验数300-5/20-30X30011/3-1/32X20101/206X1100-1/31/32检验数000-3/2-1-36（4）标准型C-11-1-11-11-11-M-M-M0bCBXBX1X2X3X4X4“X5X5“X6X6“X7X8X9X10-MX71001-1001-110009-MX831-400002-201002-MX91.200-112-2001060X10043000000000112检验数5M-1M+1-1-2MM-11-MM+11+M5M-11-5M000017M-MX70-1/34/31-1001/3-1/31-1/30028/3-1X111/3-4/300002/3-2/301/3002/3-MX90-1/310/300-114/3-4/30-1/31016/30X10043000000000112检验数04/3-2/3M14/5M-7/3M-11-MM-1M+15/3M-1/3-5/3M+1/30-5/3M+1/300-41/3M-2/3-MX70-1/501-12/5-2/5-1/51/51-1/5-2/5031/5-1X111/5000-2/52/56/5-6/501/52/5014/5-1X30-1/10100-3/103/102/5-2/50-1/103/1008/50X10043/100009/10-9/10-6/56/503/10-9/10136/5检验数0-1/5M+11/100M-11-M2/5M-17/10-2/5M+17/103/5-1/5M1/5M-3/50-6/5M-7/5M0-31M/5-22/5（5）解：标准化：C62108000bCBXBX1X2X3X4X5X6X70X556-4-4100200X63-328010250X74-21300110检验数6210800000X521-208114600X6-510200-2510X34-21300110检验数-34220-2200-10-1000X5110012120702X2-510201-2510X3-601702-320检验数7600-660-2234-210由表可得， 因此问题的解无界。（6）化为:标准形：Z=-Z（I）C-x-1-1000bCBXBX1X2X3X4X5X6-XX1100-40-25-1X20102-313-1X30012-565检验数0004-4x-87-2x5x+8 如图：1. 1. X7/2 时，检验数0 ，最优解：（5，3，5，0，0）T2. 2. 1X7/2时，4-4X0由（I）得：C-x-1-1000bCBXBX1X2X3X4X5X6-XX1101/3-10/3-5/3020/3-1X201-1/65/3-13/6013/60X6001/61/3-5/615/6检验数00X/3-7/6-10X/3+5/3-5X/3-13/6020X/3+13/63. X -2X+70 C-x-1-1000bCBXBX1X2X3X4X5X6-XX11200-6011-1X201/201-3/21/23/2-1X30-110-252检验数02x-200-6X-2511X+2检验数0，列系数0，所以解无界。4.-3/2X4-4X0C-x-1-1000bCBXBX1X2X3X4X5X6-XX1100-10/3-5/3020/3-1X20105/3-13/6013/6-1X60011/3-5/615/6检验数X/3-7/6-10X/3+5/3-5X/3-13/620X/3+13/6判断检验数的符号：1)1/2X 1 ，所有检验数 0（1/2X2）-1.3X1/2时表（A）C-x-1-1000bCBXBX1X2X3X4X5X6-XX11200-600110X403/5-1/101-13/100013/100X60-1/51/50-2/5112/5检验数02X-1-10-6X011X对-6X讨论，令-6X=0 X=01 0X1/2时， 检验数0 （0X1/2）2-1.3X0 又 X5列的系数 0 ，所以解无界3） -1.5X0 ，又 X5的列的系数0，所以解无界（7）解：化为标准形：C164000000-M-M-MbCBXBX1X2X3X4X5X6X7X8X9X10X11X120X4-122100000000130X54-41010000000200X612100110000017-MX101000000001001-MX110100000-100102-MX1200100000-10013检验数1+M6+M4+M000-M-M-M0000X4-1021000200-2090X54010100-40040260X61010010200-2013-MX10100000-10010016X20100000-100102-MX1200100000-10013检验数1+M04+M000-M6-M0-6-M00X4-1001000220-2-230X54000100-4104-1250X61000010210-2-110-MX10100000-10010016X20100000-1001024X300100000-10013检验数1+M00000-M6410-6-M-4-M0X4000100-1221-2-240X500001004-41-44-1210X6000001121-1-2-191X1100000-10010016X20100000-1001024X300100000-10013检验数0000001640X80001/200-1/2111/2-1-120X5000210205-20-5290X6000-10120-1-20151X1100000-10010016X20101/200-1/2011/21/2-144X300100000-10013检验数000-30040-20X80001/401/4013/40-1-3/413/40X500031-100600-6240X7000-1/201/210-1/2-101/25/21X1100-1/201/200-1/2001/27/26X20101/401/4003/400-3/421/44X300100000-10013检验数000-10-2000-47即：（8）解：化为标准形：C1-11-31-1-3-M-M-M-MbCBXBX1X2X3X4X5X6X7X8X9X10X11-MX8003011010006-MX9012-1000010010-MX10-100001000100-MX11001001100016检验数1-MM-16M+1-M-31+M-1+3M3+M00001X30011/31/301/30002-MX9010-1-2/3-2/30-2/31006-MX10-100001000100-MX110000-1/32/31-1/30014检验数1-MM-10-M-32/3-MM-1/3M-30001X300101/31/301/30002-1X2010-1-2/3-2/3001006-MX10-1000010-2/30100-MX110000-1/32/31-1/30014检验数1-M00-45/3M-2M-3001X300101/20-1/21/200-1/20-1X2010-1-101-110110-MX10-10001/20-3/21/201-1/2-61X60000-1/213/2-1/2003/26检验数1-M00-41/2M-1001X3111000100-110-1X2-200-100-2012-2-21X5-200010-3102-3-12-1X6-10000100100检验数-100-400-312（1）解：标准形：1C2-12000-M-M-MbCBXBX1X2X3X4X5X6X7X8X9-MX7111-1001006-MX8-1010-100102-MX902-100-10010检验数2-1+3M2+M-M-M-M000-MX7103/2-101/210-1/26-MX8-1010-100102-1X201-1/200-1/2001/20检验数205/2M+3/2-M-M1/2M-1/200-MX75/200-13/21/21-3/2-1/232X3-1010-100102-1X2-1100-1/2-1/201/21/21检验数5/2M+7/200-M3/2M1/2M02X1100-2/53/51/52/5-3/5-1/56/52X3001-2/5-2/51/52/52/5-1/516/5-1X2010-1/5-1/5-2/51/51/52/58/5检验数0007/5-3/5-6/5由表可知此题解无界。2得一辅助问题：C000000-1-1-1bCBXBX1X2X3X4X5X6X7X8X9-1X7111-1001006-1X8-1010-100102-1X902-100-10010检验数031-1-1-1000-1X7103/2-101/210-1/26-1X8-1010-1001020X201-1/200-1/2001/20检验数005/2-1-11/200-3/2-1X75/200-13/21/21-3/2-1/230X3-1010-1001020X2-1100-1/2-1/201/21/21检验数5/200-13/200X1100-2/53/51/52/5-3/5-1/56/50X3001-2/5-2/51/52/52/5-1/516/50X2010-1/5-1/5-2/51/51/52/58/5检验数000000-1-1-10C2-12000bCBXBX1X2X3X4X5X62X1100-2/53/51/5-1X3001-2/5-2/51/52X2010-1/5-1/5-2/5检验数0-334/5由表知此题属于解无界（2）大M法，先化为标准形：Z=-ZC-4-100-M-MbCBXBX1X2X3X4X5X60X41201004-MX51100103-MX643-10016检验数5M-44M-1-M0009M0X405/41/4105/2-MX501/41/4013/2-4X113/4-1/4003/2检验数0M/4+2M/4-1003M/2+6-1X2011/54/502-MX5001/5-1/511-4X110-2/5-3/500检验数00M/5-7/5-M/5-8/50M+2-1X2010110X3001-15-4X1100-12000-39 原问题唯一最优解二阶段法：引入人工变量 X5 X6得原问题的一个辅助问题：C0000-1-1bCBXBX1X2X3X4X5X60X41201004-MX51100103-MX643-10016检验数54-100090X405/41/4105/2-MX501/41/4013/2-4X113/4-1/4003/2检验数01/41/4003/2-1X2011/54/502-MX5001/5-1/511-4X110-2/5-3/500检验数001/5-1/501-1X2010110X3001-15-4X1100-12检验数000-10C-4-100bCBXBX1X2X3X4-1X2001-150X301011-4X1100-12检验数000-39（3）标准形：C-23-1000-M-MbCBXBX1X2X3X4X5X6X7X8-MX7142-100108-MX83200-10016检验数-2-4M6M+32M-1-M-M0003X21/411/2-1/4001/402-MX85/20-11/2-10-1/212检验数5/2M-11/40-M-5/21/2M+3/4-M003X2013/5-3/101/1003/10-1/109/5-2X110-2/51/5-2/50-1/52/54/5检验数00-18/513/1003X25/2100-1/2001/230X450-21-20-124检验数0-103/20-M-M由表知此题解无界；（6）两阶段法：C000000-1-1bCBXBX1X2X3X4X5X6X7X8-1X7142-100108-1X83200-10016检验数462-1-10000X21/411/2-1/4001/402-1X85/20-11/2-10-1/212检验数5/2M-11/40-M-5/21/2M+3/4-M000X2013/5-3/101/1003/10-1/109/50X110-2/51/5-2/50-1/52/54/5检验数000000-1-1C-23-1000bCBXBX1X2X3X4X5X63X2013/5-3/101/1009/5-2X110-2/51/5-2/504/5检验数00-18/513/1003X25/2100-1/2030X450-21-204检验数0-103/20由表知此题为解无界；（4）化为标准形：C101512000-MbCBXBX1X2X3X4X5X6X70X4531100090X5-5615010015-MX721100-1152M+10M+1512+M00-M010X113/51/51/50009/50X50916110024-MX70-1/53/5-2/50-112/503/5M0010X1139/80015/80-1/800015/1012X309/1611/161/16003/2-MX70-43/800-35/80-3/80-111/200013（1） （2） （3）14C2-11000bCBXBX1X2X3X4X5X60X4311100600X51-12010100X601-1001202-110000X404-51-30302X11-12010100X602-30-111001-30-200X40011-1-2102X1101/201/21/215-1X201-3/20-1/21/2500-3/20-3/2-1/2-2515.C2-11000bCBXBX1X2X3X4X5X60X22/3101/3008/30X5-4/3052/31014/30X65/304-5/30129/3-1/30-4-5/300-1X22/3101/3008/31X3-4/15012/151/5014/150X641/1500-33/15-4/5184/1544/15003/15-1/5016.17.解：由表知：（1） d=1，e=0，b=-6，f=1/3，g=0，a=7； （2）由表知所有18.证明：20解（1）第二章 线性规划的对偶理论1.解：设分别表示A、B、C各产品的数量，Z 表示总产值则： 经济解释：y1，y2，y3分别表示给别人代工时所得收入，对厂方而言，w越大越好，但定价不能太高，要对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理，厂方不会吃亏，对方也容易接受。23.证明： 是线性问题的可行解，即该问题存在可行解； 又其对偶问题为：4.证明：该线性问题的对偶问题为： 5.证明：对偶问题7. 7. 1）对偶问题： 2）由题知原问题的最优解为 由互补松弛定理得：在对偶问题中对应第一，二个约束为紧，第三个约束条件为松，即， 对偶规划问题的最优解 3）影子价格为 y1 = 4 ：8解：先写出其对偶问题。 对偶规划问题的最优解 原对偶规划问题的最优解 9. 10解11解（1）设分别表示甲、乙、丙各产品的数量，Z 表示总产值则： 化为标准形：C32100bCBXBX1X2X3X4X50X4121104000X521201500检验数321000X403/201-1/21503X111/2101/2250检验数01/2-20-3/22502X20102/3-1/31003X1101-1/32/3200检验数00-2-1/3-4/3-800此时，y1，y2分别表示出租A，B设备所得利润，由（1）中的最优表得=1/3，即如出租A设备可获得1000/3元，而1000/3350所以不合算。 12.解：（1）由影子价格的定义可得： （2）由（1）可知y1只与bi的值有关当x1的系数由3变为x的系数1/3时，yi的值并不发生变化； x1不可能在最优基中出现， x也不可能在最优基中出现（3）（4）不会。13.解：1）解：先将问题化为标准式取初始正则基 B = （p4 p5） = I则原问题已化为关于基B 的典式，C23100BCBXBX1X2X3X4X50X4-3-2310-30X5-40-201-10检验数-10-5-40000X4-9-2013/2-18-4X22010-1/25检验数-2-500-220-10X112/90-1/9-1/62-4X20-4/912/9-1/61检验数0-41/90-2/9-7/324可得原问题的最优解为：（2）将问题化为： C32100BCBXBX1X2X3X4X50X4-1-2-110-30X5-21-301-4检验数-2-3-4000X40-5/21/21-1/2-13X11-1/23/20-1/22检验数0-4-10-12502X201-1/5-2/51/52/53X11014/10-1/5-4/1011/5检验数00-9/5-8/5-1/5-28/5C350000BCBXBX1X2X3X4X5X60X4-3-10100-30X5-40-3010-60X61200013检验数-2-100000X4-3-10100-30X34/3010-1/3020X61200013检验数-2-10000-2X111/30-1/30010X30-4/914/9-1/302/30X605/301/3012检验数0-1/30-2/3002（4）化为：C-3-2-1000bCBXBX1X2X3X4X5X60X411110060X5-10-1010-40X60-11001-3检验数-3-2-10000X40101102-1X31010-1040X6-1-10011-7检验数-2-200-100X40101102-1X30-11001-3-3X11100-1-17检验数0000-3-20X4001111-1-2X201-100-13-3X11010-104检验数0000-3-2由表知，此题无可行解。14.（1）由表知，C1C2为基变量的系数 C38000bCBXBX1X2X3X4X53X1101/20-2-2000X400-311020008X201001500检验数00-3/20-20X5-1/20-1/4011000X450-1/21010008X21/21400400检验数-10-200-320015. 1）. C1变化时， C2变化时