运筹平时所有课件单纯行法-9月24日

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. 若可行域有界，线性规划的最优解一定可以在可行域的顶点上达

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

5、, x4 , x5 0 x1x2x3x4x5x3x4x5非奇异子阵，做为一个基基变量：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.

6、求初始基可行解 单纯形法原理确定进基变量因为x2的系数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表示目标函数

7、max Z=3x1 +5 x2 x1 + x3 =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

8、+0 x2 +0 x3 5/2x4 +0 x5 =-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

9、、x3、x5，即x3=8 x1 x2=6- 1/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

10、x1 8/1x1 12/3 上一次迭代后，基变量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

11、/3x5 =4 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 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，即x

12、3 =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单纯形法的几何意义x1 =82x2 =123x1 +4 x2 =36x1x248123690ABC(4,6)DX0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX2=(4,6,4,0

13、,0)T从可行域的某个顶点出发，即找到一个基可行解，拿目标函数做尺度衡量一下看是否最优。若不是，则向邻近的顶点转移，即换一个基求解、检验，如此迭代，目标值逐步改善，直至求得最优解。 提纲基本概念单纯行法表格单纯行法人工变量问题表格单纯形法 表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。 单纯形法表cjc1c2cjcn比值CBXBbx1x2xjxncB1xB1b1a11a12a1ja1n1cB2xB2b2a21a22a2ja2n2cBmxBmbmam1am2amjamnm检验数j12jn表格单纯形法 max Z=3x1 +5x2 +0 x3 +0 x4+0 x5 x1 +

14、 x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 计算举例cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x500035000-12/2=636/4=9表格单纯形法检验数j81010060101/2012300-21x3x2x5050300-5/208-4cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x500035000-12/2=636/4=9表格单纯形法cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21

15、x3x2x5050300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053000-1/2-1最优解 :X*=(4,6,4,0,0)T，Z*=42最优解判别准则：对可行基B，CN-CBB-1N 0（若非基变量的检验数小于0），B的基可行解X就是基最优解，也是最优解，B就是最优基。 max Z=3x1 +5 x2 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 x1, x2 , x3 , x4 , x5 0cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x1

16、4100-2/31/3检验数j000-1/2-1最优基:使得目标函数达到最优的基可行解对应的基最优表最优基的逆：初始基变量在最优表中对应的系数列向量按顺序构成的矩阵.例：maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 , x2 0S.t.标准化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0cj比值CBXBb检验数jx1x2x3x432002-211031-301x3x4003200-3检验数j80-512x3x10331-3010110-3大于0的检验数中，若某个k

17、所对应的系数列向量Pk0，则此问题是无界解，停止计算检验数2=110，x2所在列的系数向量元素非正，无界不考虑非正值的aij！做图查看是否为无界解-2x1 + x2 =2x1 -3x2 =3x2123-1x1123-1maxZ= 3x1 +2x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0将线性规划问题化成标准型构造m阶单位阵作为初始可行基，建立单纯形表计算各非基变量xj的检验数所有j0？问题已得到最优解大于0的检验数中某个对应的系数列向量0？无界解计算比值，确定入/出基变量，建立新的单纯形表，左侧基变量替换，系数矩阵变换是否是否将线性规划问题化成标准型。找出或构造一个

18、m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=cj-CBPj，若所有j0，则问题已得到最优解(若某非基变量的检验数为0，则有无穷多最优解，否则为唯一解)，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为入基变量，再按规则计算：=minbi/aik| aik0=bl/alk 确定xl为出基变量。建立新的单纯形表，此时基变量中xk取代了xl的位置。以alk为主元素进行迭代，把xk所对应的列向量变为单位列向量，即alk变为1，同列中其它元素为0，转第 步。 表格单

19、纯形法计算步骤 提纲基本概念单纯行法表格单纯行法人工变量问题单纯形法解题时，需要有一个单位阵作为初始基。如何用单纯行法求解下面问题的最优解？max Z= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0人工变量问题 单纯形法解题时，需要有一个单位阵作为初始基。约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。人工构造单位矩阵加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。处理方法有大M 法人工变量问题大M法 例如 max Z= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0s.t.按大M法构造人造基，引入人工变量x4 , x5 ： max Z= 3x1 - x2 -2 x3 - M x4 - M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2