线性规划及单纯形法(ppt 66页).ppt

1、运 筹 学,Operations Research,第一章 线性规划及单纯形法,第一章 线性规划及单纯形法,线性规划（Linear Programming，简称LP） 运筹学的一个重要分支，是运筹学中研究较早、发展较 快、理论上较成熟和应用上极为广泛的一个分支。,1947年G.B. Dantying提出了一般线性规划问题求解 的方法单纯形法之后，线性规划的理论与应用都得 到了极大的发展。,60年来，随着计算机的发展，线性规划已广泛应用 于工业、农业、商业、交通运输、经济管理和国防等各 个领域，成为现代化管理的有力工具之一。,1 线性规划问题及其数学模型,e.g. 1 资源的合理利用问题,问：如

2、何安排生产计划， 使得既能充分利用现有资 源又使总利润最大？,表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25,某工厂在下一个生产周期内生产甲、乙两种产品， 要消耗A、B 两种资源，已知每件产品对这两种资源的 消耗，这两种资源的现有数量和每件产品可获得的利 润如表 1。,第一章 线性规划及单纯形法,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,解 ：,设 x1，x2 为下一个生 产周期产品甲和乙的产量；,约束条件：,Subject to,x1 + 3x2 60,x1 + x2 40,x1

3、，x2 0,目标函数：,z = 15 x1 +25 x2,表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25,决策变量,1 线性规划问题及其数学模型,e.g. 2 营养问题,假定在市场上可买到 B1,B2,Bn n 种食品，第 i 种 食品的单价是 ci , 另外有 m 种营养 A1,A2,Am。设 Bj 内含有 Ai 种营养数量为 aij (i=1m,j=1n)，又知人们每 天对 Ai 营养的最少 需要量为 bi。见表2：,表 2 食品 最少 营养 B1 B2 Bn 需要量 A1 a11 a12 a1n b1 A2 a21 a22 a2n b2 Am

4、 am1 am2 amn bm 单 价 c1 c2 cn,试在满足营养要 求的前提下，确定食 品的购买量，使食品 的总价格最低。,第一章 线性规划及单纯形法,表 2 食品 最少 营养 B1 B2 Bn 需要量 A1 a11 a12 a1n b1 A2 a21 a22 a2n b2 Am am1 am2 amn bm 单 价 c1 c2 cn,解 ：,设 xj 为购买食 品 Bj 的数量 ( j=1,2, ,n ),（i = 1,2,m）,xj0 （j = 1,2,n）,0 xj lj,1 线性规划问题及其数学模型,三个基本要素：,Note：,1、善于抓住关键因素，忽略对系统影响不大的因素；,2

5、、可以把一个大系统合理地分解成 n 个子系统处理。,1、决策变量 xj0,2、约束条件 一组决策变量的线性等式或不等式,3、目标函数 决策变量的线性函数,第一章 线性规划及单纯形法,max（min）z = c1x1 + c2x2 + + cnxn s.t. a11x1 + a12x2 + + a1nxn （或=，）b1 a21x1 + a22x2 + + a2nxn （或=，）b2 am1x1 + am2x2 + + amnxn （或=，）bm xj 0 （j = 1,2,n）,其中aij、bi、cj（i = 1,2,m；j = 1,2,n）为已知 常数,1 线性规划问题及其数学模型,线性规划

6、问题的标准形式：,max z = c1x1 + c2x2 + + cnxn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm xj 0 （j = 1,2,n） bi 0 （i = 1,2,m）,特点：,1、目标函数为极 大化；,2、除决策变量的 非负约束外，所有 的约束条件都是等 式，且右端常数均 为非负；,3、所有决策变量 均非负。,第一章 线性规划及单纯形法,如何转化为标准形式？,1、目标函数为求极小值，即为： 。,因为求 min z 等价于求 max (-

7、z)，令 z = - z， 即化为：,2、约束条件为不等式，,xn+1 0 松弛变量,如何处理？,1 线性规划问题及其数学模型,、右端项bi 0, xk 0，,分两种情况讨论：,如果 p1, p2, pk 线性无关，即 x 的非零分量对应的列向量线 性无关，则由定理1知，它是LP 的一个基本可行解，定理成立。,(2) 如果p1,p2,pk线性相关，则必存在一组不全为零的数 1,2, ,k 使得,第一章 线性规划及单纯形法,假定有i0，,取,作,其中,由（6）式知，必有,即,又因为由（5）式知,故有，,，即,也是LP的两个可行解。,3 线性规划问题解的基本性质,再由 的取法知，在式 (7) 的诸

