《管理学运筹学》PPT课件.ppt

1、第一章 线性规划 linear Programming,第一节 线性规划问题及其数学模型 第二节 可行区域与基本可行解 第三节 单纯形方法,第一节 线性规划问题及其数学模型,线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。,线性规划研究的问题：,极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。,极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务。,一、实例： 生产安排问题 运输问题 二、线性规划问题的结构特征 线性规划问题的特征 线性规划问题的一般形式 线性规划问题的标准形式 一般形

2、式向标准形式的转化,本节内容安排,一、实例,例1 生产安排问题,某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？,可控因素：生产两种产品的数量，设分别为x1 , x2，目标是生产利润最大，设生产利润为z.,利润函数为：,限制条件：三台设备的使用时间不超过设备能力的限制 设备A: 3x1+2x265 设备B: 2x1+ x2 40 设备C: 3x2 75,蕴涵约束：产量为非负 x10, x2 0,目标函数 约束条件,生产两种产品的数量，设分别为为x

3、1,x2，总利润为z.,在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调运方案才能使总运输费用最少？这类问题称为运输问题,例2 运输问题,设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。,假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？,丙,问题分析： 可控因素：从三个产地到四个销地的运输量； 目标： 总运费最省； 限制条件：各个产地的产量和销

4、地的需求量的限制 。,用 （i=1,2,3; j=1,2,3,4）分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。,则问题归结为寻求一组xij的值，使函数,达到最小。并且下面的每一个约束条件都被满足,简化表达式,例 某工厂制造A,B两种产品，它们的原材料单位消耗，单位利润以及资源现有量如下表,问如何组织生产可使工厂获得最大利润？,如何建立数学模型？,1.选择决策变量：设A，B两种产品各生产 个单位；,2.建立目标函数：利润函数是 求它的最大值，即,3.生产的产量受到限制：,4.决策变量必须有非负限制：,综合上述各点，该问题的数学模型如下,目标函数,约束条件,非负限制,注意：目标函

5、数和约束条件中变量的次数都是一次的，这样的模型称为线性规划数学模型。,二、线性规划问题的结构特征：,1. 线性规划问题的特征； （1）都有一组决策变量。 （2）都有一组线性的约束条件，它们是线性等式或不等式。 （3）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。,线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。,2. 线性规划问题的一般形式,一般形式的简化表达,规范形式,极小化问题,极大化问题,3. 线性规划的标准形式,标准形式的矩阵表达,标准形式的特点：,(1).目标函数极大化,(2).约束条件全部是等式,(

6、3).所有的变量都是非负的,(4).约束条件右端常数为非负的,4. 一般形式向标准形式的转化：,(1) 目标函数极大化,(2) 不等式约束化等式约束,对于 形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。,例如：,(3) 自由变量化非负变量的差,自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量 ，可以引进两个非负变量 并设,(4) 约束条件右端的负常数化为非负常数,对于右端常数为负数的约束，可以两端同时乘以-1。,例 将下列LP问题化成标准形式,s.t.,s.t.,1、先化变量和目标函数 2、调整约束条件 3、调整目标函

7、数,作业：,1.某车间生产甲、乙两种产品，每件甲产品的利润是2元，乙产品的利润是4元。制造每件甲产品需要劳动力3个，而制造每件乙产品需要劳动力8个。车间现有劳动力总数是32个。制造每件甲产品需要原材料1000克，而乙产品需要原材料600克，车间共有原材料5500克可供利用。问应该安排甲、乙两种产品各生产多少件才能获得最大总利润？（列出数学模型并化成标准形式）,第二节 单纯形法原理,一、几个概念 二、两变量LP问题的图解法 三、可行区域的几何结构 四、基可行解及线性规划的基本定理,可行解：任何一组满足所有约束条件的决策变量值 称为LP问题的一个可行解。,最优解：使目标函数达到最大（小）值的可行解

