生产运筹学--线性规划及单纯形法（PPT 66页）

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

2、，使得既能充分利用现有资源又使总利润最大？ 表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25 某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B 两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表 1。3第一章 线性规划及单纯形法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

3、x1 +25 x2 表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25决策变量41 线性规划问题及其数学模型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 am1 am2 amn bm 单 价 c1 c2

4、 cn 试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。5第一章 线性规划及单纯形法 表 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 lj61 线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成 n 个子系统处理。1、决策变量 xj0 2、

5、约束条件 一组决策变量的线性等式或不等式3、目标函数 决策变量的线性函数7第一章 线性规划及单纯形法 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）为已知常数 线性规划问题的一般形式：81 线性规划问题及其数学模型线性规划问题的标准形式： max z = c1x1 + c2x2 +

6、+ 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、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。 9第一章 线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为： 。 因为求 min z 等价于求 max (-z)，令 z = - z，即化为： 2、约束条件为不等式，xn+1 0松弛变量如何处

7、理？101 线性规划问题及其数学模型、右端项bi 0时，只需将等式两端同乘（-1）则右端项必大于零 4、决策变量无非负约束 设 xj 没有非负约束，若 xj 0，可令 xj = - xj ，则 xj 0； 又若 xj 为自由变量，即 xj 可为任意实数，可令 xj = xj - xj，且 xj , xj 011第一章 线性规划及单纯形法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；对第一个约束条件加上松弛