8、式中， 至少有一个等于零，于是所作的可行解 中，它的 非零分量的个数至少比 x 的减少1，如果这些非零分量所对应 的列向量线性无关，则 为基可行解，定理成立。,否则，可以从 出发，重复上述步骤，再构造 一个新的可行解 ，使它的非零分量的个数继续减 少。这样经过有限次重复之后，必可找到一个可行解 使它的非零分量对应的列向量线性无关，故可行解 必为基可行解。证毕。,返回,3 线性规划问题解的基本性质,定理 3 证明,设,是 LP 的一个最优解。,如果 x* 是基本解，则定理成立；,如果 x* 不是基本解，则由定理2的证明过程可构造两个可行解,它的非零分量的个数比 x* 的减少，且有,，,又因为 x

9、* 是最优解，故有,由式（8）和（9）知，必有,即x(1),x(2) 仍为最优解。,如果 x(1)或 x(2) 是基可行解，则定理成立。,否则，按定理2证明过程，可得基可行解 x(s)或x(s+1),使得,即得基可行解 x(s)或x(s+1)为最优解。,返回,第一章 线性规划及单纯形法,LP 问题解的几何意义,定义 5 设集合 是 n 维欧氏空间中的一个点 集，如果 及实数,则称 S 是一个凸集。,几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。,Note: 空集和单点集也是凸集。,3 线性规划问题解的基本性质,定义 6 设 则称,为点 的一个凸组合。,第一章 线性

10、规划及单纯形法,定理 5 设 D 为 LP 问题的可行解集， ，则 x 是 D 的极点的充分必要条件是 x 为 LP 问题的基可行解。,prove,（此时，该LP 问题有无穷多最优解）,3 线性规划问题解的基本性质,Note:,1、如何判断 LP 问题有最优解；,2、计算复杂性问题。,设有一个50个变量、20个约束等式的 LP 问题，则 最多可能有 个基。,即约150万年,4 单纯形法的基本原理,单纯形法（Simplex Method）是1947年由 G.B. Dantzig 提出，是解 LP 问题最有效的算法之一， 且已成为整数规划和非线性规划某些算法的基础。,基本思路： 基于 LP 问题的

11、标准形式，先设法找到一个基可 行解，判断它是否是最优解，如果是则停止计算；否 则，则转换到相邻的目标函数值不减的一个基可行解. （两个基可行解相邻是指它们之间仅有一个基变量不 相同）。,第一章 线性规划及单纯形法,单纯形法引例,首先，化原问 题为标准形式：,x3, x4 是基变量.,基变量用非基变量表示：,x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2,代入目标函数：,z =15 x1+25 x2,令非基变量 x1= x2=0,z=0 基可行解 x(0)=(0,0,60,40)T,是最优解吗？,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1

12、+ x2 40 x1，x2 0,max z = 15x1 + 25x2 + 0 x3 + 0 x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1，x2 , x3, x4 0,4 单纯形法的基本原理,z =15 x1+25 x2 x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2,因为x2 的系数大，所以x2 换入基变量。,x3 = 60 - 3x2 0 x4 = 40 - x2 0,谁换出？,如果 x4 换出，则x2 = 40， x3 = -60，不可行。,如果是“+”会怎样？,如果 x3 换出，则x2 = 20， x4 = 20。,最

13、小比值法则,所以 x3 换出。,基变量用非基变量表示：,代入目标函数：,z =500+20/3 x1- 25/3 x3,令非基变量 x1= x3=0,z=500 基可行解 x(1)=(0,20,0,20)T,大于零！,第一章 线性规划及单纯形法,因为x1 的系数大，所以x1 换入基变量。,所以 x4 换出。,基变量用非基变量表示：,代入目标函数：,z =700 5 x3 10 x4,令非基变量 x3= x4=0,z=700 基可行解 x(2)=(30,10,0,0)T,因为非基变量的系数都小于零， 所以 x(2)=(30,10,0,0)T 是最优解 zmax=700,4 单纯形法的基本原理,目

14、标函数用非基变量表示时，非基变量的系数 称为检验数,(40,0),(0,0),(0,20),A,B,C,(30,10),O,L1,L2,Z=250,x2,x1,x(0)=(0,0,60,40)T z=0,x(1)=(0,20,0,20)T z=500,x(2)=(30,10,0,0)T z=700,第一章 线性规划及单纯形法,单纯形法的基本原理,称(1a)(2a)(3a)为LP问题对应于 基 B 的典则形式（典式）.,Ax = b,基变量用非基变量表示：,代入目标函数：,4 单纯形法的基本原理,如果记,则典式(1a)(2a)(3a) 可写成,第一章 线性规划及单纯形法,定理 7 在 LP 问题