8、。 最优值：最优解对应的目标函数值。,可行域：所有可行解的集合称为可行域。,一、几个概念：,二、两变量LP问题的图解法,图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。,1. 图解法的一般步骤：,（1） 建立直角坐标系，以 为横轴， 为纵轴。,（2） 将约束条件在直角坐标系中表示，并找出可行域。,（3）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。,（4）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。,例1 用图解法解下列线性规划问题,最优解 x*=(10,15)T, 最优值 z*=6010

9、+5015=1350.,例2 用图解法解线性规划问题,最优解 x*=(1,4)T, 最优值 z*=-1+4=3.,例3 用图解法求解线性规划问题,最优解不唯一（A1A2连线上的所有点都是最优解），最优值 z*=-4.,例4 用图解法解线性规划问题,可行域无界， 原问题最优解无界。,例5 用图解法解线性规划问题,无解，或无可行解,用图解法求解下面的LP问题,目标函数等值线,此点为LP的最优解,目标函数等值线,可行解集,计算出这个最优解:,上述作法称为LP的图解法.,本问题有唯一最优解.,例2 用图解法解下面的线性规划,目标函数等值线,目标函数等值线,计算出LP的最优解及目标函数最优值:,除A,B

10、两个最优解外,AB线段上的所有点都是LP的最优解.本问题有无穷多最优解.,用图解法解下面的线性规划,无可行解,本题无可行解,更无最优解,可行域是空集。 可行域存在，则一定是一个凸多边形。,无界解（可行域一定无界）。 最优解存在且唯一，则一定在顶点上达到。 最优解存在且不唯一，一定存在一个顶点是最优解 无解,2. 图解法求解两变量LP问题时可能出现的情况：,三、可行区域的几何结构,1. 凸集及其性质 2. 可行域的凸性,凸集：若集合S中任意两点X(1)S, X(2)S的连线上的所有点也都是集合S中的点，则称S为一个凸集。 X(1)S, X(2)S的连线可表示为： X(1)+ (1- )X(2)S

11、, (0 1);,性质：任意多个凸集的交集仍然是凸集。,1. 凸集及性质,顶点：设S是凸集，XS；若对任何X(1)S和 X(2)S， X(1) X(2)，以及任何0 1，都有 X X(1)+ (1- )X(2) 则称X为凸集S的一个顶点（或极点）。,凸集,凸集,不是凸集,极点,根据顶点的定义，长方形的四个角点就是长方形区域的全部顶点，而圆周上的点则是圆形区域的全部顶点。,2. 可行域的凸性,定理1：若线性规划问题的可行域 D=x Rn|AX=b,X0非空，则必为凸集。,可行域凸性的证明思路,设X1,X2为可行域R内任意两点，则X1 R,X2 R,将X1， X2带入约束条件有AX1=b,AX2=

12、b,X1和X2连线上的任意一点可表示为： X=aX1+(1-a)X2, (0a1) 则AX= AaX1+(1-a)X2=aAX1+AX2-aAX2=ab+b-ab=b, 所以XR.由于集合中任意两点连线上的点均在集合内，所以R为凸集,四、基可行解及线性规划的基本定理,基可行解的定义 线性规划的基本定理 问题,1. 基可行解的定义,考虑标准形式的线性规划问题,基：A是约束方程组的系数矩阵(设nm)，其秩为m，B是A中的一个m阶满秩子方阵，称B是线性规划问题的一个基。 B中每一个列向量称为一个基向量，与基向量对应的变量称为基变量。其余变量称为非基变量。,不失一般性，设,则Pj（j=1，2m）是基向

13、量，xj（ j=1，2m ）是基变量。 xj（ j=m+1，n ）是非基变量。,基解：在约束方程组x中令所有的非基变量m+1=x m+2=x n=0，得,此方程组有唯一解XB=(x1，x2，xm)T，将这个解加上非基变量取0的值有X=(x1，x2，xm,0,0)T,称X为线性规划问题的基解。,显然，基解中取非零值的变量个数不超过m，基解的总数不超过Cnm个。,基可行解：满足非负约束的基解称为基可行解。 可行基：对应于基可行解的基。,基可行解,用矩阵形式表示的基解,考虑标准形式的线性规划问题：,是它的两个基，对应的基解分别为,可见X1是基可行解，B1是可行基。而X2不是基可行解。,根据以上定义,

