运筹学第四版·清华大学出版社·运筹学教材组·2.1线性规划PPT课件.ppt

1,运筹学(OperationsResearch),线性规划LinearProgramming,引言,线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自1947年旦茨基（G.B.Dantzig）提出了一般线性规划问题求解的方法单纯形法（simplexmethod）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界500家最大的企业中，有85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。本章中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。解决有限资源在有竞争的使用方向中如何进行最佳分配。,4,Chapter2线性规划与单纯形法,2.1线性规划问题及其数学模型2.2线性规划问题的几何意义2.3单纯形法2.4单纯形法的计算步骤2.5单纯形法的进一步讨论2.6应用举例,本章主要内容：,2.1线性规划,2.1线性规划问题及其数学模型,2.1.1问题的提出,1.线性规划举例生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标.,（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大).,2.1线性规划问题及其数学模型,例2.1某工厂计划生产、两种产品。已知生产单位产品所需要的设备台时及A、B两种原材料的消耗如下表所示。该工厂每生产一件产品可获利2元，生产一件产品可获利3元，问企业决策者应如何安排生产计划，使该工厂获得的利润最大？,2.1线性规划问题及其数学模型,解：设x1、x2分别为产品、的产量，则数学模型为：,maxZ=2x1+3x2,x1,x20,s.t.,x1+2x284x1164x212,2.1线性规划问题及其数学模型,例2.1河流污染治理规划问题,工厂2,工厂1,500w,200w,靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。化工厂1每天排放工业污水2万立方米，化工厂2每天排放工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小？,2.1线性规划问题及其数学模型,解：设化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米,2.1线性规划问题及其数学模型,得到本问题的数学模型为：,s.t.,2.1线性规划问题及其数学模型,每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。,上述两个问题具有的共同特征：,2.1线性规划问题及其数学模型,2.1线性规划问题及其数学模型,2.线性规划的数学模型由三个要素构成,决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints,其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,2.1线性规划问题及其数学模型,目标函数：,约束条件：,3.线性规划数学模型的一般形式,简写为：,线性规划问题的求解方法,一般方法,图解法单纯形法,两个变量、直角坐标三个变量、立体坐标,适用于任意变量、但必需将一般形式变成标准形式,下面我们分析一下简单的情况只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,2.1线性规划问题及其数学模型,2.1.2图解法,2.1线性规划问题及其数学模型,目标值在（4，2）点，达到最大值14,2.1线性规划问题及其数学模型,（1）唯一最优解。（2）无穷多最优解(多重最优解)。（3）无界解。（4）无可行解。,通过图解法，可观察到线性规划的解可能出现的几种情况：,2.1线性规划问题及其数学模型,（2）无穷多最优解（多重最优解）,2.1线性规划问题及其数学模型,（3）无界解,2.1线性规划问题及其数学模型,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。,（4）无可行解,2.1线性规划问题及其数学模型,例如在例2.1的数学模型中增加一个约束条件:,2.1线性规划问题及其数学模型,则该问题的可行域即为空集，即无可行解，,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),2.1线性规划问题及其数学模型,目标函数：,约束条件：,2.1.3线性规划问题的标准形式,简写为：,2.1线性规划问题及其数学模型,特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。,2.1线性规划问题及其数学模型,向量形式：,其中：,2.1线性规划问题及其数学模型,矩阵形式：,其中：,2.1线性规划问题及其数学模型,（2）如何化标准形式,目标函数的转换,如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令，可得到上式。,即,若存在取值无约束的变量，可令其中：,变量的变换,2.1线性规划问题及其数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量的变换,可令，显然,1.3线性规划问题的标准型式,例2.3将例2.1的数学模型化为标准形式的线性规划。,2.1线性规划问题及其数学模型,例2.4将下列线性规划问题化为标准形式,用替换，且,解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以,2.1线性规划问题及其数学模型,(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到maxz=-z，即当z达到最小值时z达到最大值，反之亦然;,2.1线性规划问题及其数学模型,标准形式如下：,2.1线性规划问题及其数学模型,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,2.1.4线性规划问题解的概念,2.1线性规划问题及其数学模型,可行解：满足约束条件(2)、(3)的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件(2)的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设：,称B中每个列向量Pj(j=12m)为基向量。与基向量Pj对应的变量xj为基变量。除基变量以外的变量为非基变量。,2.1线性规划问题及其数学模型,基解：某一确定的基B，令非基变量等于零，由约束条件方程(2)解出基变量，称这组解为基解。在基解中变量取非零值的个数不大于方程数m，基解的总数不超过基可行解：满足变量非负约束条件的基本解。可行基：对应于基可行解的基称为可行基。,约束方程的解空间,基础解,可行解,非可行解,基础可行解,退化解,2.1线性规划问题及其数学模型,例2.5求下列约束方程所对应的线性规划的所有基本解，基本可行解。,解：化为标准形式,按相同步骤，可求得线性规划其他4个基：,对应基本解是一个基本可行解。,对应基本解是一个基本可行解。,对应基本解不是一个基本可行解。,对应基本解是一个基本可行解。,若利用图解法画出线性规划的可行域，如图，,C,D,O,B,A,4,4,8,1.凸集：设k是n维欧式空间的一个点集，若任意两点X(1）k,X(2）k的连线上的一切点X(1+(1-)X(2）k(01),则称k为凸集。连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。,2.2线性规划问题的几何意义,2.2线性规划问题的几何意义,2.凸组合：设X(1），X(2），X(k)是n维欧式空间中的k个点，,则称X为X(1)，X(2)，X(k)的凸组合。,凸集k中任意两点X(1)，X(2)连线上的任一点X都是X(1)与X(2)的一个凸组合。,(3)顶点：设k为凸集，Xk,若X不能用X(1)k,X(2)k两点的一个凸组合表示为X=X(1)+(1-)X(2),其中01，则称X为k的一个顶点。,2.2线性规划问题的几何意义,定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对