线性规划-2.ppt

1、1,第二部分 线性规划的单纯形法,单纯形法(Simplex Method)是美国人丹捷格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。,2,第二部分 线性规划单纯形法,第一节 单纯形法原理 第二节 表格单纯形法 第三节 单纯形法进一步讨论,3,LP问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。 从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。 如若不是，则向邻近的顶点转移，换一个基再行求解、检验，如此迭代循环目标值逐步改善，直

2、至求得最优解。,基本思路,第一节 单纯形法原理,定义：两个基称为相邻的，如果它们之间变换且仅变 换一个变量。,4,第一节 单纯形法原理,一、实例,x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1, x2 , x3 , x4 , x5 0,非奇异子阵，做为一个基,基变量 x3, x4, x5 非基变量 x1, x2,maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0,5,第一节 单纯形法原理,将基变量用非基变量线性表示，即 x3= 8 -

3、x1 x4 =12 - 2x2 x5=36 -3x1-4 x2 令非基变量x1=0，x2=0，找到一个初始基可行解： x1=0， x2 =0，x3 =8，x4 =12， x5 =36 即X0=(0,0,8,12,36) T 一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0 。,1. 求初始基可行解,6,第一节 单纯形法原理,确定进基变量 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 从目标函数-Z+3x1+5 x2 +0 x3 +0 x4+0 x5 =0可知： 非基变量x

4、1和x2的系数均为正数，生产哪种产品都会增加利润。 因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品。,2. 第一次迭代,7,第一节 单纯形法原理,确定离基变量 基变量用非基变量线性表示 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,8,第一节 单纯形法原理,2. 第一次迭代（续）,主元,x1 +0 x2 + x3 =8 2x2 + x4 =12

5、3x1 +4 x2 + x5=36 -Z+3x1 +5 x2 +0 x3 +0 x4+0 x5 =0,进基变量所在列为主列，离基变量所在行为主行,9,第一节 单纯形法原理,基变换 进行初等变换，变主元为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 =-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 =

6、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,10,第一节 单纯形法原理,2. 第一次迭代（续）,将基变量用非基变量线性表示，即 x3=8 x1 x2=6- 1/2x4 x5=12 -3x1+4 x4 令非基变量x1=0，x4=0，找到另一个基可行解 x1=0， x2 =6，x3 =8，x4 =0， x5 =12 即X1=(0,6,8,0,12) T 目标函

7、数Z=30,11,第一节 单纯形法原理,确定换入变量,3. 第二次迭代,第一次迭代结果 x1 + x3 =8 x2 +1/2 x4 =6 3x1 + -2 x4 + x5=12 -Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30,目标函数-Z+3x1 +0 x2 +0 x3 5/2x4 +0 x5 =-30， 非基变量x1的系数1=3（检验数）为正数， 确定x1为进基变量。,原则：在所有系数为正值的非基变量中，寻找系数最大的，作为换入变量。,12,第一节 单纯形法原理,确定换出变量,3. 第二次迭代 （续）,x3 =8- x1 0 x2 =6 0 x5=12 -3x10,基

8、变量用非基变量线性表示 x3=8 x1 x2=6- 1/2x4 x5=12 -3x1+4 x4,保持原非基变量x4 =0， x1变成基变量时应保证 x2 , x3, x5非负，即,原则： 1) 满足非负条件； 2) 使换入变量尽可能大（尽快使目标函数值达到最大）,13,第一节 单纯形法原理,基变换 变主元为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 x1

9、+ -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,14,第一节 单纯形法原理,3. 第二次迭代（续）,将基变量用非基变量线性表示，即,x3 =4 2/3x4 +1/3x5 x2=6-

10、1/4x4 x1=4 +2/3x4-1/3 x5,令非基变量x4=0，x5=0，又找到一个基可行解,目标函数 -Z+0 x1 +0 x2 +0 x3 -1/2x4 - x5 =-42,x1=4， x2 =6，x3 =4，x4 =0， x5 =0 即 X2=(4,6,4,0,0)T Z=42,检验数j非正，得最优解X*=(4,6,4,0,0)T，Z*=42,15,第一节 单纯形法原理,二、单纯形法的几何意义,X0=(0,0,8,12,36)T,X1=(0,6,8,0,12)T,X1=(4,6,4,0,0)T,16,第二节 表格单纯形法,表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格