8、变量 x6 ；对第二个约束条件减去松弛变量 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 121 线性规划问题及其数学模型LP的几种表示形式：132 线性规划问题的图解法定义1 在LP 问题中，凡满足约束条件(2)、(3)的 解 x = (x1,x2,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D= x | Ax

9、 = b ,x0 。定义2 设LP问题的可行域为D，若存在x*D，使得 对任意的xD 都有c x*c x，则称x*为LP 问题 的最优解，相应的目标函数值称为最优值， 记作 z*=c x*。142 线性规划问题的图解法max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0 (40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数变形：x2=-3/5 x1+z/25x2x1最优解： x1=30 x2 =10最优值：zmax=700B点是使z达到最大的唯一可行点15第一章 线性规划及单纯形法LP问题图解法的基本步骤：1、

10、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。162 线性规划问题的图解法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 Z（3.8,4）34.2 = 3 x1 +5.7 x2 可行域x1 - 1.9 x2

11、 = -3.8(0,2)(3.8,0) 绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.217第一章 线性规划及单纯形法max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0OA(,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？182 线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP 问题从解的角度可分为： 有可行解 无可行解有唯一最优解b. 有无穷多最优解C. 无最优解2、LP 问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到

12、，则这两点的连线上 任一点都是最优解。192 线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。203 线性规划问题解的基本性质讨论如下 LP 问题：其中系数矩阵决策向量 假设 A 的秩为 m ,且只讨论 m 0, x20, xk 0，分两种情况讨论： 如果 p1, p2, pk 线性无关，即 x 的非零分量对应的列向量线性无关，则由定理1知，它是LP 的一个基本可行解，定理成立。(2) 如果p1,p2,pk线性相关，则必存在一组不全为零的数 1,2, ,k 使得27第一章 线性规划及单纯形法假定有i0，取作其中由（6）式知，必有即

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

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

15、规划问题解的基本性质定义 6 设 则称为点 的一个凸组合。定义 7 设凸集 两点 表示为 则称 x 为 S 的一个极点（或顶点）。 定理 4 LP 问题的可行解集32第一章 线性规划及单纯形法定理 5 设 D 为 LP 问题的可行解集， ，则 x 是 D的极点的充分必要条件是 x 为 LP 问题的基可行解。prove推论 1 如果 LP 问题的可行解集非空，则极点集合也一定非空，且极点的个数是有限的。推论 2 如果 LP 问题有最优解，则一定可在可行解集 D 的极点上达到。定理 6 设 LP 问题在多个极点 x(1),x(2),x(k) 处取到最优解，则它们的凸组合，即也是 LP 问题的最优解

16、.（此时，该LP 问题有无穷多最优解）333 线性规划问题解的基本性质Note:1、如何判断 LP 问题有最优解；2、计算复杂性问题。 设有一个50个变量、20个约束等式的 LP 问题，则 最多可能有 个基。即约150万年 如果计算一个基可行解只需要 1 秒，那么计算所有 的基可行解需要：1364.7101.510360024365（年）344 单纯形法的基本原理 单纯形法（Simplex Method）是1947年由 G.B.Dantzig 提出，是解 LP 问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。 基本思路： 基于 LP 问题的标准形式，先设法找到一个基可行解，判

17、断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不相同）。35第一章 线性规划及单纯形法单纯形法引例 首先，化原问题为标准形式：x3, x4 是基变量.基变量用非基变量表示：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 + 25

18、x2 + 0 x3 + 0 x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1，x2 , x3, x4 0 364 单纯形法的基本原理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。最小比值法则所以 x3 换出。基变量用非基变量表示：代入目标函数：z =500+2

19、0/3 x1- 25/3 x3令非基变量 x1= x3=0 z=500 基可行解 x(1)=(0,20,0,20)T大于零！37第一章 线性规划及单纯形法因为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 384 单纯形法的基本原理 目标函数用非基变量表示时，非基变量的系数 称为检验数(40,0)(0,0)(0,20)ABC(30,

20、10)OL1L2Z=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 39第一章 线性规划及单纯形法单纯形法的基本原理称(1a)(2a)(3a)为LP问题对应于基 B 的典则形式（典式）.Ax = b基变量用非基变量表示：代入目标函数：404 单纯形法的基本原理如果记则典式(1a)(2a)(3a) 可写成41第一章 线性规划及单纯形法定理 7 在 LP 问题 的典式 (1b) (3b)中，如果有则对应于基 B 的基可行解是 LP 问题的最优解，记为相应的目标函数最优值 z*=z(0)此时，

21、基B称为最优基424 单纯形法的基本原理定理 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)出发，一定能找到一个新的基可行解 43第一章 线性规划及单纯形法定理 9 在 LP 问题的典式 (1b) (3b)中，如果检验数满足最优准则 j 0 ( j = m+1 ,n )，且其中有一个 k = 0 ( m

22、+1 k n )，则该 LP 问题有无穷多个最优解。这在应用中很有价值定理 10 在 LP 问题的典式 (1b) (3b)中，如果有某个非基变量的检验数k 0 ( m+1 k n )，且有则该 LP 问题解无界（无最优解）。445 单纯形法的计算步骤单纯形表 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 amnb1b2bm检验数 0 0 0 -z(0)45第一章 线性规划及单纯形法如何得到单纯

23、形表？ cAb检验数0B-1b- cB B-1b -z0 I B-1NB-1b 0 N检验数 B NcB cN I B-1N 0 cN-cB B-1N465 单纯形法的计算步骤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不妨已知x3 、x4 为可行基变量 ccBxB25x3x4检验数4 3 2 5x1 x2 x3 x4131242374325b51701-70126-3105-2-117101140

24、-12x(0)=(0,0,1,2 )Tz0 = 1247第一章 线性规划及单纯形法单纯形法求解 LP 问题的计算步骤：Step 1 找出初始可行基，列初始单纯形表,确定初始基可行解； Step 2 检验各非基变量 xj 的检验数 j , 如果所有 的 j 0（j = 1,2, n），则已求得最优解，停 止计算。否则转入下一步； Step 3 在所有的 j 0 中，如果有某个k 0，所对 应的 xk 的系数列向量pk0（即 aik0，i =1,2, m），则此问题解无界，停止计算。否则转入下一 步;485 单纯形法的计算步骤Step 4 根据 ,确定 xk为换入基变量，又根据最小比值法则计算:确

25、定xr为换出基变量。转入下一步; Step 5 以 为主元进行换基变换，用初等行变换将 xk 所对应的列向量变换成单位列向量，即同时将检验数行中的第k个元素也变换为零，得到新的单纯形表。返回Step 2 。49第一章 线性规划及单纯形法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 x

26、3 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/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-10505 单纯形法的计算步骤思考：在单纯形法中根据确定 xk为进基变量，是否在这次变换中，使目标函数值提高最大？ 如果不是，应选择哪个变

27、量进基，保证这次变换使得目标函数值提高最大？目标函数值能提高多少？516 单纯形法的进一步讨论一、初始可行基的求法 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+

28、m = bm xj0 （j = 1,2, n, n+1, n+m）人工变量1、试算法人造基本解： x0 = (0,0,0,b1,bm)T2、人工变 量法526 单纯形法的进一步讨论(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 是一个充分大的正数结论：设为上述问题的

29、最优解则为原问题的最优解，这时的目标函数值为最优值；则原问题无可行解。不全为零，53第一章 线性规划及单纯形法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)解：引入松弛变

30、量 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-13001-22-5121000-1-1-M2112/3x13001/3-2/32/3-5/340012/3-4/34/3-7/39000-1/3-1/32/3-

31、M-23101-M1/3-M 200-0.2M 0 ? 由于人工变量 x6 = x7 = 0, 所以,得原问题的最优解 x*=(4,1,9,0,0)T 目标函数最优值 zmax = 2 Note: 在计算过程中,某个人工变量一旦变为非基变量,则该列可被删去 546 单纯形法的进一步讨论(2)两阶段法第一阶段： 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） (3

32、c) 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（1jn）中下标最小的检验数k 所对应的非基变量xk作为进基变量，即如果(2) 选择出基变量：当按 规则计算此值时，如果存在n 个 ，

33、同时达到最小值，就选其中下标最小的那个基变量作为出基变量。即如果 则选择xl作为出基变量。587 线性规划应用举例e.g.6 生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低.试建立线性规划模型.季度 j生产能力（aj）生产成本（dj）需求量（bj）1301502024014020320153304101481059第一章 线性规划及单纯形法解：方法一设工厂第 j 季度生产产品 xj 吨需求约束：第一季度末需

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

35、in z =15.6x1 +14.4x2 +15.5x3 + 14.8x4 -26 s.t. x1+x2 40 , x1+x2 +x3 70 x1+x2 +x3 + x4 =80, 20 x130,0 x240,0 x320,0 x410.607 线性规划应用举例季度 j生产能力（aj）生产成本（dj）需求量（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, x44 10 xij 的费用 cij= di+0.2( j-i )min z =15 x11 + 15.2x12 + 15.4