15、 的典式 (1b) (3b)中， 如果有,则对应于基 B 的基可行解,是 LP 问题的最优解，记为,相应的目标函数最优值 z*=z(0),此时，基B称 为最优基,4 单纯形法的基本原理,定理 8 在 LP 问题 的典式 (1b) (3b)中，,是对应于基 B 的一个基可行解，如果满足下列条件：,(1)有某个非基变量 xk 的检验数 k 0 (m+1 k n);,(2)aik(i=1,2,m) 不全小于或等于零，即至少有一个 aik0 (i=1,2,m) ;,(3) 0 (i=1,2,m) ,即x(0) 为非退化的基可行解。,则从 x(0)出发，一定能找到一个新的基可行解,第一章 线性规划及单纯

16、形法,定理 9 在 LP 问题的典式 (1b) (3b)中，如果检验 数满足最优准则 j 0 ( j = m+1 ,n )，且其中有一 个 k = 0 ( m+1 k n )，则该 LP 问题有无穷多个 最优解。,这在应用中很有价值,则该 LP 问题解无界（无最优解）。,5 单纯形法的计算步骤,单纯形表,第一章 线性规划及单纯形法,如何得到单纯形表？,B-1b,- cB B-1b,检验数,B N,cB cN,I B-1N,0 cN-cB B-1N,5 单纯形法的计算步骤,e.g.4 列出如下 LP 问题的初始单纯形表。,max z = 4x1 + 3x2 + 2x3 + 5x4 s.t. x1

17、 + 3x2 + x3 + 2x4 = 5 4x1+ 2x2+3x3 +7x4 = 17 x1，x2 ，x3 ，x4 0,不妨已知x3 、x4 为可行基变量,1,-7,0,1,2,6,-31,0,5,-2,-1,17,1,0,1,1,4,0,-12,x(0)=(0,0,1,2 )T,z0 = 12,第一章 线性规划及单纯形法,单纯形法求解 LP 问题的计算步骤：,Step 1 找出初始可行基，列初始单纯形表,确定初 始基可行解；,Step 2 检验各非基变量 xj 的检验数 j , 如果所有 的 j 0（j = 1,2, n），则已求得最优解，停 止计算。否则转入下一步；,Step 3 在所有

18、的 j 0 中，如果有某个k 0，所对 应的 xk 的系数列向量pk0（即 aik0，i =1,2, m），则此问题解无界，停止计算。否则转入下一 步;,5 单纯形法的计算步骤,Step 4 根据 ,确定 xk为换入 基变量，又根据最小比值法则计算: 确定xr为换出基变量。转入下一步;,Step 5 以 为主元进行换基变换，用初等行变换将 xk 所对应的列向量变换成单位列向量，即,同时将检验数行中的第k个元素也 变换为零，得到新的单纯形表。 返回Step 2 。,第一章 线性规划及单纯形法,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2

19、 0,max z = 15x1 +25x2+ 0 x3 + 0 x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + + x4 = 40 x1，x2 ， x3 ， x4 0,0,0,x2,1/3,-500,x1,0,-700,1/2,检验数都小于等于零,x(2)为最优解 zmax = 700,60/3,40/1,25,3,1/3,1,20,0,0,-1/3,1,20,20/3,-25/3,0,20/1/3,20/2/3,15,2/3,2/3,1,0,-1/2,3/2,30,0,-1/2,10,0,-5,-10,5 单纯形法的计算步骤,思考：,在单纯形法中根据,确定 xk为进

20、基变量，是否在这次变换中，使目 标函数值提高最大？,如果不是，应选择哪个变量进基，保证这 次变换使得目标函数值提高最大？,目标函数值能提高多少？,6 单纯形法的进一步讨论,一、初始可行基的求法,max z = c1x1 + c2x2 + cnxn (1c) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . (2c) am1x1 + am2x2 + amnxn = bm xj0 （j = 1,2, n） (3c),a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn

21、+ xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m）,人工变量,1、试算法,人造基本解： x0 = (0,0,0,b1,bm)T,2、人工变 量法,6 单纯形法的进一步讨论,(1)大 M 法,惩罚法,max w = c1x1 + c2x2 + cnxn M ( xn+1 +xn+m ) s.t. a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0

22、 （j = 1,2, n, n+1, n+m）,M 是一个充分大的正数,结论：,设,为上述问题的最优解,则,为原问题的最优解，这时的目标函数值为最优值；,则原问题无可行解。,不全为零，,第一章 线性规划及单纯形法,e.g.5,用大 M 法求解,max z = 3x1 - x2 x3 s.t. x1 - 2x2 + x3 11 -4x1 + x2 +2 x3 3 -2x1 + x3 = 1 x1，x2 ， x3 0,max z = 3x1 - x2 x3 + 0 x4+ 0 x5 -M x6 -M x7 s.t. x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 +2 x3 -