14、可行解集,基础可行解,最优解,基础最优解,2. 线性规划的基本定理,定理2：LP问题的可行解X是基可行解的充要条件是它的正分量所对应的A中的列向量线性无关。,定理3：线性规划问题的基可行解对应可行域的顶点。（X是基可行解X是可行域的顶点）（基可行解个数有限）,定理4：一个LP问题，若有最优解，则一定存在一个基可行解是最优解。,例 设线性规划为,则下述解中为基可行解的是 A.(2,0,4,0);B.(6,0,3,3);C.(3,2,3,2);D.(0,6,0,0),3. 问题,如何得到第一个基可行解？ 如何判别一个基可行解是否最优？ 如果当前的基可行解不是最优，如何从一个基可行解转化到另一个基可

15、行解？,第三节 单纯形方法,单纯形方法（Simplex Method）是G.B.Dantzing 在1947年提出的。,一、 单纯形方法 二、 第一个基可行解的求法,一、单纯形方法,典式 最优性检验和解的判别 基可行解的改进 单纯形方法的基本步骤 单纯形表,考虑标准形式的LP问题,假设可行域非空， A为一mn实矩阵，r(A)=mn 。,1. 典式,假设B是一个可行基，不妨设B是由A的前m个列向量组成的，即A=(B,N)，则线性规划问题的等式约束AX=b 可以化成：,目标函数 Z=CX 可以化成,线性规划问题的典式（典则形式）,典式的特点：（1）约束条件中含有一个单位矩阵，（2）目标函数中不含基

16、变量。,有了典式，就很容易写出线性规划问题的基解,其中,如果基B是可行基，则 即X0是基可行解，对应的目标函数值为z0 。,问题：如何判断一个基可行解是否为最优解呢？,在典式中，目标函数中非基变量的系数称为检验数，检验数是用来判断相应基可行解是否最优的标志。,3. 基可行解的改进,1) 基的修改：进基变量、出基变量的选取准则。 2) 迭代：得到新基对应的典式。,基的修改准则：新基与原有基有m-1 个相同的基变量，只有一个基变量不同。,进基变量：从非基变量变为基变量的变量。,出基变量：由基变量变为非基变量的变量。,1) 进基变量的选取原则：,最优性原则：若K0,则与K相对应的变量xk是非基变量，

17、当xk变为基变量时，它的值由0变为正数，比如说xk=0，其余的非基变量仍取值为零。由(3.4)式知，对应新解的目标函数值为z=z0+ Kz0，显然越大目标函数值越大。,可行性原则（最小比值原则）： 的取值应保证新解仍然是基可行解。,2) 出基变量的选取原则,进基变量和出基变量的选取准则,Max z=z0+ m+1xm+1+ kxk+ nxn s.t. x1 +a1m+1xm+1+ a1kxk + a1nxn= 1 x2 +a2m+1xm+1+ a2kxk +a2nxn= 2 . xm +amm+1xm+1+ +amkxk + amnxn= m xj0 j=1,2,n,当xk=0成为基变量以后，

18、其余非基变量仍然取值为0。设新基对应的基可行解为X1=(x11, xn1)T,则X1应满足约束条件，即,x11 + a1k = 1 x21 + a2k = 2 . xm1 +amk = m xj10 j=1,2,n,由于xi1必须是非负的，即,如果aik0，显然只要0，就有xi1 = i- aik 0 ，对于aik0，就要求,所以应满足,2. 最优性检验和解的判别,对于j 0,而aij0,则可以无限大使得目标函数值的增量（ j ）无限大,注意：,1.在选取进基变量时，若有几个非基变量的检验数都是正数，则可以任意选取一个正检验数对应的非基变量作为进基变量，一般选取最大正检验数对应的非基变量。但实

