线性规划及单纯形法VIP

1、 Operations Research 第一章 线性规划及单纯形法第一章 线性规划及单纯形法 线性规划线性规划（Linear Programming，简称简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。快、理论上较成熟和应用上极为广泛的一个分支。 19471947年年G.B. Dantying提出了一般线性规划问题求解提出了一般线性规划问题求解的方法的方法单纯形法之后，线性规划的理论与应用都得单纯形法之后，线性规划的理论与应用都得到了极大的发展。到了极大的发展。 6060年来，随着计算机的发

2、展，线性规划已广泛应用年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。个领域，成为现代化管理的有力工具之一。1 线性规划问题及其数学模型e.g. 1 资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？ 表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25 某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B 两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表

3、 1。第一章 线性规划及单纯形法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 解 ： 设 x1，x2 为下一个生产周期产品甲和乙的产量； 约束条件：Subject tox1 + 3x2 60 x1 + x2 40 x1，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 种营养 A

4、1,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 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

5、cn 解 ： 设 xj 为购买食品 Bj 的数量 ( j=1,2,n )（i = 1,2,m）xj0 （j = 1,2,n）0 0 xj lj1m innjjjzc x1. .nijjijs ta xb1 线性规划问题及其数学模型三个基本要素三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成可以把一个大系统合理地分解成 n 个子系统处理。个子系统处理。1、决策变量决策变量 xj0 2、约束条件约束条件 一组决策变量的线性等式或不等式一组决策变量的线性等式或不等式3、目标函数目标函数 决策变量的线性

6、函数决策变量的线性函数第一章 线性规划及单纯形法 max（min）z = c1x1 + c2x2 + + cnxns.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 线性规划问题及其数学模型线性规划问题的标准形式： max z = c1x1 + c2x2 + + cnxns.t. a11x

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

8、z1minnjjjxcz1max 因为求 min z 等价于求 max (-z)，令 z = - z，即化为： 2、约束条件为不等式，njinjijbxxa11njijijbxa1njijijbxa1xn+1 0松弛变量如何处理？如何处理？1 线性规划问题及其数学模型、右端项右端项b bi i 0 0时，只需将等式两端同乘（时，只需将等式两端同乘（-1-1）则右端项必大于零则右端项必大于零 4 4、决策变量无非负约束、决策变量无非负约束 设设 xj 没有非负约束，若没有非负约束，若 xj 0 0，可令可令 xj = - = - xj ，则则 xj 0 0； 又若又若 xj 为自由变量，即为自由

9、变量，即 xj 可为任意实数，可为任意实数，可令可令 xj = = xj - xj，且且 xj , xj 00第一章 线性规划及单纯形法e.g. 3试将 LP 问题min z = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = -5 x1,x2 0 化为标准形式。解：令 x3= x4 - x5 其中x4、x5 0；对第一个约束条件加上松弛变量 x6 ；对第二个约束条件减去松弛变量 x7 ；对第三个约束条件两边乘以“-1” ；令 z=-z 把求 min z 改为求 max zmax z= x1-2x2+3x4- 3x5 s.t. x1+x

10、2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70 1 线性规划问题及其数学模型LP的几种表示形式：), 2 , 1(0), 2 , 1(. .max11njxmibxatsxczjinjjijnjjj12,ncc cc价值向量m ax(1). .(2)0(3)zcxs tAxbx1m ax. .0njjjzcxs tp xbx决策向量Tnxxxx,21右端向量0,21iTmbbbbb列向量的第为jAaaapTmjjjj,21系数矩阵mnmmnnaaaaaaaaaA2122221112112 线性规划问题的图解法定

11、义定义1 在在LP LP 问题中，凡满足约束条件问题中，凡满足约束条件(2)(2)、(3)(3)的的 解解 x = (x1,x2,xn)T 称为称为LP 问题的可行解，问题的可行解， 所有可行解的集合称为可行解集（或可行域）。所有可行解的集合称为可行解集（或可行域）。 记作记作 D= x | Ax = b ,x0 。定义定义2 设设LP问题的可行域为问题的可行域为D D，若存在若存在x x* *D D，使得使得 对任意的对任意的xD 都有都有c x*c x，则称则称x x* *为为LP LP 问题问题 的最优解，相应的目标函数值称为最优值，的最优解，相应的目标函数值称为最优值， 记作记作 z*

12、=c x*。m ax(1). .(2)0(3)zcxs tAxbx2 线性规划问题的图解法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 (40,0)(0,0)BC(30,10)12360 xx1240 xxO(0,20)AL1L2Z=250目标函数变形：目标函数变形：x2=-3/5 x1+z/25x2x1最优解最优解： x1=30 x2 =10最优值最优值：zmax=700B B点是使点是使z z达到最达到最大的唯一可行点大的唯一可行点第一章 线性规划及单纯形法LPLP问题图解法的基本步骤问题图解法的基本步骤：1、在平面上建立直角坐

13、标系；在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；图示目标函数（等值线）和移动方向；4、寻找最优解。寻找最优解。2 线性规划问题的图解法max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 3.8 x1 - 1.9x2 3.8 x1 + 1.9x2 11.4 x1 - 1.9x2 -3.8 x1 ，x2 0 x1x2ox1 - 1.9 x2 = 3.8 x1 + 1.9 x2= 3.8x1 + 1.9 x2 = 11.4（7.6,2）D0=3 x1 +5.7 x2 max Z min

14、Z（3.8,4）34.2 = 3 x1 +5.7 x2 可行域可行域x1 - 1.9 x2 = -3.8(0,2)(3.8,0) 绿色线段上的所有点绿色线段上的所有点都是最优解都是最优解,即有无穷多即有无穷多最优解。最优解。Zman=34.2第一章 线性规划及单纯形法max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 01222xx1244xxOA(,0)x1x2Note:可行域为无界区域，可行域为无界区域，目标函数值可无限目标函数值可无限增大，即解无界。增大，即解无界。称为无最优解称为无最优解。可行域为无界可行域为无界区域一定无最区域一定无最优

15、解吗？优解吗？2 线性规划问题的图解法由由以上两例分析可得如下重要结论：以上两例分析可得如下重要结论：1、LP LP 问题从解的角度可分为：问题从解的角度可分为： 有可行解有可行解 无可行解无可行解a. 有唯一最优解有唯一最优解b. b. 有无穷多最有无穷多最优解优解c. C. 无最优解无最优解2、LP LP 问题若有最优解，必在可行域的某个顶点上取问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。任一点都是最优解。2 线性规划问题的图解法图解法优点：图解法优点：直观、易掌握。有助于了解解的结构

16、。直观、易掌握。有助于了解解的结构。图解法缺点：图解法缺点：只能解决低维问题，对高维无能为力。只能解决低维问题，对高维无能为力。3 线性规划问题解的基本性质讨论如下 LP 问题：m ax(1). .20(3)zc xs tAxbx12,ncc cc价值向量12,Tnxx xx12,0Tmibb bbb 右 端 向 量111212122212nnmmmnaaaaaaAaaa其中系数矩阵决策向量 假设 A 的秩为 m ,且只讨论 m 0, x20, xk 0，分两种情况讨论：(1) 如果 p1, p2, pk 线性无关，即 x 的非零分量对应的列向量线性无关，则由定理1知，它是LP 的一个基本可行

17、解，定理成立。(2) 如果p1,p2,pk线性相关，则必存在一组不全为零的数 1,2, ,k 使得10(5)kjjjp第一章 线性规划及单纯形法假定有i0，=min0(6)iiix(2)xx(1)xx12(,0,0)Tk 0 (1,2,., )(7)jjxjn(1)(2)0,0,xx111()nnnjjjjjjjjjjxpx ppb(1)(2),AxbAxb(1)(2),xx取作其中由（6）式知，必有即又因为由（5）式知故有，即也是LP的两个可行解。3 线性规划问题解的基本性质 再由 的取法知，在式 (7) 的诸式中，至少有一个等于零，于是所作的可行解 中，它的非零分量的个数至少比 x 的减少

18、1，如果这些非零分量所对应的列向量线性无关，则 为基可行解，定理成立。 否则，可以从 出发，重复上述步骤，再构造一个新的可行解 ，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分量对应的列向量线性无关，故可行解必为基可行解。证毕。(1)(2)xx或(1)(2)xx或(1)(2)xx或(3)(4)xx或( )(1)ssxx或( )(1)ssxx或返回0 (1,2,., )(7)jjxjn3 线性规划问题解的基本性质定理定理 3 3 证明证明设*12(,)nxx xx是 LP 的一个最优解。如果 x* 是基本解，则定理成立；如果 x* 不是基本解，则由定理2的证

19、明过程可构造两个可行解(1)*(2)*xxxx它的非零分量的个数比 x* 的减少，且有 ， (1)*(2)*,(8)cxcxccxcxc 又因为 x* 是最优解，故有*(1)*(2),(9)cxcxcxcx由式（8）和（9）知，必有(1)(2)*0,ccxcxcx 故 即x(1),x(2) 仍为最优解。如果 x(1)或 x(2) 是基可行解，则定理成立。否则，按定理2证明过程，可得基可行解 x(s)或x(s+1),使得( )*(1)*sscxcxcxcx 或即得基可行解 x(s)或x(s+1)为最优解。返回第一章 线性规划及单纯形法LP 问题解的几何意义定义 5 设集合 是 n 维欧氏空间中的

20、一个点集，如果 及实数 (1)(2)(1)xxSnSR(1)(2)xxS、0,1都有则称 S 是一个凸集。几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。 Note: 空集和单点集也是凸集。3 线性规划问题解的基本性质定义定义 6 6 设 则称( )1,0,1,2, ,1kiniiixRik且，(1)(2)( )12kkxxxx为点 的一个凸组合。(1)(2)( )kxxx，定义定义 7 7 设凸集 两点 表示为 则称 x 为 S 的一个极点（或顶点）。 ,nSR xSxS如果 不能用 中不同的(1)(2)xx，(1)(2)(1)(01)xxx定理定理 4 LP 问

21、题的可行解集,0DxAxb x是凸集。第一章 线性规划及单纯形法定理定理 5 5 设设 D 为为 LP 问题的可行解集，问题的可行解集， ，则，则 x 是是 D的极点的充分必要条件是的极点的充分必要条件是 x 为为 LP 问题的基可行解。问题的基可行解。xDprove推论推论 1 1 如果如果 LP 问题的可行解集非空，则极点集合也问题的可行解集非空，则极点集合也一定非空，且极点的个数是有限的一定非空，且极点的个数是有限的。推论推论 2 2 如果如果 LP 问题有最优解，则一定可在可行解集问题有最优解，则一定可在可行解集 D 的极点上达到。的极点上达到。定理定理 6 6 设设 LP 问题在多个

22、极点问题在多个极点 x(1),x(2),x(k) 处取到最优处取到最优解，则它们的凸组合，即解，则它们的凸组合，即*( )110,1kkiiiiiixx也是也是 LP 问题的最优解问题的最优解. .（此时，该（此时，该LPLP 问题有无穷多最优解）问题有无穷多最优解）3 线性规划问题解的基本性质Note:1、如何判断如何判断 LP 问题有最优解；问题有最优解；2、计算复杂性问题。计算复杂性问题。 设有一个设有一个5050个变量、个变量、2020个约束等式的个约束等式的 LP LP 问题，则问题，则 最多可能有最多可能有 个基。个基。20135050!4.7 1020!30!C即约即约15015

23、0万年万年 如果计算一个基可行解只需要如果计算一个基可行解只需要 1 秒，那么计算所有秒，那么计算所有 的基可行解需要：的基可行解需要：1364.7101.510360024365（ 年 ）4 单纯形法的基本原理 单纯形法单纯形法（Simplex Method）是是19471947年由年由 G.B.Dantzig 提出，是解提出，是解 LP 问题最有效的算法之一，问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础且已成为整数规划和非线性规划某些算法的基础。 基本思路：基本思路： 基于基于 LP 问题的标准形式，先设法找到一个基可问题的标准形式，先设法找到一个基可行解，判断它是否是

24、最优解，如果是则停止计算；否行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解则，则转换到相邻的目标函数值不减的一个基可行解. .（两个基可行解相邻是指它们之间仅有一个基变量不（两个基可行解相邻是指它们之间仅有一个基变量不相同）。相同）。第一章 线性规划及单纯形法单纯形法引例单纯形法引例 首先，化原问首先，化原问题为标准形式：题为标准形式：12341310,1101Appppx3, x4 是基变量.34,Bpp是可行基，基变量用非基变量表示：基变量用非基变量表示：x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2代入目标函数：代入目标

25、函数：z =15 x1+25 x2令非基变量令非基变量 x1= x2=0z=0 基可行解基可行解 x(0)=(0,0,60,40)T是最优解吗？max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + 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 x2x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2因为因为x2 的的系数大，所以系数大，所以x2

26、换入基变量。换入基变量。x3 = 60 - 3x2 0 x4 = 40 - x2 0谁换出？谁换出？如果如果 x4 换出，则换出，则x2 = 40， x3 = -60，不可行不可行。如果是如果是“+”+”会怎样？会怎样？如果如果 x3 换出，则换出，则x2 = 20， x4 = 20。260 40min,2031x取最小比值法则最小比值法则所以所以 x3 换出。换出。基变量用非基变量表示：基变量用非基变量表示：213413112033212033xxxxxx代入目标函数：代入目标函数：z =500+20/3 x1- 25/3 x3令非基变量令非基变量 x1= x3=0 z=500 基可行解基可

27、行解 x(1)=(0,20,0,20)T大于零！大于零！第一章 线性规划及单纯形法13213413202550033112033212033zxxxxxxxx因为因为x1 的系数大，所以的系数大，所以x1 换入基变量。换入基变量。12020min,301233x因所以所以 x4 换出。换出。基变量用非基变量表示：基变量用非基变量表示：134234313022111022xxxxxx代入目标函数：代入目标函数：z =700 5 x3 10 x4令非基变量令非基变量 x3= x4=0 z=700 基可行解基可行解 x(2)=(30,10,0,0)T 因为非基变量的系数都小于零，因为非基变量的系数都

28、小于零， 所以所以 x(2)=(30,10,0,0)T 是最优解是最优解 zmax=700 4 单纯形法的基本原理 目标函数用非基变量表示时，非基变量的系数目标函数用非基变量表示时，非基变量的系数 称为称为检验数检验数(40,0)(0,0)(0,20)ABC(30,10)12360 xx1240 xxOL1L2Z=250 x2x1x(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 第一章 线性规划及单纯形法单纯形法的基本原理单纯形法的基本原理max(1). .(2)0(3)ijmnzcxs tAxbxAaA

29、m=秩 （ ） =1111max()(1 ). .(2 )0,0(3 )BNBNBNBNzc B bcc B N xastxB NxB baxxa称称(1a)(2a)(3a)为为LP问题对应于问题对应于基基 B 的典则形式（典式）的典则形式（典式）. .Ax = bBNBxNxb基变量用非基变量表示：基变量用非基变量表示：11BNxB NxB b11BNxB bB Nx代入目标函数：代入目标函数：1111,()()BBNBBNNNBNNNBNBNxzcxccc xc xxcB bB Nxc xc B bcc B N x4 单纯形法的基本原理如果记如果记(0)1Bzc B b112(,)Nmmn

30、NBcc B N111111(,)mnmnmmmnaaNB Nppaa11( ,)TmbB bbb则则典式典式(1a)(2a)(3a) 可写成( 0 )11221111122112211222221122m ax. .0(1, 2,)mmmmnnmmmmnnmmmmnnmm mmm mmm nnmjzzxxxs txaxaxaxbxaxaxaxbxaxaxaxbxjn 1jjBjjBjcc Bpcc p第一章 线性规划及单纯形法(0)11max(1 ). .(1,2,) (2 )0 (1,2, )(3 )njjj mniijjij mjzzxbstxa xbimbxjnb定理定理 7 在在 L

31、P 问题问题 的典式的典式 (1b) (3b)中，中，如果有如果有0 (1,2, )jjmmn则则对应于基对应于基 B 的基可行解的基可行解(0)12( ,0,0)Tmxb bb是是 LP 问题的最优解，记为问题的最优解，记为12( ,0,0)Tmxb bb相应的目标函数最优值相应的目标函数最优值 z*=z(0)此时，基此时，基B B称称为最优基为最优基11,0,BNBNBcc B Acc B N4 单纯形法的基本原理定理定理 8 在在 LP 问题问题 的典式的典式 (1b) (3b)中，中，(0)11max(1 ). .(1,2,) (2 )0 (1,2, )(3 )njjj mniijji

32、j mjzzxbstxa xbimbxjnb 01,0,0Tmxbb是是对应于基对应于基 B 的一个基可行解，如果满足下列条件：的一个基可行解，如果满足下列条件：(1)(1)有某个非基变量有某个非基变量 xk 的的检验数检验数 k 0 (m+1 k n);(2)(2)aik(i=1,2,m) 不全小于或等于零，即至少有一个不全小于或等于零，即至少有一个 aik0 (i=1,2,m) ;(3) (3) 0 (i=1,2,m) ,即即x(0) 为非退化的基可行解。为非退化的基可行解。ib则则从从 x(0)出发，一定能找到一个新的基可行解出发，一定能找到一个新的基可行解 (1)(1)(1)(1)(1

33、)(0)12,.Tnxxxxcxcx使得第一章 线性规划及单纯形法定理定理 9 在在 LP 问题的典式问题的典式 (1b) (3b)中，如果检验中，如果检验数满足最优准则数满足最优准则 j 0 ( j = m+1 ,n )，且且其中有一其中有一个个 k = 0 ( m+1 k n )，则则该该 LP 问题有无穷多个问题有无穷多个最优解。最优解。这在应用这在应用中很有价中很有价值值定理定理 10 在在 LP 问题的典式问题的典式 (1b) (3b)中，如果有某中，如果有某个非基变量的检验数个非基变量的检验数k 0 ( m+1 k n )，且有且有0 (1,2,)0ikkaimp即则该则该 LP

34、问题解无界（无最优解）。问题解无界（无最优解）。5 单纯形法的计算步骤单纯形表( 0 )11221111122112211222221122m ax. .0(1, 2,)mmmmnnmmmmnnmmmmnnmm mmm mmm nnmjzzxxxs txaxaxaxbxaxaxaxbxaxaxaxbxjn c c1 c2 cm cm+1 cm+2 cncBxB x1 x2 xm xm+1 xm+2 xnbc1c2cmx1x2xm 1 0 0 a1m+1 a1m+2 a1n 0 1 0 a2m+1 a2m+2 a2n 0 0 1 amm+1 amm+2 amnb1b2bmn2m1m第一章 线性规

35、划及单纯形法如何得到单纯形表？1111max()(1 ). .(2 )0,0(3 )BNBNBNBNzc B bcc B N xastxB NxB baxxa cAb检验数0B-1b- cB B-1b -z0 I B-1NB-1b 0 N检验数 B NcB cN I B-1N 0 cN-cB B-1N5 单纯形法的计算步骤e.g.4 列出如下列出如下 LP 问题问题的初始单纯形表。的初始单纯形表。max z = 4x1 + 3x2 + 2x3 + 5x4 s.t. x1 + 3x2 + x3 + 2x4 = 5 4x1+ 2x2+3x3 +7x4 = 17 x1，x2 ，x3 ，x4 0不妨已

36、知不妨已知x3 、x4 为为可行基变量可行基变量 ccBxB25x3x4检验数4 3 2 5x1 x2 x3 x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2 )Tz0 = 12第一章 线性规划及单纯形法单纯形法求解单纯形法求解 LP 问题的计算步骤：问题的计算步骤：Step 1 找出初始可行基，列初始单纯形表找出初始可行基，列初始单纯形表, ,确定初确定初始基可行解；始基可行解；jjkP1ka Step 2 检验各非基变量检验各非基变量 xj 的的检验数检验数 j , 如果所有如果所有 的的 j 0 0（j j = 1,2

37、, = 1,2, , n n），），则已求得最优解，停则已求得最优解，停 止计算。否则转入下一步；止计算。否则转入下一步； Step 3 在所有的在所有的 j 0 0 中，如果有某个中，如果有某个k 00，所对所对 应的应的 xk 的系数列向量的系数列向量pk0 0（即即 aik0 0，i =1,2, m），），则此问题解无界，停止计算。否则转入下一则此问题解无界，停止计算。否则转入下一 步步; ;5 单纯形法的计算步骤Step 4 根据根据 , ,确定确定 xk为换入为换入基变量，又根据最小比值法则计算基变量，又根据最小比值法则计算: :确定确定xr为换出基变量。转入下一步为换出基变量。转入

38、下一步; ;max0,1kjjjn min0,1irikikrkbbaimaa 120010kkkrkmnaaPaa rka Step 5 以以 为主元进行换基变换，用初等行变换将为主元进行换基变换，用初等行变换将 xk 所对应的列向量变换成单位列向量，即所对应的列向量变换成单位列向量，即同时将检验数行中的第同时将检验数行中的第k个元素也个元素也变换为零，得到新的单纯形表。变换为零，得到新的单纯形表。返回返回Step 2 。第一章 线性规划及单纯形法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 max z = 15x1 +25x2+

39、 0 x3 + 0 x4s.t. x1 + 3x2 + x3 = 60 x1 + x2 + + x4 = 40 x1，x2 ， x3 ， x4 0 00 ccBxB00 x3x4检验数15 25 0 0 x1 x2 x3 x413101101152500b6040001x(0)=(0,0,60,40 )Tz0 = 0 x21/3-500 x(1)=(0,20,0,20 )Tz1 = 500 x10-700 x(2)=(30,10,0,0 )Tz2 = 7001/2检验数检验数都小于都小于等于零等于零x(2)为为最优解最优解 zmax = 70060/340/12531/312000-1/312

40、020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-105 单纯形法的计算步骤思考：思考：在单纯形法中根据在单纯形法中根据max0,1kjjjn 确定确定 xk为进基变量，是否在这次变换中，使目为进基变量，是否在这次变换中，使目标函数值提高最大？标函数值提高最大？ 如果不是，应选择哪个变量进基，保证这如果不是，应选择哪个变量进基，保证这次变换使得目标函数值提高最大？次变换使得目标函数值提高最大？目标函数值能提高多少？目标函数值能提高多少？6 单纯形法的进一步讨论一、初始可行基的求法一、初始可行基的求法 max z = c1x1 + c2x2

41、 + 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 + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m）人工变人工变量量1、试算法、试算法人造基本解人造基本解： x0 = (0,0,0,b1,

42、bm)T2、人工变、人工变 量法量法6 单纯形法的进一步讨论(1)(1)大大 M 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 （j = 1,2, n, n+1, n+m）M 是一个充是一个充分大的正数分大的正数结论：结论： 设121(,)Tnnnmxxxxxx为上述问题的最优解为上述问题的最优解120nnn mxxx

43、1、如果 ，则则12( ,)Tnx xx为为原问题的最优解，这时的目标函数值为最优值；原问题的最优解，这时的目标函数值为最优值；则原问题无可行解。则原问题无可行解。12,nnn mxxx2、如果 不不全为零，全为零，第一章 线性规划及单纯形法e.g.5用大用大 M 法求解法求解max z = 3x1 - x2 x3s.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 x7s.t. x1 - 2x2 + x3 + x4 = 11 -4

44、x1 + x2 +2 x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 xj 0 ( j = 1,2,7)解解： 引入松弛变量引入松弛变量 x4， x5 和人工变量 x6， x7 得 ccBxB-M0 x4x6检验数检验数 3 -1 -1 0 0 -M -Mx1 x2 x3 x4 x5 x6 x7131011012-100b110001-2-4-20011x7-M3-1-100-M-M3-4MM-12M-10-M0-M3M3-6MM-13M-10-M004M11/13/21/1x3-113-201100-1100100-11-211M-100-M1-3MM+11/11x2

45、-13001-22-5121000-1-1-M2112/3x13001/3-2/32/3-5/340012/3-4/34/3-7/39000-1/3-1/32/3-M-23 101-M1/3-M 200-0.2M 0 ? 由于人工变量由于人工变量 x6 = x7 = 0, 所以所以, ,得原问题的最优解得原问题的最优解 x*=(4,1,9,0,0)T 目标函数最优值目标函数最优值 zmax = 2 Note: 在计算过程中在计算过程中, ,某个人工变量一旦变为非基变量某个人工变量一旦变为非基变量, ,则该列可被删去则该列可被删去 6 单纯形法的进一步讨论(2)(2)两阶段法两阶段法第一阶段第一

46、阶段： 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) 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 =

47、1,2, n, n+1, n+m） (3d) 判断原判断原LP 问题问题（1c） （3c）是否存在可行解，如果存在就找出一是否存在可行解，如果存在就找出一个初始基可行解；个初始基可行解；解之可得：解之可得：（a）如果如果 wmax 00（1 1j jn n）中下标中下标最小的检验数最小的检验数k 所对应的非基变量所对应的非基变量xk作为进基变量，作为进基变量，即如果即如果min0,1jkjjn(2) 选择出基变量：当按选择出基变量：当按 规则计算此值时，如果规则计算此值时，如果存在存在n n 个个 ，同时达到最小值，就选其中下标，同时达到最小值，就选其中下标最小的那个基变量作为出基变量。即如果

48、最小的那个基变量作为出基变量。即如果 则选择则选择x xl l作为出基变量。作为出基变量。rr kbaminmin0,1rrikrirkrkbblraimaa 7 线性规划应用举例e.g.6 生产计划问题生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表品，有关信息如表，若当季生产的产品过多，季末有积余，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费则一个季度每积压一吨产品需支付存贮费0.20.2万元万元. . 现该厂现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全考虑明年的最佳生产方案，

49、使该厂在完成合同的情况下，全年的生产费用最低年的生产费用最低. .试建立线性规划模型试建立线性规划模型. .季度 j生产能力（aj）生产成本（d dj j）需求量（bj）13015020240140203201533041014810第一章 线性规划及单纯形法解：解：方法一方法一设设工厂第工厂第 j 季度生产产品季度生产产品 xj 吨吨需求约束：需求约束：第一季度末需交货第一季度末需交货 20 20 吨，吨， x1 1 20第二季度末需交货第二季度末需交货 20 20 吨，吨， x1 1-20+-20+x2 20这是上季末这是上季末交货后积余交货后积余第三季度末需交货第三季度末需交货 30 3

