运筹学课后习题答案

第一章线性规划1、由图可得最优解为2、用图解法求解线性规划MINZ2X1X20584212XX解由图可得最优解X16,Y643用图解法求解线性规划MAXZ5X16X20,321X解由图可得最优解MAXZ5X16X2,MAXZ4用图解法求解线性规划MAXZ2X1X20,5462121XX由图可得最大值，所以3512X231XMAXZ8121225MAX38460,MAXZJZXX如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式MINZX12X23X3无约束321321,0,57XXX解令ZZ,引进松弛变量X40，引入剩余变量X50，并令X3X3X3,其中X30,X30MAXZX12X23X33X30,0,0,537543213214XXXXX7将线性规划模型化为标准形式MINZX12X23X3无约束，321321,06449XXX解令ZZ，引进松弛变量X40,引进剩余变量X50,得到一下等价的标准形式。,0,63244954151XXX2X2X3X3X3ZMINZX12X23X36324491531XX123134258MAXZ30660,JXXCJ33400CBXBBX1X2X3X4X5I0X4403451080X5606430120J334004X383/54/511/5040/30X54221/58/503/5160/7J3/51/504/504X3204/714/351/73X11018/2101/75/21J03/7031/351/710,MAX最优解为（，），目标函数Z389用单纯形法求解线性规划问题MAXZ70X1120X23016492X解MAXZ70X1120X23013649524X单纯形表如下MAXZ3908121212345345124150MAX4305,00,3JZXXXXXX解引入松弛变量CJ43000CBXBBX1X2X3X4X5I0X330002210015000X440005250108000X550010001500CJZJ430001122121MIN5MIN51430,AX,405CZX检验数,AX对应的为换入变量为换出变量CJ43000CBXBBX1X2X3X4X5I0X32000021020X415000250150X150010001CJZJ0000412345115,0,1,0,452XXCZ非基变量检验数，得到最优解X目标函数的MAXZ411解（1）引入松弛变量X4，X5，X6，将原问题标准化，得MAXZ10X16X24X3X1X2X3X410010X14X25X3X56002X12X26X3X6300X1,X2,X3,X4,X5,X60得到初始单纯形表CJ1064000CBXBBX1X2X3X4X5X6000X4X5X6100600300110214215610001000110060150CJZJ1064000（2）其中1C1Z110（0101002）10，同理求得其他根据MAXMAX10,6,410,对应的X1为换入变量，计算得到，MINMIN100/1,600/10,300/260,X5为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程CJ1064000CBXBBX1X2X3X4X5X60100X4X1X640601800103/52/56/51/21/251001/101/101/5001200/3150150CJZJ0210106100X2X1X6200/3100/31000101005/61/645/32/321/61/60001200/3150150CJZJ008/310/32/30J0，迭代已得到最优解，X（100/3，200/3，0，0，0，100）T，Z10100/36200/3402200/3。12解（1）引入松弛变量X3，X4，X5将原问题标准化，得MAXZ2X1X25X2X3156X12X2X424X12X2X55X1,X2,X3,X4,X50得到初始单纯形表CJ21000CBXBBX1X2X3X4X5000X3X4X51524506152110001000145CJZJ21000（2）其中1C1Z12（0101002）2，同理求得其他根据MAXMAX2,1,02,对应的X1为换入变量，计算得到，MINMIN,24/6,5/14,X4为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程CJ106400CBXBBX1X2X3X4X5020X3X1X5154101051/32/310001/61/60013123/2CJZJ01/301/30021X3X1X215/217/23/20100011005/41/41/415/21/23/2CJZJ0001/41/2J0，迭代已得到最优解，X（7/2，3/2，0，0，0）T，Z27/23/217/2。13解引入松弛变量X3、X4，约束条件化成等式，将原问题进行标准化，得MAXZ25X1X23X15X2X3155X12X2X410X1,X2,X3,X40（1）确定初始可行基为单位矩阵IP3，P4，基变量为X3，X4，X5，非基变量为X1，X2，则有MAXZ25X13X2X3153X15X2STX4105X12X2XI0，J1，2，3，4将题求解过程列成单纯形表格形式，表1由上述可得，将1X替换为4表2，单纯形迭代过程JC25100BXB1X23X403X1504103510520152JJCZ25100JC25100BBXB1X23X4由表2可得，将2X替换为3表3最终单纯形表非基变量检验数0,，得到该线性规划另一最优解，（，0,0）,3412X2019455，该线性规划具有无穷多个解Z14用单纯形法求解线性规划问题052461MAX2112XTSZ，解（1）将原问题转化为标准形式，得03X92512019/513/512/501/545/195JJCZ00005JC25100BBBX1X23X412X459251001591102JJCZ00010,0,052426150MAX43214135421XXXTSXZ（2）建立单纯性，并进行迭代运算（3）得到最优解X,9,0,0T，Z1956544515用单纯形法求解线性规划问题CJ21000C8XBBX1X2X3X4X50X315051000X4246101040X55110015CJZJ210000X3150510032X1411/601/60240X5105/601/616/5CJZJ02/301/300X39001162X119/51001/51/51X26/50101/56/5CJZJ0001/54/50，42MAX21121XTSZ解（1）将原问题转化为标准形式，得0,0,042200MAX54321542135421XXXTSXXZ（2）建立单纯性，并进行迭代运算本例第二个单纯形表中，非基变量X2对应的检验数0，并且对应的变量系数AI，20（I1，2，3），根据无界解判定定理，该线性规划问题有无界解（或无最优解）。如果从方程角度看，第二个表格还原线性方程CJ21000C8XBBX1X2X3X4X50X3211210020X42210100X5411001CJZJ110001X12121000X46032100X5601101CJZJ031006232MAX534312XTSZ也即62335431X令0，则3622541X此时，若进基，则，会和基变量同时增加，同时目标函数值无限增14X52X长，所以本题无解。16解（1）引入松弛变量X3，X4，X5将原问题标准化，得MAXZ2X14X20X30X40X5X12X2X38X1X44X2X53X1,X2,X3,X4,X50（1）得到初始单纯形表CJ24000CBXBBX1X2X3X4X5000X3X4X584311020110001000143CJZJ24000（2）重复（1）过程得到如下迭代过程CJ106400CBXBBX1X2X3X4X5004X3X4X224311000110001000124CJZJ20004204X1X4X2223100001110010001CJZJ0020050，30增加人工变量X6,X7,得到MAXZ5X12X24X3MX6MX73X1X22X3X4X646X13X25X3X5X710X1,X2,X3,X4,X50大M法求解过程如下CJ52400MMCBXBBX1X2X3X4X5X6X7IMMX6X7410361325100110014/35/3CJZJ59M24M47MMM005MX1X74/32101/312/311/32011/32011CJZJ01/3M2/3M5/32MM5/33M05X15/311/25/601/601/610/30X4101/21/211/211/22CJZJ01/21/605/6M5/6M52X1X22/3210011/31121/31121/31CJZJ001/311/31M1/3M最优解为X12/3,X22,X30最优目标函数值MINZ22/319、解化为标准形式MAXZ540X1450X2720X33X15X29X3X4709X15X23X3X530X1,X2,X3,X4,X50增加人工变量X6,X7,得到MAXZ540X1450X2720X3MX6MX73X15X29X3X4X6709X15X23X3X5X730X1,X2,X3,X4,X50大M法求解过程如下CJ54045072000MMICBXBBX1X2X3X4X5X6X7MMX6X770303955931001100170/330/9CJZJ12M54010M45012M720MM00M540X6X16010/30110/35/981/3101/31/9101/31/92510CJZJ015010M/38M540MM/3600M/360720540X3X115/25/6015/125/12101/81/241/241/81/81/241/241/8182CJZJ01250135/2475/12135/2M75/2M720450X3X220/32112/501101/61/101/63/101/61/101/63/10570036018045007200757515157575M1515M最优解为X0,2,20/3,0,0最优目标函数值MINZ570020解先将其化成标准形式，有MAXZ3001X34X54（A）12421（B）3539（C）2X，0145X这种情况可以添加两列单位向量，P7，连同约束条件中的向量P4构成单位矩阵6P4P6P7100010001P6，P7是人为添加上去的，它相当于在上述问题的约束条件（B）中添加变量，约束条件6X（C）中添加变量，这两个变量相应称为人工变量。由于约束条件（B）（C）在添加人工变7X量前已是等式，为使这些等式得到满足，因此在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的负数，用“M”代表。添加人工变量后数学模型变为MAXZ300MM1X34X567X42211X235X6397，012456X得到初始可行解，并列出初始单纯形表。在单纯形法迭代运算中，M0,4,9X可当作一个数学符号一起参加运算。检验数中含M符号的，当M的系数为正时，该检验数为正；当M的系数为负时，该检验数为负。求解过程见下表CJ30100MMCB基BX1X2X3X4X5X6X704XM16M97111100021101100310001CJZJ2M34M10M00034X012M67302111021101106040331CJZJ6M304M103M4M0004X0323100011/21/21/2011/30001/3102/301/21/21/6CJZJ00303/2M3/2M1/2004X025/213/2300011/21/21/21/21001/41/41/43/20103/43/41/4CJZJ9/20003/4M3/4M1/4最优解为（0，5/2，3/2）21、解将原问题转化为标准型MAXZ3X12X22X1X2X32ST3X14X2X412XI0，I1,2,3,4然后添加人工变量X5，将原线性规划问题变为MAXZ3X12X2MX52X1X2X32ST3X14X2X4X512XI0，I1,2,3,4,5取基变量为X3,X5,建立单纯形表，迭代过程如下CJ3200MCBXBBX1X2X3X4X5I0X32211002MX512340113CJZJ33M24M0M0CJ3200MCBXBBX1X2X3X4X5I0X2221100MX5450411CJZJ35M04MM0在单纯形表中，非基变量的检验值都是小于0，而人工变量仍不为0，则该线性规划无最优解。22、解假设甲、乙俩种产品产量分别为X1、X2，产品售后的最大利润为Z，则根据题意可建立以下线性规划模型MAX70X1120X29X14X2360ST4X16X22003X110X2300XI0，I1,2231121294360X12X0,ZMAX72,ZSTX解设甲、乙产品的生产数量应为、，则、设是产品售后的总利润，则2412121212ZMAXZ,433054,XXST解设甲、乙两种产品的生产数量为，设为产品售后总利润，则123231231231,25MAX04150650ABCZXXX、设分别为产品、的产量，则数学模型为1,2343412341223436,MAX70,1,JXCXCZXX设分别为产品A、B的产量，为副产品的销售量，为副产品的销毁量，有为总利润，则数学模型为27设生产四种产品分别为X1,X2,X3X4,则应满足的目标函数为MAX2X13X2X3X4满足的约束条件为05X13X2X305X418002X1X2X3X4280005X105X2X3X418003X1X22X33X41800X11000X2600X3500X440028设X1A出售的数量，X2A在第二车间加工后的出售数量，X3B的出售数量，X4B在第三车间加工后的出售数量，X5第一车间所用的原料数量目标函数为MAXZ8X195X27X38X4275X5满足的约束条件为X51000003X22X415X5200000X1X23X50X3X42X50X1,X2,X3,X4029,解现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型（1）设工厂第季度生产产品吨JJX首先，考虑约束条件第一季度末工厂需交货20吨，故应有X120；第一季度末交货后积余（X120）吨；第二季度末工厂需交货20吨，故应有X120X220；类似地，应有；第四季度末供货后工厂不能积压产品，故应有30421XX；又考虑到工厂每个季度的生产能力，故应有1743JJAX0其次，考虑目标函数第一季度工厂的生产费用为150，第二季度工厂生产的费用包1X括生产费用14及积压产品的存贮费；类似地，第三季度费用为2X201X，第四季度费用为工厂一年的001513708432费用即为这四个季度费用之和整理后，得下列线性规划模型MIN654654321ZSTX0327841，02X203X104X（2）设第季度工厂生产的产品为吨，第季度初存贮的产品为吨（显然，JJJJY）01Y因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有，210YX320YX，；4314Y同时，每季度的生产量不能超过生产能力；而工厂四个季度的总费用由每季的JJA生产费用与存贮费用组成，于是得线性规划MIN4433218120150405XYXYXYXZST3243104XY01234，2，3，40JYJ（3）设第季度生产而用于第季度末交货的产品数量为吨IJIX根据合同要求，必须有，201X2012X，331434X又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力，故应有，014312XX，43第季度生产的用于第季度交货的每吨产品的费用，于是，有线性规IJ20IJDCIIJ划模型MINX2432438ST102X3314411203X441，4；1，4，JIIJIJ30,解设为型飞机被派遣去工厂执行任务的架数IJXJ甲方的目标是希望事件“至少摧毁一个工厂”的概率最大这相当于希望事件“不摧毁任何工厂”的概率最小我们有F232211312110608500XXXXXX它不是线性的，为此将上式改写为80LOG4L920LOG85LL9OG2322113121XXXXFZ于是，模型的目标函数为23221110546037957XXXZ关于燃料的约束条件为21323221131148005734805574IJIXXXX经过整理，即为4802675823113121XXX飞机数量约束，3140JJX8312JJX综上所述，本问题的线性规划模型为MAXZ131217496057XXX2322105460XXXST840833221，1，2；1，2，30IJXIJ第二章线性规划1对偶问题和对偶变量的经济意义是什么从经济学的角度来说,对偶变量反映的是对应的原变量的边际效应,即每增加一单位的原变量使目标函数变化的值,当原变量在目标函数取得最优解时没有用完的情况下,原变量的增加不会改变目标函数的值,此时原变量的边际效应为0,即对偶变量为0,这就是强对偶理论。2简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么计算步骤见书P42单纯形法对偶单纯形法原理保证原问题是可行解的情况下向对偶问题可行的方向迭代保证对偶问题是可行解的情况下向原问题可行的方向迭代最优解判断看非基变量的检验数是否都小于等于零看对偶单纯形表的B1B是否都大于等于零迭代原则最大最小比值原则最大检验数最大的那个非基变量为换入变量；最小B1B/AIK最小的那个对应的基变量为换出变量最小最小比值原则最小B1B列数字最小（负数）的那个对应的基变量为换出变量；最小CJZI/ALJ最小的那个对应的非基变量为换入变量3什么是资源的影子价格他和相应的市场价格之间有什么区别对偶变量YI的意义代表在资源最优利用条件下对第I种资源的估价，这是根据资源在生产作用中做出的贡献而得到的估价，称为影子价格。市场价格是指实际发生的市场交易价格，它是计量财务支出和收入的直接依据；机会成本或支付意愿就是经济分析中的影子价格。4如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系（1）对偶MIN型变量的最优解等于原问题松弛变量检验数的绝对值（2）对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值（3）由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。（4）更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量松弛或剩余的检验数对应其对偶问题实变量对偶变量的最优解，原问题实变量决策变量的检验数对应其对偶问题虚变量松弛或剩余变量的最优解。51MINW30Y180Y22MAXW30Y180Y250Y3Y14Y22Y1Y24Y323Y12Y223Y15Y22Y383Y14Y243Y14Y24Y34Y1,Y20Y10,Y2无限制，Y306解MAXZ4X2X26X32X14X28X3X424ST4X1X24X3X58XJ0,J1,2,3,4,5CJ42600CBXBBX1X2X3X4X50X424248100X5841401CJZJ4262X261/211/21/400X527/207/21/41CJZJ3051/204X14/71011/142/72X240/70102/71/7CJZJ0022/76/7所以X4/7,40/7,0,0,0,Z96/77MAXZX12X23X34X4X12X22X33X4X5202X1X23X32X4X620XJ0,J1,2,3,4,5,6对偶问题MINW20Y120Y2Y12Y21Y1Y2Y312Y1Y222Y1Y2Y422Y13Y232Y13Y2Y533Y12Y243Y12Y2Y64Y1,Y20YI0,I1,6已知对偶问题最优解为Y16/5,Y21/5代入，得Y33/5,Y43/5,Y50,Y60YXSY1,Y2X5,X6T0XYSX1,X2,X3,X4TY3,Y4,Y5,Y60SOX5X60,X1X20代入得,X3X44,SO最优解X0,0,4,48设甲、乙、丙3种产品数量分别为X1,X2,X3，总利润为ZMAXZ4X1X25X3X12X23X3456X13X25X3X4453X14X25X3303X14X25X3X530X1,X2,X30XI0,I1,5CJ42600ICXIBX1X2X3X4X50X4456351090X5303450116CJZJ415005X63/54101/13/5500X415310115CJZJ130014X1511/301/31/35X330111/52/5CJZJ08/301/32/3所以最优解为X5,0,3Z201535即甲生产5件，乙不生产，丙生产3件。2PCCBB1PC1,1,5,0,0C1,511/301/31/30111/52/5C1,1,5,0,0C1,5C1/3,5,C1/31,C1/320,C1/34,0,1C1/3,C1/32C1/3401C1/30SO3C16C1/320SO当年的利润在3，6时，最优解不变3设丁为X6,C65/2,P63,2TP6B1P61/31/331/31/52/521/5C6C6CBB1P65/24,51/31/51/60继续迭代CJ415005/2ICXIBX1X2X3X4X5X64X1511/301/31/31/3155X330111/52/51/515CJZJ08/301/32/31/65/2X6150551214X10125/32/310CJZJ07/25/31/310SO最优解X0,0,0,15Z375即值得安排生产，最优计划为甲、乙、丙不生产，丁生产15件（4）由（1）知对偶价格为2/305所以应购买45/553015,应购进15单位的B（5）1500CXBBX1X2X3X4I0X345351090X43045006CJZJ155X293/511/500X1014151CJZJ20105X364/5101/50X4151011CJZJ3001SOX0,0,6Z30即乙不生产，丙生产6件9解（1）设321,X分别为产品甲、乙、丙的产量，其模型为3240MAZ0,625131X；得此问题的最终单纯形表如下（表34）表34JC1064000BCXB12X3X56X62X200/3015/65/31/60101100/3101/62/31/60010000401JZ2200/310620/310/32/30JC008/310/32/30可得TX,3/2,/10，/2Z；（2）5675；（3）6C；（4）；（5）该产品值得安排生产；（6）TX10,3/75,/9。101由题意已知原线性规划问题目标函数为MAX（因J0为最优），且C4、C5为0（松弛变量目标函数系数为0）。根据知，得1JJBJCCP2311CC406C23123C60根据，得51122216300A|B15A|B01则原线性规划问题的数学模型为123312MAXZ6X05ST,其对偶问题的数学模型为1212MIN5Y36ST0Y,2直接由表写出对偶问题得最优解为Y4,23令原解，得BR的变化范围为1IBIIXX，其中。则IRIRIRIIIMAB/|0MN/A|01IRIRAB，即，则1551XI22615B10B24以单价25购入第一种资源是值得的，因其小于该资源“影子价格”（即254），可盈利；第二种资源应要价至少为2（影子价格），否则不如自己组织生产。第三章运输问题习题答案31判断表335至336中的方案是否为运输问题的初始方案。表335运量表B1B2B3B4B5产量A1101525A2301545A3251035A43535销量1045152545表336运量表B1B2B3B4B5产量A152025A2181230A31552040A42020销量2038172020解表335不是初始方案。表335中只有7个数字格，而作为初始解，应有个数字格，所以给出的调运方案不能作为初始方案。1458MN表336是初始方案。表336中有8个数字格，而作为初始解，应有个数字格，所以给出的调运方案能作为初始方案。32表337为某运输问题各产地到各销地之间的单位运价表和产销平衡表，试用最小元素法、伏格尔法求初始基本可行解。表337单位运价表和产销平衡表销地单位运价产地B1B2B3产量（吨）A151812A224114A33674销销地地产产地地销量（吨）9101130解最小元素法1在表337中找出最小运价1，表示先将A1的产品运送到B2，在（A1，B2）的交叉处填上10；同时，B2的销量得以满足，划掉其所在列，得表3371。2在表3371中未划去的元素中再找出最小运价1，确定A2的产品运送到B3，在（A2，B3）的交叉处填上11；同时，B3的销量得以满足，划掉其所在列，得表3372。3在表3372中未划去的元素中再找出最小运价2；重复进行下去，直至所有运价都被划掉，得到一个运输方案，即初始基本可行解，见表3373。解伏格尔法1计算各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表3374；2在所有行差、列差中找到MAX差额6，选出它所在第三列中的MIN运费1，确定A2的产品运送到B3，在（A2，B3）的交叉处填上11；同时，B3的销量得以满足，划掉其所在列，得表3375。3对表3375中未划掉的元素再分别计算各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行；并重复1）、2），直至给出初始解如表3376所示。33用表上作业法求解表338和表339描述的运输问题。表338单位运价表和产销平衡表销地单位运价B1B2B3B4B5产量产地A1101520204050A22040153030100A33035402550150销量25115603070表339单位运价表和产销平衡表销地单位运价产地B1B2B3B4产量A198131418A21010121424A38911136A4107111212销量6143530解表338。利用伏格尔法给出初始解，过程如下1计算各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行；2在所有行差、列差中找到MAX差额，选出它所在行或列中的MIN运费，确定供销关系（填入数字）；划掉满足产量的行或满足销量的列；若产、销同时满足，在对应同时划掉的那行或那列的任意空格处填0，再同时划掉那行或那列；3对未划掉的元素再分别计算各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行；4重复1）、2），直至给出初始解，如图表3381所示。利用位势法进行检验。1在初始可行解的表格上增加一行一列，在列中填入，在行中填入；IUJV2计算位势。令，对于数字格，根据相继计算，得表310U,IJIJVCB,IJU382。3计算检验数（只计算空格检验数，数字格检验数为0），如表3383所示。4最优解的判断。由于所有检验数都非负，故初始解即为最优解，如表3381所示。由于表3383中有检验数为0，故该问题有无穷多最优解。最小运费为25315630153240350812Z解表339该问题中，总产量为，总销量为，销量大于产量，属于供1824606143508销不平衡问题，虚拟新的产地，产量为吨，其产品运往各销地的运价为0。得到新的852产销平衡表如表3391所示。针对表3391利用伏格尔法给出初始解，过程如下1计算各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行；2在所有行差、列差中找到MAX差额12，选出它所在行或列中的MIN运费，确定A5的产品运送到B4，在（A5，B4）的交叉处填上25；同时，A5的产量得以满足，划掉其所在行，得表3392供销关系（填入数字）；3对未划掉的元素再分别计算各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行；4重复1）、2），直至给出初始解，如表3393所示。注若填入某个数字时，产量、销量同时满足，在对应同时划掉的那行或那列的任意空格处（本题选择最小运费处）填0，再同时划掉那行或那列（本题在确定（A3，B1）处的6时产销同时满足，在最小运费9（A3，B2）处填0）。利用位势法进行检验。1在初始可行解的表格上增加一行一列，在列中填入，在行中填入；IUJV2计算位势。令，对于数字格，根据相继计算，如表310U,IJIJVCB,IJU394所示。3根据计算所有空格的检验数。,IJIJIJCUVN如12129072上述计算可以直接在表上进行，最终结果如表3395所示。由于存在负检验数，没有达到最优解，需进行闭回路调整。4闭回路调整。A找出最小负检验数（3）所对应空格（A3，B3）的闭回路，如表3396所示；B确定最大调整量；奇数顶点加，偶数顶点减。1MIN0,C调整后的方案如表3397所示。重复进行检验数计算，进行解得最优性判断，直至所有检验数非负，达到最优解。计算过程如表3398至表33915所示。以空格（A4，B3）为调入格，以（A4，B3）（A4，B2）（A1，B2）（A1，B3）（A4，B3）为闭回路进行调整，调整量，得表3399。2MIN1,计算位势计算检验数以空格（A4，B4）为调入格，以（A4，B4）（A4，B2）（A1，B2）（A1，B4）（A4，B4）为闭回路进行调整，调整量，得表33912。3MIN1,5计算位势和检验数如表33913所示。以空格（A1，B1）为调入格，以（A1，B1）（A1，B4）（A4，B4）（A4，B3）（A3，B3）（A3，B1）（A1，B1）为闭回路进行调整，调整量，得3MIN,16表33914。计算位势和检验数如表33915所示。可以看出，所有检验数非负，已得到最优解，如表33914所示。由于空格的检42,AB验数为0，表明该问题有无穷多最优解。最小运输成本为。492814241751263Z34某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服务，生产和需求及从各炼油厂运往各销售区每公升汽油平均运费（单位角/公升）如表340所示。问应如何安排调运，使运费最省。表340炼油厂供应销售区的相关数据销地运费产地销售区1销售区2销售区3销售区4销售区5销售区6销售区7日产量（万公升）炼油厂1652636335炼油厂2375869225炼油厂3486558515炼油厂4744747440日最大销售量（万公升）25201025101510解设为炼油厂供应给顾客的汽油数量，则该问题的模型如下IJXIJ1213415617223334124345647MA656789ZXXXXST11672123425233344671231423142345005XXXXX566172374100,235,67IJXXJ利用EXCEL电子表格求解该问题，关键步骤如图31图33所示。图31原始数据和最优解表使用到的部分公式如下J10SUMC10I10；C14SUMC10C13；K16SUMPRODUCTC3I6,C10I13。图32规划求解参数设置表I图33规划求解参数设置II因此，最有供应方案为，最低运费为480。35某公司在四个工厂中专门生产一种产品。在未来的四个月中，有四个处于国内不同区域的潜在顾客（批发商）很可能大量采购。顾客1是公司优先级最高的顾客，所以他的全部订购量都应该满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；顾客4，营销经理认为不需要进行特殊考虑。由于运输成本上的差异，销售一个产品得到的净利润也不同，其在很大程度上取决于哪个工厂供应哪个顾客（见表341）。那么，如何供应货物使公司总利润最大表341工厂供应顾客的相关数据销地单位运价产地顾客1顾客2顾客3顾客4产量（KG）A19813141800A2101012142400A38911131600A410711122200订购量（KG）1600140034003000解根据题意，各工厂要满足不同顾客的需求（采购量），即每位顾客的实际供给量大于等于其最小采购量而小于等于其最大采购量，得到表3411。表3411IJX销地单位运价产地顾客1顾客2顾客3顾客4产量（KG）A19813141800A2101012142400A38911131600A410711122200最小采购量（KG）160014001/334001/30最大采购量（KG）1600140034003000设为工厂供应给顾客的产品数量，则该问题的模型如下IJXIJ1213421232434121342MA980178ZXXXXXXST（工厂）3123441231423426041012XX（工厂）（工厂3）（工厂）（顾客）（顾客）13142403,IJJ（顾客）（顾客4）利用EXCEL电子表格求解该问题，关键步骤如图34图36所示。图34原始数据和最优解表使用到的部分公式如下G8SUMC18F8；C15SUMC8C11；I15SUMPRODUCTC2F5,C8F11。图35规划求解参数设置表I图36规划求解参数设置表II因此，最有供应方案为最大利润为34267。36某玩具公司生产三种新型玩具，每月可供应量分别为1500、2500、3000件，分别送到三个玩具店销售。已知每月各玩具店各类玩具的总预期销售量均为2000件，由于经营方面的原因，各玩具店销售各类玩具的盈利额不同（见表342）。又有甲玩具店要求至少供应B玩具1000件，而拒绝引进A玩具。求满足上述条件下使总获利最大的供销分配方案。表342三种新型玩具的相关数据玩具店盈利新型玩具甲乙丙可供应量（件）A561500B159102500C1311123000预期销量（件）200020002000解设为三种各玩具供应给各玩具店的数量，根据题意甲玩具店要求至少供应B玩IJXIJ具1000件，而拒绝引进A玩具可得，A玩具不能供应给甲玩具店，B玩具至少供应甲玩具店1000件，故该问题的模型如下123212313232123321321MAX56590000,IJZXXXXXSTXJ利用EXCEL电子表格求解该问题，关键步骤如图37图39所示。图37原始数据和最优解表使用到的部分公式如下F7SUMC7E7；C10SUMC7C9；H12SUMPRODUCTC2E4,C7E9。图38规划求解参数设置表I图39规划求解参数设置表II因此，最有供应方案为最大利润为72000。第四章整数规划习题答案41用分支定界法求解如下整数规划问题1212MAX49563,0Z且且1212MAX349,0ZX且且解（1）暂不考虑整数约束，利用图解法求解对应的松弛问题LP1212MAX49563,0ZXLPST得到最优解和最有目标函数值为0123,987XZ该解不符合整数约束，但是可理解为该整数规划问题最优解的上界，记087ZZ。而，很显然是问题的一个整数可行解，这时是的一个下界，0Z120,XA0记。即。87Z针对这一非整数解进行分枝，构造两个约束条件和分别加到原135X1X12整数规划问题中，可得如下两个新的分枝问题和1LP21212MA495631,0ZXLPSTX1212MA495632,0ZXLST求解LP1，得到最优解和最优目标函数为；112,73XZ求解LP2，得到最优解和最优目标函数为。294由于，先对LP2继续分支，构造两个约束条件和分别加到原规划21ZX3问题中，可得如下两个新的分枝问题和LP121221MAX495632,0ZXLPSTX121221MAX495632,0ZXLPSTX求解LP21，得到最优解和最优目标函数为；21234,64XZ求解LP22，得到最优解和最优目标函数为。对于LP22，从图解中看出，没有可能的整数解使其目标函数值满足，01Z故结束该分支。对于LP21，构造两个约束条件和分别加到原规划问题LP21中，可得如下两12X13个新的分枝问题和21LP121221MAX495632,0ZXLPSTX121221MAX495632,0ZXLPSTXLP211最优解和最优目标函数为2112,4XZLP211最优解和最优目标函数为整数解，故无需对LP1进行分枝。212ZZ所以，原整数规划问题的最优解为12,3,1TTX最优目标函数值为。4（2）暂不考虑整数约束，利用图解法求解对应的松弛问题LP，1212MAX349,0ZXLPST得到最优解和最有目标函数值为01234,594XZ针对这一非整数解进行分枝，构造两个约束条件和分别加到原整134X13X1数规划问题中，可得如下两个新的分枝问题和LP1212MA3491,0ZXLPSTX1212MA3492,0ZXLSTX求解LP1，得到最优解和最优目标函数为；1123,843XZ求解LP2，得到最优解和最优目标函数为，已得到整数解，该分24枝停止继续计算。由于，对LP1继续分支，构造两个约束条件和分别加到原规划问12Z2X2题LP1中，可得如下两个新的分枝问题和1LP121212MAX3491,0ZXLPSTX1221MA349123,0ZXLPSTX求解LP11，得到最优解和最优目标函数为。由于得到整数解，1123,3XZ该分枝停止计算。求解LP12，得到最优解和最优目标函数为。由于12125,5，该分枝已无必要继续计算，剪掉改枝。12Z由于，所以原整数规划的最优解12Z4,TX最优目标函数值为。442用割平面法求解如下整数规划问题1212MAX6450,Z且且1212MAX456,0ZXX且且解（1）1将原线性规划约束条件添加松弛变量，化为标准型，不考虑整数约束条件，用单纯形法求解，计算结果如表41所示。表41因而最优解为12345,8,0135XXZ2选择真分数部分MAX的基变量所在行为源行；本题中，IB1203BJC1100BCBXBX23X403X6211004204501初始表J110011X5/3105/61/6128/3012/31/3最终表J001/61/6，两者真分数相同，故任选一行作为源行。这里我们选第二行作283B为源行。23418XX3将约束条件系数分离如是整数则不变；如是分数，写成一个整数加一个正的真分数；234213XX4将真分数部分留在左边，整数部分移动到右边；3423X5由此得到切割条件341X6将切割条件系数整数化，即得到切割方程（）；3434522XX标准化7将添加到原最终表，得到非可行解，见表42。从表42中可以看出，得到的是非可行解，用对偶单纯形表继续进行计算。表42添加切割方程后的单纯形表JC110000BCBXBX23X45X11X5/3105/61/60128/3012/31/3005X200111J001/61/6011X210101/612201101/304X200111J00001/6此时得到最优解为，最优目标函数值为。,TX4Z（2）1将原线性规划约束条件添加松弛变量，化为标准型，不考虑整数约束条件，用单纯形法求解，计算结果如表43所示。表43JC114000BCBXB1X23X45X03X41210004165201005X421001初始表J11400003X40011/34/3424/30102/95/9111X8/31001/92/9最终表J00019/92/9因而最优解为123454,8,143XXZ2选择真分数部分MAX的基变量所在行为源行；本题中选第三行作为源行。IB1452893XX3将约束条件系数分离如是整数则不变；如是分数，写成一个整数加一个正的真分数；得到切割条件为45X4将切割条件系数整数化，即得到切割方程（）；45456262XX标准化5将添加到原最终表，得到非可行解，见表44。从表44中可以看出，得到的是非可行解，用对偶单纯形表继续进行计算。表44添加切割方程后的单纯形表JC1140000BCBXB1X23X45X603X40011/34/30424/30102/95/90111X8/31001/92/90066000121J00019/92/9003X0001102/34230101/205/18111X2100001/90530001/211/2J000201/9由此得到最优解为，最优目标函数值为此时得到最优解为，最优目标函数值为。2,3TX34Z43用隐枚举法求下列01规划问题。123123MAX45,0ZXX且且123123123MAX546,0ZXX且且解（1）将各约束条件编号如下12312