《线性规划的提出ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性规划的提出ppt课件.ppt（24页珍藏版）》请在三一办公上搜索。
1、1,第一章 线性规划与单纯形法,在线性约束条件下,求线性目标函数的最大值或最小值问题,称为线性规划问题.,线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。,2,线性规划是运筹学的重要分枝，也是运筹学最基本的部分。,20 世纪 30 年代末，前苏联学者康托洛维奇首先研究了线性规划问题。1939年，他撰写的生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著作。 然而这项工作长期不为人们所知。,3,第二次世界大战期间，由于战争的需要，柯勃门（T. C. Koopmans）重行、独立地研究了运输问题。,后来丹捷格（G. B. Dantzig）于 1947 年发现了单纯形方
2、法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题。此后，线性规划的理论和方法日渐趋于成熟。,4,两类决策问题,5,运筹学中应用最广泛的方法之一运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大历史悠久、理论成熟、应用广泛从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等,线性规划的特点,6,第一节 线性规划问题及其数学模
3、型,例1：某企业生产甲、乙两种产品，这两种产品都需要用到A、B两原材料，每吨甲、乙产品所需的原材料数量及利润值以及这两种原材料在计划期内能提供的数量见下表，问如何安排生产计划，即甲乙各生产多少吨，使该厂和利润最大？,7,线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素：,决策变量（decision variables）：它们是决策者所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值。,8,约束条件（constraints）：它们是决策者在现实世界中所受到的限制，或者说决策变
4、量在这些限制范围之内才有意义。,目标函数（objective function）：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。,线性规划问题的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的 (否则不存在有实际意义的解)。,9,例2：某公司经销一种产品，下设三个生产点，每日的产量分别是A1：5，A2：7，A3：8（吨），分别运往四个销售点，各地的销量分别为B1：3，B2：4，B3：5，B4：8（吨），已知每吨产品从各生产地到各销售点的运价如下，问该公司如何调运产品，可在满足各销售点需要量的前提下，总运费最小？,10,每一个问题都有一组变量-称为
5、决策变量，一般记为,下面从数学的角度来归纳上述两个例子的共同点。, 每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。,对决策变量每一组值：,代表了,一种决策方案。通常要求决策变量取值非负，即,二、线性规划问题的数学模型,11, 都有一个关于决策变量的线性函数-称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。,将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)其数学模型为：,12,上述模型的简写形式为：,这里“s.t.”是“subject to”的缩写，即“满足于”的意思。,1
6、3,若令,14,线性规划问题可记为矩阵和向量的形式：,用向量表示时，上述模型可写为：,15,注意,目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则不属于线性规划。,16,基本概念,约束条件 (constraint conditions),目标函数 (objective function),决策变量 (decision variable),数学规划问题,线性规划问题（Linear Programming , LP.）,约束条件是变量的线性方程或不等式组，目标函数也是变量的线性函数的数学规划问题,线性规划的基本任务,在线性约束下，求出适当的决策变量使得线性目标函数达到最大或最小,1
7、7,18,三、线性规划问题的标准形式,LP问题的数学模型的标准形式为：,其中常数项,19,LP问题标准形式的特征是：, 求目标函数的最大值； 约束条件为变量满足线性方程组且为等式； 方程组中变量、常数项皆非负。,20,一般形式化为标准形式,当约束条件中有“=”时，减去一个非负新变量，使之成为等式这个新变量称为剩余变量（surplus variable） 当约束条件右端常数项为负数时，将等式两边乘以（-1）当某一决策变量没有非负限制时，引进两个新的非负变量x,x，令X= X-X，代入约束条件和目标函数中，即可化为非负变量的问题当要求解目标函数 Z 的最大值时，引进新的目标函数Z，令Z=-Z，则变
8、成求Max。,21,例3 将LP问题,化为标准形。,解：引进新的目标函数,于是原LP问题化为标准形式：,22,例：MAXZ=3X1-X2+2X3 2X1- X2+ X3 = 4 -4X1+ X2+ 3X3 = 8 3X1+ 2X2+ X3 =0,X3自由变量,MAXZ=3X1-X2+2X3-2X3 2X1- X2+ X3 -X3X4 = 4 -4X1+ X2+ 3X3 -3X3 = 8 3X1+ 2X2+ X3 -X3 +X5 = 9 X1,X2,X3 ,X3 ,X4,X5 =0,23,例：公交线路人员优化问题 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下： 班 次 时 间 所
9、需人数 1 6:00 -10:00 60 2 10:00-14:00 70 3 14:00-18:00 60 4 18:00-22:00 50 5 22:00- 2:00 20 6 2:00 - 6:00 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，问该公交线路至少配备多少名司机和乘务人员。 列出此问题的线性规划模型。,P46:Ex9,24,决策变量：Xi为第i班开始上班的人数 i=1,6目标函数：Min Z= X1+X2+X3+X4+X5+X6约束条件： X6 + X1 = 60 X1 + X2 = 70 X2 + X3 = 60 X3 + X4 = 50 X4 + X5 = 20 X5 + X6 = 30 Xi=0,1=1,6,
