《第一章线性规划10-2-28.ppt》由会员分享，可在线阅读，更多相关《第一章线性规划10-2-28.ppt（118页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章第一章 线性规划及单纯形法线性规划及单纯形法 Linear Programming(LP)Linear Programming(LP)北京物资学院运筹学教学课件北京物资学院运筹学教学课件北京物资学院信息学院北京物资学院信息学院 2010 2010年年3 3月月第一节第一节 线性规划问题的数学模型线性规划问题的数学模型第二节第二节 两变量线性规划问题的图解法两变量线性规划问题的图解法第三节第三节 单纯形法的原理单纯形法的原理第四节第四节 单纯形法的计算步骤单纯形法的计算步骤第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论第六节第六节 线性规划应用举例线性规划应用举例本章内容本章内容第
2、一节第一节 线性规划问题的数学模型线性规划问题的数学模型线性规划是运筹学中研究较早、发展较快、应用较广、线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。资源的数学方法。线性规划研究的问题线性规划研究的问题：极大化问题：面对一定的资源，要求充分利用，极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。以获得最大的经济效益。极小化问题：给定一项任务，要求统筹安排，尽极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务量做到用最少的人力、物力资源去完
3、成这一任务。一、实例：一、实例：生产安排问题生产安排问题 运输问题运输问题二、线性规划问题的结构特征二、线性规划问题的结构特征 线性规划问题的特征线性规划问题的特征 线性规划问题的一般形式线性规划问题的一般形式 线性规划问题的标准形式线性规划问题的标准形式 一般形式向标准形式的转化一般形式向标准形式的转化本节内容安排本节内容安排一、实例一、实例例例1 1 生产安排问题生产安排问题 某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，生产甲、乙两种产三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的
4、利润以及三种设备可利用的时数如下表所示：可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品甲产品乙产品乙设备时数设备时数设备设备A A3 32 26565设备设备B B2 21 14 40 0设备设备C C0 03 37575利润（元利润（元/件）件）1500150025002500问题：工厂应如何安排生产可获得最大的总利润？问题：工厂应如何安排生产可获得最大的总利润？可控因素：生产两种产品的数量，设分别为可控因素：生产两种产品的数量，设分别为x1,x2，目标是生产利润最大，设生产利润为目标是生产利润最大，设生产利润为z.z.利润函数为：利润函数为：限制条件：三台设备的使用时间不超过
5、设备能力的限制条件：三台设备的使用时间不超过设备能力的限制限制设备设备A:A:3 3x1 1+2+2x2 26565设备设备B:B:2 2x1 1+x2 2 40 40设备设备C:C:3 3x2 2 7575蕴涵约束：产量为非负蕴涵约束：产量为非负 x1 0,x2 0目标函数目标函数约束条件约束条件设生产甲乙两种产品的数量分别为设生产甲乙两种产品的数量分别为x1,x2件件，总利总利润为润为z.在处理产、供、销的经济活动中，会经常遇到物在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产
6、地调运到若干个销售化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调运方案才能使总运输地。问题是，怎样制定合理的调运方案才能使总运输费用最少？这类问题称为运输问题费用最少？这类问题称为运输问题例例2 2 运输问题运输问题 设要从甲地调出物资设要从甲地调出物资20002000吨，从乙地调出物资吨，从乙地调出物资600600吨，吨，从丙地调出物资从丙地调出物资500500吨，分别供应给吨，分别供应给A A地地17001700吨、吨、B B地地11001100吨、吨、C C地地200200吨、吨、D D地地100100吨。已知每吨运费如下表所吨。已知每吨运费如下表所示。示。假
7、定运费与运量成正比例，问怎样才能找到一个总运假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？费最省的调拨计划？丙丙1726384315375151 乙乙1572521 甲甲D DC CB BA A销地销地产地产地单位：元单位：元/t tx22x11x12x13x21x23x31x32x33x14x24x34问题分析：问题分析：可控因素：可控因素：从三个产地到四个销地的运输量；从三个产地到四个销地的运输量；目标：目标：总运费最省；总运费最省；限制条件：限制条件：各个产地的产量和销地的需求量的限制各个产地的产量和销地的需求量的限制。用用 （i=1,2,3;j=1,2,3,4i=1,
8、2,3;j=1,2,3,4）分别表示从甲乙丙三个产地运往分别表示从甲乙丙三个产地运往A,B,C,DA,B,C,D四个销地的物资数量。四个销地的物资数量。则该问题的数学模型为则该问题的数学模型为简化表达式简化表达式二、线性规划问题的结构特征：二、线性规划问题的结构特征：1 1.线性规划问题的特征线性规划问题的特征；（1 1）都有一组决策变量。）都有一组决策变量。（2 2）都有一组线性的约束条件，它们是线性等式）都有一组线性的约束条件，它们是线性等式或不等式。或不等式。（3 3）都有一个确定的目标，这个目标可以表示成）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求
9、实决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。现极大化，有的要求实现极小化。线性规划问题的本质：研究在一组线性约束下，线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题一个线性函数的极值问题。所以称为线性规划所以称为线性规划 linear programming (LP)2.2.线性规划问题的一般形式线性规划问题的一般形式s.t（1）（2）（3）一般形式的简化表达一般形式的简化表达线性规划问题的规范形式线性规划问题的规范形式s.t极大化问题极大化问题极小化问题极小化问题s.t3.3.线性规划的标准形式线性规划的标准形式s.t.s.t（1）（2）（3）
10、标准形式的简化表达标准形式的简化表达标准形式的矩阵表达标准形式的矩阵表达标准形式的向量表达标准形式的向量表达标准形式的特点标准形式的特点：(1).目标函数极大化目标函数极大化(2).约束条件全部是等式约束条件全部是等式(3).所有的变量都是非负的所有的变量都是非负的(4).约束条件右端常数为非负的约束条件右端常数为非负的4.4.一般形式向标准形式的转化一般形式向标准形式的转化：(1)目标函数极大化目标函数极大化对于极小化的目标函数对于极小化的目标函数 可以等价地转化成求可以等价地转化成求的极大化的极大化。(2)不等式约束化等式约束不等式约束化等式约束对于对于 形的不等式，可以在不等式的左边加上
11、形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。变量称为松弛（剩余）变量。例如：例如：(3)自由变量化非负变量的自由变量化非负变量的差差自由变量可以用两个非负变量的差代替，例如对于自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量一个符号无限制的变量 ，可以引进两个非负变量，可以引进两个非负变量 并设并设(4)约束条件右端的负常数化为正常数约束条件右端的负常数化为正常数对于右端常数为负数的约束，可以两端同时乘对于右端常数为负数的约束，可以两端同时乘以以-1-1。取值小于等于取值
12、小于等于0的变量，可以用一个非负变量的相的变量，可以用一个非负变量的相反数表示。反数表示。例例 将下列将下列LPLP问题化成标准形式问题化成标准形式s.t.s.t.课堂练习：将下列课堂练习：将下列LPLP问题化成标准形式问题化成标准形式作业：作业：补充补充 习题一习题一 第第 1 1、2 2、9 9 题题第二节第二节 两变量线性规划问题的图解法两变量线性规划问题的图解法一、一、几个概念几个概念二、二、两变量两变量LPLP问题的图解法问题的图解法可行解可行解：任何一组满足所有约束条件的决策变量值：任何一组满足所有约束条件的决策变量值 称为称为L LP P问题的一个可行解。问题的一个可行解。最优解
13、最优解：使目标函数达到：使目标函数达到最大（小最大（小）值的可行解。）值的可行解。最优值最优值：最优解对应的目标函数值。：最优解对应的目标函数值。可行域可行域：所有可行解的集合称为可行域。：所有可行解的集合称为可行域。一、几个概念一、几个概念：二、两变量二、两变量LPLP问题的图解法问题的图解法图解法是根据平面直角坐标系和二元一次方程图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。（不等式）的特点设计的。1.1.图解法的一般步骤图解法的一般步骤：（1 1）建立直角坐标系，以建立直角坐标系，以 为横轴，为横轴，为纵轴。为纵轴。（2 2）将约束条件在直角坐标系中表示，并找出可行域将
14、约束条件在直角坐标系中表示，并找出可行域。（3 3）作出目标函数的等值线簇，找出目标函数值的增加）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。（或减小）方向，用箭头表示。（4 4）确定出问题的最优解。若为极大（小）化问题，）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。一个交点即为最优解。例例1 1 用图解法解下列线性规划问题用图解法解下列线性规划问题最优解最优解 x*=(10,15)T,最优值最优值 z*=60 10+50 15=1350.0 1 0 20
15、30 4 0 1 0 2 0 3 0 x2 x1(1)(2)(10,15)可行域有界可行域有界,有唯一最优解有唯一最优解课堂练习：用图解法求课堂练习：用图解法求解下列解下列LP问题问题x1x2 最优解为最优解为X=(5，25)T，最优值，最优值 70000。例例2 2、无穷多最优解无穷多最优解x1x2 例例3 3、无有限无有限最优解最优解x1x2 可行域无界可行域无界,有唯一最优解有唯一最优解x1x2 例例4 4、x1x2 可行域为空可行域为空,无可行解无可行解例例5 5、可行域是空集。可行域是空集。可行域存在，则一定是一个凸多边形可行域存在，则一定是一个凸多边形.无无有限有限最优解（可行域一
16、定无界）。最优解（可行域一定无界）。最优解存在且唯一，则一定在顶点上达到。最优解存在且唯一，则一定在顶点上达到。最优解存在且不唯一，一定存在一个顶点是最优解。最优解存在且不唯一，一定存在一个顶点是最优解。2.2.图解法求解两变量图解法求解两变量LPLP问题时可能出现的情况问题时可能出现的情况：3.3.两变量线性规划问题解的性质两变量线性规划问题解的性质 1.1.两变量线性规划问题的可行域是若干个半平两变量线性规划问题的可行域是若干个半平面的交集，它是一个有界或无界的凸多边形，并面的交集，它是一个有界或无界的凸多边形，并且有有限个顶点。且有有限个顶点。2.2.对于给定的线性规划问题，如果它有最优
17、解，对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。最优解总可以在可行域的某个顶点上达到。第三节第三节 单纯形法的原理单纯形法的原理一、一、可行区域的几何结构可行区域的几何结构二、二、基可行解及线性规划的基本定理基可行解及线性规划的基本定理三、三、单纯形法的原理单纯形法的原理单纯形方法（单纯形方法（Simplex Method）是是G.B.Dantzing 在在1947年提出的。年提出的。一、可行区域的几何结构一、可行区域的几何结构1.1.基本假设基本假设2.2.凸集及其性质凸集及其性质3.3.可行域的凸性可行域的凸性4.4.问题问题1.1.基本假设基本假设凸集凸
18、集：设设S是是n维欧氏空间的一个点集，若任意两点维欧氏空间的一个点集，若任意两点X(1)S,X(2)S 的连线上的一切点的连线上的一切点 X(1)+(1-)X(2)S,(0 1);则称则称S为一个凸集。为一个凸集。性质性质：任意多个凸集的交集仍然是任意多个凸集的交集仍然是凸集凸集。2.2.凸集及性质凸集及性质顶点顶点：设设S是凸集，是凸集，X S；若对任何若对任何X(1)S和和 X(2)S，X(1)X(2)，以及任何以及任何0 m)，其秩为其秩为m，B是是A中的一个中的一个m阶满秩子方阵，称阶满秩子方阵，称B是线性规划问题的一个基是线性规划问题的一个基。B中每一个列向量称为一个中每一个列向量称
19、为一个基向量基向量，与基向量对应的变量称，与基向量对应的变量称为为基变量基变量。其余变量称为。其余变量称为非基变量非基变量。不失一般性，设不失一般性，设则则Pj（j=1，2m）是基向量，是基向量，xj（j=1，2m）是基变量。是基变量。xj（j=m+1，n）是非基变量。是非基变量。基解基解：在约束方程组中令所有的非基变量：在约束方程组中令所有的非基变量xm+1=x m+2=x n=0，得得此方程组有唯一解此方程组有唯一解XB=(x1，x2，xm)T，将这个解将这个解加上非基变量取加上非基变量取0的值有的值有X=(x1，x2，xm,0,0)T,称称X为线性规划问题的基解。为线性规划问题的基解。显
20、然，基解中取非零值的变量个数不超过显然，基解中取非零值的变量个数不超过m，基基解的总数不超过解的总数不超过Cnm个。个。基可行解基可行解：满足非负约束的基解称为基可行解。：满足非负约束的基解称为基可行解。可行基可行基：对应于基可行解的基。：对应于基可行解的基。可行解可行解基解基解基可行解基可行解用矩阵形式表示的基解用矩阵形式表示的基解考虑标准形式的线性规划问题：考虑标准形式的线性规划问题：例如例如LPLP问题问题是它的两个基，对应的基解分别为是它的两个基，对应的基解分别为可见可见X1是基可行解，故是基可行解，故B1是可行基。而是可行基。而X2不是基可行不是基可行解，故解，故B2不是可行基。不是
21、可行基。根据以上定义根据以上定义基基基解基解是否基可行解是否基可行解目标函数值目标函数值(x1,x2,x3,x4,x5)(P1,P2,P4)(3,3,0,4,0)是是15(P1,P2,P5)(4,2,0,0,5)是是14(P2,P3,P4)(0,3,6,16,0)是是9(P1,P3,P5)(4,0,4,0,15)是是8(P3,P4,P5)(0,0,12,16,15)是是0(P1,P2,P3)(4,3,-2,0,0)否否17(P1,P4,P5)(6,0,0,-8,15)否否12(P2,P4,P5)(0,6,0,16,-15)否否182.2.线性规划的基本定理线性规划的基本定理引理引理：LP问题的
22、可行解问题的可行解X是基可行解的充要条件是它是基可行解的充要条件是它的正分量所对应的的正分量所对应的A中的列向量线性无关。中的列向量线性无关。定理定理2 2：线性规划问题的基可行解对应可行域的顶：线性规划问题的基可行解对应可行域的顶点。（点。（X是基可行解是基可行解X是可行域的顶点）（基可是可行域的顶点）（基可行解个数有限）行解个数有限）定理定理3 3：一个一个LP问题，若有最优解，则一定存在一问题，若有最优解，则一定存在一个基可行解是最优解。个基可行解是最优解。3.3.问题问题1)1)如何得到第一个基可行解？如何得到第一个基可行解？2)2)如何判别一个基可行解是否最优？如何判别一个基可行解是
23、否最优？3)3)如果当前的基可行解不是最优，如何从一个如果当前的基可行解不是最优，如何从一个基可行解转化到另一个基可行解？基可行解转化到另一个基可行解？三、单纯形法原理三、单纯形法原理1.确定初始基可行解确定初始基可行解2.最优性检验和解的判别最优性检验和解的判别3.基可行解的改进基可行解的改进情况情况1 1 约束条件全部是约束条件全部是“”型不等式且右端常数非负型不等式且右端常数非负（化成标准形后，约束条件系数矩阵含有单位子矩阵）（化成标准形后，约束条件系数矩阵含有单位子矩阵）加上松弛变量，化为标准形式：加上松弛变量，化为标准形式：1.1.确定初始基可行解确定初始基可行解其约束条件系数矩阵为
24、其约束条件系数矩阵为令其中的单位矩阵作为基，可得初始基可行解令其中的单位矩阵作为基，可得初始基可行解考虑标准形式的考虑标准形式的LP问题问题假设可行域非空，假设可行域非空，A为一为一 m n实矩阵，实矩阵，r(A)=m 0，而，而 ij 0，则原问，则原问题无界；题无界；如果某个非基变量的检验数如果某个非基变量的检验数 j 0，且至少存在一个，且至少存在一个i，使得，使得 ij 0，则可以找到一个新的基可行解，则可以找到一个新的基可行解X1，使，使得得CX1CX。3.3.基可行解的改进基可行解的改进1)1)基的修改：基的修改：进基变量、出基变量的选取准则。进基变量、出基变量的选取准则。2)2)
25、迭代：迭代：得到新基对应的典式。得到新基对应的典式。基的修改准则：新基与原有基有基的修改准则：新基与原有基有m-1 个相同的基个相同的基变量，只有一个基变量不同。变量，只有一个基变量不同。进基变量进基变量：从非基变量变为基变量的变量：从非基变量变为基变量的变量。出基变量出基变量：由基变量变为非基变量的变量。：由基变量变为非基变量的变量。1)1)进基变量的选取原则进基变量的选取原则：最优性原则最优性原则：若：若 k 0,则与则与 k 相对应的变量相对应的变量xk 是非基是非基变量，当变量，当xk 变为基变量时，它的值由变为基变量时，它的值由0变为正数，比变为正数，比如说如说xk=0，其余的非基变
26、量仍取值为零。由其余的非基变量仍取值为零。由(3.4)式知，对应新解的目标函数值为式知，对应新解的目标函数值为z=z0+K z0，显显然然 越大目标函数值越大越大目标函数值越大。可行性原则（最小比值原则）可行性原则（最小比值原则）：的取值应保的取值应保证新解仍然是基可行解。证新解仍然是基可行解。2)2)出基变量的选取原则出基变量的选取原则进基变量和出基变量的选取准则进基变量和出基变量的选取准则例例:求解下列线性规划问题求解下列线性规划问题O 1 0 20 30 4 0 1 0 2 0 3 0 x2 x1(1)(2)B (10,15)AC化成标准形式（典式）化成标准形式（典式）约束条件系数矩阵含
27、单位矩阵；约束条件系数矩阵含单位矩阵；目标函数中基变量系数为目标函数中基变量系数为0 0。O 1 0 20 30 4 0 1 0 2 0 3 0 x2 x1(1)(2)B (10,15)AC第一个基可行解第一个基可行解X0=(0,0,80,60)T目标函数值为目标函数值为0对应可行域顶点对应可行域顶点O(0，0).让让x1进基，不妨假设进基，不妨假设x1 ，x2仍为非基变量。目标函数仍为非基变量。目标函数值为值为 60 。从最优性角度看，从最优性角度看，越大越好越大越好为了保持解的可行性，原先的基变量取值必须满足为了保持解的可行性，原先的基变量取值必须满足综上得到X4出基，新的基变量为出基，新
28、的基变量为X1，X3，对应的典式可以由对应的典式可以由方程组的初等变换得到方程组的初等变换得到新的基可行解：新的基可行解：X1=(20,0,40,0)T,对应的目标函数值为对应的目标函数值为1200。对应可行域对应可行域C点。点。取取x2为进基变量，为进基变量，x3为出基变量。为出基变量。新的基可行解：新的基可行解：X1=(10,15,0,0)T,对应的目标函数值为对应的目标函数值为1350。对应可行域对应可行域B点。点。检验数均非正，所以已得到检验数均非正，所以已得到最优解。最优解。当当xk=0成为基变量以后，其余非基变量仍然成为基变量以后，其余非基变量仍然取值为取值为0。设新基对应的基可行
29、解为。设新基对应的基可行解为X1=(x11,xn1)T,则则X1应满足约束条件，即应满足约束条件，即由于由于xi1必须是非负的，即必须是非负的，即如果如果 ik 0，显然只要显然只要 0，就有就有xi1 =i-ik 0，对对于于 ik0，就要求就要求所以所以 应满足应满足假定至少有一个假定至少有一个ai k0，i=1,2,m，并且所有的并且所有的 i 0,则则0 0，从最优性原则出发，让从最优性原则出发，让 取值尽量大，即取取值尽量大，即取然后把然后把xt从原有的基中取出来，得到一组新的基可行解从原有的基中取出来，得到一组新的基可行解X1 使目标函数取值使目标函数取值 z1=z0+k 0 z0
30、.注意：注意：1.1.在选取在选取进基变量进基变量时，若有几个非基变量的检验数都时，若有几个非基变量的检验数都是正数，则可以任意选取一个正检验数对应的非基变量是正数，则可以任意选取一个正检验数对应的非基变量作为进基变量，一般选取最大正检验数对应的非基变量。作为进基变量，一般选取最大正检验数对应的非基变量。但实际情况表明这种策略不一定最好。但实际情况表明这种策略不一定最好。2.2.在选取在选取出基变量出基变量时，若有几个比值同时达到最小，时，若有几个比值同时达到最小，可以任意选择一个，但在新的基本可行解中这些对应分可以任意选择一个，但在新的基本可行解中这些对应分量均为零。从而新的基本可行解是一个
31、退化的基本可行量均为零。从而新的基本可行解是一个退化的基本可行解。假若问题是非退化的，则不会出现这种情况。解。假若问题是非退化的，则不会出现这种情况。迭代（新的基可行解对应的典式的确定）迭代（新的基可行解对应的典式的确定）利用线性方程组的等价变换将约束条件和目标函数利用线性方程组的等价变换将约束条件和目标函数化成新基对应的典式，从而求出新的基可行解及相化成新基对应的典式，从而求出新的基可行解及相应的检验数应的检验数第四节第四节 单纯形方法的计算步骤单纯形方法的计算步骤Step 1Step 1 将线性规划问题化成典式将线性规划问题化成典式,求出各个非基变量求出各个非基变量的检验数的检验数.Ste
32、p 2Step 2 判断所有非基变量的检验数是否非正判断所有非基变量的检验数是否非正,若是若是,则则结束结束;否则转否则转step 3.Step 3Step 3 选取一个检验数大于零的非基变量为进基变量选取一个检验数大于零的非基变量为进基变量;Step 4Step 4 若进基变量所对应的约束条件系数全为非正数若进基变量所对应的约束条件系数全为非正数,则原问题无界则原问题无界,结束结束;否则否则,按最小比值原则确定出基变按最小比值原则确定出基变量量;Step 5Step 5 进行迭代进行迭代(用方程组的初等变换法确定新的基用方程组的初等变换法确定新的基对应的典式及检验数对应的典式及检验数),),
33、转转step 2.例例1 1：利用单纯形法求下列线性规划问题：利用单纯形法求下列线性规划问题将该问题化成标准形式（也是典式）将该问题化成标准形式（也是典式）基变量是：基变量是：x3，x4，x5，非基变量是非基变量是 x1 x2求出第一个基可行解求出第一个基可行解X0=(0,0,65,40,75)T，非基变量非基变量的检验数均为正数，所以的检验数均为正数，所以X0不是最优解。不是最优解。确定进基变量确定进基变量 x2，按照最小比值原则确定出基变量按照最小比值原则确定出基变量x5，最小比值是最小比值是 0=25.求出新基对应的典式求出新基对应的典式X1=(0,25,15,15,0)T目标函数值为目
34、标函数值为62500。确定进基变量确定进基变量 x1，按照最小比值原则确定出基变量按照最小比值原则确定出基变量x3，最小比值是最小比值是 0=5.求出新基对应的典式求出新基对应的典式X*=(5,25,0,5,0)T目标函数值为目标函数值为70000。当前的解是最优解当前的解是最优解利用（利用（1）消去目标函数中的）消去目标函数中的x1单纯形表单纯形表=-cn+i bi j=cj-cn+i CBXBbc1c2cmcm+1cnx1x2xmxm+1xnc1x1b110 1m+1 1n:cmxmbm01 mm+1 mn检验数检验数z000 m+1 n用单纯形表求解例用单纯形表求解例1解：先化成标准形式
35、解：先化成标准形式15002500000CBXBbx1x2x3x4x50 x365321000 x440210100 x57503001 j0150025000000 x3153010-2/30 x4152001-1/32500 x22501001/3 j-625001500000-2500/31500 x15101/30-2/90 x4500-2/311/92500 x22501001/3 j-7000000-5000-50032.5402557.5例例2 2：利用单纯形法求下列线性规划问题：利用单纯形法求下列线性规划问题将该问题化成标准形式（也是典式）将该问题化成标准形式（也是典式）基变量
36、是：基变量是：x3，x4，x5，非非基变量是基变量是x1 x2填入单纯形表求解填入单纯形表求解25000CBXBbx1x2x3x4x50 x34101000 x43010100 x5812001 j0250000 x34101005x23010100 x52100-21 j-15200-500 x320012-15x23010102x12100-21 j-19000-1-2 3442最优解最优解X*=(2,3,2,0,0)T，最优值最优值19。例例3 3：用单纯形法求解线性规划问题（多解问题）：用单纯形法求解线性规划问题（多解问题）解解:化成标准形式化成标准形式填入单纯形表求解填入单纯形表求解
37、(5,1)(1,5)11000CBXBbx1x2x3x4x50 x34-111000 x441-10100 x5611001 j0110001x24-111000 x48001100 x5220-101 j-420-1001x25011/201/20 x48001101x1110-1/201/2 j-60000-14611x21010-1/21/20 x38001101x151001/21/2 j-60000-1108最优解最优解X1=(1,5,0,8,0)T，最优值最优值6。最优解最优解X2=(5,1,8,0,0)T，最优值最优值6。实际上实际上X1与与X2的连线上的任意点都是最优解的连线上
38、的任意点都是最优解.(5,1)(1,5)例例4 4：用单纯形法求解线性规划问题（无有限最优解的：用单纯形法求解线性规划问题（无有限最优解的情况）情况）解：化成标准形（典式）解：化成标准形（典式）（5，0）（0，5）2100CBXBbx1x2x3x40 x35-11100 x4102-501 j0 2 1 000 x3100-3/211/2 2 x15 1 -5/2 0 1/2 j-10060 -1 5X2的检验数为正，但约束条件中的检验数为正，但约束条件中x2的系数全为负，的系数全为负，因此该问题无有限最优解。因此该问题无有限最优解。第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论在给定
39、的在给定的LP问题的标准形式中，如果约束条件系数矩问题的标准形式中，如果约束条件系数矩阵阵A中含有一个中含有一个m阶单位矩阵，并且阶单位矩阵，并且b 0，则我们已经则我们已经找到了一个明显的基可行解，并且约束方程组已经是典找到了一个明显的基可行解，并且约束方程组已经是典式，这时可以直接填入单纯形表中进行迭代。但是实际式，这时可以直接填入单纯形表中进行迭代。但是实际问题往往并非如此，因此我们需要寻找第一个基可行解，问题往往并非如此，因此我们需要寻找第一个基可行解，通常使用两种常用的方法求解第一个基可行解。通常使用两种常用的方法求解第一个基可行解。1.大大M法法2.两阶段法两阶段法考虑标准形式的线
40、性规划问题考虑标准形式的线性规划问题1.大大M法法原问题原问题辅助问题辅助问题人工变量人工变量X是原问题是原问题的基可行解的基可行解是辅助问题是辅助问题的基可行解。的基可行解。为了得到原问题的一个基可行解，只要将辅助问题为了得到原问题的一个基可行解，只要将辅助问题的基可行解中的人工变量全部变为非基变量即可。的基可行解中的人工变量全部变为非基变量即可。为此，将人工变量加到辅助问题的目标函数中并赋为此，将人工变量加到辅助问题的目标函数中并赋予系数予系数-M。（。（M可以看成惩罚系数）可以看成惩罚系数）添加添加M以后，直接求解辅助问题，可能有两种情况：以后，直接求解辅助问题，可能有两种情况：1.辅助
41、问题的最优解中人工变量全部是非基变量，辅助问题的最优解中人工变量全部是非基变量，此时去掉人工变量直接得到原问题的最优解。此时去掉人工变量直接得到原问题的最优解。2.2.在辅助问题的最优解中某些人工变量是基变量在辅助问题的最优解中某些人工变量是基变量且取值非零，此时原问题无可行解。且取值非零，此时原问题无可行解。例例5：用大：用大M法求解下列线性规划问题法求解下列线性规划问题化标准型化标准型添加人工变量得辅助问题添加人工变量得辅助问题-30100-M-MCBXBbx1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001 j10M-2M-34M10
42、-M000 x4330211-100 x21-21-10-110-Mx7660403-31 j6M6M-304M+103M-4M00 x400001-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6 j300303/2-M-3/2-M+1/21x33/23/20103/4-3/41/40 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/4 j-3/2-9/2000-3/4-M+3/4-M-1/44131193/2例例6 6：用单纯形法求解线性规划问题：用单纯形法求解线性规划问题添加人工变量，化成典式添加人工变量，化
43、成典式2300-MCBXBbx1x2x3x4x50 x31222100-Mx514120-11 j14M2+M3+2M0-M03x26110.500-Mx52-10-1-11 j2M-18-1-M0-1.5-M-M0所有的检验数都不大于零，人工变量所有的检验数都不大于零，人工变量X5 仍留在仍留在基变量中且不为零，故原问题无可行解。基变量中且不为零，故原问题无可行解。672.2.两阶段法两阶段法第一阶段：寻找原问题的一个基可行解第一阶段：寻找原问题的一个基可行解 第二阶段：求原问题的最优解第二阶段：求原问题的最优解通过求解一个目标函数只含有人工变量的通过求解一个目标函数只含有人工变量的辅助问题
44、辅助问题实现实现。原问题原问题辅助问题辅助问题第一阶段解的情况第一阶段解的情况1.第一阶段人工变量取值为第一阶段人工变量取值为0 0，目标函数值也为，目标函数值也为0 0。此时得到原问题的第一个基可行解。结束第。此时得到原问题的第一个基可行解。结束第一阶段，去掉人工变量，进入第二阶段求原问题一阶段，去掉人工变量，进入第二阶段求原问题的最优解。的最优解。2.2.第一阶段最优解的基变量中含有人工变量，第一阶段最优解的基变量中含有人工变量，表明原问题无可行解。表明原问题无可行解。例例7 7：用两阶段法求解下列线性规划问题：用两阶段法求解下列线性规划问题化标准型化标准型第一阶段的线性规划问题为第一阶段
45、的线性规划问题为第一阶段：用单纯形法求解辅助问题第一阶段：用单纯形法求解辅助问题00000-1-1CBXBbx1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001 j10-2400-1000 x4330211-100 x21-21-10-110-1x7660403-31 j660403-400 x400001-1/21/2-1/20 x23011/30001/30 x11102/301/2-1/21/6 j000000-1-1得原问题的基可行解得原问题的基可行解X=(1,3,0,0,0)T。41311第二阶段：将上表中的人工变量去除，目标函数
46、第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数，从上表的最后一个单纯换成原问题的目标函数，从上表的最后一个单纯形表出发，继续计算。形表出发，继续计算。-30100CBXBbx1x2x3x4x50 x400001-1/20 x23011/300-3x11102/301/2 j300303/2 0 x25/2-1/210 0-1/41x33/23/20103/40 x400001-1/2 j-3/2-9/2000-3/4得原问题的最优解得原问题的最优解X=（0，5/2，3/2，0，0）T，最优值是最优值是3/2。93/2单单纯纯形形法法计计算算小小结结作业作业:用单纯形法求解下列线
47、性规划问题用单纯形法求解下列线性规划问题第六节第六节 线性规划应用举例线性规划应用举例例例1 1 混合配料问题混合配料问题 某糖果厂用原料某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲、加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中乙、丙。已知各种牌号糖果中A,B,C的含量，原料成本，的含量，原料成本，各种原料的每月限制用量，三种糖果的单位加工费如下各种原料的每月限制用量，三种糖果的单位加工费如下表所示问该厂每月生产这三种牌号的糖果各多少千克，表所示问该厂每月生产这三种牌号的糖果各多少千克，才能获利最大才能获利最大？甲甲乙乙丙丙原料成本原料成本（元（元/kg）每月限制用每月限制用量
48、（量（kg)A 60%30%2.002000B1.502500C20%50%60%1.001200加工费加工费(元元/kg)0.500.400.30售价售价(元元/kg)3.402.852.25解解:用用i=1，2，3代表代表A,B,C三种原料，用三种原料，用j=1,2,3分别代表甲，分别代表甲，乙，丙三种糖果，设乙，丙三种糖果，设xij为生产第为生产第j种糖果使用的第种糖果使用的第i种原料的质种原料的质量，则问题的数学模型为：量，则问题的数学模型为：用单纯形法解得：用单纯形法解得：例例2 配料问题配料问题 某饲养场用某饲养场用n种原料种原料B1,B2,Bn配置成含有配置成含有m种含营养成分种
49、含营养成分A1,A2,Am的混合饲料，每种原料含各种营养成分的数量的混合饲料，每种原料含各种营养成分的数量及原料单价、混合饲料中各种营养成分的最低含量如下表所及原料单价、混合饲料中各种营养成分的最低含量如下表所示。问应如何配料，才能既满足需要，又使混合饲料的总成示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？本最低？原料原料 含量含量成分成分 B1 Bn最最 低低需要量需要量 A1 Amb1bm原料单价原料单价c1 cn某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省
50、？问两种食物各食用多少，才能既满足需要、又使总费用最省？设：设：x1，x2分别表示分别表示 甲、甲、乙乙 两种食物的食用量。两种食物的食用量。2 1.5原料单价原料单价1.007.5010.0 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 甲甲 乙乙 含含 食物食物 量量成分成分例例3 3投资项目的组合问题投资项目的组合问题兴安公司有一笔兴安公司有一笔3030万元的资金，考虑今后万元的资金，考虑今后3 3年内用于下列年内用于下列项目的投资：项目的投资：项目一三年内的每年年初可投资，每年获利为投资项目一三年内的每年年初可投资，每年获利为投资额的额的2