线性规划及单纯形法(同名32)课件.ppt

1、11 线性规划问题及其数学模型e.g.1 资源的合理利用问题资源的合理利用问题问：如何安排生产计划，问：如何安排生产计划，使工厂获总利润最大？使工厂获总利润最大？表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25 某工厂在下一个生产周期内生产甲、乙两种产品，某工厂在下一个生产周期内生产甲、乙两种产品，要消耗要消耗A、B两种资源，已知每件产品对这两种资源的两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利消耗，这两种资源的现有数量和每件产品可获得的利润如表润如表 1 1。2第二章第二章 线性规划及单纯形法线性规划及单纯形法

2、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决策变量决策变量31 线性规划问题及其数学模型e.g.2 营养问题营养问题 假定在市场上可买到假定在市场上可买到 B1,B2,Bn n 种食品，第种食品，第 i 种种食品的单价是食品的单价是

3、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 am1 am2 amn bm 单 价 c1 c2 cn 试在满足营养要试在满足营养要求的前提下，确定食求的前提下，确定食品的购买量，使食品品的购买量，使食品的总价格最低。的总价格最低。4第二章第二章 线性规划及单纯形法线性规划及单

4、纯形法 表 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 0 xj lj1m innjjjzc x1.nijjijs ta xb51 线性规划问题及其数学模型三个基本要素三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成可以把一个大系统合理地分

5、解成 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）为已知常数 线性规划问题的一般形式：线性规划问题的

6、一般形式：71 线性规划问题及其数学模型线性规划问题的标准形式：max z=c1x1+c2x2+cnxns.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 1、目标函数为极、目标函数为极大化；大化；2 2、除决策变量的、除决策变量的非负约束外，所有非负约束外，所有的约束条件都是等的约束条件都是等式，且右端常数均式，且右端常数均为非负；为非负；3 3、所有决策变量、所有决策变量均非负均非负。8第二章第二章 线性规划及单纯形法线性规划及单纯形法如

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

8、束，若 xj 0 0，可令，可令 xj=-=-xj ，则则 xj 0 0；又若又若 xj 为自由变量，即为自由变量，即 xj 可为任意实数，可为任意实数，可令可令 xj=xj-xj，且，且 xj,xj 0010第二章第二章 线性规划及单纯形法线性规划及单纯形法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 00；对第一个约束条件加上松弛变量对第一个约束条件加上松弛变量 x6；对第二个约束条件减去松弛

