(OROperationsResearch运筹学是应用分析、试验、量课件.ppt

1、运筹学（运筹学（O.R.）Operations Research 运筹学是应用分析、试验、量化的方运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。依据的最优方案，以实现最有效的管理。中国古代运筹学思想：中国古代运筹学思想：齐王赛马齐王赛马丁渭修皇宫丁渭修皇宫沈括运粮沈括运粮防空系统防空系统商船护航商船护航运筹学的产生：运筹学的产生：运筹学发展三阶段：运筹学发展三阶段：创建时期（创建时期（45年至年至50年代初）年代初）1948年年

2、英国成立英国成立“运筹学运筹学”俱乐部俱乐部1948年年 麻省理工学院麻省理工学院 介绍运筹学介绍运筹学1950年年 伯明翰大学开设运筹学课程伯明翰大学开设运筹学课程1952年年 卡斯大学卡斯大学 设立运筹学硕士和博士学位设立运筹学硕士和博士学位1947年年 丹捷格丹捷格 提出单纯形法提出单纯形法50年代初年代初 计算机求解线性规划获得成功计算机求解线性规划获得成功成长时期（成长时期（50年代初至年代初至50年代末）年代末）多个国家成立运筹学会，多种运筹学刊物问世多个国家成立运筹学会，多种运筹学刊物问世1957年年 在牛津大学召开第一次国际运筹学会议在牛津大学召开第一次国际运筹学会议1959年

3、年 成立国际运筹学联合会成立国际运筹学联合会迅速发展时期（迅速发展时期（60年代以来）年代以来）运筹学进一步分为各个分支，更多运筹学出版物运筹学进一步分为各个分支，更多运筹学出版物运筹学课程纳入教学计划运筹学课程纳入教学计划我国运筹学发展历程：我国运筹学发展历程：1956年年 运筹学小组运筹学小组1958年年 运筹学研究室运筹学研究室1960年年 应用运筹学经验交流会议应用运筹学经验交流会议1962年年 全国运筹学专业学术会议全国运筹学专业学术会议1978年年 全国运筹学专业学术会议全国运筹学专业学术会议1980年年 成立中国运筹学学会成立中国运筹学学会国际著名运筹学刊物：国际著名运筹学刊物：

4、Management ScienceOperations ResearchInterfacesJournal of Operational Research SocietyEuropean Journal of Operations Research运筹学的分支运筹学的分支:线性规划（线性规划（linear programming）非线性规划（非线性规划（nonlinear programming）动态规划（动态规划（dynamic programming）图论与网络分析（图论与网络分析（graph theory and network analysis）存贮论（存贮论（inventory t

5、heory）排队论（排队论（queueing theory）对策论（对策论（game theory）决策论（决策论（decision theory）运筹学在工商管理中的应用运筹学在工商管理中的应用:生产计划：生产作业的计划、日程表的编排、合理下料、生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成配料问题、物料管理等，追求利润最大化和成 本最小化本最小化库存管理：多种物资库存量的管理，库存方式、库存量等库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输运输问题：确定最小成本的运输线路、物资的调拨、运输 工

6、具的调度以及建厂地址的选择等工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售市场营销：广告预算、媒介选择、定价、产品开发与销售 计划制定等计划制定等财务会计：预测、贷款、成本分析、定价、证券管理、财务会计：预测、贷款、成本分析、定价、证券管理、现金管理等现金管理等组织组织 应用应用 Interfaces 期期刊号刊号 每年节支每年节支（美元）（美元）联合航空公司联合航空公司 满足乘客需求前提下满足乘客

7、需求前提下,以最低成本进行订票及安排以最低成本进行订票及安排机场工作班次机场工作班次 1-2/1986 600 万万 Citgo 石油石油 优化炼油程序及产品供应、配送及营销优化炼油程序及产品供应、配送及营销 1-2/1987 7000 万万 荷马特发展公司荷马特发展公司 优化商业区和办公楼销售程序优化商业区和办公楼销售程序 1-2/1987 4000 万万 AT&T 优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址 1-2/1990 4.06 亿亿 更多销更多销售售 标准品牌公司标准品牌公司 控制成品库存（制定最优再订购点和订购量，确保控制成品库存（制定最优再订购点和订购量，确保

8、安全库存）安全库存）12/1981 380 万万 施乐施乐公司公司 通过战略调整，缩短维修机器的反应时间和改进维通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率修人员的生产率 11/1975 生产率提高生产率提高50%以上以上 宝洁公司宝洁公司 重新设计北美生产和分销系统以降低成本并加快了重新设计北美生产和分销系统以降低成本并加快了市场进入速度市场进入速度 1-2/1997 2 亿亿 法国国家铁路法国国家铁路 制定最优铁路时刻表并调整铁路日运营量制定最优铁路时刻表并调整铁路日运营量 1-2/1998 1500 万万 更多年收更多年收入入 Delta 航空公司航空公司 进行上千个国内航

9、线的飞机优化配置来最大化利润进行上千个国内航线的飞机优化配置来最大化利润 1-2/1994 1 亿亿 IBM 重组全球供应链，保持最小库存重组全球供应链，保持最小库存同时满足客户需求同时满足客户需求 1-2/2000 第一年第一年 7.5 亿亿 Merit 青铜制品公司青铜制品公司 安装统安装统计销售预测和成品库存管理系统，改进客户计销售预测和成品库存管理系统，改进客户服务服务 1-2/1993 更优的服务更优的服务 学习管理运筹学学习管理运筹学:必须使用相应的计算机软件必须使用相应的计算机软件必须注重于学以致用的原则必须注重于学以致用的原则要把注意力放在要把注意力放在:结合实际问题建立运筹学

10、模型结合实际问题建立运筹学模型解决问题的方案或模型的解解决问题的方案或模型的解中间的计算过程尽可能让计算机软件完成中间的计算过程尽可能让计算机软件完成运筹学的工作步骤：运筹学的工作步骤：1提出和形成问题提出和形成问题2收集资料，确定参数收集资料，确定参数3建立模型建立模型4模型求解和检验模型求解和检验5解的控制解的控制第一章第一章 线性规划线性规划例例1.1 某厂生产某厂生产P、Q两种产品，主要消耗两种产品，主要消耗A、B、C三种原料，已知单位产品的原料三种原料，已知单位产品的原料消耗数量等资料如表所示。确定消耗数量等资料如表所示。确定P、Q的产的产量，使产值最大。量，使产值最大。PQ原料总量

11、原料总量ABC1502248吨吨20吨吨12吨吨产品单价产品单价2万元万元5万元万元 第一节第一节 线性规划的基本概念线性规划的基本概念设设P、Q的产量分别为的产量分别为x1，x2 0,124 202582 52 max212212121xxxxxxxxxz数学模型：数学模型：例例1.2 某公司打算利用甲、乙、丙三种原料配置某公司打算利用甲、乙、丙三种原料配置一种新型保健饮料，已知每千克原料中两种主一种新型保健饮料，已知每千克原料中两种主要保健成分要保健成分A，B含量及原料单价如表所示。质含量及原料单价如表所示。质量标准规定每千克饮料中，营养成分量标准规定每千克饮料中，营养成分A，B的含的含量

12、不低于量不低于10个与个与8个单位。如何制定饮料配方，个单位。如何制定饮料配方，既满足质量标准又使成本最低？既满足质量标准又使成本最低？甲甲乙乙丙丙AB2010400020单价（元单价（元/千克）千克）223设每千克饮料中原料甲、乙、丙的投入量设每千克饮料中原料甲、乙、丙的投入量分别为分别为x1，x2，x3千克千克 数学模型：数学模型：0,820 1010 4020 322 min3213121321xxxxxxxxxxz例例1.3 A1 A2是两个粮库，每月分别可调出粮食是两个粮库，每月分别可调出粮食30 吨与吨与40吨，三个粮店吨，三个粮店B1，B2，B3每月需求量每月需求量分别为分别为2

13、0吨，吨，25吨与吨与18吨。粮库与粮店之间每吨。粮库与粮店之间每吨粮食的运费如下表所示。要求安排粮食调运吨粮食的运费如下表所示。要求安排粮食调运方案，在满足需求的前提下使总运费最低。方案，在满足需求的前提下使总运费最低。B1B2B3 A1A22436533040202518 设从设从Ai到到Bj调运量为调运量为xij数学模型：数学模型：3,2,1 2,1 018 25 20 4030 364532 min231322122111232221131211232221131211jixxxxxxxxxxxxxxxxxxxzij共同特点：共同特点：（1）每个行动方案可用一组变量（）每个行动方案可用

14、一组变量（x1,xn）的值表示，这些变量一般取非负值；的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它是变量的线）有一个需要优化的目标，它是变量的线性函数。性函数。1 12211 1122111 1221max(min)(,)(,),0nnnnmmmnnmnzc xc xc xa xa xa xba xaxaxbxx (1.1)(1.2)(1.3)njxmibxaxczjinjjijnjjj,2,1 0,2,1 ),(max(min)11例例1.

15、4 求下列问题的最优解。求下列问题的最优解。0,124 202582 52 max212212121xxxxxxxxxzx1x2x1+2x2=85x1+2x2=204x2=12432101235645Q1Q2Q3Q4(3,2.5)(2,3)z的等值线：的等值线：21255zxx 二、图解法图解法例例1.5 在例在例1.4中，约束条件不变，而目标中，约束条件不变，而目标函数改为函数改为max z=2x1+4x2 x1x2x1+2x2=85x1+2x2=204x2=12432101235645Q1Q2Q3Q4(3,2.5)(2,3)全部最优解：全部最优解：X1+（1）X2（01）2/53 2X32

16、1X例例1.6 0,2 42-zmax 21212121xxxxxxxxDA24x2x1BCx1x2=2 2x1+x2=4 O例例1.7在例在例1.6中，约束条件改为中，约束条件改为 0,2 42-212121xxxxxx第二节第二节 线性规划的标准形式和解的性质线性规划的标准形式和解的性质 一、一、LP的标准形式的标准形式 njxmibxaxczjinjjijnjjj,2,1 0,2,1 max11(1.4)(1.5)(1.6)0,(min)max1221122222121112121112211nmnmnmmnnnnnnxxbxaxaxabxaxaxabxaxaxaxcxcxcZ方法：方法

17、：（1）目标函数求极小：令）目标函数求极小：令z1=z，（2）某右端常数）某右端常数bi0，以，以1乘该约束两端。乘该约束两端。（3）约束为）约束为“”型，左端加非负变量（松弛变量）型，左端加非负变量（松弛变量）约束为约束为“”型，左端减去非负变量（剩余变量）型，左端减去非负变量（剩余变量）（4）若）若xj0；令；令xj=xj，则，则xj0；若若xj无符号限制无符号限制,令令xj=xj-xj,其中其中xj0，xj0。njjjxcz11)(max例例1.8 0,124 202582 52 max212212121xxxxxxxxxz0,12 4 20 258 2 52 max5432152421

18、32121xxxxxxxxxxxxxxxz0,5 2232 7 332 max54 3321 33215 33214 3321 33211xxxxxxxxxxxxxxxxxxxxxxxxz无符号约束321321321321321,0,5232 7 32 minxxxxxxxxxxxxxxxz例例1.9 二、二、LPLP的基可行解的概念的基可行解的概念 0b maxXAXCXz决策变量向量：决策变量向量：X=(x1，x2，xn)T价值向量：价值向量：C=(c1，c2，cn)资源向量：资源向量：b=(b1，b2，bm)T系数矩阵系数矩阵A=（aij）mn=mnmmnnaaaaaaaaa 21222

19、21112110,(min)max1221122222121112121112211nmnmnmmnnnnnnxxbxaxaxabxaxaxabxaxaxaxcxcxcZ设系数矩阵设系数矩阵A的秩是的秩是m，即，即A的的m个行向量个行向量是线性无关的。若是线性无关的。若B是是A的的m阶满秩子阵，阶满秩子阵，称称B为问题的一个基。为问题的一个基。B=(P1，P2 ，Pm)对应的变量对应的变量(x1，x2 ，xm)称为基变量称为基变量其它的变量称为非基变量；其它的变量称为非基变量；令非基变量等于令非基变量等于0，从方程组可以唯一解出基变量，从方程组可以唯一解出基变量的值，从而得到方程组的一个解，称

20、为基本解；的值，从而得到方程组的一个解，称为基本解；如果它的各个分量非负，即它同时又是可行解，如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。则称之为基可行解，对应的基称为可行基。三、三、LP解的性质解的性质 1.凸集和极点凸集和极点 设设D为为n维空间的点集，若对任意维空间的点集，若对任意X1D，X2D，和实数，和实数（01），都有），都有X1+（1）X2D，则称，则称D为凸集。为凸集。凸集凸集D中如果不存在两个不同的点中如果不存在两个不同的点X1D，X2D，使，使X=X1+（1）X2（01）成立，那么点成立，那么点X称为极点。称为极点。2.线性规划解的性质线

21、性规划解的性质定理定理1 线性规划的可行域线性规划的可行域R是凸集。是凸集。证证 对于对于LP max z=CX AX=b X 0设设X1R，X2R，则有，则有Xi0，AXi=b对于任意对于任意0，1，X=X1+（1）X20AX=AX1+（1）X2 =AX1+（1）AX2 =b+（1）b=b故故XR，R是凸集。是凸集。引理引理 设设X是线性规划的可行解，则是线性规划的可行解，则X是基可行解的是基可行解的充分必要条件是充分必要条件是X的正分量对应的系数列向量是线的正分量对应的系数列向量是线性无关的。性无关的。证证（1）必要性。由基可行解的定义显然成立。）必要性。由基可行解的定义显然成立。（2）充

22、分性。不妨设）充分性。不妨设X的前的前k个分量为正，若向量个分量为正，若向量P1,P2,Pk线性无关，则必有线性无关，则必有km。当。当k=m时，它们时，它们恰好构成一个基，从而恰好构成一个基，从而X是基可行解。当是基可行解。当km时，时，由于由于A的秩为的秩为m，从，从A中一定可以再找出中一定可以再找出m-k个列向个列向量与量与P1,P2,Pk线性无关，共同构成一个基，其对线性无关，共同构成一个基，其对应的解就是应的解就是X，所以，所以X是基可行解。是基可行解。定理定理2 X是线性规划基可行解的充分必要条件是是线性规划基可行解的充分必要条件是X是可行域的极点。是可行域的极点。证证（1）X不是

23、基可行解，不是基可行解，则则X不是可行域的极点。不是可行域的极点。不失一般性，假设不失一般性，假设X的前的前m个分量为正，则有个分量为正，则有1bmjjjP x由引理知由引理知P1,P2,Pm线性相关，即存在不全为零的数线性相关，即存在不全为零的数(1,)iim使得使得1 1220mmPPP1 1220mmPPP（1）（2）令令min0jjjx则则0jjx设设11122(,0,0)TmmXxxx21122(,0,0)TmmXxxx则则12,XR XR（1）+（2）得：）得：111222()()()bmmmxPxPxP（1）-（2）得：）得：111222()()()bmmmxPxPxP又又12(

24、)/2XXX即即X不是可行域的顶点。不是可行域的顶点。（2）X不是可行域的极点，不是可行域的极点，则则X不是基可行解。不是基可行解。不失一般性，设不失一般性，设12(,0,0)TrXx xx不是可行域的极点不是可行域的极点存在两个不同的点存在两个不同的点,YR ZR有有X=Y+(1)Z即即(1)(01;1,)jjjxyzjn 因因0,10故故0jx 时时0jjyz故故11=bnrjjjjjjP xP x因因11=bnrjjjjjjP yP y11=bnrjjjjjjP zP z（1）（2）（1）-（2）得：）得：1()=0rjjjjyzP因因YZ故故P1,P2,Pr线性相关线性相关定理定理3

25、线性规划如果有可行解，则一定有基可行解；线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。如果有最优解，则一定有基可行解是最优解。证证（1）不失一般性，假设可行解）不失一般性，假设可行解X的前的前m个分量为正。个分量为正。如果如果P1,P2,Pm线性无关，则线性无关，则X是基可行解。是基可行解。(1,)iim使得使得1 1220mmPPP令令min0jkjkjxx则则0jjx设设11122(,0,0)TmmXxxx21122(,0,0)TmmXxxx则则12,XR XR12()/2XXX若若0k则则X2比比X少一个正分量，若少一个正分量，若X2的的m-1个列向量个

26、列向量线性无关，则线性无关，则X2是基可行解，否则，重复以上过程，是基可行解，否则，重复以上过程，直到找到基可行解为止。直到找到基可行解为止。如果线性相关即存在不全为零的数如果线性相关即存在不全为零的数（2）设）设X0是最优解，如果它不是基可行解，则有是最优解，如果它不是基可行解，则有10XXR20XXR100()CXC XCXC200()CXC XCXC00CXCXC00CXCXC则则0C012CXCXCX故故X1，X2也是最优解，如前所述，也是最优解，如前所述，X1，X2中一定有一个点比中一定有一个点比X0少一个正分量。同理，如果少一个正分量。同理，如果X1（X2）还不是基可行解，则）还不

27、是基可行解，则能找到第三个最优解，其正分量比能找到第三个最优解，其正分量比X1（X2）少一个，如此继）少一个，如此继续下去，一定可以求得一个最优解，它的正分量是线性无关续下去，一定可以求得一个最优解，它的正分量是线性无关的，即这个最优解为基可行解。的，即这个最优解为基可行解。第三节单纯形法第三节单纯形法一、一、单纯形法的解题思路单纯形法的解题思路cjc1 c2 cm cm+1 ck cnCBXBbx1 x2 xm xm+1 xk xnc1c2cmx1x2xmb1b2bm1 0 0 a1m+1 a1k a1n0 1 0 a2m+1 a2k a2n 0 0 1 amm+1 amk amnj0 0

28、0miimimacc111miikikacc1miininacc1二、单纯形表二、单纯形表 3.单纯形法的基本法则法则法则1 最优性判定法则若对基可行解X1，所有检验数j0，则X1为最优解。法则法则2 换入变量确定法则设 ，则xk为换入变量。0maxjjjk法则法则3 换出变量确定法则lklikikiiabaab0min例例12 求下列LP问题 0,108 34 12 42 7 2 3 23 max65432165324325321532xxxxxxxxxxxxxxxxxxxxzCj0-130-20CBXBbx1x2x3x4x5x60 x1713-10200 x4120-241000 x6 1

29、0 0-43081j 0-130-200 x11015/201/4203x330-1/211/4000 x6 1 0-5/20-3/481j01/20-3/4-20-1x242/5101/104/503x351/5013/102/500 x6 11 100-1/2101j-1/500-4/5-12/50三、三、关于单纯形法的补充说明关于单纯形法的补充说明 1.无穷多最优解与唯一最优解的判别法则若对某可行解X1，（1）所有检验数j0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数j0，但aik0，i=1，2，m即xk的系数列向量无正分量，则问题无最优解。3.

30、求min z 的情况直接计算最优性检验条件改为：所有j0；换入变量确定法则改为：如果则xk为换入变量。例例14 求例2中的LPkjjj 0min0,8 20 1010 4020 322 min54321531421321xxxxxxxxxxxxxxz52201 2141 401 21531421xxxxxx52201 2141 401 21322 min531421321xxxxxxxxxzcj22300CBXBbx1x2x3x4x523x2x31/42/51/21/21001-1/4000-1/20j-1/2001/203/2023x1x31/23/20102-101-1/201/400-1

31、/20j0101/403/20X*=(0.5,0,0.15,0,0)T，z=21/2+33/20=1.45 第四节第四节 初始可行基的求法初始可行基的求法人工变量法人工变量法一、大大M法法 例例15 求下列LP问题的最优解 0,1 2324112 3 max32131321321321xxxxxxxxxxxxxxz0,1 23 2411 2 3 max71731653214321763211xxxxxxxxxxxxxxMxMxxxxz二、二、两阶段法两阶段法0,1 2324112 3 max32131321321321xxxxxxxxxxxxxxz0,1 23 2411 2 min717316

32、5321432176xxxxxxxxxxxxxxxxw例例170,1 23 2411 2 min7173165321432176xxxxxxxxxxxxxxxxwcj0000011CBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-2101211000-10010001j6-1-30100010 x4x6x3101130-2-2100011000-10010-1-21j0-100103000 x4x2x3121130-2010001100-2-10210-5-21j0000011cj3-1-100CBXBbx1x2x3x4x50-1-1x4x2x3121130-2010

33、001100-2-10j1000-13-1-1x1x2x34191000100011/302/3-2/3-1-4/3j000-1/3-1/3X*=(4，1，9，0，0)T，z*=2 三、三、关于退化解的说明关于退化解的说明 0,1 1 4 min43214324314321xxxxxxxxxxxxxxzcj-1-1-41CBXBbx1x2x3x4-1-1x1x211100111-11j00-21-4-1x3x2101-10110-12j200-1-41x3x4101/2-1/21/21/21001j3/21/200第五节线性规划应用举例第五节线性规划应用举例建立LP模型步骤：（1）深入分析问题

34、特点，适当选择决策变量；（2）确定优化对象目标函数，它必须表达为决策变量的线性函数；（3）分析制约变量的各种因素，用线性等式或不等式把这些条件反映出来。例例18 利用长度为7.4米的角钢，要做成三边长为2.9米，2.1米，1.5米的三角架100套。如何下料，才能使消耗的原料最少？123456782.9米2.1米1.5米201120111103030022013004合计长余料长7.30.17.10.36.50.97.406.31.17.20.26.60.861.4变量编号x2x4x6x1x7x3x5x80,1004 3 23100 322 100 2 min818653217654364218

35、7654321xxxxxxxxxxxxxxxxxxxxxxxxxz例例19 某食品厂要用C，P，H三种原料混合加工成三种不同档次的产品A，B，C，已知三种产品中原料含量限制，原料成本和每月限制用量，三种产品的加工费和单价等资料如表所示。该厂应当每月生产三种产品多少公斤，才能使利润最大？试建立问题的线性规划模型。解解 设AC，AP，AH分别表示产品A中三种原料的含量，其它符号BC，BP，BH和DC，DP，DH的含义相仿。含量限制AC+AP+AH=ABC+BP+BH=BDC+DP+DH=DAC AAP ABC BBP BDP D 4141212153 AC+AP+AH0 AC+AP AH0 BC+

36、BP+BH0 BC+BP BH0 DC+DP DH0214141215321212143434141215253AC+BC+DC3000AP+BP+DP3000AH+BH+DH2400原料数量限制：产品销售收入为：60（AC+AP+AH）+45（BC+BP+BH）+40（DC+DP+DH）加工费为：6（AC+AP+AH）+5（BC+BP+BH）+4（DC+DP+DH）原料成本为：65（AC+BC+DC）+25（AP+BP+DP）+35（AH+BH+DH）利润：z=60（x1+x2+x3）+45（x4+x5+x6）+40（x7+x8+x9）6（x1+x2+x3）5（x4+x5+x6）4（x7+x8+x9）65（x1+x4+x7）25（x2+x5+x8）35（x3+x6+x9）=11x1+29x2+19x325x4+15x5+5x629x7+11x8+x99,2,1 02400 3000 3000 0323 0 0 3 0 30 112951525192911 max963852741987654654321321987654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzj