线性规划的提出ppt课件.ppt

《线性规划的提出ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性规划的提出ppt课件.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第一章第一章 线性规划与单纯形法线性规划与单纯形法 在线性约束条件下在线性约束条件下, ,求线性目标函数的最大值或最求线性目标函数的最大值或最小值问题小值问题, ,称为称为线性规划问题线性规划问题. . 线性规划主要解决：如何利用现有的资源，使得预线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。期目标达到最优。2 线性规划是运筹学的重要分枝，也是线性规划是运筹学的重要分枝，也是运筹学最基运筹学最基本的部分本的部分。 20 20 世纪世纪 30 30 年代末，前苏联学者康托洛维奇首年代末，前苏联学者康托洛维奇首先研究了线性规划问题。先研究了线性规划问题。19391939年，他撰写的

2、年，他撰写的生产组生产组织与计划中的数学方法织与计划中的数学方法一书，是线性规划应用于工一书，是线性规划应用于工业生产问题的经典著作。业生产问题的经典著作。 然而这项工作长期不为人们所知。然而这项工作长期不为人们所知。3 第二次世界大战期间，由于战争的需要，柯第二次世界大战期间，由于战争的需要，柯勃门（勃门（T. C. Koopmans）重行、独立地研究了运重行、独立地研究了运输问题。输问题。 后来丹捷格后来丹捷格（G. B. Dantzig）于于 1947 1947 年发现年发现了单纯形方法，并将其应用于与国防有关的诸如人了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题

3、。此后，线性规划的员的轮训、任务的分派等问题。此后，线性规划的理论和方法日渐趋于成熟。理论和方法日渐趋于成熟。 4两类决策问题两类决策问题 对给定的任务，如何用最少的资源去完对给定的任务，如何用最少的资源去完成它成它 如何利用有限的紧缺资源产生最大的经如何利用有限的紧缺资源产生最大的经济或社会效益济或社会效益 5n 运筹学中应用最广泛的方法之一运筹学中应用最广泛的方法之一n 运筹学的最基本的方法之一，网络规划，整数规划，目运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的标规划和多目标规划都是以线性规划为基础的n 解决稀缺资源最优分配的有效方法，使付出的费

4、用最小解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大或获得的收益最大n 历史悠久、理论成熟、应用广泛历史悠久、理论成熟、应用广泛n 从从19641964年诺贝尔奖设经济学奖后，到年诺贝尔奖设经济学奖后，到19921992年年2828年间的年间的3232名获奖者中有名获奖者中有1313人人(40%)(40%)从事过与线性规划有关的研究从事过与线性规划有关的研究工作，其中比较著名的还有工作，其中比较著名的还有SimonSimon，SamullsonSamullson，LeontiefLeontief，ArrowArrow，MillerMiller等等 线性规划的特点线性规划的特点

5、6第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型 例例1 1：某企业生产甲、乙两种产品，这两种产品都需某企业生产甲、乙两种产品，这两种产品都需要用到要用到A A、B B两原材料，每吨甲、乙产品所需的原材料两原材料，每吨甲、乙产品所需的原材料数量及利润值以及这两种原材料在计划期内能提供的数量及利润值以及这两种原材料在计划期内能提供的数量见下表，问如何安排生产计划，即甲乙各生产多数量见下表，问如何安排生产计划，即甲乙各生产多少吨，使该厂和利润最大？少吨，使该厂和利润最大？ 单位产品所单位产品所用原材料用原材料甲甲乙乙原材料数量原材料数量（吨）（吨）A A5 54 42424B B8

6、 86 64848利润（千元利润（千元/ /吨）吨）4 45 5求求MAXMAX7 线性规划所研究的对象属于最优化的范畴，本质上线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确规划问题的数学模型时，应首先明确三个基本要素三个基本要素： 决策变量（决策变量（decision variablesdecision variables）：它们是决策：它们是决策者所控制的那些数量，它们取什么数值需要决策者来者所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变

7、量的最优值。决策，问题的求解就是找出决策变量的最优值。 8 约束条件（约束条件（constraintsconstraints）：）：它们是决策者它们是决策者在现实世界中所受到的限制，或者说决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。在这些限制范围之内才有意义。 目标函数（目标函数（objective functionobjective function）：）：它代它代表决策者希望对其进行优化的那个指标。目标表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。函数是决策变量的函数。 线性规划问题的特征是目标函数和约束条件线性规划问题的特征是目标函数和约束

