《运筹学教学资料》运筹学第1章1-2节.ppt

Chapter1 线性规划(Linear Programming),线性规划问题及其模型线性规划问题几何意义单纯形法单纯形法计算步骤单纯形法进一步讨论应用举例掌握Excel软件求解线性规划,本章主要内容：,线性规划是运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。由前苏联经济学家康托洛维奇于1939年提出，而此人也因此获得1960年的诺贝尔经济学奖。,1947年，G.B.Dantzig（丹捷格）提出求线性规划的单纯形法，理论上趋向成熟，实际上的应用也越来越广泛。,因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。,线性规划所研究的问题主要包括两个方面：,一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；,二是如何在现有资源条件下进行组织和安排，以产生最大收益。,第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,1.1 问题的提出在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。,我们先通过几个实际问题来认识什么是线性规划。,1.1 问题的提出,【例1】某企业生产 A1,A2,A3三种产品，这些产品分别需要甲、乙两种原料。生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表1.1所示。（生产计划问题）,利润最大化问题,试问：该企业怎样安排生产才会使每天的利润最大？,表1.1 企业生产数据表,1.1 问题的提出,解 设该企业每天生产产品 的数量分别为（单位：吨），则总利润的表达式为,我们希望在现有资源条件下总利润最大.现有资源的限制为,（原料甲的限制）,（原料乙的限制）,此外，由于未知数（我们称之为决策变量）是计划产量，应有为非负的限制，即,1.1 问题的提出,由此得到问题的数学模型为,其中s.t.为英文“subject to”的缩写，表示决策变量xj(j=1,2,3)受它后面的条件约束.,1.1 问题的提出,决策变量：需决策的量，即待求的未知数；目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。,线性规划模型的三要素,1.1 问题的提出,练习1 某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A 4吨，原材料B12吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。,1.1 问题的提出,成本最小化问题,【例2】某钢铁厂熔炼一种新型不锈钢，需要4种合金T1T2T3T4为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表1.2所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料T1T2T3T4各多少吨，能够使成本最小？,1.1 问题的提出,表1.2 生产某种不锈钢的相关数据表,1.1 问题的提出,解:设选用原料T1、T2、T3、T4 的量分别为x1、x2、x3、x4（单位：吨）.由于追求的目标是成本最小，故有最小成本 表达式：,又因该不锈钢所需铬、锰和镍的最低质量分数是由4种合金T1、T2、T3、T4 对相应元素的质量分数构成，注意到要熔炼该种不锈钢100吨，于是得到铬、锰和镍的质量分数满足的不等式依次为,以下分析约束条件。由于假设熔炼时质量没有损耗，熔炼该种不锈钢100吨，它由原料T1、T2、T3、T4 熔炼而成，故有等式约束,1.1 问题的提出,此外，各种合金的加入量以整吨为单位，即有限制x1、x2、x3、x40 且为整数。综合上述讨论，我们得到该问题的数学模型为,这类问题也称为混合配料问题。,1.1 问题的提出,运输问题【例3】某建材公司有三个水泥厂，四个销地，其产量、销量、运费见表1.3.,如何制定调运方案，使总的运费或总货运量最小？,1.1 问题的提出,解 设由水泥厂Ai 运到销地Bj 的货运量 为xij(i=1,2,3;j=1,2,3,4)，则得到问题的数学模型为,1.1 问题的提出,【例4】设某单位现有 n 个人员A1,A2,An 来完成n项工作B1,B2,Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai 做工作Bj 的效率是cij。问应如何分配，才使总效率最好。,在本例中,决策变量：x ij 表示分配人员Ai 完成工作 Bj,x ij=1 表示分配 Ai 干工作 Bj xij=0 表示不分配 Ai干工作 Bj,人员分配问题,1.1 问题的提出,对工作Bj；要求一人员去完成：,对人员Ai；要求承担一项工作：,派工方案的总效益,按问题要求，每人要做一项工作，每项工作需一人去做。建立该问题的数学模型的过程：,1.1 问题的提出,分配问题的数学模型,1.1 问题的提出,从前面对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第1步 理解要解决的问题；第2步 定义决策变量；第3步 确定约束条件；第4步 列出目标函数。,1.1 问题的提出,共同表现：线性规划的数学模型,1.1 问题的提出,1.2 线性规划问题的图解法,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。,图解法的步骤可概括为：在平面上建立直角坐标系；图示约束条件，找出可行域；图示目标函数和寻找最优解。,1.2 线性规划问题的图解法,先做约束的图形 先做非负约束的图形；再做资源约束的图形。以练习1为例，其约束为,可行域Q,1.2 线性规划问题的图解法,函数任给二不同的值，便可做出相应的二直线，用虚线表示。例1中，其目标为z=3x1+5x2，分别令z=20和z=36，做出相应的二直线，便可看出增大的方向。,再做目标图形,3x1+5x2=z=36,3x1+5x2=z=20,3x1+5x2=z=0,1.2 线性规划问题的图解法,求出最优解将目标直线向使目标z优化的方向移动，直至可行域的边界为止，这时其与可行域的“切”点X*即最优解。,练习1中，X*是可行域的一个角点。,X*,1.2 线性规划问题的图解法,注：本问题只有唯一最优解,让直线束 3x1+5x2=z 沿正法线在可行域Q移动，通过点（2，6）的直线,1.2 线性规划问题的图解法,求解A的坐标，从而得到最优解，最大值,练习1 用图解法求解线性规划问题,解：,-x1+x2=0,x1+x2=5,6x1+2x2=21,3x1+x2=z=0,3x1+x2=z=6,3x1+x2=z=21/2,A(11/4,9/4),B(21/6,0),1.2 线性规划问题的图解法,练习2,注：本问题有无穷多个最优解。,解：,该问题的可行域是一个无界的凸多边形。,1.2 线性规划问题的图解法,练习3,让直线束-2x1+x2=z 沿其负法线方向移动，可以无限制地移动下去，一直与相交，所以其最小值为-；即函数z=-2x1+x2 在 上无下界。,注：本问题有可行解，但无最优解，称为无界解.,解,x1-x2=-1,x1+x2=-1,注：本问题无可行解，更无最优解。,该问题的可行域是空的，即无可行解。,1.2 线性规划问题的图解法,练习4,作图的关键有三点(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线平行移动方向,1.2 线性规划问题的图解法,思考线性规划的可行域是一个什么形状？多边形，而且是“凸”形的多边形。最优解在什么位置获得？在边界，而且是在某个顶点获得。线性规划的可行域是一个什么形状？,1.2 线性规划问题的图解法,凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。,由图解法得到线性规划解的一些特性,凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。,（1）线性规划的约束集（即可行域）是一个凸边形（多面体）。,1.2 线性规划问题的图解法,（2）线性规划的最优解（若存在的话）必能在可行域的顶点获得,因为，由图解法可知，只有当目标直线平移到边界时，才能使目标z 达到最大限度的优化。,问题：本性质有何重要意义？,1.2 线性规划问题的图解法,（3）线性规划解的几种情形1）唯一解 2）多重最优解注：出现3）、4）情况时，建模有问题3）无可行解 4）无有限最优解,这也是一般线性规划问题的类似结论。,1.2 线性规划问题的图解法,线性规划问题的一般数学模型,1.3 线性规划的标准型,1.3 线性规划的标准型,方程组（1.2）中不含有多余的方程（一般mn）,bi0(i=1,m),解决一般线性规划问题的第一步：标准形的转换,标准型的特征：Max型、等式约束、非负约束,1.3 线性规划的标准型,只需令,再求 的最大值,线性规划问题的一般型如何化为标准型？,（1）如果目标函数求极小，则,1.3 线性规划的标准型,（2）若约束关系是不等式，引入松弛变量(slack variables),把不等式改成等式。,（3）若变量不满足“0”，决策变量的标准化,（4）当bi0，约束常数的标准化,约束方程两边同乘-1,将下列线性规划化成标准形。,解：先引入三个松弛变量x3、x4、x5在每个约束不等式中分别加上松弛变量使不等式化为等式，,3x1+2x2 18,3x1+2x2+x3=18,x1 4,x1+x4=4,2x2 12,2x2+x5=12,1.3 线性规划的标准型,【例5】,得到标准形：,注：加入的松弛变量x3、x4、x5可以看成没有被利用的资源，当然不会产生利润，故在目标函数中的系数应为0。此时，z 仍可简写为,松弛变量在目标函数中的系数是什么？,1.3 线性规划的标准型,从而，该问题的标准型为：,将下列线性规划化成标准形。,1.3 线性规划的标准型,【例6】,1.3 线性规划的标准型,线性规划问题标准形的矩阵表示：,A为系数矩阵；b是资源向量，C是价值向量，X为决策变量向量.,记,则矩阵表示为：,1.3 线性规划的标准型,线性规划问题标准形的向量表示:,目标函数 z=CX 可写成：,此时约束方程AX=b 可写成：,则向量表示为：,若令,z=c1 x1+c2 x2+cn xn,P1x1+P2 x2+Pn xn=b,max z=c1 x1+c2 x2+cn xn,s.t.P1x1+P2x2+Pn xn=b x j 0,j=1,2,n,1.3 线性规划的标准型,1.4 线性规划问题解的概念,给定一个线性规划问题LP：,1.4 线性规划问题解的概念,所有可行解的集合称为可行域(feasible region),记为,使目标函数达到最大值的可行解称为最优解(an optimal solution)。,(1)可行解(a feasible solution),满足约束条件的 X 称为线性规划问题的可行解;,直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的顶点，是一个最优的方案。,1.4 线性规划问题解的概念,即,是 A 的任意 m 个列向量,r(A)=m,设,是线性无关的，,如果,构成线性规划问题的一个基(base)。,则称,对应的变量,称为基变量。,其余的变量称为非基变量(non-basic-variable)。,称为基阵。,矩阵,（2）基矩阵与基变量,记约束方程系数矩阵A的列向量是,1.4 线性规划问题解的概念,=,目标函数,约束条件,右边常量,1.4 线性规划问题解的概念,列出基变量、非基变量等各项参数.,解：约束方程A的系数矩阵为：,1.4 线性规划问题解的概念,【例7】,1.4 线性规划问题解的概念,（2）设B是A的一个 m 阶子矩阵，则B是线性规划问题的基阵，当且仅当B是可逆阵,（3）基的个数,（1）基不一定唯一.,注：,1.4 线性规划问题解的概念,P1x1+P2x2+Pn xn=b,（3）基本解与基本可行解,1.4 线性规划问题解的概念,可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。,非负的基本解为基本可行解（简称基可行解）。,1.4 线性规划问题解的概念,B1=(P3P4P5)为基阵,x3 x4 x5为基变量,得到的基可行解(0,0,18,4,12。,在上例7中，,B2=(P2P4P5)为基阵,x2 x4 x5为基变量,得到基解(0,9,0,4,-6),但不是基可行解。,1.4 线性规划问题解的概念,上二组概念间的联系：,系数阵A中可找出若干个基B,每个基B都对应于一个基本解,非负的基本解就是基本可行解,几种解之间的关系：,非可行解,可行解,基 解,基可行解,解空间,问题：基本可行解是可行域中的哪些点？,基可行解的数目是有限个，不会超过,1.4 线性规划问题解的概念,第一章 线性规划,1 线性规划问题及其模型,2 线性规划问题几何意义,3 单纯形法,4 单纯形法计算步骤,5 单纯形法进一步讨论,6 应用举例,本节学习要点：1、了解线性规划问题可行域的特征；2、了解基可行解的性质和几何特征。,在上一节中：,maxz=3x1+5x2,二维：线性规划的可行域的形状；最优解获得的位置。n维？可行域的顶点与基可行解的关系？,设如果存在 k 个实数使得则称。,2.1 凸组合、凸集与顶点,凸组合,一般地，在Rn 中，给定 k+1 个顶点 如果 线性无关，则称 的凸组合是Rn中的一个 k 维单纯形，简称单形（simplex）。,单纯形,2.1凸组合、凸集与顶点,设，如果K中任意两点间的连线仍属于K，即对于任意 及 0，1，成立,则称K是凸集。,凸 集,直观上，凸集是没有凹入部分，且其内部又没有空洞的几何形体。,2.1凸组合、凸集与顶点,设 是一个凸集，如果X不是K中任意两个不同点连线的中间点，即X 不是 K 中的两个不同点的凸组合，则称X是K的一个顶点。,K,顶 点,例如，在右图的凸多边形K 中，仅有四个顶点X1、X2、X3、X4。,而在一个实心圆区域内，其边界圆周上的每个点都是该凸集的顶点。,2.1凸组合、凸集与顶点,2.2 基可行解的性质与几何特征,定理1.若，则是凸集。,定理2.如果线性规划问题有可行解，则一定有基可行解。,定理3.设X0 是一个可行解，则X0是基可行解当且仅 当X0是的顶点。,定理4.如果线性规划问题有最优解，则一定存在一个基 可行解是最优解。,应用上述术语，我们讨论线性规划可行域的特征。,不一定所有的基可行解都是最优解，最优解也不一定都是基解；如果有两个基可行解是最优解，则两解的凸组合也都是最优解。如果最优解不唯一，则会有多个基本可行解是最优解，它们必然在同一个面上。基可行解个数有限，可以在基可行解中寻找最优解。剩余的问题是如何判断一个基可行解是最优解，如果不是则如何从一个基可行解转到另一个基可行解。,说明：,2.2 基可行解的性质与几何特征,小结：基本定理,（1）线性规划的可行域是一个凸多面体。,（2）线性规划可行域的顶点与基本可行解一一对应。,（3）线性规划的最优解（若存在的话）必能在可行域的顶点获得。,2.2 基可行解的性质与几何特征,