数学建模第二章线性规划及单纯形法课件.ppt

数学建模第二章线性规划及单纯形法1第1页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法 线性规划线性规划（Linear Programming，简称，简称LP）运筹学的一个重要分支，是运筹学中研究运筹学的一个重要分支，是运筹学中研究较早、早、发展展较快、理快、理论上上较成熟和成熟和应用上极用上极为广泛的一个分支。广泛的一个分支。19471947年年G.B.Dantying 提出了一般提出了一般线性性规划划问题求解求解的方法的方法单纯形法之后，形法之后，线性性规划的理划的理论与与应用都得用都得到了极大的到了极大的发展。展。6060年来，随着年来，随着计算机的算机的发展，展，线性性规划已广泛划已广泛应用用于工于工业、农业、商、商业、交通运、交通运输、经济管理和国防等各管理和国防等各个个领域，成域，成为现代化管理的有力工具之一。代化管理的有力工具之一。2第2页，此课件共67页哦1 线性规划问题及其数学模型e.g.1 资源的合理利用问题资源的合理利用问题问：如何安排生：如何安排生产计划，划，使工厂使工厂获总利利润最大？最大？表1产品资源 甲乙库存量A1360B1140单件利润1525 某工厂在下一个生某工厂在下一个生产周期内生周期内生产甲、乙两种甲、乙两种产品，品，要消耗要消耗A、B两种两种资源，已知每件源，已知每件产品品对这两种两种资源的源的消耗，消耗，这两种两种资源的源的现有数量和每件有数量和每件产品可品可获得的利得的利润如表如表 1 1。3第3页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20 解：设 x1，x2 为下一个生下一个生产周期周期产品甲和乙的品甲和乙的产量量；约束条件束条件：Subject tox1+3x260 x1+x240 x1，x20目目标函数函数：z=15x1+25x2表1产品资源 甲乙库存量A1360B1140单件利润1525决策决策变量量4第4页，此课件共67页哦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 am1 am2 amn bm 单价 c1 c2 cn 试在在满足足营养要养要求的前提下，确定食求的前提下，确定食品的品的购买量，使食品量，使食品的的总价格最低。价格最低。5第5页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法表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 lj6第6页，此课件共67页哦1 线性规划问题及其数学模型三个基本要素三个基本要素：Note：1、善于抓住关善于抓住关键因素，忽略因素，忽略对系系统影响不大的因素；影响不大的因素；2、可以把一个大系可以把一个大系统合理地分解成合理地分解成 n 个子系个子系统处理。理。1、决策决策变量量 xj02、约束条件束条件 一一组决策决策变量的量的线性等式或不等式性等式或不等式3、目目标函数函数 决策决策变量的量的线性函数性函数7第7页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法 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）为已知常数 线性规划问题的一般形式：线性规划问题的一般形式：8第8页，此课件共67页哦1 线性规划问题及其数学模型线性规划问题的标准形式：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、所有决策、所有决策变量量均非均非负。9第9页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法如何转化为标准形式？如何转化为标准形式？1、目目标函数函数为求极小求极小值，即，即为：。因因为求求 min z 等价于求等价于求 max(-z)，令令 z=-z，即化即化为：2、约束条件为不等式，xn+1 0松弛变量如何处理？如何处理？10第10页，此课件共67页哦1 线性规划问题及其数学模型、右端右端项b bi i 0 0时，只需将等式两端同乘（，只需将等式两端同乘（-1-1）则右端右端项必大于零必大于零 4 4、决策、决策变量无非量无非负约束束 设 xj 没有非没有非负约束，若束，若 xj 0 0，可令，可令 xj=-=-xj ，则 xj 0 0；又若又若 xj 为自由自由变量，即量，即 xj 可可为任意任意实数，数，可令可令 xj=xj-xj，且，且 xj,xj 0011第11页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法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；对第二个约束条件减去松弛变量对第二个约束条件减去松弛变量 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 12第12页，此课件共67页哦1 线性规划问题及其数学模型LP的几种表示形式：13第13页，此课件共67页哦2 线性规划问题的图解法定定义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*=c x*。14第14页，此课件共67页哦2 线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目目标函数函数变形：形：x2=-3/5 x1+z/25x2x1最最优解解：x1=30 x2=10最最优值：zmax=700B B点是使点是使z z达到最大达到最大的唯一可行点的唯一可行点15第15页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法LPLP问题图解法的基本步解法的基本步骤：1、在平面上建立直角坐在平面上建立直角坐标系；系；2、图示示约束条件，确定可行域和束条件，确定可行域和顶点坐点坐标；3、图示目示目标函数（等函数（等值线）和移）和移动方向；方向；4、寻找最找最优解。解。16第16页，此课件共67页哦2 线性规划问题的图解法maxz=3x1+5.7x2s.t.x1+1.9x23.8x1-1.9x23.8 x1+1.9x211.4x1-1.9x2-3.8x1，x20 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=-3.8(0,2)(3.8,0)绿色色线段上的所有点段上的所有点都是最都是最优解解,即有无即有无穷多最多最优解。解。Zman=34.217第17页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法maxz=2x1+2x2s.t.2x1x22-x1+4x24x1，x20OA(,0)x1x2Note:可行域可行域为无界区域，无界区域，目目标函数函数值可无限可无限增大，即解无界。增大，即解无界。称称为无最无最优解解。可行域可行域为无界区无界区域一定无最域一定无最优解解吗？18第18页，此课件共67页哦2 线性规划问题的图解法由以上两例分析可得如下重要由以上两例分析可得如下重要结论：1、LP 问题从解的角度可分从解的角度可分为：有可行解有可行解 无可行解无可行解a.有唯一最有唯一最优解解b.有无有无穷多最多最优解解c.无最无最优解解2、LP 问题若有最若有最优解，必在可行域的某个解，必在可行域的某个顶点上取点上取 到；若有两个到；若有两个顶点上同点上同时取到，取到，则这两点的两点的连线上上 任一点都是最任一点都是最优解。解。19第19页，此课件共67页哦2 线性规划问题的图解法图解法解法优点：点：直直观、易掌握。有助于了解解的、易掌握。有助于了解解的结构。构。图解法缺点：解法缺点：只能解决低只能解决低维问题，对高高维无能无能为力。力。20第20页，此课件共67页哦3 线性规划问题解的基本性质讨论如下 LP问题：其中系数矩阵决策向量 假假设 A 的秩的秩为 m,且只且只讨论 m 0,x20,xk 0，分两种情况讨论：(1)如果p1,p2,pk 线性无关，即x 的非零分量对应的列向量线性无关，则由定理1知，它是LP 的一个基本可行解，定理成立。(2)如果p1,p2,pk线性相关，则必存在一组不全为零的数1,2,k 使得27第27页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法假定有i0，取作其中由（6）式知，必有即又因为由（5）式知故有，即也是LP的两个可行解。28第28页，此课件共67页哦3 线性规划问题解的基本性质 再由 的取法知，在式(7)的诸式中，至少有一个等于零，于是所作的可行解 中，它的非零分量的个数至少比 x 的减少1，如果这些非零分量所对应的列向量线性无关，则 为基可行解，定理成立。否则，可以从 出发，重复上述步骤，再构造一个新的可行解 ，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分量对应的列向量线性无关，故可行解必为基可行解。证毕。返回e29第29页，此课件共67页哦3 线性规划问题解的基本性质定理定理 3 3 证明明设是 LP 的一个最优解。如果 x*是基本解，则定理成立；如果 x*不是基本解，则由定理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第30页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法LP问题解的几何意义定定义 5 5 设集合集合 是是 n n 维欧氏空欧氏空间中的一个点中的一个点集，如果集，如果 及及实数数 则称称 S 是一个凸集。是一个凸集。几何意几何意义：如果集合中任意两点：如果集合中任意两点连线上的一切点都在上的一切点都在 该集合中，集合中，则称称该集合集合为凸集。凸集。Note:空集和空集和单点集也是凸集。点集也是凸集。31第31页，此课件共67页哦3 线性规划问题解的基本性质定定义 6 6 设 则称为点 的一个凸组合。定定义 7 7 设凸集 两点 表示为 则称 x 为 S 的一个极点（或顶点）。定理定理 4 LP 问题的可行解集32第32页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法定理定理 5 5 设 D 为 LP 问题的可行解集，的可行解集，则 x 是是 D的极点的充分必要条件是的极点的充分必要条件是 x 为 LP 问题的基可行解。的基可行解。prove推推论 1 1 如果如果 LP 问题的可行解集非空，的可行解集非空，则极点集合也极点集合也一定非空，且极点的个数是有限的一定非空，且极点的个数是有限的。推推论 2 2 如果如果 LP 问题有最有最优解，解，则一定可在可行解集一定可在可行解集 D 的极点上达到。的极点上达到。定理定理 6 6 设 LP 问题在多个极点在多个极点 x(1),x(2),x(k)处取到最取到最优解，解，则它它们的凸的凸组合，即合，即也是也是 LP 问题的最的最优解解.（此（此时，该LPLP 问题有无有无穷多最多最优解）解）33第33页，此课件共67页哦3 线性规划问题解的基本性质Note:1、如何判断如何判断 LP 问题有最有最优解；解；2、计算复算复杂性性问题。设有一个有一个5050个个变量、量、2020个个约束等式的束等式的 LP LP 问题，则 最多可能有最多可能有 个基。个基。即即约150150万年万年 如果如果计算一个基可行解只需要算一个基可行解只需要 1 秒，那么秒，那么计算所有算所有 的基可行解需要：的基可行解需要：1364.7101.510360024365（年）34第34页，此课件共67页哦4 单纯形法的基本原理 单纯形法形法（Simplex Method）是是19471947年由年由 G.B.Dantzig 提出，是解提出，是解 LP 问题最有效的算法之一，最有效的算法之一，且已成且已成为整数整数规划和非划和非线性性规划某些算法的基划某些算法的基础。基本思路：基本思路：基于基于 LP 问题的的标准形式，先准形式，先设法找到一个基可法找到一个基可行解，判断它是否是最行解，判断它是否是最优解，如果是解，如果是则停止停止计算；否算；否则，则转换到相到相邻的目的目标函数函数值不减的一个基可行解不减的一个基可行解.（两个基可行解相（两个基可行解相邻是指它是指它们之之间仅有一个基有一个基变量不量不相同）。相同）。35第35页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法单纯形法引例形法引例 首先，化原首先，化原问题为标准形式：准形式：x3,x4 是基变量.基基变量用非基量用非基变量表示：量表示：x3=60-x1-3x2x4=40-x1-x2代入目代入目标函数：函数：z=15x1+25x2令非基令非基变量量 x1=x2=0z=0 基可行解基可行解 x(0)=(0,0,60,40)T是最优解吗？maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20 maxz=15x1+25x2+0 x3+0 x4s.t.x1+3x2+x3=60 x1+x2+x4=40 x1，x2,x3,x40 36第36页，此课件共67页哦4 单纯形法的基本原理z=15x1+25x2x3=60-x1-3x2x4=40-x1-x2因因为x2 的系数大，所以的系数大，所以x2 换入基入基变量。量。x3=60-3x20 x4=40-x20谁换出？出？如果如果 x4换出，出，则x2=40，x3=-60，不可行不可行。如果是如果是“+”会怎会怎样？如果如果 x3换出，出，则x2=20，x4=20。最小比最小比值法法则所以所以 x3 换出。出。基基变量用非基量用非基变量表示：量表示：代入目代入目标函数：函数：z=500+20/3x1-25/3x3令非基令非基变量量 x1=x3=0 z=500 基可行解基可行解 x(1)=(0,20,0,20)T大于零！大于零！37第37页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法因因为x1 的系数大，所以的系数大，所以x1 换入基入基变量。量。所以所以 x4换出。出。基基变量用非基量用非基变量表示：量表示：代入目代入目标函数：函数：z=7005x310 x4令非基令非基变量量 x3=x4=0 z=700 基可行解基可行解 x(2)=(30,10,0,0)T 因因为非基非基变量的系数都小于零，量的系数都小于零，所以所以 x(2)=(30,10,0,0)T是最是最优解解 zmax=700 38第38页，此课件共67页哦4 单纯形法的基本原理 目目标函数用非基函数用非基变量表示量表示时，非基，非基变量的系数量的系数 称称为检验数数(40,0)(0,0)(0,20)ABC(30,10)OL1L2Z=250 x2x1x(0)=(0,0,60,40)Tz=0 x(1)=(0,20,0,20)Tz=500 x(2)=(30,10,0,0)T z=700 39第39页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法单纯形法的基本原理形法的基本原理称称(1a)(2a)(3a)为LP问题对应于于基基 B 的典的典则形式（典式）形式（典式）.Ax=b基基变量用非基量用非基变量表示：量表示：代入目代入目标函数：函数：40第40页，此课件共67页哦4 单纯形法的基本原理如果如果记则典式典式(1a)(2a)(3a)可写成41第41页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法定理定理 7 在在 LP 问题 的典式的典式(1b)(3b)中，中，如果有如果有则对应于基于基 B 的基可行解的基可行解是是 LP 问题的最的最优解，解，记为相相应的目的目标函数最函数最优值 z*=z(0)此此时，基，基B B称称为最最优基基42第42页，此课件共67页哦4 单纯形法的基本原理定理定理 8 在在 LP 问题 的典式的典式(1b)(3b)中，中，是是对应于基于基 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)为非退化的基可行解。非退化的基可行解。则从从 x(0)出出发，一定能找到一个新的基可行解，一定能找到一个新的基可行解 43第43页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法定理定理 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)，且有且有则该 LP 问题解无界（无最解无界（无最优解）。解）。44第44页，此课件共67页哦5 单纯形法的计算步骤单纯形表 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第45页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法如何得到单纯形表？cAb检验数0B-1b-cB B-1b -z0 I B-1NB-1b 0 N检验数 B NcB cN I B-1N 0 cN-cB B-1N46第46页，此课件共67页哦5 单纯形法的计算步骤e.g.4 列出如下列出如下 LP 问题的初始的初始单纯形表。形表。maxz=4x1+3x2+2x3+5x4s.t.x1+3x2+x3+2x4=54x1+2x2+3x3+7x4=17x1，x2，x3，x40不妨已知不妨已知x3、x4 为可行基可行基变量量 ccBxB25x3x4检验数4325x1x2x3x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2)Tz0=1247第47页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法单纯形法求解形法求解 LP 问题的的计算步算步骤：Step 1 找出初始可行基，列初始找出初始可行基，列初始单纯形表形表,确定初确定初始基可行解；始基可行解；Step 2 检验各非基各非基变量量 xj 的的检验数数 j ,如果所有如果所有的的j 00（j j=1,2,=1,2,n n），），则已求得最已求得最优解，停解，停 止止计算。否算。否则转入下一步；入下一步；Step 3 在所有的在所有的 j 0 0 中，如果有某个中，如果有某个k 00，所，所对 应的的 xk 的系数列向量的系数列向量pk00（即（即 aik00，i=1,2,m），），则此此问题解无界，停止解无界，停止计算。否算。否则转入下一入下一 步步;48第48页，此课件共67页哦5 单纯形法的计算步骤Step 4 根据根据 ,确定确定 xk为换入入基基变量，又根据最小比量，又根据最小比值法法则计算算:确定确定xr为换出基出基变量。量。转入下一步入下一步;Step 5 以以 为主元主元进行行换基基变换，用初等行，用初等行变换将将 xk 所所对应的列向量的列向量变换成成单位列向量，即位列向量，即同同时将将检验数行中的第数行中的第k个元素也个元素也变换为零，得到新的零，得到新的单纯形表。形表。返回返回Step 2。49第49页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20 maxz=15x1+25x2+0 x3+0 x4s.t.x1+3x2+x3=60 x1+x2+x4=40 x1，x2，x3，x40 00 ccBxB00 x3x4检验数152500 x1x2x3x413101101152500b6040001x(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-1050第50页，此课件共67页哦5 单纯形法的计算步骤思考：思考：在在单纯形法中根据形法中根据确定确定 xk为进基基变量，是否在量，是否在这次次变换中，使目中，使目标函数函数值提高最大？提高最大？如果不是，如果不是，应选择哪个哪个变量量进基，保基，保证这次次变换使得目使得目标函数函数值提高最大？提高最大？目目标函数函数值能提高多少？能提高多少？51第51页，此课件共67页哦6 单纯形法的进一步讨论一、初始可行基的求法一、初始可行基的求法maxz=c1x1+c2x2+cnxn (1c)s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.(2c)am1x1+am2x2+amnxn=bmxj0（j=1,2,n）(3c)a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmxj0（j=1,2,n,n+1,n+m）人工人工变量量1、试算法算法人造基本解人造基本解：x0=(0,0,0,b1,bm)T2、人工、人工变 量法量法52第52页，此课件共67页哦6 单纯形法的进一步讨论(1)(1)大大 M 法法惩罚法 max w=c1x1+c2x2+cnxn M(xn+1+xn+m)s.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmxj0（j=1,2,n,n+1,n+m）M 是一个充分是一个充分大的正数大的正数结论：结论：设为上述上述问题的最的最优解解则为原原问题的最的最优解，解，这时的目的目标函数函数值为最最优值；则原原问题无可行解。无可行解。不不全为零，全为零，53第53页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法e.g.5用大用大 M 法求解法求解maxz=3x1-x2x3s.t.x1-2x2+x311-4x1+x2+2x33-2x1 +x3=1 x1，x2，x30 maxz=3x1-x2x3+0 x4+0 x5-M x6-M x7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1 +x3+x7=1 xj0 (j=1,2,7)解解：引入松弛引入松弛变量量 x4，x5 和人工和人工变量量 x6，x7 得得 ccBxB-M0 x4x6检验数数3-1-100-M -Mx1x2x3x4x5x6x7131011012-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-23101-M1/3-M 200-0.2M 0?由于人工由于人工变量量 x6=x7=0,所以所以,得原得原问题的最的最优解解 x*=(4,1,9,0,0)T 目目标函数最函数最优值 zmax=2 Note:在在计算算过程中程中,某个人工某个人工变量一旦量一旦变为非基非基变量量,则该列可被列可被删去去 54第54页，此课件共67页哦6 单纯形法的进一步讨论(2)(2)两两阶段法段法第一第一阶段段：maxz=c1x1+c2x2+cnxn (1c)s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.(2c)am1x1+am2x2+amnxn=bmxj0（j=1,2,n）(3c)maxw=xn+1xn+2xn+m (1d)s.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2(2d)am1x1+am2x2+amnxn+xn+m=bmxj0（j=1,2,n,n+1,n+m）(3d)判断原判断原LP 问题（1c）（3c）是否存在可行解，如果存在就找出一是否存在可行解，如果存在就找出一个初始基可行解；个初始基可行解；解之可得：解之可得：（a）如果如果 wmax 00（11j jn n）中下）中下标最小的最小的检验数数k 所所对应的非基的非基变量量xk作作为进基基变量，量，即如果即如果(2)选择出基出基变量：当按量：当按 规则计算此算此值时，如果，如果存在存在n n 个个 ，同，同时达到最小达到最小值，就，就选其中下其中下标最小的那个基最小的那个基变量作量作为出基出基变量。即如果量。即如果 则选择x xl l作作为出基出基变量。量。58第58页，此课件共67页哦7 线性规划应用举例e.g.6 生生产计划划问题 某工厂明年根据合同，每个季度末向某工厂明年根据合同，每个季度末向销售公司提供售公司提供产品，有关信息如表，若当季生品，有关信息如表，若当季生产的的产品品过多，季末有多，季末有积余，余，则一个季度每一个季度每积压一吨一吨产品需支付存品需支付存贮费0.20.2万元万元.现该厂厂考考虑明年的最佳生明年的最佳生产方案，使方案，使该厂在完成合同的情况下，全厂在完成合同的情况下，全年的生年的生产费用最低用最低.试建立建立线性性规划模型划模型.季度j生产能力（aj）生产成本（d dj j）需求量（bj）1301502024014020320153304101481059第59页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法解：解：方法一方法一设工厂第工厂第 j 季度生季度生产产品品 xj 吨吨需求需求约束：束：第一季度末需交第一季度末需交货 20 20 吨，吨，x1 120第二季度末需交第二季度末需交货 20 20 吨，吨，x1 1-20+-20+x220这是上季末交是上季末交货后后积余余第三季度末需交第三季度末需交货 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）13015020240140203201533041014810生生产、存、存储费用：用：第一季度：第一季度：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.60第60页，此课件共67页哦7 线性规划应用举例季度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)minz=15x11+15.2x12+15.4x13+15.6x14+14x22+14.2x23+14.4x24+15.3x33+15.5x34+14.8x44 s.t.x11=20 x11+x12+x13+x1430 x12+x22=20 x22+x23+x2440 x13+x23+x33=30 x33+x3420 x14+x24+x34+x44=10 x4410 xij 0 i=1,4;j=1,4,j i61第61页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法e.g.7 合理下料合理下料问题某工厂要制作某工厂要制作100套套专用用钢架，每套架，每套钢架需要用架需要用长为2.9m、2.1m和和1.5m的的圆钢各一根。已知原料每根各一根。已知原料每根长7.4m，现考考虑应如何下料，可使所用原料最省？如何下料，可使所用原料最省？解：解：一根原料做一一根原料做一套，料套，料头0.9m.下料方案表下料方案表 方案方案毛坯毛坯/m m方案方案1 1方案方案2 2方案方案3 3方案方案4 4方案方案5 5方案方案6 6方案方案7 7方案方案8 8292111000021021032101510130234合合 计7371657463726660料料 头0103090011020814去掉料去掉料头0.90.9的的方案可以方案可以吗？62第62页，此课件共67页哦7 线性规划应用举例解：解：设 xj(j=1,8)分分别按按8 8种方案下料的原材料根数种方案下料的原材料根数 方案方案毛坯毛坯/m m方案方案1 1方案方案2 2方案方案3 3方案方案4 4方案方案5 5方案方案6 6方案方案7 7方案方案8 8292111000021021032101510130234合合 计7371657463726660料料 头0103090011020814约束条件：束条件：2.9m:2x1+x2+x3+x41002.1m:2x2+x3+3x5+2x6+x71001.5m:x1+x3+3x4+2x6+3x7+4x8100 xj 0(j=1,8)63第63页，此课件共67页哦第二章第二章 线性规划及单纯形法线性规划及单纯形法目目标函数分函数分别为：1 1、材料根数最少；、材料根数最少；min z=x1+x2+x3+x4+x5+x6+x7+x8s.t.2x1+x2+x3+x41002x2+x3+3x5+2x6+x7100 x1+x3+3x4+2x6+3x7+4x8100 xj 0(j=1,8)用用单纯形法求解可得：形法求解可得：x*=（10，50，0，30，0，0，0，0）T，最少使用的材料最少使用的材料为9090根，各种根，各种圆钢数均正好数均正好100100个个.64第64页，此课件共67页哦7 线性规划应用举例2 2、剩余料、剩余料头最少最少min z=0.1x1+0.3x2+0.9x3+0 x4+1.1x5+0.2x6+0.8x7+1.4x8s.t.2x1+x2+x3+x41002x2+x3+3x5+2x6+x7100 x1+x3+3x4+2x6+3x7+4x8100 xj 0(j=1,8)用用单纯形法求解可得：形法求解可得：x*=（0，0，0，100，0，50，0，0）T，最少的剩余料最少的剩余料头为1010m，但原料使用了但原料使用了150150根。不是最根。不是最优的。的。什么原因？什么原因？z=0.1x1+0.3 x2+0.9x3+0 x4+1.1x5+0.2x6+0.8x7+1.4x8 =7.4(x1+x2+x3+x4+x5+x6+x7+x8)-6.5100+2.9(2x1+x2+x3+x4-100)+2.1(2x2+x3+3x5+2x6+x7-100)+1.5(x1+x3+3x4+2x6+3x7+4x8-100)65第65页，此课件共67页哦第二章第二章 线性性规划及划及单纯形法形法完完66第66页，此课件共67页哦 s.t.用用单纯形法求解如下形法求解如下LP问题：67第67页，此课件共67页哦