1、线性规划(续1.3) 1.3单纯形法 利用单纯形表的方法求解线性规 划重点(p30-4513.1,132, 13.3) 此项内容是本章的重点,学习中应注 意掌握表格单纯形法求解线性规划问题 的基本过程。要通过读懂教材内容以及 大量练习来掌握。 16
16 1、 线 性 规 划 （续1.3） 1. 3 单纯形法 利用单纯形表的方法求解线性规 划——重点 (p30--45 1.3.1, 1.3.2, 1.3.3) 此项内容是本章的重点，学习中应注 意掌握表格单纯形法求解线性规划问题 的基本过程。要通过读懂教材内容以及 大量练习来掌握
1、线性规划(续1.3) 表格单纯形法(p40-p45) 考虑:b1>0i=1,…,m Maxz=c1X1+c2x2+….+ XIt a 111 X2+..+a1 12X2 a21 X1+ a22 X2+...+ a2n Xn s b2 a. x,+ ++ax< b 1,x2,…,Xn≥0 加入松弛变量: Max Z t. au XI+a12 X2+...+ ain Xn+ Xn+1=bI a21 X1+ a22 X2+...+ a2n Xn+ Xn+2= b2 amI X+ am2 X2+...+ amn Xn+ Xnm=b X1, X27 n+1 Xam≥0 17
17 1、 线 性 规 划 （续1.3） • 表格单纯形法( p40-- p 45) • 考虑： 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 • 加入松弛变量： Max z = c1 x1 + c2 x2 + … + cn xn 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
1、线性规划(续1.3) 显然,x=0j=1,…,n;x=b11=1,…,m是基本可行解 对应的基是单位矩阵 以下是初始单纯形表: c n+1 Cntm Cp X B B X ntm n+1 In ain+ aint n+2 2 a2 a 2n+1 a 0 n+m ntm nn amn+m 0 0 m 其中:f=∑Cn+i =c2cm2ai为检验数cn+=0 m 0(+ 18
18 显然，xj = 0 j = 1, … , n ; xn+i = bi i = 1 , … , m 是基本可行解 对应的基是单位矩阵。 以下是初始单纯形表： m m 其中：f = -∑ cn+i bi j = cj -∑ cn+i aij 为检验数 cn+i = 0 i= 1,…,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m 1、 线 性 规 划 （续1.3） c1 … cn cn+1 … cn+m CB XB x1 … xn xn+1 … xn+m θi cn+1 xn+1 b1 a11 … a1n a1n+1 … a1n+m θ1 cn+2 xn+2 b2 a21 … a2n a2n+1 … a2n+m θ2 ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ cn+m xn+m bm am1 … amn amn+1 … amn+m θm -z f σ1 … σn 0 … 0
1、幾性规划(块1.3单纯形法解题例) 例1。化标准形式:Maxz=50x1+100x2 S t X1+ 300 2 400 Xo+ 250 X1,X2,X3,X4,x5≥0 L501000 0 X 0 300 0 0 300 400 0 400 250 0 0 250 50100 50 0 0 75 100 250 0 0 2500050 0 50 50 0 0 100 0 50 5 最优解ⅹ1=50x2=250x4=50(松弛标量,表示原料A有50个单位的剩余)
19 1、 线 性 规 划 （续1.3单纯形法解题例） 50 100 0 0 0 CB XB x1 x2 x3 x4 x5 θi 0 x3 300 1 1 1 0 0 300 0 x4 400 2 1 0 1 0 400 0 x5 250 0 (1) 0 0 1 250 -z 0 50 100* 0 0 0 0 x3 50 (1) 0 1 0 -1 50 0 x4 150 2 0 0 1 -1 75 100 x2 250 0 1 0 0 1 -z -25000 50* 0 0 0 -100 50 x1 50 1 0 1 0 -1 0 x4 50 0 0 -2 1 1 100 x2 250 0 1 0 0 1 -z -27500 0 0 -50 0 -50 例1。化标准形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250 x1 , x2 , x3 , x4 , x5 ≥ 0 最优解 x1 = 50 x2 = 250 x4 = 50（松弛标量，表示原料A有50个单位的剩余）
1、线性规划(续1.3) 注意:单纯形法中 1、每一步运算只能用矩阵初等行变换 2、表中第3列的数总应保持非负(≥0); 3、当所有检验数均非正(≤0)时,得到最 优单纯形表。 20
20 • 注意：单纯形法中， 1、每一步运算只能用矩阵初等行变换； 2、表中第3列的数总应保持非负（≥ 0）； 3、当所有检验数均非正（≤ 0）时，得到最 优单纯形表。 1、 线 性 规 划 （续1.3）