1、线性规划(续1.3) 般情况的处理及注意事项的强调(p45-55) 1.3.4段主要是讨论初始基本可行解不明显时,常用的方法。 要弄清它的原理,并通过例1-14~例1-17掌握这些方法,同 时进一步熟悉用单纯形法解题。 考虑一般问题:b1>0i=1,…,m Aaxz=c1x1+c2x2+…+ S t 11X1 122 +.+a In b 21X1+a2X2+..+a2n amIX+ am2 x2+...+ amn Xn= b X xn≥0
21 1、 线 性 规 划 （续1.3） • 一般情况的处理及注意事项的强调（p45--55） 1.3.4段主要是讨论初始基本可行解不明显时，常用的方法。 要弄清它的原理，并通过例1-14 ~ 例1-17掌握这些方法，同 时进一步熟悉用单纯形法解题。 考虑一般问题： bi > 0 i = 1 , … , m Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0
1、线性规划(续1.3) 大M法:引入人工变量x1≥0i=1,…,m;充 分大正数M。得到, Maxz=c1X1+C2X2+….+CnX1+Mxn+1+….+Mxm+m S t 112X1+a12X2+ +ain Xn t Xn+1=b1 t axt nn amI x,t X,+ mn Xn+ Xn+m-b xn+m≥0 显然,x=0j=1,…,n,x=b1i=1,…,m是基本可行解 对应的基是单位矩阵。 结论:若得到的最优解满足x=0i=1,…,m则是原 问题的最优解;否则,原问题无可行解。 22
22 1、 线 性 规 划 （续1.3） • 大M法： 引入人工变量 xn+i ≥ 0 i = 1 , … , m ; 充 分大正数 M 。 得到， Max z = c1 x1 + c2 x2 + … + cn xn + M xn+1 + … + M xn+m s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0 显然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解 对应的基是单位矩阵。 • 结论：若得到的最优解满足 xn+i = 0 i = 1 , … , m 则是原 问题的最优解；否则，原问题无可行解
1、 线性规划(续1.3) 两阶段法:引入人工变量x1≥0,i=1,…,m;构造, Max Z=-Xn+1-Xn+2 n+m S t a1 X II 12 X2+.+a b n X1+a22x2+….+a2nxn+x amI X1+ am2 x2+...+ amn Xn +Xn+m= bm ,xn+m≥0 第一阶段求解上述问题: 显然,x=0j=1,…,n;Xm1=b1i=1,…,m是基本可行解 对应的基是单位矩阵 结论:若得到的最优解满足xn+;=0i=1,…,m则是原问 题的基本可行解;否则,原问题无可行解。 ·得到原问题的基本可行解后,第二阶段求解原问题
23 1、 线 性 规 划 （续1.3） • 两阶段法：引入人工变量xn+i ≥ 0，i = 1 , … , m；构造， Max z = - xn+1 - xn+2 - … - xn+m s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0 • 第一阶段求解上述问题： 显然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解 对应的基是单位矩阵。 • 结论：若得到的最优解满足 xn+i = 0 i = 1 , … , m 则是原问 题的基本可行解；否则，原问题无可行解。 • 得到原问题的基本可行解后，第二阶段求解原问题
1、线性规划(续1.3)例题 例:(LP)Max 5x1+2x2+3 X X1+2x2+3x 2x1+X2+5x3 X1+2x2+4x3+x4=26 XI.X. X2. X 大M法问题(LP-M) Max Z=5X1+2X2+3- X4-M X5-MX6 x1+2x2+3x2+x 5 15 2X +5x 6 20 +2x2+ 4x3+ 4 26 XI X X5,X6≥0 ·两阶段法:第一阶段问题(LP-1) Max Z X1+2x2+3x3+xs=15 2x1+x2+5x3 X 20 x1+2x2+4x2+x1=26 3
24 1、 线 性 规 划 （续1.3）例题 例：（LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0 • 大M法问题（LP - M） Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 • 两阶段法 ：第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
1、线性规划(续1.3)大M法例 大M法(LP-M) 5 2 C 15 20 x212 0 4 6.5 35M+263M+63M+48M+70 0 1/5 (7/5) 0 3/5 15/7 4 2/5 0 1/5 20 10 3/5 6/5 0 0 25/3 3M-2M5+16/57/5M+13/500 0-8/5M-7/5 2 15/7 -1/7 5/7 3/7 25/7 (3/7 0 1/7 25/3 -6/7 2/7 53/7 25/7 0M-13/7M2/7 2 10/3 0 0001000 1/3 2/3 1/3 25/3 7/3 0010 -1/3 2/3 112/3 25/3 M-2/3M+8/3 得到最优解:(25/3,10/3,0,11)T最优目标值:112/3
25 1、 线 性 规 划 （续1.3）大M法例 5 2 3 -1 -M -M CB XB x1 x2 x3 x4 x5 x6 θi -M x5 15 1 2 3 0 1 0 5 -M x6 20 2 1 (5) 0 0 1 4 -1 x4 26 1 2 4 1 0 0 6.5 -z 35M+26 3M+6 3M+4 8M+7 0 0 0 -M x5 3 -1/5 (7/5) 0 0 1 -3/5 15/7 3 x3 4 2/5 1/5 1 0 0 1/5 20 -1 x4 10 -3/5 6/5 0 1 0 -4/5 25/3 -z 3M-2 -M/5+16/5 7/5M+13/5 0 0 0 -8/5M-7/5 2 x2 15/7 -1/7 1 0 0 5/7 -3/7 3 x3 25/7 (3/7) 0 1 0 -1/7 2/7 25/3 -1 x4 52/7 -3/7 0 0 1 -6/7 -2/7 -z -53/7 25/7 0 0 0 -M-13/7 -M-2/7 2 x2 10/3 0 1 1/3 0 2/3 -1/3 5 x1 25/3 1 0 7/3 0 -1/3 2/3 -1 x4 11 0 0 1 1 -1 0 -z -112/3 0 0 -25/3 0 -M-2/3 -M+8/3 •大M法 （LP - M） • 得到最优解：(25/3，10/3，0，11)T 最优目标值：112/3