9、变量对第二个约束条件减去松弛变量 x7；对第三个约束条件两边乘以对第三个约束条件两边乘以“-1”；令令 z=-z 把求把求 min z 改为求改为求 max zmax z=x1-2x2+3x4-3x5 s.t.x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70 111 线性规划问题及其数学模型LP的几种表示形式：),2,1(0),2,1(.max11njxmibxatsxczjinjjijnjjj12,ncc cc价值向量m ax(1).(2)0(3)zcxs tAxbx1m ax.0njjjzcxs tp

10、 xbx决策向量Tnxxxx,21右端向量0,21iTmbbbbb列向量的第为jAaaapTmjjjj,21系数矩阵mnmmnnaaaaaaaaaA212222111211122 线性规划问题的图解法定义定义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，使得，使得 对任

11、意的对任意的xD 都有都有c x*c x，则称，则称x x*为为LP LP 问题问题 的最优解，相应的目标函数值称为最优值，的最优解，相应的目标函数值称为最优值，记作记作 z*=c x*。m ax(1).(2)0(3)zcxs tAxbx132 线性规划问题的图解法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点

12、是使点是使z z达到最达到最大的唯一可行点大的唯一可行点14第二章第二章 线性规划及单纯形法线性规划及单纯形法LPLP问题图解法的基本步骤问题图解法的基本步骤：1、在平面上建立直角坐标系；在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；图示目标函数（等值线）和移动方向；4、寻找最优解。寻找最优解。152 线性规划问题的图解法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-

13、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 Z（3.8,4）34.2=3 x1+5.7 x2 可行域可行域x1-1.9 x2=-3.8(0,2)(3.8,0)绿色线段上的所有点绿色线段上的所有点都是最优解都是最优解,即有无穷多即有无穷多最优解。最优解。Zman=34.216第二章第二章 线性规划及单纯形法线性规划及单纯形法max z=2x1+2x2 s.t.2x1 x2 2 -x1+4x2 4 x1，x2 01222xx1244xxOA(,0)x1x2Note:可行域为无界区域，可行域为无界区域，目

14、标函数值可无限目标函数值可无限增大，即解无界。增大，即解无界。称为无最优解称为无最优解。可行域为无界可行域为无界区域一定无最区域一定无最优解吗？优解吗？172 线性规划问题的图解法由以上两例分析可得如下重要结论：由以上两例分析可得如下重要结论：1、LP 问题从解的角度可分为：问题从解的角度可分为：有可行解有可行解 无可行解无可行解a.有唯一最优解有唯一最优解b.有无穷多最优解有无穷多最优解c.无最优解无最优解2、LP 问题若有最优解，必在可行域的某个顶点上取问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上到；若有两个顶点上同时取到，则这两点的连线上 任一点

15、都是最优解。任一点都是最优解。182 线性规划问题的图解法图解法优点：图解法优点：直观、易掌握。有助于了解解的结构。直观、易掌握。有助于了解解的结构。图解法缺点：图解法缺点：只能解决低维问题，对高维无能为力。只能解决低维问题，对高维无能为力。193 线性规划问题解的基本性质讨论如下 LP 问题：m ax(1).20(3)zc xs tAxbx12,ncc cc价值向量12,Tnxx xx12,0Tmibb bbb 右 端 向 量111212122212nnmmmnaaaaaaAaaa其中系数矩阵决策向量 假设假设 A 的秩为的秩为 m,且只讨论且只讨论 m 0,x20,xk 0，分两种情况讨论

16、：(1)如果 p1,p2,pk 线性无关，即 x 的非零分量对应的列向量线性无关，则由定理1知，它是LP 的一个基本可行解，定理成立。(2)如果p1,p2,pk线性相关，则必存在一组不全为零的数 1,2,k 使得10(5)kjjjp26第二章第二章 线性规划及单纯形法线性规划及单纯形法假定有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的两个可行解。273

17、线性规划问题解的基本性质 再由 的取法知，在式(7)的诸式中，至少有一个等于零，于是所作的可行解 中，它的非零分量的个数至少比 x 的减少1，如果这些非零分量所对应的列向量线性无关，则 为基可行解，定理成立。否则，可以从 出发，重复上述步骤，再构造一个新的可行解 ，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分量对应的列向量线性无关，故可行解必为基可行解。证毕。(1)(2)xx或(1)(2)xx或(1)(2)xx或(3)(4)xx或()(1)ssxx或()(1)ssxx或返回0(1,2,.,)(7)jjxjn283 线性规划问题解的基本性质定理定理 3 3

18、 证明证明设*12(,)nxx xx是 LP 的一个最优解。如果 x*是基本解，则定理成立；如果 x*不是基本解，则由定理2的证明过程可构造两个可行解(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)

19、或x(s+1)为最优解。返回29第二章第二章 线性规划及单纯形法线性规划及单纯形法LP 问题解的几何意义定义定义 5 5 设集合设集合 是是 n n 维欧氏空间中的一个点维欧氏空间中的一个点集，如果集，如果 及实数及实数 (1)(2)(1)xxSnSR(1)(2)xxS、0,1都有则称则称 S 是一个凸集。是一个凸集。几何意义：如果集合中任意两点连线上的一切点都在几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。该集合中，则称该集合为凸集。Note:空集和单点集也是凸集。空集和单点集也是凸集。303 线性规划问题解的基本性质定义定义 6 6 设 则称()1,0,1,2

20、,1kiniiixRik且，(1)(2)()12kkxxxx为点 的一个凸组合。(1)(2)()kxxx，定义定义 7 7 设凸集 两点 表示为 则称 x 为 S 的一个极点（或顶点）。,nSR xSxS如果 不能用 中不同的(1)(2)xx，(1)(2)(1)(01)xxx定理定理 4 LP 问题的可行解集,0DxAxb x是凸集。31第二章第二章 线性规划及单纯形法线性规划及单纯形法定理定理 5 5 设设 D 为为 LP 问题的可行解集，问题的可行解集，则，则 x 是是 D的极点的充分必要条件是的极点的充分必要条件是 x 为为 LP 问题的基可行解。问题的基可行解。xDprove推论推论

21、1 1 如果如果 LP 问题的可行解集非空，则极点集合也问题的可行解集非空，则极点集合也一定非空，且极点的个数是有限的一定非空，且极点的个数是有限的。推论推论 2 2 如果如果 LP 问题有最优解，则一定可在可行解集问题有最优解，则一定可在可行解集 D 的极点上达到。的极点上达到。定理定理 6 6 设设 LP 问题在多个极点问题在多个极点 x(1),x(2),x(k)处取到最优处取到最优解，则它们的凸组合，即解，则它们的凸组合，即*()110,1kkiiiiiixx也是也是 LP 问题的最优解问题的最优解.（此时，该（此时，该LPLP 问题有无穷多最优解）问题有无穷多最优解）323 线性规划问

22、题解的基本性质Note:1、如何判断如何判断 LP 问题有最优解；问题有最优解；2、计算复杂性问题。计算复杂性问题。设有一个设有一个5050个变量、个变量、2020个约束等式的个约束等式的 LP LP 问题，则问题，则 最多可能有最多可能有 个基。个基。20135050!4.7 1020!30!C即约即约150150万年万年 如果计算一个基可行解只需要如果计算一个基可行解只需要 1 秒，那么计算所有秒，那么计算所有 的基可行解需要：的基可行解需要：1364.7101.510360024365（年）334 单纯形法的基本原理 单纯形法单纯形法（Simplex Method）是是19471947年

23、由年由 G.B.Dantzig 提出，是解提出，是解 LP 问题最有效的算法之一，问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础且已成为整数规划和非线性规划某些算法的基础。基本思路：基本思路：基于基于 LP 问题的标准形式，先设法找到一个基可问题的标准形式，先设法找到一个基可行解，判断它是否是最优解，如果是则停止计算；否行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不（两个基可行解相邻是指它们之间仅有一个基变量不相同）。相同）。34第二章第

24、二章 线性规划及单纯形法线性规划及单纯形法单纯形法引例单纯形法引例 首先，化原问首先，化原问题为标准形式：题为标准形式：12341310,1101Appppx3,x4 是基变量.34,Bpp是可行基，基变量用非基变量表示：基变量用非基变量表示：x3=60-x1-3x2 x4=40-x1-x2代入目标函数：代入目标函数：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

25、.t.x1+3x2+x3 =60 x1+x2 +x4=40 x1，x2,x3,x4 0 354 单纯形法的基本原理z=15 x1+25 x2x3=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。260 40min,2031x取最小比值法则最小比值法则所以所以 x3 换出。换出。基变量用非基变量表示：基变量用

26、非基变量表示：213413112033212033xxxxxx代入目标函数：代入目标函数：z=500+20/3 x1-25/3 x3令非基变量令非基变量 x1=x3=0 z=500 基可行解基可行解 x(1)=(0,20,0,20)T大于零！大于零！36第二章第二章 线性规划及单纯形法线性规划及单纯形法13213413202550033112033212033zxxxxxxxx因为因为x1 的系数大，所以的系数大，所以x1 换入基变量。换入基变量。12020min,301233x因所以所以 x4 换出。换出。基变量用非基变量表示：基变量用非基变量表示：134234313022111022xxx

27、xxx代入目标函数：代入目标函数：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 374 单纯形法的基本原理 目标函数用非基变量表示时，非基变量的系数目标函数用非基变量表示时，非基变量的系数 称为称为检验数检验数(40,0)(0,0)(0,20)ABC(30,10)12360 xx1240 xxOL1L2Z=250 x2x1x(0)=(0,0,60,40)T z=0 x(

28、1)=(0,20,0,20)T z=500 x(2)=(30,10,0,0)T z=700 38第二章第二章 线性规划及单纯形法线性规划及单纯形法单纯形法的基本原理单纯形法的基本原理max(1).(2)0(3)ijmnzcxs tAxbxAaAm=秩（）=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代入目标

29、函数：代入目标函数：1111,()()BBNBBNNNBNNNBNBNxzcxccc xc xxcB bB Nxc xc B bcc B N x394 单纯形法的基本原理如果记如果记(0)1Bzc B b112(,)NmmnNBcc B N111111(,)mnmnmmmnaaNB Nppaa11(,)TmbB bbb则典式则典式(1a)(2a)(3a)可写成(0)11221111122112211222221122m ax.0(1,2,)mmmmnnmmmmnnmmmmnnmm mmm mmm nnmjzzxxxs txaxaxaxbxaxaxaxbxaxaxaxbxjn 1jjBjjBjc

30、c Bpcc p40第二章第二章 线性规划及单纯形法线性规划及单纯形法(0)11max(1).(1,2,)(2)0(1,2,)(3)njjj mniijjij mjzzxbstxa xbimbxjnb定理定理 7 在在 LP 问题问题 的典式的典式(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 Ac

31、c B N414 单纯形法的基本原理定理定理 8 在在 LP 问题问题 的典式的典式(1b)(3b)中，中，(0)11max(1).(1,2,)(2)0(1,2,)(3)njjj mniijjij 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

32、,m),即即x(0)为非退化的基可行解。为非退化的基可行解。ib则从则从 x(0)出发，一定能找到一个新的基可行解出发，一定能找到一个新的基可行解 (1)(1)(1)(1)(1)(0)12,.Tnxxxxcxcx使得42第二章第二章 线性规划及单纯形法线性规划及单纯形法定理定理 9 在在 LP 问题的典式问题的典式(1b)(3b)中，如果检验中，如果检验数满足最优准则数满足最优准则 j 0(j=m+1,n)，且其中有一且其中有一个个 k=0 (m+1 k n)，则该则该 LP 问题有无穷多个问题有无穷多个最优解。最优解。这在应用这在应用中很有价中很有价值值定理定理 10 在在 LP 问题的典式

33、问题的典式(1b)(3b)中，如果有某中，如果有某个非基变量的检验数个非基变量的检验数k 0(m+1 k n)，且有且有0(1,2,)0ikkaimp即则该则该 LP 问题解无界（无最优解）。问题解无界（无最优解）。435 单纯形法的计算步骤单纯形表(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

34、0 0 a1m+1 a1m+2 a1n 0 1 0 a2m+1 a2m+2 a2n 0 0 1 amm+1 amm+2 amnb1b2bm检验数检验数 0 0 0-z(0)n2m1m44第二章第二章 线性规划及单纯形法线性规划及单纯形法如何得到单纯形表？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-1N455 单纯形法的计算步骤e.g.4 列出如下列出如下 LP 问题问题的初始单纯形表。

35、的初始单纯形表。max z=4x1+3x2+2x3+5x4 s.t.x1+3x2+x3+2x4=5 4x1+2x2+3x3+7x4=17 x1，x2，x3，x4 0不妨已知不妨已知x3、x4 为可行基变量为可行基变量 ccBxB25x3x4检验数4 3 2 5x1 x2 x3 x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2)Tz0=1246第二章第二章 线性规划及单纯形法线性规划及单纯形法单纯形法求解单纯形法求解 LP 问题的计算步骤：问题的计算步骤：Step 1 找出初始可行基，列初始单纯形表找出初始可行基，列初始单纯形

36、表,确定初确定初始基可行解；始基可行解；jjkP1ka Step 2 检验各非基变量检验各非基变量 xj 的检验数的检验数 j ,如果所有如果所有 的的 j 0 0（j j=1,2,=1,2,n n），则已求得最优解，停），则已求得最优解，停 止计算。否则转入下一步；止计算。否则转入下一步；Step 3 在所有的在所有的 j 0 0 中，如果有某个中，如果有某个k 00，所对，所对 应的应的 xk 的系数列向量的系数列向量pk0 0（即（即 aik0 0，i=1,2,m），则此问题解无界，停止计算。否则转入下一），则此问题解无界，停止计算。否则转入下一 步步;475 单纯形法的计算步骤Step

37、 4 根据根据 ,确定确定 xk为换入为换入基变量，又根据最小比值法则计算基变量，又根据最小比值法则计算:确定确定xr为换出基变量。转入下一步为换出基变量。转入下一步;max0,1kjjjn min0,1irikikrkbbaimaa 120010kkkrkmnaaPaa rka Step 5 以以 为主元进行换基变换，用初等行变换将为主元进行换基变换，用初等行变换将 xk 所对应的列向量变换成单位列向量，即所对应的列向量变换成单位列向量，即同时将检验数行中的第同时将检验数行中的第k个元素也个元素也变换为零，得到新的单纯形表。变换为零，得到新的单纯形表。返回返回Step 2。48第二章第二章

38、线性规划及单纯形法线性规划及单纯形法max z=15x1+25x2s.t.x1+3x2 60 x1+x2 40 x1，x2 0 max z=15x1+25x2+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检验数检验数都小于都小于等于零

39、等于零x(2)为最优解为最优解 zmax=70060/340/12531/312000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-10495 单纯形法的计算步骤思考：思考：在单纯形法中根据在单纯形法中根据max0,1kjjjn 确定确定 xk为进基变量，是否在这次变换中，使目为进基变量，是否在这次变换中，使目标函数值提高最大？标函数值提高最大？如果不是，应选择哪个变量进基，保证这如果不是，应选择哪个变量进基，保证这次变换使得目标函数值提高最大？次变换使得目标函数值提高最大？目标函数值能提高多少？目标函数值能提高多少？50

40、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+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)T2、人工变、人工变