23、 x5 + x6 = 3 -2x1 + x3 + x7 = 1 xj 0 ( j = 1,2,7),解：,引入松弛变量 x4， x5 和人工变量 x6， x7 得,3-4M,M-1,2M-1,0,-M,0,-M,3M,3-6M,M-1,3M-1,0,-M,0,0,4M,11/1,3/2,1/1,x3,-1,1,3,-2,0,1,1,0,0,-1,10,0,1,0,0,-1,1,-2,1,1,M-1,0,0,-M,1-3M,M+1,1/1,1,x2,-1,3,0,0,1,-2,2,-5,12,1,0,0,0,-1,-1-M,2,1,12/3,x1,3,0,0,1/3,-2/3,2/3,-5/3,

24、4,0,0,1,2/3,-4/3,4/3,-7/3,9,0,0,0,-1/3,-1/3,2/3-M,-2,3,1,0,1-M,1/3-M,200-0.2M 0 ?,由于人工变量 x6 = x7 = 0, 所以,得原问题的最优解 x*=(4,1,9,0,0)T 目标函数最优值 zmax = 2,Note: 在计算过程中,某个人工变量一旦变为非基变量,则该列可被删去,6 单纯形法的进一步讨论,(2)两阶段法,第一阶段：,max z = c1x1 + c2x2 + cnxn (1c) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2

25、 . (2c) am1x1 + am2x2 + amnxn = bm xj0 （j = 1,2, n） (3c),max w = xn+1 xn+2 xn+m (1d) s.t. a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 (2d) am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m） (3d),判断原LP 问题,（1c） （3c）是否存在可行解，如果存在就找出一 个初始基可行解；,解之可得：,（a）如果 wmax 0, 则原问题无可行

26、解，停止计算；,（b）如果 wmax = 0, 且人工变量都不是基变量，则转入 第二阶段；,第一章 线性规划及单纯形法,（c）如果 wmax = 0, 但仍有取零的人工变量为基变量；,x1 x2 xn xn+1 xn+k xn+m b al1 al2 aln aln+1 1 an+m 0,如 x n+k =0 是基变量，在最终单纯形表中：,al1 al2 aln 不可能全为零，必有某个 alj 0， 这时 xj 不是基变量，与 x n+k 交换即可。,第二阶段：,从第一阶段所求得的初始可行基出发，求解原问题,6 单纯形法的进一步讨论,二、关于退化和循环,1955 年 Beale 给出如下例子：

27、,最优解：,第一章 线性规划及单纯形法,Bland 法则：,（对极大值问题而言）,则选择 xk 作为进基变量。,7 线性规划应用举例,e.g.6 生产计划问题,某工厂明年根据合同，每个季度末向销售公司提供产 品，有关信息如表，若当季生产的产品过多，季末有积余， 则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂 考虑明年的最佳生产方案，使该厂在完成合同的情况下，全 年的生产费用最低.试建立线性规划模型.,第一章 线性规划及单纯形法,解：,方法一,设工厂第 j 季度生产产品 xj 吨,需求约束：,第一季度末需交货 20 吨， x1 20,第二季度末需交货 20 吨， x1-20+x2 20

28、,这是上季末交货后积余,第三季度末需交货 30 吨， x1+x2 -40+x3 30,第四季度末需交货 10 吨， x1+x2 +x3 -70 +x4 = 10,生产能力约束：,0xj aj j =1,2,3,4,生产、存储费用：,第一季度：15x1 第二季度: 14x2+0.2(x1-20) 第三季度: 15.3x3+0.2(x1+x2 -40) 第四季度: 14.8x4 +0.2(x1+x2 +x3 -70 ),min z =15.6x1 +14.4x2 +15.5x3 + 14.8x4 -26 s.t. x1+x2 40 , x1+x2 +x3 70 x1+x2 +x3 + x4 =80, 20x130,0 x240,0 x320,0 x410.,7 线性规划应用举例,方法二,设第 i 季度生产而用于第 j 季度末交货的产 品数量为 xij 吨.,需求约束：,x11=20 x12+x22=20,x13+x23+x33=30 x14+x24+x34+x44=10,生产能力约束：,x11 + x12 + x13+ x14 30,x22 +x23 +x24 40, x33 +x34 20, x44 10,xij 的费用 cij= di+0.2( j-i ),min z =15 x11 + 15.2x12 + 15.4x13 + 15.6x14 +14x22 +14.2