第 9 页 共 64 页
x1+4x2+2x3?8
3x1+2x2?6
x1，x2，x3?0
（3）max z=10x1+15x2+12x3 5x1+3x2+x3?9 -5x1+6x2+15x3?15 2x1+x2+x3?5
x1，x2，x3?0
（4）max z=2x1-x2+2x3
x1+x2+x3?6
-2x1+x3?2 2x2-x3?0
x1，x2，x3?0
解：（1）解法一：大M法
化为标准型：
Max z=2x1+3x2-5x3-Mx4+0x5-Mx6 s.t. x1+x2+x3+x4=7 2x1-5x2+x3-x5+x6=10
x1,x2,x3,x5,x4,x6?0 M是任意大整数。
单纯形表： cj 2 b 7 x1 3 x2 -5 x3 -M x4 0 x5 -M x6 ?i CB XB x4 -M 1 1 1 1 0 0 7 第 10 页 共 64 页
-M x6 10 17M 2 5 [2] -5 1 2M-5 1/2 1/2 0 0 1 0 -1 -M 1/2 -1/2 1 0 -1/2 1/2 5 4/7 - -z -M 2 x4 x1 3M+2 3-4M 0 [7/2] 1 -5/2 -z 3 2 x2 x1 2M-10 0 4/7 45/7 0 1 (7/2)M+8 0.5M-6 0 1 0 0 1/7 6/7 -50/7 2/7 5/7 0.5M+1 -1.5M-1 1/7 -1/7 -1/7 1/7 -z -102/7 0 -M-16/7 -1/7 -M+1/7 最优解是： X=（45/7，4/7，0，0，0 )T 目标函数最优值 max z=102/7 有唯一最优解。 解法二： 第一阶段数学模型为 min w= x4+ x6 S.t. x1 +x2+ x3+ x4=7 2 x1-5 x2+ x3- x5+ x6=10 x1,x2,x3,x4，x5,x6?0 （单纯形表略） 最优解 X=（45/7，4/7，0，0，0 )T 目标函数最优值 min w=0 第二阶段单纯形表为： 2 c j3 x2 -5 x3 0 x5 ?i CB XB x2 x1 b 4/7 45/7 x1 3 2 0 1 1 0 1/7 6/7 1/7 -1/7 第 11 页 共 64 页
-z 最优解是 -102/7 0 0 -50/7 -1/7 X=（45/7，4/7，0，0，0 )T
Max z=102/7
（2）解法一：大M法
z?=-z 有max z?=-min （-z?）=-min z 化成标准形：
Max z?=-2x1-3x2-x3+0x4+0x5-Mx6-Mx7 S.T.
x1+4x2+2x3-x4+x6=4 3x1+2x2-x5+x7=6 x1,x2,x3,x4，x5,x6，x7?0 （单纯性表计算略）
线性规划最优解X=（4/5，9/5，0，0，0 ，0)T 目标函数最优值 min z=7 非基变量x3的检验数?3=0，所以有无穷多最优解。 两阶段法：
第一阶段最优解X=（4/5，9/5，0，0，0，0 )T是基本可行解,min w=0 第二阶段最优解（4/5，9/5，0，0，0，0 )T min z=7 非基变量x3的检验数?3=0，所以有无穷多最优解。
（3）解：大M法 加入人工变量，化成标准型：
Max z=10 x1+15 x2+12 x3+0 x4+0 x5+0 x6-M x7 s.t. 5 x1+3 x2+ x3+ x4=9 -5 x1+6 x2+15 x3+ x5=15 2 x1+ x2+ x3- x6+ x7=5 x1,x2,x3,x4，x5,x6，x7?0 单纯形表计算略
第 12 页 共 64 页
当所有非基变量为负数，人工变量x7=0.5，所以原问题无可行解。 两阶段法（略）
（4）解法一：大M法
单纯形法，（表略）非基变量x4的检验数大于零，此线性规划问题有无界解。 两阶段法略
1.7求下述线性规划问题目标函数z的上界和下界；
Max z=c1x1+c2x2
a11x1?a12x2?b1 a21x1?a22x2?b2
1?c1?3，4?c2?6，8?b1?12，10?b2?14，?1?a11?3，2?a12?5，其中：
2?a21?4，4?a22?6
解：
? 求Z的上界
Max z=3x1+6x2 s.t. -x1+2x2?12 2x1+4x2?14 x2，x1?0 加入松弛变量，化成标准型，用单纯形法解的，最优解 X=（0，7/2，5，0 )T
目标函数上界为z=21 存在非基变量检验数等于零，所以有无穷多最优解。 ? 求z的下界 线性规划模型： Max Z= x1+4x2 s.t. 3x1+5x2?8 4x1+6x2?10 x2，x1?0
加入松弛变量，化成标准型，解得：
相关推荐：
loading