第一章线性规划及单纯形法ppt课件.ppt

第一章 线性规划及单纯形法Linear Programming and Simplex Method,北京物资学院运筹学教学课件,北京物资学院信息学院 李珍萍2013年9月,第一节 线性规划问题的数学模型第二节 两变量线性规划问题的图解法第三节 线性规划问题的基本定理第四节 单纯形法第五节 单纯形法的进一步讨论第六节 线性规划应用案例分析,本章内容,第一节 线性规划问题的数学模型,线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。,线性规划研究的问题：,极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。,极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务。,一、引例： 生产安排问题 原料配比问题 运输问题二、线性规划问题的结构特征三、线性规划问题的数学模型 线性规划问题的一般形式 线性规划问题的标准形式 一般形式向标准形式的转化,本节内容安排,一、引例,例1 生产安排问题,某企业使用A、B、C三台机器生产甲、乙两种产品。已知未来两周内A、B、C三台机器的使用时间分别不得超过80，60，45小时，生产每单位产品所需要各台机器的加工时间及每单位产品的利润如下表所示，问企业如何安排未来两周的生产，才能使总利润达到最大？,可控因素：生产两种产品的数量，设分别为x1 , x2，目标是生产利润最大，设生产利润为z.,利润函数为：,限制条件：三台设备的使用时间不超过可利用机时设备A: 2x1+4x280设备B: 3x1+2x260设备C: 3x1 45,蕴涵约束：产量为非负 x10, x2 0,目标函数约束条件,设生产甲乙两种产品的数量分别为x1,x2单位，总利润为z.,例2 原料配比问题 某企业使用三种原料B1,B2,B3配置某种食品，要求食品中蛋白质、脂肪、糖、维生素的含量分别不低于15、20、25、30单位。以上三种原料的单价以及每单位原料所含各种成分的数量如下表所示，问应如何配置食品，才能使成本最低？,设x1,x2,x3分别表示原料B1,B2,B3的用量，z表示食品成本。该问题的数学模型为：,例3 运输问题,设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。,假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？,丙,17,26,38,43,15,37,51,51,乙,15,7,25,21,甲,D,C,B,A,销地产地,单位：元 / 吨,用 （i=1,2,3; j=1,2,3,4）分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。,则该问题的数学模型为,简化表达式,二、线性规划问题的结构特征：,（1）都有一组决策变量。（2）都有一组线性的约束条件，它们是线性等式或不等式。（3）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。,线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。所以称为线性规划 linear programming (LP),1. 线性规划问题的一般形式,一般形式的简化表达,三、线性规划问题的数学模型：,规范形式,极大化问题,极小化问题,2. 线性规划的标准形式,标准形式的简化表达,标准形式的矩阵表达,标准形式的向量表达,标准形式的特点：,(1).目标函数极大化,(2).约束条件全部是等式,(3).所有的变量都是非负的,(4).约束条件右端常数为非负的,3.一般形式向标准形式的转化：,(1) 目标函数极大化,(2) 不等式约束化等式约束,对于 形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。,例如：,(3) 自由变量化非负变量的差,自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量 ，可以引进两个非负变量 并设,(4) 约束条件右端的负常数化为正常数,对于右端常数为负数的约束，可以两端同时乘以-1。,取值小于等于0的变量，可以用一个非负变量的相反数表示。,例 将下列LP问题化成标准形式,s.t.,课堂练习：将下列LP问题化成标准形式,作业： P46页 习题 1-4题,第二节 两变量线性规划问题的图解法,一、几个概念二、两变量线性规划问题的图解法三、两变量线性规划问题解的性质,可行解：任何一组满足所有约束条件的决策变量值 称为LP问题的一个可行解。,最优解：使目标函数达到最大（小）值的可行解。最优值：最优解对应的目标函数值。,可行域：所有可行解的集合称为可行域。,一、几个概念：,二、两变量LP问题的图解法,图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。,1. 图解法的一般步骤：,（1） 建立直角坐标系，以 为横轴， 为纵轴。,（2） 将约束条件在直角坐标系中表示，并找出可行域。,（3）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。,（4）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。,例1 用图解法解下列线性规划问题,最优解 x*=(10,15)T, 最优值 z*=5010+6015=1400.,0,1 0 20 30 4 0,1 0 2 0 3 0,x2,x1,(1),(2),(10,15),可行域有界,有唯一最优解,z =0,z =600,(3),例2,无穷多最优解,x1,x2,例3、,无有限最优解,x1,x2,可行域无界, 有唯一最优解,x1,x2,例4、,x1,x2,可行域为空, 无可行解,例5、,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4 2),课堂练习:用图解法求解,可行域是空集。可行域存在，则一定是一个凸多边形.,无有限最优解（可行域一定无界）。最优解存在且唯一，则一定在顶点上达到。最优解存在且不唯一，一定存在一个顶点是最优解。,2. 图解法求解两变量LP问题时可能出现的情况：,三. 两变量线性规划问题解的性质,1. 两变量线性规划问题的可行域是若干个半平面的交集，它是一个有界或无界的凸多边形，并且有有限个顶点。,2. 对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。,第三节 线性规划问题的基本定理,一、可行区域的几何结构二、基可行解及线性规划的基本定理,一、可行区域的几何结构,1. 基本假设2. 凸集及其性质3. 可行域的凸性4. 问题,1. 基本假设,凸集：设S是n维欧氏空间的一个点集，若任意两点X(1)S, X(2)S 的连线上的一切点 X(1)+ (1- )X(2)S, (0 1); 则称S为一个凸集。,性质：任意多个凸集的交集仍然是凸集。,2. 凸集及性质,顶点：设S是凸集，XS；若对任何X(1)S和 X(2)S， X(1) X(2)，以及任何0 1，都有 X X(1)+ (1- )X(2) 则称X为凸集S的一个顶点（或极点）。,根据顶点的定义，长方形的四个角点就是长方形区域的全部顶点，而圆周上的点则是圆形区域的全部顶点。,在平面区域中，每个顶点至少是两条直线的交点。,3. 可行域的凸性,定理1：若线性规划问题的可行域D=x Rn|AX=b,X0非空，则必为凸集。,可以直接按照凸集的定义证明，也可以按照以下思路证明。,可行域凸性的证明思路,超平面：给定b R1及非零向量a Rn，称集合 H=x Rn|aTX=b 是Rn中的一个超平面。,超平面是二维空间中的直线、三维空间中的平面在高维空间中的推广。超平面是凸集。,由超平面产生的两个闭的半空间H+=x Rn|aTXbH-=x Rn|aTXb都是凸集。,可行域是有限个超平面的交，因此可行域是凸集。,4. 问题,可行域顶点的个数是否有限？最优解是否一定在可行域顶点上达到？如何找到顶点？如何从一个顶点转移到另一个顶点？,二、基可行解及线性规划的基本定理,基可行解的定义线性规划的基本定理问题,1. 基可行解的定义,考虑标准形式的线性规划问题,基：A是约束方程组的系数矩阵(设nm)，其秩为m，B是A中的一个m阶满秩子方阵，称B是线性规划问题的一个基。B中每一个列向量称为一个基向量，与基向量对应的变量称为基变量。其余变量称为非基变量。,不失一般性，设,则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为线性规划问题的基解。,显然，基解中取非零值的变量个数不超过m，基解的总数不超过Cnm个。,基可行解：满足非负约束的基解称为基可行解。可行基：对应于基可行解的基。,基可行解,用矩阵形式表示的基解,考虑标准形式的线性规划问题：,例如LP问题,是它的两个基，对应的基解分别为,可见X1是基可行解，故B1是可行基。而X2不是基可行解，故B2不是可行基。,根据以上定义,2. 线性规划的基本定理,引理：LP问题的可行解X是基可行解的充要条件是它的正分量所对应的A中的列向量线性无关。,定理3：线性规划问题的基可行解对应可行域的顶点。（X是基可行解X是可行域的顶点）（基可行解个数有限）,定理4：若线性规划问题有有限最优值，则一定存在一个基可行解是最优解。,定理2：若线性规划问题有非零可行解，则其必有基可行解。,3. 问题,如何得到第一个基可行解？如何判别一个基可行解是否最优？如果当前的基可行解不是最优，如何从一个基可行解转化到另一个基可行解？,一、单纯形法的求解思路二、单纯形法的基本步骤及单纯形表,第四节 单纯形法,确定初始基可行解最优性检验基可行解的改进,一、单纯形法的求解思路,当约束条件全部是“”型不等式且右端常数非负（化成标准形后，约束条件系数矩阵含有单位子矩阵），可按照下列方法找到第一个基可行解。,加上松弛变量，化为标准形式：,1. 确定初始基可行解,其约束条件系数矩阵为,令其中的单位矩阵作为基，可得初始基可行解,当线性规划问题的约束条件中含有“=”或“ ”型约束时，化成标准形式后，约束条件系数矩阵中不含单位子矩阵，这时需要通过添加人工变量的方法寻找第一个可行基。（本节第5节介绍）,对于线性规划问题的标准形式,假设可行域非空， A为一 mn实矩阵，r(A)=mn 。,2 最优性检验,假设B是一个可行基，不妨设B是由A的前m个列向量组成的，即A=(B,N)，则线性规划问题的等式约束AX=b 可以化成：,两端同时左乘B-1，得,令=B-1b ,则上式可以写成,上式所对应的约束方程称为对应于基B 的典式。,有了典式，就很容易写出线性规划问题的基解,其中,如果0 ，则典式对应的基解X0是基可行解，从而B是可行基。当0时，该基可行解为非退化的基可行解。,问题：如何判断一个基可行解是否为最优解呢？,目标函数 Z=CX 可以化成,将约束方程组化成典式以后，对目标函数做相应变换,由于CB-CBB-1B=0,令,则,其中z0是基可行解对应的目标函数值，是将目标函数中基变量消掉以后非基变量的系数。该系数是判断基可行解是否最优的依据，称为检验数。,当所有检验数j0时，当前的基可行解为最优解；如果某个非基变量的检验数j 0，而ij 0，则原问题无界；如果某个非基变量的检验数j 0，且至少存在一个i，使得ij 0，则可以找到一个新的基可行解X1，使得CX1CX。,3. 基可行解的改进,1) 基的修改：进基变量、出基变量的选取准则。2) 迭代：得到新基对应的典式。,基的修改准则：新基与原有基有m-1 个相同的基变量，只有一个基变量不同。,进基变量：从非基变量变为基变量的变量。,出基变量：由基变量变为非基变量的变量。,1) 进基变量的选取原则：,最优性原则：若k 0,则与k 相对应的变量xk 是非基变量，当xk 变为基变量时，它的值由0变为正数，比如说xk= 0，其余的非基变量仍取值为零。由(3.4)式知，对应新解的目标函数值为z=z0+ K z0，显然越大目标函数值越大。,可行性原则（最小比值原则）： 的取值应保证新解仍然是基可行解。,2) 出基变量的选取原则,进基变量和出基变量的选取准则,0,1 0 20 30 4 0,1 0 2 0 3 0,x2,(10,15),例10:求解下列线性规划问题,x1,添加松弛变量，化成标准形式（典式）,约束条件系数矩阵含单位矩阵；目标函数中基变量系数为0。,第一个基可行解X0=(0,0,80,60,45)T目标函数值为0对应可行域顶点O(0，0).,0,1 0 20 30 4 0,1 0 2 0 3 0,x2,(10,15),x1,A,B,C,D,让x2进基，不妨假设x2 ， x1仍为非基变量。目标函数值为 60 。从最优性角度看，越大越好,为了保持解的可行性，原先的基变量取值必须满足,综上得到,x3出基，新的基变量为x2 ，x4，x5 对应的典式可以由方程组的初等变换得到,新的基可行解：X1=(0,20,0,20,45)T, 对应的目标函数值为1200。对应可行域A点。,取x1为进基变量，,x4为出基变量。,新的基可行解：X1=(10,15,0,0,15)T, 对应的目标函数值为1400。对应可行域B点。,检验数均非正，所以已得到最优解。,当xk= 0成为基变量以后，其余非基变量仍然取值为0。设新基对应的基可行解为X1=(x11, xn1)T,则X1应满足约束条件，即,由于xi1必须是非负的，即,如果ik0，显然只要0，就有xi1 = i- ik 0 ，对于ik0，就要求,所以应满足,假定至少有一个ai k0，i=1,2,m，并且所有的i 0,则0 0，从最优性原则出发，让 取值尽量大，即取,然后把xt从原有的基中取出来，得到一组新的基可行解,X1 使目标函数取值 z1=z0+ k 0 z0.,迭代（新的基可行解对应的典式的确定）,利用线性方程组的等价变换将约束条件和目标函数化成新基对应的典式，从而求出新的基可行解及相应的检验数,二、单纯形法基本步骤及单纯形表,Step 1 将线性规划问题化成标准形式下的典式,求出各个非基变量的检验数.Step 2 判断所有非基变量的检验数是否非正,若是,则结束;否则转step 3.Step 3 选取一个检验数大于零的非基变量为进基变量;Step 4 若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束;否则,按最小比值原则确定出基变量;Step 5 利用方程组的初等变换得到新的基对应的典式，及的基可行解和检验数,转step 2.,单纯形表,= - cn+i bi j = cj - cn+i,例11 用单纯形表求解例1中的线性规划问题,解：先化成标准形式,最优解X*=(10,15,0,0,15)T，最优值1400。,例2：利用单纯形法求下列线性规划问题,将该问题化成标准形式（也是典式）,基变量是：x3 ，x4 ，x5 ，非基变量是x1 x2,填入单纯形表求解,最优解X*=(2,3,2,0,0)T，最优值19。,注意：,1. 在选取进基变量时，若有几个非基变量的检验数都是正数，则可以任意选取一个正检验数对应的非基变量作为进基变量，一般选取最大正检验数对应的非基变量。但实际情况表明这种策略不一定最好。,2. 在选取出基变量时，若有几个比值同时达到最小，可以任意选择一个，但在新的基可行解中这些对应分量均为零。从而新的基可行解是一个退化的基可行解。假若问题是非退化的，则不会出现这种情况。,例12：用单纯形法求解线性规划问题（多解问题）,解: 化成标准形式,填入单纯形表求解,最优解X1=(1,5,0,8,0)T，最优值6。,最优解X2=(5,1,8,0,0)T，最优值6。,实际上X1与X2的连线上的任意点都是最优解.,例13：用单纯形法求解线性规划问题（无有限最优解的情况）,解：化成标准形（典式）,X2的检验数为正，但约束条件中x2的系数全为负，因此该问题无有限最优解。,作业P48 7 （1） 8 （1）（3）,第五节 单纯形法的进一步讨论,在给定的LP问题的标准形式中，如果约束条件系数矩阵A中含有一个m阶单位矩阵，并且b0，则我们已经找到了一个明显的基可行解，并且约束方程组已经是典式，这时可以直接填入单纯形表中进行迭代。但是实际问题往往并非如此，因此我们需要寻找第一个基可行解，通常使用两种常用的方法求解第一个基可行解。,一.大M法二.两阶段法,考虑标准形式的线性规划问题,一. 大M法,原问题,辅助问题,人工变量,为了得到原问题的一个基可行解，只要将辅助问题的基可行解中的人工变量全部变为非基变量即可。为此，将人工变量加到辅助问题的目标函数中并赋予系数-M。（M可以看成惩罚系数）,添加M以后，直接求解辅助问题，可能有两种情况：,1.辅助问题的最优解中人工变量全部是非基变量，此时去掉人工变量直接得到原问题的最优解。,2.在辅助问题的最优解中某些人工变量是基变量且取值非零，此时原问题无可行解。,例14：用大M法求解下列线性规划问题,添加人工变量得辅助问题,例15：用单纯形法求解线性规划问题,添加人工变量，化成典式,所有的检验数都不大于零，人工变量X5 仍留在基变量中且不为零，故原问题无可行解。,二. 两阶段法,第一阶段：寻找原问题的一个基可行解,第二阶段：求原问题的最优解,通过求解一个目标函数只含有人工变量的辅助问题实现。,原问题,辅助问题,第一阶段解的情况,1. 第一阶段人工变量取值为0，目标函数值也为0。此时得到原问题的第一个基可行解。结束第一阶段，去掉人工变量，进入第二阶段求原问题的最优解。,2. 第一阶段最优解的基变量中含有人工变量，表明原问题无可行解。,例16：用两阶段法求解下列线性规划问题,第一阶段的线性规划问题为,第一阶段：用单纯形法求解辅助问题,得原问题的基可行解X=(1,3,0,0,0)T。,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数，从上表的最后一个单纯形表出发，继续计算。,得原问题的最优解X=（0，5/2，3/2，0，0）T，最优值是3/2。,单纯形法计算小结,作业: P48 9（2） 10,第六节 线性规划应用案例分析,例17 混合配料问题某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A,B,C的含量，原料成本，各种原料的每月限制用量，三种糖果的单位加工费如下表所示问该厂每月生产这三种牌号的糖果各多少千克，才能获利最大？,解:用i=1，2，3代表A,B,C三种原料，用j=1,2,3分别代表甲，乙，丙三种糖果，设xij为生产第j种糖果使用的第i种原料的质量，则问题的数学模型为：,用单纯形法解得：,例18投资项目的组合问题兴安公司有一笔30万元的资金，考虑今后3年内用于下列项目的投资：项目一三年内的每年年初可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；项目二只允许第一年初投资，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元；项目三允许于第二年初投资，于第三年末收回，本利合计为投资额的160%，但限额投资为20万元；项目四允许于第三年初投资，年末收回，可获利40%，但限额为10万元。试为该公司确定一个使第三年末本利和为最大的投资组合方案。,解：用xij 表示第i 年初投资到第j 项目的资金数，则可得下列线性规划模型,求解得,例19 下料问题工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4米，现考虑应如何下料，可使所用原料最省？,解：设x1 ,x2 ,x3 ,x4 ,x5 ,x6 ,x7 ,x8 分别表示按上述8种方案下料的原料根数。则：,例20 人员安排问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表,每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量。,为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,解：设第 i 天开始工作的人员数为xi, i=1,2,7.,例21 生产与库存的优化安排问题,yi jdi j (i=1,5;j=1,6),作业：P 4912，14，15,