兰州大学运筹学——线性规划问题的计算机求解课后习题题解.doc

第四章 线性规划问题的计算机求解4.1 有以下线性规划数学问题： max Z=2xl+3 x2 S.T. xl+ x210 2xl+ x24xl+3 x2242xl+ x216 xl 、 x201、 用EXCEL线性规划求解模板求解该数学模型。2、 本问题的最优解是什么？此时最大目标函数值是多少？3、 四个约束条件中，哪些约束条件起到了作用？各约束条件的剩余量或松弛量及对偶价格是多少？4、 目标函数中各变量系数在什么范围内变化时，最优解不变？5、 确定各给定条件中的常数项的上限和下限。解：1、 2、最优解：（3，7），最优值：27可变单元格终递减目标式允许的允许的单元格名字值成本系数增量减量$C$34x130211$D$34x270331约束终阴影约束允许的允许的单元格名字值价格限制值增量减量$R$11 实际值101.5101.22$R$12 实际值130491E+30$R$13 实际值240.52466$R$14 实际值130161E+303 3、 对于求最大化的问题，对偶价格=阴影价格 松弛量/剩余量 对偶价格xl+ x210 0 1.5 2xl+ x24 9 0 xl+3 x224 0 0.52xl+ x216 13 0 因第一、第三个约束条件的松弛量/剩余量为0 ，所以这两个约束条件起到了约束作用。 4、目标函数中各变量系数 1 C13 2 C16 5、常数项 8 b19.2 无限 b213 18 b33013 b4无限4.2 有以下线性规划数学问题： min f=8xl+3 x2 S.T. 500xl+100 x21200000 5xl+4 x260000100xl300000 xl 、 x201、用EXCEL线性规划求解模板求解该数学模型。2、本问题的最优解是什么？此时最大目标函数值是多少？3、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。4、目标函数中各变量系数在什么范围内变化时，最优解不变？5、确定各给定条件中的常数项的上限和下限。解：本问题无解。4.3 有以下线性规划数学问题： max Z=xl+2 x2+3 x3- x4 S.T. xl+2 x2+3 x315 2xl+ x2+5 x320xl+2 x2+ x3+ x410 xl 、 x2、 x3、 x401、用EXCEL线性规划求解模板求解该数学模型。2、本问题的最优解是什么？此时最大目标函数值是多少？3、分别解释“递减成本”栏中各数据的含义。4、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。5、C2再增加2，同时C3再减少2，其最优解是否会变化？为什么？6、b1再增加3，同时b2再减少3，其对偶价格是否会变化？为什么？解：1、2、最优解：（0，2.143，3.571，0），最优值：15 （本问题可能是多解问题）3、可变单元格终递减目标式允许的允许的单元格名字值成本系数增量减量$C$34x100101E+30$D$34x22.1428571430201.4$E$34x33.5714285710370$F$34x40-1-111E+30约束终阴影约束允许的允许的单元格名字值价格限制值增量减量$R$11 实际值151151.6666666673$R$12 实际值2002053.75$R$13 实际值7.8571428570101E+302.142857143递减成本栏中的数据的绝对值，分别表示四个变量在目标函数中系数，当最优解中不为0的变量，其递减成本必为0，最优解中变量值为0时，要使其解不为0时要使相应系数增加递减成本的绝对值，其解不为0。本问题中，x1为0 ，递减成本的绝对值也为0 ，说明c1=1就能使x10; x4为0，递减成本的绝对值为1，说明c4=0才能使x40。4、 松弛量 对偶价格xl+2 x2+3 x315 0 1 2xl+ x2+5 x320 0 0xl+2 x2+ x3+ x410 2.143 05、上表中 0.6C22 3C310 可见C2没有增加允许，C3没有减少允许，所以C2再增加2，同时C3再减少2，其最优解必将发生变化。6、b1的允许增量是1.667,所以b1再增加3，同时b2再减少3，其对偶价格必将发生变化。 4.4 有以下线性规划数学问题： min f=-2xl- x2+3 x3-4 x4 S.T. xl+2 x2+4 x3- x46 2xl+3 x2- x3+ x418xl+ x2+ x34 xl 、 x2、 x3、 x401、用EXCEL线性规划求解模板求解该数学模型。2、本问题的最优解是什么？此时最大目标函数值是多少？3、分别解释“递减成本”栏中各数据的含义。4、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。5、C1再减少5，同时C3再增加5，其最优解是否会变化？为什么？6、b1再减少5，同时b3再增加5，其对偶价格是否会变化？为什么？解：1、2、最优解：（0，0，4，22），最优值：-76。3、终递减目标式允许的允许的单元格名字值成本系数增量减量$C$34x107-21E+307$D$34x2012-11E+3012$E$34x340311E+30$F$34x4220-411E+30终阴影约束允许的允许的单元格名字值价格限制值增量减量$R$11 实际值-6061E+3012$R$12 实际值18-4181E+3012$R$13 实际值4-1444递减成本栏中的数据的绝对值，分别表示四个变量在目标函数中系数，当最优解中不为0的变量，其递减成本必为0，最优解中变量值为0时，要使其解不为0时要使相应系数增加递减成本的绝对值，其解不为0。本问题中，x1为0 ，递减成本的绝对值为7 ，说明c1由现在的-2变为-1时，就能使x10; x2为0，递减成本的绝对值为12，说明c2=0由现在的-1变为11时才能使x20。4、 松弛量 对偶价格xl+2 x2+4 x3- x46 12 0 2xl+3 x2- x3+ x418 0 4xl+ x2+ x34 0 1 5、上表中 -9C1无限 无限C34 可见C3只能允许增加1，当增加5时其最优解必将发生改变。6、b3只能增加4，所以当b3只能增加5时，其对偶价格必将发生改变。4.5 某公司根据订单安排生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用如下表：月份123456需求量（件）504050455530单位生产费用（元/件）825775850850775825单位存储费用（元/件）403035204040又知公司每月的生产能力为100件，每月仓库的容量为50件。问：如何确定产品未来半年内每月最佳生产量和存储量才能使总的费用为最少？若设未来6个月每月的生产量分别为 xl、 x2、 x3、 x4、 x5、 x6 每月的存储量分别为 x7、 x8、 x9、 x10、 x11、 x12可得线性规划数学模型：min f=825xl+775 x2+850 x3+850 x4+775 x5+825 x6+40x7+30 x8+35 x9+20 x10+40 x11+40 x12 S.T. xl- x7=50 x2+ x7- x8=40x3+ x8- x9=50x4+ x9- x10=45x5+ x10- x11=55x6+ x11- x12=30xl100x2100x3100x4100x5100x6100x750x850x950x1050x1150x1250 xi 0 (i=1,2,.12)1、用EXCEL线性规划求解模板求解该数学模型。2、本问题的最优解是什么？此时最大目标函数值是多少？3、分别解释“递减成本”栏中各数据的含义4、各约束条件的剩余量或松驰量及对偶价格是多少？其中一些约束条件的对偶价格为负，其意义是什么？。5、后12个约束条件中，大部分约束条件的对偶价格为0是什么意思？不为0的又具有什么含义？6、为什么目标函数中有些变量系数的取值范围为无上限？解：1、Excel求解2、本问题的最优解：（50，90，0，45，85，0，0，50，0，0，30，0） 最优值：2178253、可变单元格终递减目标式允许的允许的单元格名字值成本系数增量减量$C$34x15008251E+3090$D$34x2900775451E+30$E$34x3008501E+3035$F$34x44508503595$G$34x585077510855$H$34x60108251E+3010$I$34x7090401E+3090$J$34x850030451E+30$K$34x9035351E+3035$L$34x10095201E+3095$M$34x113004010855$N$34x120855401E+30855约束终阴影约束允许的允许的单元格名字值价格限制值增量减量$R$11实际值50825505050$R$12实际值40775401090$R$13实际值50850501000$R$14实际值45850455545$R$15实际值55775551585$R$16实际值30815301530$R$17实际值5001001E+3050$R$18实际值9001001E+3010$R$19实际值001001E+30100$R$20实际值4501001E+3055$R$21实际值8501001E+3015$R$22实际值001001E+30100$R$23实际值00501E+3050$R$24实际值50-4550050$R$25实际值00501E+3050$R$26实际值00501E+3050$R$27实际值300501E+3020$R$28实际值00501E+3050从这个灵敏度分析表：递减成本栏表示的是：对于解为0的变量，其目标函数系数在现在基础上再减少的量，使其对应的解不为0 。4、 约束 松弛量 对偶价格xl- x7=50 0 -825 x2+ x7- x8=40 0 -775x3+ x8- x9=50 0 -815x4+ x9- x10=45 0 -850x5+ x10- x11=55 0 -775x6+ x11- x12=30 0 -815xl100 50 0x2100 10 0x3100 100 0x4100 55 0x5100 15 0x6100 100 0x750 50 0x850 0 45x950 50 0x1050 50 0x1150 20 0x1250 50 0 其中对偶价格为负的意思是这些约束条件中，每增加一个常数项值，将会使目标函数值增加量，因为