第四章 线性规划问题的计算机求解
4.1 有以下线性规划数学问题： max Z=2xl+3 x2
S.T. xl+ x2≤10
2xl+ x2≥4
xl+3 x2≤24 2xl+ x2≤16
xl 、 x2≥0
1、 用EXCEL线性规划求解模板求解该数学模型。 2、 本问题的最优解是什么？此时最大目标函数值是多少？
3、 四个约束条件中，哪些约束条件起到了作用？各约束条件的剩余量或松弛量及对偶价格是多少？
4、 目标函数中各变量系数在什么范围内变化时，最优解不变？ 5、 确定各给定条件中的常数项的上限和下限。 解： 1、
2、最优解：（3，7），最优值：27
3、第一、第三个约束条件起到了约束作用。
松弛量/剩余量 对偶价格
xl+ x2≤10 0 1.5
2xl+ x2≥4 9 0
xl+3 x2≤24 0 0.5 2xl+ x2≤16 13 0 4、目标函数中各变量系数 1≤ C1≤3 2≤ C1≤6 5、常数项 8≤ b1≤9.2 无限≤ b2≤13 18≤ b3≤30
13≤ b4≤无限
4.2 有以下线性规划数学问题：
min f=8xl+3 x2
S.T. 500xl+100 x2≤1200000 5xl+4 x2≥60000
100xl≥300000 xl 、 x2≥0
1、用EXCEL线性规划求解模板求解该数学模型。
2、本问题的最优解是什么？此时最大目标函数值是多少？
3、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。 4、目标函数中各变量系数在什么范围内变化时，最优解不变？ 5、确定各给定条件中的常数项的上限和下限。 解：
本问题无解。
4.3 有以下线性规划数学问题： max Z=xl+2 x2+3 x3- x4 S.T. xl+2 x2+3 x3≤15 2xl+ x2+5 x3≤20 xl+2 x2+ x3+ x4≤10
xl 、 x2、 x3、 x4≥0
1、用EXCEL线性规划求解模板求解该数学模型。
2、本问题的最优解是什么？此时最大目标函数值是多少？ 3、分别解释“递减成本”栏中各数据的含义。
4、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。 5、C2再增加2，同时C3再减少2，其最优解是否会变化？为什么？ 6、b1再增加3，同时b2再减少3，其对偶价格是否会变化？为什么？ 解：
1、
2、最优解：（0，2.143，3.571，0），最优值：15
3、递减成本栏中的数据的绝对值，分别表示四个变量在目标函数中系数的相差值。 4、 松弛量 对偶价格
xl+2 x2+3 x3≤15 0 1 2xl+ x2+5 x3≤20 0 0
xl+2 x2+ x3+ x4≤10 2.143 0 5、最优解必将发生变化。 6、对偶价格必将发生变化。
4.4 有以下线性规划数学问题： min f=-2xl- x2+3 x3-4 x4 S.T. xl+2 x2+4 x3- x4≤6 2xl+3 x2- x3+ x4≤18
xl+ x2+ x3≤4
xl 、 x2、 x3、 x4≥0
1、用EXCEL线性规划求解模板求解该数学模型。
2、本问题的最优解是什么？此时最大目标函数值是多少？
3、分别解释“递减成本”栏中各数据的含义。
4、各约束条件的剩余量或松弛量及对偶价格是多少？分别解释其含义。 5、C1再减少5，同时C3再增加5，其最优解是否会变化？为什么？ 6、b1再减少5，同时b3再增加5，其对偶价格是否会变化？为什么？ 解：
1、
2、最优解：（0，0，4，22），最优值：-76。
3、递减成本栏中的数据的绝对值，分别表示四个变量在目标函数中系数的相差值。 4、 松弛量 对偶价格 xl+2 x2+4 x3- x4≤6 12 0
2xl+3 x2- x3+ x4≤18 0 4
xl+ x2+ x3≤4 0 1
5、最优解必将发生改变。 6、对偶价格必将发生改变。
4.5 某公司根据订单安排生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用如下表：
月份 需求量（件） 1 50 2 40 3 50 4 45 5 55 6 30 单位生产费用（元/件） 825 775 850 850 775 825 单位存储费用（元/件） 40 30 35 20 40 40 又知公司每月的生产能力为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=40
x3+ x8- x9=50 x4+ x9- x10=45 x5+ x10- x11=55 x6+ x11- x12=30 xl≤100 x2≤100 x3≤100 x4≤100 x5≤100 x6≤100 x7≤50 x8≤50 x9≤50 x10≤50 x11≤50
x12≤50
xi ≥0 (i=1,2,.......12)
1、用EXCEL线性规划求解模板求解该数学模型。
2、本问题的最优解是什么？此时最大目标函数值是多少？ 3、分别解释“递减成本”栏中各数据的含义
4、各约束条件的剩余量或松弛量及对偶价格是多少？其中一些约束条件的对偶价格为负，其意义是什么？。
5、后12个约束条件中，大部分约束条件的对偶价格为0是什么意思？不为0的又具有什么含义？
6、为什么目标函数中有些变量系数的取值范围为无上限？
解：
1、
2、本问题的最优解：（50，90，0，45，85，0，0，50，0，0，30，0） 最优值：217825
3、递减成本栏中的数据的绝对值，分别表示四个变量在目标函数中系数的相差值。 4、 约束 松弛量 对偶价格 xl- x7=50 0 -825
x2+ x7- x8=40 0 -775
x3+ x8- x9=50 0 -815 x4+ x9- x10=45 0 -850 x5+ x10- x11=55 0 -775 x6+ x11- x12=30 0 -815 xl≤100 50 0 x2≤100 10 0 x3≤100 100 0 x4≤100 55 0 x5≤100 15 0 x6≤100 100 0 x7≤50 50 0 x8≤50 0 45 x9≤50 50 0 x10≤50 50 0 x11≤50 20 0 x12≤50 50 0
5、后12个约束条件中，大部分约束条件的对偶价格为0是因为这些约束中，其松弛量都不为0，也就是说在前6个约束中，生产量没有达到最大量（最大生产能力）的要求，再扩大生产能力不会对最优目标产生影响；后6个约束中，说明仓库没有放满，再扩建立仓库也不会改变总的存储存用。
6、目标函数中有些变量系数的取值范围为无上限一般表示其解为0 ，而不为的相关值是应减少的数，所以对于增加的值，无论多大都不会影响相应的解。
