单纯行法-截止至理论部分

1、单 纯 行 法线性规划问题的解求解方法一 般 有两种方法图 解 法单纯形法两个变量、直角坐标适用于任意变量、但需将一般形式变成标准形式提纲基本概念单纯行法表格单纯行法人工变量问题提纲基本概念单纯行法表格单纯行法人工变量问题例1（仍然使用图解法的例题）首先检验是否为标准形式！ max Z= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 x1x2x3x4x5单位矩阵max Z= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x

2、2 0基本概念 A是约束方程组的mn维系数矩阵，mn，其rank(A) = m；B是矩阵A中m阶非奇异子矩阵，则称B是线性规划问题的一个基。B=(P1, P2, Pm)，其列向量Pj称为基B的基向量。与基向量Pj相对应的变量xj就成为基变量，其余的就成为非基变量。约束条件数远少于决策变量数！例1（仍然使用图解法的例题）首先检验是否为标准形式！ max Z= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 x1x2x3x4x5单位矩阵基变量x3，x4， x5，非

3、基变量是x1，x2的基最多有Cnm=C53=10 x3x4x5x1x4x5x2x4x5x3x1x5x3x2x5x3x4x1x3x4x2x1x2x5x1x2x4x1x2x5问题：是否所有33的子矩阵都是基？例题的演示基 可 行 解 定 义x3x4x5基变量x3，x4， x5，非基变量是x1，x2令非基变量x1=x2=0，得到一个基解 x3=8，x4=12， x5=36。此时得到一个基可行解，B为可行基。基 可 行 解 定 义可行解基解基可行解提纲基本概念单纯行法表格单纯行法人工变量问题基本定理定理1. 若可行域有界，线性规划的最优解一定可以在可行域的顶点上达到。 定理2. 线性规划问题的基可行解

4、对应可行域的顶点。线性规划的基本定理 从可行域的某个顶点出发，即找到一个基可行解，拿目标函数做尺度衡量一下看是否最优。如若不是，则向邻近的顶点转移，即换一个基求解、检验，如此迭代，目标值逐步改善，直至求得最优解。 线性规划的解题思路 用单纯行法求解最优解的步骤Step1：确定基变量，非基变量；Step2：用非基变量表示基变量和目标函数；Step3：求得基可行解，判断是否为最优解，是则停止，不是则转Step1。 max Z=3x1 +5 x2 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 x1, x2 , x3 , x4 , x5 0 x1x2x3x4x5x

5、3x4x5非奇异子阵，做为一个基基变量：x3, x4, x5非基变量：x1, x2单纯形法原理用非基变量线性表示基变量，即x3= 8 - x1 x4 =12 - 2x2 x5=36 -3x1-4 x2 用非基变量线性表示目标函数：Z=3x1 +5x2 令非基变量x1=0，x2=0，找到一个初始基可行解： x1=0， x2 =0，x3 =8，x4 =12，x5 =36即X0=(0,0,8,12,36) T，Z=3x1 +5x2=0。从目标函数Z=3x1 +5x2可知：非基变量x1和x2的系数(检验数)均为正数，增大x1，x2或都会增大目标函数。1. 求初始基可行解 单纯形法原理确定进基变量因为x

6、2的系数5（检验数）大于x1的系数3（检验数），即每增加一个单位x2，目标函数增加得多，因此x2被选为进基变量。2. 第一次迭代 单纯形法原理确定离基变量x3 =8 x1 x4 =12- 2x2 x5=36 -3x1-4 x2保持原非基变量x1 =0 x2变成基变量时应保证 x3 , x4, x5非负，即2. 第一次迭代（续） x3 =8 0 x4 =12- 2x2 0 x5=36 -4 x2 0 x2 12/2x2 36/4 单纯形法原理2. 第一次迭代（续）用非基变量x1、 x4线性表示基变量x2、x3、x5用非基变量x1、 x4表示目标函数 max Z=3x1 +5 x2 x1 + x3

7、 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 x1, x2 , x3 , x4 , x5 0单纯形法原理2. 第一次迭代（续）主行主列主元 x1 +0 x2 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 -Z+3x1 +5x2 +0 x3 +0 x4+0 x5 =0进基变量所在列为主列，确定离基变量所在的行为主行单纯形法原理进行初等变换，变主元为1，主列为单位列向量。2. 第一次迭代（续） x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5

8、 =-30 x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +5 x2 +0 x3 +0 x4 +0 x5 =0 x1 +0 x2 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 x2 +1/2 x4 =6 3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4 +0 x5 =0单纯形法原理2. 第一次迭代（续）用非基变量x1、 x4表示基变量x2、x3、x5，即x3=8 x1 x2=6- 1

9、/2x4 x5=12 -3x1+4 x4用非基变量x1、 x4表示目标函数Z=3x15/2x4 +30令非基变量x1=0，x4=0，找到另一个基可行解 x1=0， x2 =6，x3 =8，x4 =0， x5 =12即X1=(0, 6, 8, 0, 12) T目标函数Z=3x15/2x4 + 30=30单纯形法原理确定进基变量3. 第二次迭代 目标函数Z=3x1 5/2x4 +30 =30，非基变量x1的检验数为正数，确定x1为进基变量。单纯形法原理确定离基变量3. 第二次迭代 （续） x3 =8- x1 0 x2 =6 0 x5=12 -3x10 x1 8/1x1 12/3 上一次迭代后，基变

10、量x2、x3、x5用非基变量x1 、x4表示 x3=8 x1 x2=6- 1/2x4 x5=12 -3x1+4 x4保持原非基变量x4 =0，x1变成基变量时应保证 x2 , x3, x5非负，即 单纯形法原理用非基变量x4,x5线性表示基变量x1,x2,x3进基变量所在列为主列，确定离基变量所在的行为主行变主元为1，主列为单位列向量3. 第二次迭代（续） x1 + x3 =8 x2 +1/2 x4 =6 x1 + -2/3 x4 + 1/3x5=4 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30 x3 +2/3 x4 -1/3x5 =4 x2 +1/2 x4 =6 x

11、1 + -2/3 x4 + 1/3x5=4 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30 x3 +2/3 x4 -1/3x5 =4 x2 +1/2 x4 =6 x1 + -2/3 x4 +1/3x5=4 -Z+0 x1 +0 x2 +0 x3 -1/2x4 - x5 =-42 1 x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30单纯形法原理3. 第二次迭代（续）用非基变量x4,x5表示基变量x1,x2,x3，即x3 =4 2/3x4 +1/3x5x2=6- 1/4x4 x1=4 +2/3x4-1/3 x5 令非基变量x4=0，x5=0，又找到一个基可行解 目标函数中非基变量检验数均非正，得最优解X*=(4,6,4,0,0)T，Z*=42 x1=4， x2 =6，x3 =4，x4 =0， x5 =0即 X2=(4,6,4,0,0)T Z=42 用非基变量x4,x5表示目标函数Z= -1/2x4 -x5 +42单纯形法的几