11、化的结果。,一、单纯形法,17,第二节 表格单纯形法,将线性规划问题化成标准型。 找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。 计算各非基变量xj的检验数j=Cj-CBPj ，若所有j0，则问题已得到最优解，停止计算，否则转入下步。 在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。 根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik| aik0=bl/ aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。 以aik为主元素进行迭代，把xk所对应的列向量变为单

12、位列向量，即aik变为1，同列中其它元素为0，转第 步。,二、单纯形法的计算步骤,18,第二节 表格单纯形法,maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36,三、单纯形法计算举例,19,第二节 表格单纯形法,20,第二节 表格单纯形法,最优解 :X*=(4,6,4,0,0)T，Z*=42,21,第二节 表格单纯形法,maxZ=2x1 +4 x2 +3x3 +0 x4+0 x5+0 x6 3x1 +4 x2 +3x3 + x4 =60 2x1 + x2 +2x3 + x5 =40 x1 +3

13、 x2 +2x3 + x6 =80,表格单纯性法-例二,教材P25,xi 0,(i=1,2, ,6),22,第二节 表格单纯形法,问题？,约束条件不等式形式改变时?-人工变量的引入 无可行解的判别？ 目标函数极小化时的解决思路？,23,用单纯形法解题时，需要有一个单位阵作为初始基。 当约束条件都是“”时，加入松弛变量就形成了初始基。 但实际存在“”或“”型的约束，没有现成的单位矩阵。,一、人工变量,采用人造基的办法：人工构造单位矩阵 在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。 人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意

14、义。,处理方法有两种： 大M 法（手工计算最优方法） 两阶段法（可解决大M法计算机处理时可能错误；手工计算复杂）,第三节 单纯形法进一步讨论,24,没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。 人工变量最终必须等于0才能保持原问题性质不变。 为保证人工变量为0，在目标函数中令其系数为 -M（M0）。 M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。 如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,大M法,第三节 单纯形法进一步讨论,25,按大M法构造人造基，引入人工变量x4

15、 , x5 的辅助问题如下： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0,第三节 单纯形法进一步讨论,26,第三节 单纯形法进一步讨论,27,两阶段法,第一阶段： 建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。 辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。 第二阶段： 将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优

16、解。,第三节 单纯形法进一步讨论,28,进基变量相持： 单纯形法运算过程中，同时出现多个相同的j最大。 在符合要求的j(目标为max：j0，min：j0)中，选取下标最小的非基变量为换入变量； 离基变量相持： 单纯形法运算过程中，同时出现多个相同的最小值。 继续迭代，便有基变量为0，称这种情况为退化解。 选取其中下标最大的基变量做为换出变量。,二、可能问题及处理方法,第三节 单纯形法进一步讨论,?,29,多重最优解： 最优单纯形表中，存在非基变量的检验数j=0。 让这个非基变量进基，继续迭代，得另一个最优解。 无界解： 大于0的检验数中，若某个k所对应的系数列向量Pk0，则解无界。 无可行解：

17、 最终表中存在人工变量是基变量。,计算问题： 主元列元素部分非正数时，无需计算，解的可行性自然满足； 若主元列元素全部为非正数，则LP无界解。,第三节 单纯形法进一步讨论,30,三、目标Min型直接求解原则,最优性判别： 所有检验数非负 换入变量的选择原则： （最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小； 当需用大M法求解时： 在目标函数中人工变量的前面添上一个很大的正系数M。,第三节 单纯形法进一步讨论,31,例：求解下面的LP,?,第三节 单纯形法进一步讨论,课堂练习！ 两种方法,32,原问题最优解为X*=（0，1）T, min Z=2,第三节 单纯形法进一步讨论,33,

18、第三部分 LP总结,一、LP建模,决策变量 决策问题待定的量值称为决策变量。 决策变量的取值要求非负。 约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数。 目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 有的目标要实现极大，有的则要求极小。 目标函数是决策变量的线性函数。,34,第三部分 LP总结,二、LP标准型,35,第三部分 LP总结,三、LP单纯形法,36,第三部分 LP总结,四、各种类型LP的处理,类型一： 目标“Max”；“”型约束 左边加上非负松弛变量变成等式约束（约束条件标准化），将引入