8、条件中的函数都是决策变量的中的函数都是决策变量的线性函数线性函数，并且约束是，并且约束是必不可少的必不可少的 ( (否则不存在有实际意义的解否则不存在有实际意义的解) )。9例例2 2：某公司经销一种产品，下设三个生产点，每日的某公司经销一种产品，下设三个生产点，每日的产量分别是产量分别是A A1 1：5 5，A A2 2：7 7，A A3 3：8 8（吨），分别运往四（吨），分别运往四个销售点，各地的销量分别为个销售点，各地的销量分别为B B1 1：3 3，B B2 2：4 4，B B3 3：5 5，B B4 4：8 8（吨），已知每吨产品从各生产地到各销售点的运价（吨），已知每吨产品从各生

9、产地到各销售点的运价如下，问该公司如何调运产品，可在满足各销售点需如下，问该公司如何调运产品，可在满足各销售点需要量的前提下，总运费最小？要量的前提下，总运费最小？单位运价（百单位运价（百元元/ /吨）吨）B B1 1B B2 2B B3 3B B4 4A A1 14 411113 31010A A2 21 19 92 28 8A A3 37 74 410105 510每一个问题都有一组变量每一个问题都有一组变量-称为称为决策变量决策变量，一般记为，一般记为下面从数学的角度来归纳上述两个例子的共同点。下面从数学的角度来归纳上述两个例子的共同点。 每个问题中都有决策变量需满足的一组每个问题中都有