19、际情况表明这种策略不一定最好。(当 j最大时对应的xj 不一定最大，我们要求的是 j 0最大),2.在选取出基变量时，若有几个比值同时达到最小，可以任意选择一个，但在新的基本可行解中这些对应分量均为零。从而新的基本可行解是一个退化的基本可行解。假若问题是非退化的，则不会出现这种情况。,迭代（新的基可行解对应的典式的确定）,利用线性方程组的等价变换将约束条件和目标函数化成新基对应的典式，从而求出新的基可行解及相应的检验数,4. 单纯形方法的基本步骤,Step 1 将线性规划问题化成典式,求出各个非基变量的检验数. Step 2 判断所有非基变量的检验数是否非正,若是,则结束;否则转step 3.

20、 Step 3 选取一个检验数大于零的非基变量为进基变量; Step 4 若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束;否则,按最小比值原则确定出基变量; Step 5 进行迭代(用方程组的初等变换法确定新的基对应的典式)及检验数),转step 2.,例1：利用单纯形法求下列线性规划问题,将该问题化成标准形式（也是典式）,基变量是：x3 ，x4 ，x5 ，非基变量是x1 x2,求出第一个基可行解X0=(0,0,65,40,75)T，非基变量的检验数均为正数，所以X0不是最优解。,确定进基变量 x2，按照最小比值原则确定出基变量x5，最小比值是0=25. 求出新基对应的典式,X1

21、=(0,25,15,15,0)T,目标函数值为62500。,确定进基变量 x1，按照最小比值原则确定出基变量x3，最小比值是0=5. 求出新基对应的典式,X2=(5,25,0, 5,0)T,目标函数值为70000。,当前的解是最优解,5. 单纯形表,= - cn+i bi j = cj - cn+i,用单纯形表求解例1,例2：利用单纯形法求下列线性规划问题,将该问题化成标准形式（也是典式）,基变量是：x3 ，x4 ，x5 ，非基变量是x1 x2,填入单纯形表求解,最优解X*=(2,3,2,0,0)T，最优值19。,例3：用单纯形法求解线性规划问题（多解问题）,Max z = x1 + x2 s

22、.t. -x1 + x2 4 x1 - x2 4 x1+ x2 6 x1 , x2 0,Max z = x1 + x2 s.t. -x1 + x2 + x3 = 4 x1 - x2 + x4 = 4 x1+ x2 + x5 = 6 x1 , x2 , x3 , x4 , x5 0,解: 化成标准形式,填入单纯形表求解,最优解X1=(1,5,0,8,0)T，最优值6。,最优解X2=(5,1,8,0,0)T，最优值6。,实际上X1与X2的连线上的任意点都是最优解.,例4：用单纯形法求解线性规划问题（无有限最优解的情况）,Max z = 2 x1 + x2 s.t. - x1 + x2 + x3 =

23、 5 2 x1-5 x2 + x4 = 10 x1 , x2 , x3 , x4 0,X2的检验数为正，但约束条件中x2的系数全为负，因此该问题无有限最优解。,二、 第一个基可行解的求法,在给定的LP问题的标准形式中，如果约束条件系数矩阵A中含有一个m阶单位矩阵，并且b0，则我们已经找到了一个明显的基可行解，并且约束方程组已经是典式，这时可以直接填入单纯形表中进行迭代。但是实际问题往往并非如此，因此我们需要寻找第一个基可行解，通常使用两种常用的方法求解第一个基可行解。,1.大M法 2.两阶段法,Max z =c1x1 +c2x2 +cnxn s.t. a11x1+a12x2 +a1nxn = b1 a21x1+a22x2 + a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 0,考虑标准形式的线性规划问题,1. 大M法,原问题,辅助问题,人工变量,为了得到原问题的一个基可行解，只要将辅助问题的基可行解中的人工变量全部变为非基变量即可。为此，将人工变量加到辅助问题的目标函数中并赋予系数-M。（M