1、管理运筹学第二版课后习题参考标准答案管理运筹学（第二版）课后习题参考答案第1章线性规划（复习思考题）1.什么是线性规划线性规划的三要素是什么答：线性规划（Linear Programming, LP）是运筹学中最成熟的一个分支，并且是 应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化 工具，能够解决有限资源的最佳分配问题。建立线性规划问题要具备三要素：决策变量、约束条件、LI标函数。决策变量是决 策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条 件的限制，保障决策方案的可行性；U标函数是决策者希望实现的LI标，为决策变量的 线性函数表达式
2、，有的LI标要实现极大值，有的则要求极小值。2.求解线性规划问题时可能出现儿种结果，哪种结果说明建模时有错误答：（1）唯一最优解：只有一个最优点；（2） 多重最优解：无穷多个最优解：（3） 无界解：可行域无界，目标值无限增大；（4） 没有可行解：线性规划问题的可行域是空集。当无界解和没有可行解时，可能是建模时有错。3.什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么答：线性规划的标准型是：LI标函数极大化，约束条件为等式，右端常数项0, 决策变量满足非负性。如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业 来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的
3、话，则说明“事”型约 束的左边取值大于右边规划值，出现剩余量。4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件AX=b, X0的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解。可行基：对应于基可行解的基，称为可行基。最优解：使訂标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。它们的相互关系如右图所示：5.用表格单纯形法求解如下线性规划。max Z = 4Xj + x2+ 2x38Xj + 3x2 +x3 26xj + x2 + 兀3 8 飞解：标准化 max Z = 4xt + x2 + 2x38xj +
4、 3x2 + x3 + x4 = 2 + x2 + x3 +x5 = 8列出单纯形表ci41200qxb旺勺勺V50“421831102/808611018/64120041/413/81/81/80(1/4)/(1/8)013/265/41/43/41(13/2)/(1/4)J01/23/2-1/202兀32831100622011J125020故最优解为X* = (0Q2Q6V ,即m = 09x2 = 0內=2 ,此时最优值为Z(X*) = 4 6.表115中给出了求极大化问题的单纯形表，问表中5 0,c, 0, c2 cx 0,c2 （X （X ；4 a2（4） c2 0,| ；或者氐
5、为人工变量,4 a2且C2为包含的大于零的数，0,0.7.用大於法求解如下线性规划。max Z = 5州 + 3x2 + 6x3%, + 2x2 + 182x, +x2 + 3x3 0解：加入人工变量，进行人造基后的数学模型如下：max Z = 5旺 + 3x2 + 6x3 + 0x4 + 0x5 - Mx（ + 2x2 + x3 + x4 = 182xl +x2 + 3x5 + x5 = 16x+x2+xy+x6=00 （心 12,6）列出单纯形表553600McBb小X2尤5尤60X48112110018/10X56121301016/3MX60111100110/1J5+M3+M+M60
6、000X4 8/331/35/3011/3038/56X6/312/31/3101/3016MX64/311/32/3001/3114/2J + -M31 +-M300-2-00X411/20011/25/26A331/20101/21/263X271/21001/23/214J1/20003/232M0X4400111-35X1610201-13Xr40110-120010-2-1M故最优解为X* = (64040,0)7,即州=6,x2 = 4, = 0,此时最优值为Z(X*) = 42 8.A, B, C三个城市每年需分别供应电力320, 250和330单位，I Id I, II两个电
7、站提供，它们的最大可供电量分别为400单位和450单位，单位费用如表1-16所示。 山于需要量大于可供量，决定城市A的供应量可减少030单位，城市B的供应量不变, 城市C的供应量不能少于270单位。试建立线性规划模型，求将可供电量用完的最低总 费用分配方案。表116 单位电力输电费(单位：元)站城市ABCI151822II212516解：设&为“第，电站向第丿城市分配的电量(2=1,2; 1,2,3),建立模型如下:max Z = 15xH + 18x12 +22xl3 + 21x2I + 25x22 + 16x23Xj, +X|2 +山3 = 400| + %22 + = 4b0+x2i 2
8、90 +x2( 270 xl3 + x2i 0,/ = 1,2; J = 1,2,39.某公司在3年的计划期内，有4个建设项目可以投资：项目I从第一年到第三 年年初都可以投资。预计每年年初投资，年末可收回本利120%,每年乂可以重新将所获 本利纳入投资计划；项LI II需要在第一年初投资，经过两年可收回本利150%, 乂可以 重新将所获本利纳入投资计划，但用于该项LI的最大投资不得超过20万元；项H ill 需要在第二年年初投资，经过两年可收回本利160%,但用于该项LI的最大投资不得超过 15万元；项目IV需要在第三年年初投资，年末可收回本利140%,但用于该项目的最大 投资不得超过10万元
9、。在这个计划期内，该公司第一年可供投资的资金有30万元。问 怎样的投资方案，才能使该公司在这个计划期获得最大利润解：设才）表示第一次投资项目i,设才）表示第二次投资项目i,设兀表示第三 次投资项目几（7=1,2, 3,4）,则建立的线性规划模型为max Z = 1.2才）+ 16叩 + 1屮屮）+30_屮）_绘旺 +创=1.2牢）+1.5绘 +1.2屮 +30-拌）WT. 昌） 20斗）15） 10）,#2）,兀“,心 1,2,3,4通过LINGO软件计算得：州=10, = 20朗 =0,x；2） = 12,屮=44 .10.某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、
10、 上漆儿道重要工序。每种家具的每道工序所用的时间、每道工序的可用时间、每种家具 的利润由表117给出。问工厂应如何安排生产，使总利润最大表117 家具生产工艺耗时和利润表生产工序所需时间（小时）每道工序 可用时间（小 时）12345成型346233600打磨435643950上漆233432800利润（百元）33解：设“表示第，种规格的家具的生产量（：1,2,5）,则max Z = 27片 + 3x2 + 4.5x3 + 2.5x4 + 3x53x, + 4x2 + 6小 + 2x4 + 3x5 36004x, + 3x2 + 5x3 + 6x4 + 4xs 39502x + 3x2 + 3x
11、2 + 4x4 + 3x5 2800xr noj = l,2,5通过 LINGO 软件计算得：“ =0,x2 =38,x3 =254,x4 =0,x5 =642,Z = 3181 .11.某厂生产甲、乙、丙三种产品，分别经过A, B, C三种设备加工。已知生产单 位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表2-10所示。表1-18 产品生产工艺消耗系数甲乙丙设备能力A （小时）111100B （小时）1045600C （小时）226300单位产品利润（元）1064（1） 建立线性规划模型，求该厂获利最大的生产计划。（2） 产品丙每件的利润增加到多大时才值得安排生产如产品丙每件
12、的利润增加到 6,求最优生产计划。（3） 产品屮的利润在多大范圉内变化时，原最优计划保持不变（4） 设备A的能力如为IOO+IOq,确定保持原最优基不变的q的变化范圉。（5） 如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。解：（1）设册,吃,心分别表示甲、乙、丙产品的生产量，建立线性规划模型max Z = 10x( + 6x2 + 4x3Xf +X2+Xy 001 Ox, + 4x2 + 5x3 6002%| + 2x2 + 6勺 0标准化得max Z = IO + 6x2 + 4x3 + 0x4 + 0x5 + 0x6x+x2+x3+ x4 = 1001 OXj + 4x2 +
13、5x3 +x5= 600+ 2x2 + 6x3 +x6= 300列出单纯形表Cj1064000c Xb bz屯心心X6110X1111000000660X450100010031022600100501J6400004120X.01003/5 /21/1000/3162111X10000/5 /2/10501610050180/51/550J020011255/6X01000/3/631/61111100000/3/62/3/61000401002J0008/3 10/3 2/3故最优解为Xj = 100/3,x2 = 200/3,x3 =0 , 乂由于xl,x2,x3取整数，故四舍五入可得最
14、优解为册=33以2 =67,屯=0, Zmax = 732 （2）产品丙的利润6变化的单纯形法迭代表如下:5106C3000C X bX2心尤566X200/3015/65/31/6010X100/3101/62/31/60010000420100C3-20/310/32/30要使原最优计划保持不变，只要円之3-学0,即c36|6.67.故当产品丙每件的利润增加到大于时，才值得安排生产。如产品丙每件的利润增加到6时，此时6，故原最优计划不变。（3）由最末单纯形表计算出1 2 1cr3 = 1 C） 0,cr4 = 10+ c 0,cr5 = 1 c, 0 ,6 3 6WW6c115 ,即当产品
15、甲的利润5在6,15范围内变化时，原最优讣划保持不变。5/31/6 0 ,新的最优解为（4）曲最末单纯形表找出最优基的逆为Bl= -2/3100 + 100 1200 + 50、6001_ 310020“、300 ）、3(100 20妙 1丿 一25/3X；=B-H= -2/3I -2解得-4S0S5,故要保持原最优基不变的q的变化范围为7,5 （5）如合同规定该厂至少生产10件产品丙，则线性规划模型变成max Z = 10%! + 6x2 + 4x3+ x2 + x3 1001 Oxj + 4x2 + 5x3 600 2x）+ 2x2 + 6x3 10xpx2,x3 0通过LINGO软件计算
16、得到:X）= 32,花=58,勺=10,Z = 708第2章对偶规划（复习思考题）1.对偶问题和对偶向量（即影子价值）的经济意义是什么答：原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来 考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品 生产带来的，同时乂是资源消耗带来的。对偶变量的值兀表示第,种资源的边际价值，称为影子价值。可以把对偶问题的解Y定义为每增加一个单位的资源引起的口标函数值的增量。2.什么是资源的影子价格它与相应的市场价格有什么区别答：若以产值为U标，则儿是增加单位资源，对产值的贡献，称为资源的影子价格（Shadow Price）o
17、即有“影子价格二资源成本+影子利润”。因为它并不是资源的实际价 格，而是企业内部资源的配比价格，是III企业内部资源的配置状况来决定的，并不是山 市场来决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当市场价 格小于影子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子 价格时，企业可以考虑暂不购进资源，减少不必要的损失。3.如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系答：（1）最优性定理：设疋P分别为原问题和对偶问题的可行解，且CX=bTY, 则分别为各自的最优解。（2）对偶性定理：若原问题有最优解，那么对偶问题也有最优解
18、，而且两者的LI标函数值相等。（3） 互补松弛性：原问题和对偶问题的松弛变量为Xs和厶，它们的可行解 为最优解的充分必要条件是r*x.s.=o,r5x- =0.（4） 对偶问题的最优解对应于原问题最优单纯形表中，初始基变量的检验数的负 值。若-人对应于原问题决策变量乂的检验数，则-Y对应于原问题松弛变量心的检验 数。4.已知线性规划问题max Z = 4x, + x2 + 2x38Xj +3x2 + x3 2 （第一种资源）.* 6x, + x2 + x3 0（1） 求出该问题产值最大的最优解和最优值。（2） 求出该问题的对偶问题的最优解和最优值。（3） 给出两种资源的影子价格，并说明其经济含
19、义：第一种资源限量曲2变为4, 最优解是否改变（4） 代加工产品丁，每单位产品需消耗第一种资源2单位，消耗笫二种资源3单位，应该如何定价解：（1）标准化，并列出初始单纯形表勺412006CbXbbX2心些心02831102/808611018/64120041/413/81/81/802013/265/41/43/412601/23/2-1/20228311006220116125020山最末单纯性表可知，该问题的最优解为：X = （0,020,6）了 ,即E = 0宀=0內=2 ,最优值为Z = 4.（2） III原问题的最末单纯形表可知，对偶问题的最优解和最优值为：y = 2, y2 =
20、0, w = 4 （3） 两种资源的影子价格分别为2、0,表示对产值贡献的大小；第一种资源限量 山2变为4,最优解不会改变。（4） 代加工产品丁的价格不低于2x2 + 0x3 = 4.5.某厂生产A, B, C, D4种产品,有关资料如表26所示。表26资源消耗产品资源供应量（公斤）原料成本（元/公斤）ABCD甲2312800乙54341200丙34531000单位产品售价（元）21（1）请构造使该厂获利润最大的线性规划模型，并用单纯形法求解该问题（不计 加工成本）。（2） 该厂若出租资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数 学模型，资源甲、乙、丙的影子价格是多少若工厂可在市场
21、上买到原料丙，工厂是否应 该购进该原料以扩大生产（3） 原料丙可利用量在多大范围内变化，原最优生产方案中生产产品的品种不变 （即最优基不变）（4） 若产品B的价格下降了元，生产计划是否需要调整解：（1）设坷,心,勺，兀分别表示甲、乙、丙产品的生产量，建立线性规划模型max Z = X + 5x2 + 3x3 + 4x42Xj + 3x2 +x3 + 2x4 8005%j + 4x2 + 3x3 + 4x4 12003x + 4兀2 + 5x3 + 3x4 Oj = 1,23,4w 初始单纯形表51534000Ct b坷V2勺小心x&心8800 “2312100000/31120 尢543401020000/41100 x1353001000400/41534000最末单纯形表Cj15340000Xb心尤5乂600011/4013/4011/4140022021011