10、决策变量需满足的一组约束条件约束条件-线性线性的等式或不等式。的等式或不等式。 .,21nxxx对决策变量每一组值：对决策变量每一组值：Tnxxx),()0()0(2)0(1代表了代表了一种决策方案。通常要求决策变量取值非负，即一种决策方案。通常要求决策变量取值非负，即)., 2 , 1( , 0nixi二、线性规划问题的数学模型二、线性规划问题的数学模型11 都有一个关于决策变量的线性函数都有一个关于决策变量的线性函数-称为称为目标函目标函数数。要求这个目标函数在满足约束条件下实现最大化。要求这个目标函数在满足约束条件下实现最大化或最小化。或最小化。 将约束条件及目标函数都是决策变量的线性函

11、数将约束条件及目标函数都是决策变量的线性函数的规划问题称为的规划问题称为线性规划线性规划。有时也将线性规划问题简。有时也将线性规划问题简记为记为LPLP（linear programming)linear programming)其数学模型为：其数学模型为：12nnxcxcxcZ2211max(min), 2 , 1( , 0),(),(),(.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn上述模型的简写形式为：上述模型的简写形式为：njjjxcZ1max(min), 2 , 1(0), 2 , 1(),(.1njxmibxa

12、tsjnjijij这里“s.t.”是“subject to”的缩写，即“满足于”的意思。13若令若令);,(21ncccC;21nxxxX;21mbbbb),(21212222111211nmnmmnnPPPaaaaaaaaaA14线性规划问题可记为矩阵和向量的形式：线性规划问题可记为矩阵和向量的形式：CXZ max(min)0),(.XbAXtsCXZ max(min)0),(.1XbxPtsnjjj用向量表示时，上述模型可写为：用向量表示时，上述模型可写为：15注意 目标和约束均为变量的线性表达式目标和约束均为变量的线性表达式 如果模型中出现如如果模型中出现如 的非线性表达式，则不属于线性

13、规划。的非线性表达式，则不属于线性规划。32211ln2xxx16基本概念基本概念 约束条件约束条件 (constraint conditions) (constraint conditions) 目标函数目标函数 (objective function) (objective function) 决策变量决策变量 (decision variable) (decision variable) 821,xxx数学规划问题数学规划问题 在某些约束条件下，求解目标函数在某些约束条件下，求解目标函数达到极大或极小的问题达到极大或极小的问题 线性规划问题线性规划问题（Linear Programmin

14、g , LP.Linear Programming , LP.） 约束条件是变量的线性方程或不等式组，目标函数也是约束条件是变量的线性方程或不等式组，目标函数也是变量的线性函数的数学规划问题变量的线性函数的数学规划问题 线性规划的基本任务线性规划的基本任务 在线性约束下，求出适当的决策变量使得线性目标函在线性约束下，求出适当的决策变量使得线性目标函数达到最大或最小数达到最大或最小 17可行解可行解（feasible sol.feasible sol.） 使得约束条件成立的决策变量的一组值使得约束条件成立的决策变量的一组值可行域可行域（feasible regionfeasible region

15、） 全体可行解组成的集合（经常记为全体可行解组成的集合（经常记为S S） 最优解最优解（optimal sol.optimal sol.） 可行域中使目标函数达到所需最大或最小的可行解可行域中使目标函数达到所需最大或最小的可行解 18三、线性规划问题的标准形式三、线性规划问题的标准形式LPLP问题的数学模型的标准形式为：问题的数学模型的标准形式为：nnxcxcxcZ2211max), 2 , 1( , 0.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn其中常数项其中常数项 , 0ib), 2 , 1(mi19LPLP问题标准形

16、式的特征是：问题标准形式的特征是： 求目标函数的求目标函数的最大值最大值； 约束条件为变量满足线性方程组且为约束条件为变量满足线性方程组且为等式等式； 方程组中变量、常数项皆方程组中变量、常数项皆非负非负。20一般形式化为标准形式一般形式化为标准形式 当约束条件中有当约束条件中有“=”=”=”时，减去一个非负新变量，使之时，减去一个非负新变量，使之成为等式这个新变量称为成为等式这个新变量称为剩余变量剩余变量（surplus surplus variablevariable） 当约束条件右端常数项为负数时，将等式两边乘以（当约束条件右端常数项为负数时，将等式两边乘以（-1-1）当某一决策变量没有

17、非负限制时，引进两个新的非负变当某一决策变量没有非负限制时，引进两个新的非负变量量x x,x,x，令，令X= XX= X-X-X，代入约束条件和目标函数，代入约束条件和目标函数中，即可化为非负变量的问题中，即可化为非负变量的问题当要求解目标函数当要求解目标函数 Z Z 的最大值时，引进新的目标函数的最大值时，引进新的目标函数ZZ，令，令Z=-ZZ=-Z，则变成求，则变成求MaxMax。21例例3 3 将将LPLP问题问题3212minxxxZ)2 , 1(0222.31321ixxxxxxtsi化为标准形。化为标准形。解：引进新的目标函数解：引进新的目标函数,ZZ于是原于是原LP问题化为标准形

18、式：问题化为标准形式：)2 , 1(0222.31321ixxxxxxtsi3212maxxxxZ22例：例：MAXZ=3XMAXZ=3X1 1-X-X2 2+2X+2X3 3 2X 2X1 1- X- X2 2+ X+ X3 3 = 4 = 4 -4X -4X1 1+ X+ X2 2+ 3X+ 3X3 3 = 8 = 8 3X 3X1 1+ 2X+ 2X2 2+ X+ X3 3 = 9 =0,X=0,X3 3自由变量自由变量 MAXZ=3X MAXZ=3X1 1-X-X2 2+2X+2X3 3-2X-2X3 3 2X 2X1 1- X- X2 2+ X+ X3 3 -X-X3 3XX4 4

19、= = 4 4 -4X -4X1 1+ X+ X2 2+ 3X+ 3X3 3 -3X-3X3 3 = = 8 8 3X 3X1 1+ 2X+ 2X2 2+ X+ X3 3 -X-X3 3 +X +X5 5 = = 9 9 X X1 1,X,X2 2,X,X3 3 ,X,X3 3 , ,X X4 4,X,X5 5 =0 =023例：公交线路人员优化问题例：公交线路人员优化问题 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下： 班班 次次 时时 间间 所需人数所需人数 1 6:00 -10:00 60 1 6:00 -10

20、:00 60 2 10:00-14:00 70 2 10:00-14:00 70 3 14:00-18:00 60 3 14:00-18:00 60 4 18:00-22:00 50 4 18:00-22:00 50 5 22:00- 2:00 20 5 22:00- 2:00 20 6 2:00 - 6:00 30 6 2:00 - 6:00 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，小时，问该公交线路至少配备多少名司机和乘务人员。问该公交线路至少配备多少名司机和乘务人员。 列出此问题的线性规划模型。列出此

21、问题的线性规划模型。 P46:Ex9P46:Ex924决策变量：决策变量：X Xi i为第为第i i班开始上班的人数班开始上班的人数 i=1,6i=1,6目标函数：目标函数：Min Z= XMin Z= X1 1+X+X2 2+X+X3 3+X+X4 4+X+X5 5+X+X6 6约束条件：约束条件： X X6 6 + X+ X1 1 = 60= 60 X X1 1 + X+ X2 2 = 70= 70 X X2 2 + X+ X3 3 = 60= 60 X X3 3 + X+ X4 4 = 50= 50 X X4 4 + X+ X5 5 = 20= 20 X X5 5 + X+ X6 6 = 30= 30 X Xi i=0,1=1,6=0,1=1,6