《第一章线性规划及单纯形法第讲课件.ppt》由会员分享，可在线阅读，更多相关《第一章线性规划及单纯形法第讲课件.ppt（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章线性规划及单纯形法第讲第1页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法 线性规划线性规划（Linear Programming，简称，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。快、理论上较成熟和应用上极为广泛的一个分支。19471947年年G.B.Dantying 提出了一般线性规划问题求解提出了一般线性规划问题求解的方法的方法单纯形法之后，线性规划的理论与应用都得单纯形法之后，线性规划的理论与应用都得到了极大的发展。到了极大的发展。6060年来，随着计算
2、机的发展，线性规划已广泛应用年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。个领域，成为现代化管理的有力工具之一。第2页，此课件共64页哦1 线性规划问题及其数学模型e.g.1 资源的合理利用问题资源的合理利用问题问：如何安排生产计划，问：如何安排生产计划，使工厂获总利润最大？使工厂获总利润最大？表1产品资源甲乙库存量A1360B1140单件利润1525 某工厂在下一个生产周期内生产甲、乙两种产品，某工厂在下一个生产周期内生产甲、乙两种产品，要消耗要消耗A、B两种资源
3、，已知每件产品对这两种资源的两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利消耗，这两种资源的现有数量和每件产品可获得的利润如表润如表 1 1。第3页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20 解：设设 x1，x2 为下一个生为下一个生产周期产品甲和乙的产量产周期产品甲和乙的产量；约束条件约束条件：Subject tox1+3x260 x1+x240 x1，x20目标函数目标函数：z=15x1+25x2表1产品资源 甲乙库存量A1360B1140单件利润
4、1525决策变量决策变量第4页，此课件共64页哦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 am
5、n bm 单价 c1 c2 cn 试在满足营养要试在满足营养要求的前提下，确定食求的前提下，确定食品的购买量，使食品品的购买量，使食品的总价格最低。的总价格最低。第5页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法表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 lj第6页，此课件共64页哦1 线性规划问题及其数学模型
6、三个基本要素三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成可以把一个大系统合理地分解成 n 个子系统处理。个子系统处理。1、决策变量决策变量 xj02、约束条件约束条件 一组决策变量的线性等式或不等式一组决策变量的线性等式或不等式3、目标函数目标函数 决策变量的线性函数决策变量的线性函数第7页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法 max（min）z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn（或=，）b1 a21x1+a22x2+a2
7、nxn（或=，）b2 am1x1+am2x2+amnxn（或=，）bm xj 0（j=1,2,n）其中aij、bi、cj（i=1,2,m；j=1,2,n）为已知常数 线性规划问题的一般形式：线性规划问题的一般形式：第8页，此课件共64页哦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、除决策变量的、
8、除决策变量的非负约束外，所有非负约束外，所有的约束条件都是等的约束条件都是等式，且右端常数均式，且右端常数均为非负；为非负；3 3、所有决策变量、所有决策变量均非负均非负。第9页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法如何转化为标准形式？如何转化为标准形式？1、目标函数为求极小值，即为目标函数为求极小值，即为：。因为求因为求 min z 等价于求等价于求 max(-z)，令令 z=-z，即化为即化为：2、约束条件为不等式，xn+1 0松弛变量如何处理？如何处理？第10页，此课件共64页哦1 线性规划问题及其数学模型、右端项右端项b bi i 0 0时，只需将等式两端
9、同乘（时，只需将等式两端同乘（-1-1）则右端项必大于零则右端项必大于零 4 4、决策变量无非负约束、决策变量无非负约束 设设 xj 没有非负约束，若没有非负约束，若 xj 0 0，可令，可令 xj=-=-xj ，则则 xj 0 0；又若又若 xj 为自由变量，即为自由变量，即 xj 可为任意实数，可为任意实数，可令可令 xj=xj-xj，且，且 xj,xj 00第11页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法e.g.3试将试将 LP 问题问题min z=-x1+2x2-3x3 s.t.x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3=-5 x1,
10、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页，此课件共64页哦1 线性规划问题及其数学模型LP的几种表示
11、形式：第13页，此课件共64页哦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 问题问题 的最优解，相应的目标函数值称为最优值，的最优解，相应的目标
12、函数值称为最优值，记作记作 z*=c x*。第14页，此课件共64页哦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页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法LPLP问题图解法的基本步骤问题图解法的基本步骤：1、在平面上建立直角坐标系；
13、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；图示目标函数（等值线）和移动方向；4、寻找最优解。寻找最优解。第16页，此课件共64页哦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
14、可行域可行域x1-1.9 x2=-3.8(0,2)(3.8,0)绿色线段上的所有点绿色线段上的所有点都是最优解都是最优解,即有无穷多最优即有无穷多最优解。解。Zman=34.2第17页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法maxz=2x1+2x2s.t.2x1x22-x1+4x24x1，x20OA(,0)x1x2Note:可行域为无界区域，可行域为无界区域，目标函数值可无限目标函数值可无限增大，即解无界。增大，即解无界。称为无最优解称为无最优解。可行域为无界可行域为无界区域一定无最区域一定无最优解吗？优解吗？第18页，此课件共64页哦2 线性规划问题的图解法由以上
15、两例分析可得如下重要结论：由以上两例分析可得如下重要结论：1、LP 问题从解的角度可分为：问题从解的角度可分为：有可行解有可行解 无可行解无可行解a.有唯一最优解有唯一最优解b.有无穷多最优解有无穷多最优解c.无最优解无最优解2、LP 问题若有最优解，必在可行域的某个顶点上取问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。任一点都是最优解。第19页，此课件共64页哦2 线性规划问题的图解法图解法优点：图解法优点：直观、易掌握。有助于了解解的结构。直观、易掌握。有助于了解解的结构。图解法缺点：图
16、解法缺点：只能解决低维问题，对高维无能为力。只能解决低维问题，对高维无能为力。第20页，此课件共64页哦3 线性规划问题解的基本性质讨论如下 LP问题：其中系数矩阵决策向量 假设假设 A 的秩为的秩为 m,且只讨论且只讨论 m 0,x20,xk 0，分两种情况讨论：(1)如果p1,p2,pk 线性无关，即x 的非零分量对应的列向量线性无关，则由定理1知，它是LP 的一个基本可行解，定理成立。(2)如果p1,p2,pk线性相关，则必存在一组不全为零的数1,2,k 使得第27页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法假定有i0，取作其中由（6）式知，必有即又因为由（5）
17、式知故有，即也是LP的两个可行解。第28页，此课件共64页哦3 线性规划问题解的基本性质 再由 的取法知，在式(7)的诸式中，至少有一个等于零，于是所作的可行解 中，它的非零分量的个数至少比 x 的减少1，如果这些非零分量所对应的列向量线性无关，则 为基可行解，定理成立。否则，可以从 出发，重复上述步骤，再构造一个新的可行解 ，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分量对应的列向量线性无关，故可行解必为基可行解。证毕。返回e第29页，此课件共64页哦3 线性规划问题解的基本性质定理定理 3 3 证明证明设是 LP 的一个最优解。如果 x*是基本解，则
18、定理成立；如果 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页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法LP问题解的几何意义定义定义 5 5 设集合设集合 是是 n n 维欧氏空间中的一个点维欧氏空间中的一个点集，如果集，如果 及实数及实数 则称则称 S 是一个凸集。是
19、一个凸集。几何意义：如果集合中任意两点连线上的一切点都在几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。该集合中，则称该集合为凸集。Note:空集和单点集也是凸集。空集和单点集也是凸集。第31页，此课件共64页哦3 线性规划问题解的基本性质定义定义 6 6 设 则称为点 的一个凸组合。定义定义 7 7 设凸集 两点 表示为 则称 x 为 S 的一个极点（或顶点）。定理定理 4 LP 问题的可行解集第32页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法定理定理 5 5 设设 D 为为 LP 问题的可行解集，问题的可行解集，则，则 x 是是 D的极
20、点的充分必要条件是的极点的充分必要条件是 x 为为 LP 问题的基可行解。问题的基可行解。prove推论推论 1 1 如果如果 LP 问题的可行解集非空，则极点集合也问题的可行解集非空，则极点集合也一定非空，且极点的个数是有限的一定非空，且极点的个数是有限的。推论推论 2 2 如果如果 LP 问题有最优解，则一定可在可行解集问题有最优解，则一定可在可行解集 D 的极点上达到。的极点上达到。定理定理 6 6 设设 LP 问题在多个极点问题在多个极点 x(1),x(2),x(k)处取到最优处取到最优解，则它们的凸组合，即解，则它们的凸组合，即也是也是 LP 问题的最优解问题的最优解.（此时，该（此
21、时，该LPLP 问题有无穷多最优解）问题有无穷多最优解）第33页，此课件共64页哦3 线性规划问题解的基本性质Note:1、如何判断如何判断 LP 问题有最优解；问题有最优解；2、计算复杂性问题。计算复杂性问题。设有一个设有一个5050个变量、个变量、2020个约束等式的个约束等式的 LP LP 问题，则问题，则 最多可能有最多可能有 个基。个基。即约即约150150万年万年 如果计算一个基可行解只需要如果计算一个基可行解只需要 1 秒，那么计算所有秒，那么计算所有 的基可行解需要：的基可行解需要：1364.7101.510360024365（年）第34页，此课件共64页哦4 单纯形法的基本原
22、理 单纯形法单纯形法（Simplex Method）是是19471947年由年由 G.B.Dantzig 提出，是解提出，是解 LP 问题最有效的算法之一，问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础且已成为整数规划和非线性规划某些算法的基础。基本思路：基本思路：基于基于 LP 问题的标准形式，先设法找到一个基可问题的标准形式，先设法找到一个基可行解，判断它是否是最优解，如果是则停止计算；否行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不
23、（两个基可行解相邻是指它们之间仅有一个基变量不相同）。相同）。第35页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法单纯形法引例单纯形法引例 首先，化原问首先，化原问题为标准形式：题为标准形式：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+
24、0 x3+0 x4s.t.x1+3x2+x3=60 x1+x2+x4=40 x1，x2,x3,x40 第36页，此课件共64页哦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 换出。换出。基变量用非基变量表示：基变量用非基变量表
25、示：代入目标函数：代入目标函数：z=500+20/3x1-25/3x3令非基变量令非基变量 x1=x3=0 z=500 基可行解基可行解 x(1)=(0,20,0,20)T大于零！大于零！第37页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法因为因为x1 的系数大，所以的系数大，所以x1 换入基变量。换入基变量。所以所以 x4换出。换出。基变量用非基变量表示：基变量用非基变量表示：代入目标函数：代入目标函数：z=7005x310 x4令非基变量令非基变量 x3=x4=0 z=700 基可行解基可行解 x(2)=(30,10,0,0)T 因为非基变量的系数都小于零，因为非基
26、变量的系数都小于零，所以所以 x(2)=(30,10,0,0)T是最优解是最优解 zmax=700 第38页，此课件共64页哦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页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法单纯形法的基本原理单纯形法的基本原理称称(1a)(2
27、a)(3a)为为LP问题对应于问题对应于基基 B 的典则形式（典式）的典则形式（典式）.Ax=b基变量用非基变量表示：基变量用非基变量表示：代入目标函数：代入目标函数：第40页，此课件共64页哦4 单纯形法的基本原理如果记如果记则典式则典式(1a)(2a)(3a)可写成第41页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法定理定理 7 在在 LP 问题问题 的典式的典式(1b)(3b)中，中，如果有如果有则对应于基则对应于基 B 的基可行解的基可行解是是 LP 问题的最优解，记为问题的最优解，记为相应的目标函数最优值相应的目标函数最优值 z*=z(0)此时，基此时，基B
28、B称称为最优基为最优基第42页，此课件共64页哦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)出发，一定能找到一个新的基可行解出发，一定
29、能找到一个新的基可行解 第43页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法定理定理 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 问题解无界（无最优解）。问题解无界
30、（无最优解）。第44页，此课件共64页哦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页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法如何得到单纯形表？cAb检验数0B-1b-cB B-1b -z0 I B-1NB-1b 0 N检验数 B NcB cN I B-1N 0 cN-cB B-
31、1N第46页，此课件共64页哦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=12第47页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法单纯形法求解单纯形法求解
32、 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），则此问题解无界，停止计算。否则转入下
33、一），则此问题解无界，停止计算。否则转入下一 步步;第48页，此课件共64页哦5 单纯形法的计算步骤Step 4 根据根据 ,确定确定 xk为换入为换入基变量，又根据最小比值法则计算基变量，又根据最小比值法则计算:确定确定xr为换出基变量。转入下一步为换出基变量。转入下一步;Step 5 以以 为主元进行换基变换，用初等行变换将为主元进行换基变换，用初等行变换将 xk 所对应的列向量变换成单位列向量，即所对应的列向量变换成单位列向量，即同时将检验数行中的第同时将检验数行中的第k个元素也个元素也变换为零，得到新的单纯形表。变换为零，得到新的单纯形表。返回返回Step 2。第49页，此课件共64页
34、哦第一章第一章 线性规划及单纯形法线性规划及单纯形法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
35、)为最优解为最优解 zmax=70060/340/12531/312000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-10第50页，此课件共64页哦5 单纯形法的计算步骤思考：思考：在单纯形法中根据在单纯形法中根据确定确定 xk为进基变量，是否在这次变换中，使目为进基变量，是否在这次变换中，使目标函数值提高最大？标函数值提高最大？如果不是，应选择哪个变量进基，保证这如果不是，应选择哪个变量进基，保证这次变换使得目标函数值提高最大？次变换使得目标函数值提高最大？目标函数值能提高多少？目标函数值能提高多少？第51页，此课件共
36、64页哦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、人工变、人工变 量法量法第
37、52页，此课件共64页哦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页，此课件
38、共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法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 -Mx1x2x3x4x5x6x7131011
39、012-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
40、 目标函数最优值目标函数最优值 zmax=2 Note:在计算过程中在计算过程中,某个人工变量一旦变为非基变量某个人工变量一旦变为非基变量,则该列可被删去则该列可被删去 第54页，此课件共64页哦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+a
41、22x2+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 个个 ，同时达到最小值，就选其中
42、下标，同时达到最小值，就选其中下标最小的那个基变量作为出基变量。即如果最小的那个基变量作为出基变量。即如果 则选择则选择x xl l作为出基变量。作为出基变量。第58页，此课件共64页哦7 线性规划应用举例e.g.6 生产计划问题生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费则一个季度每积压一吨产品需支付存贮费0.20.2万元万元.现该厂现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全考
43、虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低年的生产费用最低.试建立线性规划模型试建立线性规划模型.季度j生产能力（aj）生产成本（d dj j）需求量（bj）13015020240140203201533041014810第59页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法解：解：方法一方法一设工厂第设工厂第 j 季度生产产品季度生产产品 xj 吨吨需求约束：需求约束：第一季度末需交货第一季度末需交货 20 20 吨，吨，x1 120第二季度末需交货第二季度末需交货 20 20 吨，吨，x1 1-20+-20+x220这是上季末交这是上季末交货后
44、积余货后积余第三季度末需交货第三季度末需交货 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
45、-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页，此课件共64页哦7 线性规划应用举例季度j生产能力（aj）生产成本（d dj j）需求量（bj）13015020240140203201533041014810方法二方法二设第设第 i 季度生产而用于第季度生产而用于第 j 季度末交
46、货的产季度末交货的产品数量为品数量为 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
47、=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 i第61页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法e.g.7 合理下料问题合理下料问题某工厂要制作某工厂要制作100套专用钢架，每套钢架需要用长套专用钢架，每套钢架需要用长为为2.9m、2.1m和和1.5m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4m，现考虑应如何下料，可使所用原料最省？现考虑应如何下料，可使所用原料最省？解：解：一根原料做一根原料做一套，料头一套，料头0.
48、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页，此课件共64页哦7 线性规划应用举例解：解：设设 xj(j=1,8)分别按分别按8 8种方案下料的原材料根数种方案下料的原材料根数 方案方案毛坯毛坯/m m方案方案1 1方案方案2 2方案方案3 3方案方案4 4方案方案5 5
49、方案方案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页，此课件共64页哦第一章第一章 线性规划及单纯形法线性规划及单纯形法目标函数分别为：目标函数分别为：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页哦