运筹学(OR).ppt
运筹学（运筹学（O.R.）OperationsResearch运筹学是应用分析、试验、量化的方运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。依据的最优方案，以实现最有效的管理。中国古代运筹学思想：中国古代运筹学思想：齐王赛马齐王赛马丁渭修皇宫丁渭修皇宫沈括运粮沈括运粮防空系统防空系统商船护航商船护航运筹学的产生：运筹学的产生：运筹学发展三阶段：运筹学发展三阶段：创建时期（创建时期（45年至年至50年代初）年代初）1948年年英国成立英国成立“运筹学运筹学”俱乐部俱乐部1948年年麻省理工学院麻省理工学院介绍运筹学介绍运筹学1950年年伯明翰大学开设运筹学课程伯明翰大学开设运筹学课程1952年年卡斯大学卡斯大学设立运筹学硕士和博士学位设立运筹学硕士和博士学位1947年年丹捷格丹捷格提出单纯形法提出单纯形法50年代初年代初计算机求解线性规划获得成功计算机求解线性规划获得成功成长时期（成长时期（50年代初至年代初至50年代末）年代末）多个国家成立运筹学会，多种运筹学刊物问世多个国家成立运筹学会，多种运筹学刊物问世1957年年在牛津大学召开第一次国际运筹学会议在牛津大学召开第一次国际运筹学会议1959年年成立国际运筹学联合会成立国际运筹学联合会迅速发展时期（迅速发展时期（60年代以来）年代以来）运筹学进一步分为各个分支，更多运筹学出版物运筹学进一步分为各个分支，更多运筹学出版物运筹学课程纳入教学计划运筹学课程纳入教学计划我国运筹学发展历程：我国运筹学发展历程：1956年年运筹学小组运筹学小组1958年年运筹学研究室运筹学研究室1960年年应用运筹学经验交流会议应用运筹学经验交流会议1962年年全国运筹学专业学术会议全国运筹学专业学术会议1978年年全国运筹学专业学术会议全国运筹学专业学术会议1980年年成立中国运筹学学会成立中国运筹学学会国际著名运筹学刊物：国际著名运筹学刊物：ManagementScienceOperationsResearchInterfacesJournalofOperationalResearchSocietyEuropeanJournalofOperationsResearch运筹学的分支运筹学的分支:线性规划（线性规划（linearprogramming）非线性规划（非线性规划（nonlinearprogramming）动态规划（动态规划（dynamicprogramming）图图论与网络分析（论与网络分析（graphtheoryandnetworkanalysis）存贮论（存贮论（inventorytheory）排队论（排队论（queueingtheory）对策论（对策论（gametheory）决策论（决策论（decisiontheory）运筹学在工商管理中的应用运筹学在工商管理中的应用:生产计划：生产作业的计划、日程表的编排、合理下料、生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成配料问题、物料管理等，追求利润最大化和成本最小化本最小化库存管理：多种物资库存量的管理，库存方式、库存量等库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等计划制定等财务会计：预测、贷款、成本分析、定价、证券管理、财务会计：预测、贷款、成本分析、定价、证券管理、现金管理等现金管理等学习管理运筹学学习管理运筹学:必须使用相应的计算机软件必须使用相应的计算机软件必须注重于学以致用的原则必须注重于学以致用的原则要把注意力放在要把注意力放在:结合实际问题建立运筹学模型结合实际问题建立运筹学模型解决问题的方案或模型的解解决问题的方案或模型的解中间的计算过程尽可能让计算机软件完成中间的计算过程尽可能让计算机软件完成运筹学的工作步骤：运筹学的工作步骤：1提出和形成问题提出和形成问题2收集资料，确定参数收集资料，确定参数3建立模型建立模型4模型求解和检验模型求解和检验5解的控制解的控制第一章第一章线性规划线性规划例例1.1某厂生产某厂生产P、Q两种产品，主要消耗两种产品，主要消耗A、B、C三种原料，已知单位产品的原料消三种原料，已知单位产品的原料消耗数量等资料如表所示。确定耗数量等资料如表所示。确定P、Q的产量，的产量，使产值最大。使产值最大。PQ原料总量原料总量ABC1502248吨吨20吨吨12吨吨产品单价产品单价2万元万元5万元万元第一节第一节 线性规划的基本概念线性规划的基本概念设设P、Q的产量分别为的产量分别为x1，x2数学模型：数学模型：例例1.2某公司打算利用甲、乙、丙三种原料配置某公司打算利用甲、乙、丙三种原料配置一种新型保健饮料，已知每千克原料中两种主一种新型保健饮料，已知每千克原料中两种主要保健成分要保健成分A，B含量及原料单价如表所示。质含量及原料单价如表所示。质量标准规定每千克饮料中，营养成分量标准规定每千克饮料中，营养成分A，B的含的含量不低于量不低于10个与个与8个单位。如何制定饮料配方，个单位。如何制定饮料配方，既满足质量标准又使成本最低？既满足质量标准又使成本最低？甲甲乙乙丙丙AB2010400020单价（元单价（元/千克）千克）223设每千克饮料中原料甲、乙、丙的投入量设每千克饮料中原料甲、乙、丙的投入量分别为分别为x1，x2，x3千克千克数学模型：数学模型：例例1.3A1A2是两个粮库，每月分别可调出粮食是两个粮库，每月分别可调出粮食30吨与吨与40吨，三个粮店吨，三个粮店B1，B2，B3每月需求量每月需求量分别为分别为20吨，吨，25吨与吨与18吨。粮库与粮店之间每吨。粮库与粮店之间每吨粮食的运费如下表所示。要求安排粮食调运吨粮食的运费如下表所示。要求安排粮食调运方案，在满足需求的前提下使总运费最低。方案，在满足需求的前提下使总运费最低。B1B2B3A1A22436533040202518设从设从Ai到到Bj调运量为调运量为xij数学模型：数学模型：共同特点：共同特点：（1）每每个个行行动动方方案案可可用用一一组组变变量量（x1,xn）的值表示，这些变量一般取非负值；的值表示，这些变量一般取非负值；（2）变变量量的的变变化化要要受受某某些些限限制制，这这些些限限制制条条件用一些线性等式或不等式表示；件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它是变量的线）有一个需要优化的目标，它是变量的线性函数。性函数。(1.1)(1.2)(1.3)例例1.4求下列问题的最优解。求下列问题的最优解。x1x2x1+2x2=85x1+2x2=204x2=12432101235645Q1Q2Q3Q4(3,2.5)(2,3)z的等值线：的等值线：二、图解法图解法例例1.5在在例例1.4中中，约约束束条条件件不不变变，而而目目标标函数改为函数改为maxz=2x1+4x2x1x2x1+2x2=85x1+2x2=204x2=12432101235645Q1Q2Q3Q4(3,2.5)(2,3)全部最优解：全部最优解：X1+（1）X2（01）例例1.6DA24x2x1BCx1x2=22x1+x2=4O例例1.7在例在例1.6中，约束条件改为中，约束条件改为第二节第二节线性规划的标准形式和解的性质线性规划的标准形式和解的性质一、一、LP的标准形式的标准形式(1.4)(1.5)(1.6)方法：方法：（1）目标函数求极小：令）目标函数求极小：令z1=z，（2）某右端常数某右端常数bi0，以以1乘该约束两端。乘该约束两端。（3）约束为）约束为“”型，左端加非负变量（松弛变量）型，左端加非负变量（松弛变量）约束为约束为“”型，左端减去非负变量（剩余变量）型，左端减去非负变量（剩余变量）（4）若）若xj0；令令xj=xj，则则xj0；若若xj无符号限制无符号限制,令令xj=xj-xj,其中其中xj0，xj0。例例1.8例例1.9二、二、LPLP的基可行解的概念的基可行解的概念 决策变量向量：决策变量向量：X=(x1，x2，xn)T价值向量：价值向量：C=(c1，c2，cn)资源向量：资源向量：b=(b1，b2，bm)T系数矩阵系数矩阵A=（aij）mn=设设系系数数矩矩阵阵A的的秩秩是是m，即即A的的m个个行行向向量量是是线线性性无无关关的的。若若B是是A的的m阶阶满满秩秩子子阵阵，称称B为问题的一个基。为问题的一个基。B=(P1，P2，Pm)对应的变量对应的变量(x1，x2，xm)称为基变量称为基变量其它的变量称为非基变量；其它的变量称为非基变量；令非基变量等于令非基变量等于0，从方程组可以唯一解出基变量，从方程组可以唯一解出基变量的值，从而得到方程组的一个解，称为基本解；的值，从而得到方程组的一个解，称为基本解；如果它的各个分量非负，即它同时又是可行解，如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。则称之为基可行解，对应的基称为可行基。三、三、LP解的性质解的性质1.凸集和极点凸集和极点2.设设D为为n维空间的点集，若对任意维空间的点集，若对任意X1D，X2D，和实数和实数（01），），都有都有X1+（1）X2D，则称则称D为凸集。为凸集。凸集凸集D中如果不存在两个不同的点中如果不存在两个不同的点X1D，X2D，使，使X=X1+（1）X2（01）成立，那么点成立，那么点X称为极点。称为极点。2.线性规划解的性质线性规划解的性质定理定理1线性规划的可行域线性规划的可行域R是凸集。是凸集。证证对于对于LPmaxz=CXAX=bX0设设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）充分性。不妨设充分性。不妨设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不是基可行解，不是基可行解，则则X不是可行域的极点。不是可行域的极点。不失一般性，假设不失一般性，假设X的前的前m个个分量为正，则有分量为正，则有由由引理知引理知P1,P2,Pm线性相关，即存在不全为零的数线性相关，即存在不全为零的数使得使得（1）（2）令令则则设设则则（1）+（2）得：）得：（1）-（2）得：）得：又又即即X不是可行域的顶点。不是可行域的顶点。（2）X不是可行域的极点，不是可行域的极点，则则X不是基可行解。不是基可行解。不失一般性，设不失一般性，设不是可行域的极点不是可行域的极点存在两个不同的点存在两个不同的点有有X=Y+(1)Z即即因因故故时时故故因因（1）（2）（1）-（2）得：）得：因因故故P1,P2,Pr线性相关线性相关定理定理3线性规划如果有可行解，则一定有基可行解；线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。如果有最优解，则一定有基可行解是最优解。证证（1）不失一般性，假设可行解）不失一般性，假设可行解X的前的前m个个分量为正。分量为正。如果如果P1,P2,Pm线性无关，则线性无关，则X是是基可行解。基可行解。使得使得令令则则设设则则若若则则X2比比X少一个正分量，若少一个正分量，若X2的的m-1个个列向量列向量线性无关，则线性无关，则X2是基可行解，否则，重复以上过程，是基可行解，否则，重复以上过程，直到找到基可行解为止。直到找到基可行解为止。如果线性相关即存在不全为零的数如果线性相关即存在不全为零的数（2）设）设X0是是最优解，如果它不是基可行解，则有最优解，如果它不是基可行解，则有则则故故X1，X2也是最优解，如前所述，也是最优解，如前所述，X1，X2中中一定有一个点比一定有一个点比X0少少一个正分量。同理，如果一个正分量。同理，如果X1（X2）还不是基可行解，则还不是基可行解，则能找到第三个最优解，其正分量比能找到第三个最优解，其正分量比X1（X2）少一个，如此继少一个，如此继续下去，一定可以求得一个最优解，它的正分量是线性无关续下去，一定可以求得一个最优解，它的正分量是线性无关的，即这个最优解为基可行解。的，即这个最优解为基可行解。第三节单纯形法第三节单纯形法一、一、单纯形法的解题思路单纯形法的解题思路cjc1c2cmcm+1ckcnCBXBbx1x2xm xm+1xkxnc1c2cmx1x2xmb1b2bm100 a1m+1a1ka1n010 a2m+1a2ka2n001amm+1amkamnj000二、单纯形表二、单纯形表3.单纯形法的基本法则法则法则1最优性判定法则若对基可行解X1，所有检验数j0，则X1为最优解。法则法则2换入变量确定法则设，则xk为换入变量。法则法则3换出变量确定法则例例12求下列LP问题Cj0-130-20CBXBbx1x2x3x4x5x60 x1713-10200 x4120-241000 x6 100-43081j0-130-200 x11015/201/4203x330-1/211/4000 x610-5/20-3/481j01/20-3/4-20-1x242/5101/104/503x351/5013/102/500 x6 11100-1/2101j-1/500-4/5-12/50三、三、关于单纯形法的补充说明关于单纯形法的补充说明1.无穷多最优解与唯一最优解的判别法则若对某可行解X1，（1）所有检验数j0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数j0，但aik0，i=1，2，m即xk的系数列向量无正分量，则问题无最优解。3.求minz的情况直接计算最优性检验条件改为：所有j0；换入变量确定法则改为：如果则xk为换入变量。例例14求例2中的LPcj22300CBXBbx1x2x3x4x523x2x31/42/51/21/21001-1/4000-1/20j-1/2001/203/2023x1x31/23/20102-101-1/201/400-1/20j0101/403/20X*=(0.5,0,0.15,0,0)T，z=21/2+33/20=1.45第四节第四节初始可行基的求法初始可行基的求法人工变量法人工变量法一、大大M法法例例15求下列LP问题的最优解二、二、两阶段法两阶段法例例17cj0000011CBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-2101211000-10010001j6-1-30100010 x4x6x3101130-2-2100011000-10010-1-21j0-100103000 x4x2x3121130-2010001100-2-10210-5-21j0000011cj3-1-100CBXBbx1x2x3x4x50-1-1x4x2x3121130-2010001100-2-10j1000-13-1-1x1x2x34191000100011/302/3-2/3-1-4/3j000-1/3-1/3X*=(4，1，9，0，0)T，z*=2三、三、关于退化解的说明关于退化解的说明cj-1-1-41CBXBbx1x2x3x4-1-1x1x211100111-11j00-21-4-1x3x2101-10110-12j200-1-41x3x4101/2-1/21/21/21001j3/21/200第五节线性规划应用举例第五节线性规划应用举例建立LP模型步骤：（1）深入分析问题特点，适当选择决策变量；（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变量编号x2x4x6x1x7x3x5x8例例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=DACAAPABCBBPBDPD AC+AP+AH0AC+APAH0BC+BP+BH0BC+BPBH0DC+DPDH0AC+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+x9