41、 量法量法516 单纯形法的进一步讨论(1)(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 （j=1,2,n,n+1,n+m）M 是一个充是一个充分大的正数分大的正数结论：结论：设121(,)Tnnnmxxxxxx为上述问题的最优解为上述问题的最优解120nnn mxxx1、如果，则则12(,)Tnx xx为原问题的最优解，这时的目标函数值为最优值；为原问题的最优解，这时的目标函

42、数值为最优值；则原问题无可行解。则原问题无可行解。12,nnn mxxx2、如果 不不全为零，全为零，52第二章第二章 线性规划及单纯形法线性规划及单纯形法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 -4x1+x2+2 x3 -x5+x6 =3 -2x1 +x3 +x7 =1 xj 0 (j=1,2,7)解解：引入松弛变量引入松弛变量 x4，x5 和人工

43、变量和人工变量 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-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

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

45、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 00（1 1j jn n）中下标）中下标最小的检验数最小的检验数k 所对应的非基变量所对应的非基变量xk作为进

46、基变量，作为进基变量，即如果即如果min0,1jkjjn(2)选择出基变量：当按选择出基变量：当按 规则计算此值时，如果规则计算此值时，如果存在存在n n 个个 ，同时达到最小值，就选其中下标，同时达到最小值，就选其中下标最小的那个基变量作为出基变量。即如果最小的那个基变量作为出基变量。即如果 则选择则选择x xl l作为出基变量。作为出基变量。rr kbaminmin0,1rrikrirkrkbblraimaa 577 线性规划应用举例e.g.6 生产计划问题生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表品，有关信息

47、如表，若当季生产的产品过多，季末有积余，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费则一个季度每积压一吨产品需支付存贮费0.20.2万元万元.现该厂现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低年的生产费用最低.试建立线性规划模型试建立线性规划模型.季度 j生产能力（aj）生产成本（d dj j）需求量（bj）1301502024014020320153304101481058第二章第二章 线性规划及单纯形法线性规划及单纯形法解：解：方法一方法一设工厂第设工厂第 j 季度生产产品季度生产产

48、品 xj 吨吨需求约束：需求约束：第一季度末需交货第一季度末需交货 20 20 吨，吨，x1 1 20第二季度末需交货第二季度末需交货 20 20 吨，吨，x1 1-20+-20+x2 20这是上季末这是上季末交货后积余交货后积余第三季度末需交货第三季度末需交货 30 30 吨，吨，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）130150202401402032

49、01533041014810生产、存储费用：生产、存储费用：第一季度：第一季度：1515x1第二季度第二季度:14:14x2+0.2(x1 1-20-20)第三季度第三季度:15.3:15.3x3+0.2(x1 1+x2-40-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.597 线性规划应用举

50、例季度 j生产能力（aj）生产成本（d dj j）需求量（bj）13015020240140203201533041014810方法二方法二设第设第 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,20,x44 10 xij 的费用的费用 cij=di+0.2(j-i)min z=15 x11+15.2