50、0 吨，吨， x1 1+ +x2 -40+-40+x3 30第四季度末需交货第四季度末需交货 10 10 吨，吨， x1 1+ +x2 + +x3 -70-70 + +x4 = 10生产能力约束：生产能力约束：00 xj aj j =1,2,3,4=1,2,3,4季度 j生产能力（aj）生产成本（d dj j）需求量（bj）13015020240140203201533041014810生产、存储费用：生产、存储费用：第一季度：第一季度：1515x1第二季度第二季度: 14: 14x2+0.2(x1 1-20-20)第三季度第三季度: 15.3: 15.3x3+0.2(x1 1+ +x2 -4

51、0-40)第四季度第四季度: 14.8: 14.8x4 +0.2(x1 1+ +x2 + +x3 -70-70 )min z =15.6x1 +14.4x2 +15.5x3 + 14.8x4 -26 s.t. x1 1+ +x2 40 , 40 , x1 1+ +x2 + +x3 7070 x1+x2 +x3 + x4 =80, 20 x130,030,0 x240,040,0 x320,020,0 x410.10.7 线性规划应用举例季度 j生产能力（aj）生产成本（d dj j）需求量（bj）13015020240140203201533041014810方法二方法二设第设第 i 季度生产而用于第季度生产而用于第 j 季度末交货的产季度末交货的产品数