运筹学案例.pptx

OR11OPERATIONS RESEARCH 运筹学怎样把事情做到最好郝英奇OR12第一章 绪论w1.1题解 Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本运用学 港台作业研究中国大陆运筹学Operational Research原来名称，意为军事行动研究历史渊源OR13绪论w1.2 运筹学的历史 早期运筹思想：田忌赛马 丁渭修宫 沈括运粮 Erlang 1917 排队论 Harris 1920 存储论 Levinson 1930 零售贸易 康脱洛维奇 1939 LP OR14绪论w1.2运筹学的历史 军事运筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队OR15绪论w1.2运筹学的历史 管理运筹学阶段 战后人员三分:军队、大学、企业 大学：课程、专业、硕士、博士 企业：美国钢铁联合公司 英国国家煤炭局 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题 OR161.3学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。OR171.4定性与定量w例：店主进货w两者都是常用的决策方法w定性是基础，定量是工具，定量为定性服务。w定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。OR181.5运筹学的模型w模型：真实事物的模仿，主要因素、相互关系、系统结构。w形象模型：如地球仪、沙盘、风洞w模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。w数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk)G(xi,yj,uk)0OR191.6运筹学的学科体系w规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划w图论与网络w存储论w排队论w决策论w对策论w计算机仿真OR1101.7运筹学的工作步骤w确定问题w搜集数据建立模型w检验模型w求解模型w结果分析w结果实施OR1111.8运筹学与计算机w计算机为运筹学提供解题工具。w本书有现成的程序可以利用w要学会解题的思路与方法，建立模型很重要。OR112第二章 线性规划与单纯形法w2.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。OR1132.1.1 LP的数学模型 例题1生产计划问题w某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120OR114例题1建模w问题：如何安排生产计划，使得获利最多？w步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20OR115例题2配方问题w养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200OR116例题2建模w设抓取饲料I x1kg;饲料II x2kg;饲料III x3kgw目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5w约束条件：3x2+2x2+x3+6x4+18x5 700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1 50,x2 60,x3 50,x4 70,x5 40非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0 OR117例题3：人员安排问题w医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：序号时段最少人数安排人数1061060X12101470X23141860X34182250X45220220X56020630 x6OR118例题3建模w目标函数：min Z=x1+x2+x3+x4+x5+x6w约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30非负性约束：xj 0,j=1,2,6OR119归纳：线性规划的一般模式w目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxnw约束条件：a11x1+a12x2+a13x3+a1nxn(=)b1 a21x1+a22x2+a23x3+a2nxn(=)b2 am1x1+am2x2+am3x3+amnxn(=)bn非负性约束：x1 0,x2 0,xn 0OR1202.1.2线性规划图解法w由中学知识可知：y=ax+b是一条直线，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一条直线，以Z为参数的一族等值线。9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。OR121例1图示.90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2OR122概念w概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形OR123结论w可行域是个凸集w可行域有有限个顶点w最优值在可行域的顶点上达到w无穷多解的情形w无界解情形w无解情形OR1242.1.3线性规划的标准型w代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,nOR125线性规划的标准型w和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=1OR126线性规划的标准型w向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2c3,cn)X=(X1,X2,X3,Xn)Tnj=1OR127线性规划的标准型w矩阵式：maxZ=CX AX=b X 0 其中：b=(b1,b2,bm)T a11 a12.a1n A=a21 a22 a2n am1 am2 amnOR128标准型的特征w目标函数极大化w约束条件为等式w决策变量非负OR129非标准型转化为标准型w目标函数极小化转为极大化：minZ=max(Z)，一个数的极小化等价于其相反数的极大化。w不等式约束的转化：aijxjbi 加入松弛变量 aijxjbi 减去剩余变量w非正变量：即xk 0 则令xk=xk 自由变量：即xk无约束，令xk=xkx”kOR130非标准型转化举例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2+x4=200 3X1+10X2 300 3X1+10X2+x5=300 X10 X20 Xj0 j=1,2,5OR131非标准型转化举例之二之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3)x1+x2+x3 9 x1+x2+x3 x”3+x4=9-x1-2x2+x3 2 x12x2+x3 x”3-x5=2 3x1+x2-3x3=5 3x1+x23(x3 x”3)=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 OR1322.1.4基可行解w基的概念基的概念：如前所述LP标准型和式：maxZ=cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A的秩为m，且m0 =bL/aLk。这时原基变量XL=0，由基变量变成非基变量，aLk处在变量转换的交叉点上，称之为枢轴元素j 0OR141单纯形法解题举例单纯形表的格式：CjC1 C2 Cn i CBXBbx1 x2 .xn C1 C2 Cmx1x2xmb 1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n OR142 CjC1 C2 CnCBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100j3600 34 0 0 0 -12701200X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -52OR1432.2.3单纯形法的计算步骤w找到初始可行基，建立单纯形表w计算检验数，若所有j 0 则得最优解，结束。否则转下步w若某K 0而PK 0，则最优解无界，结束。否则转下步w根据max j =K 原则确定XK 进基变量；根据规则：=min bi/aik aik 0=bL/aLk 确定XL为出基变量w以aLk 为枢轴元素进行迭代，回到第二步OR1442.3单纯形法的进一步探讨w2.3.1极小化问题直接求解：检验数的判别由所有j 0 即为最优，变为所有j 0则为最优。w人工变量法之一：大M法 人工变量价值系数M例w 人工变量法之二：构造目标函数，分阶段求解例w2.3.2无穷多最优解情形：非基变量检验数 j=0w2.3.3退化解的情形：有两个以上 值相等OR1452.3.4单纯形法的计算机求解w程序说明w应用举例例题1例题2OR1462.5LP应用举例之一w例13合理下料问题料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。方案料型 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合计 残料 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4OR147应用举例之二 w例14混合配方问题A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量。OR148应用举例之三w例15.滚动投资问题兹有100万元闲钱，投资方向有四：第四年第一年第二年第三年A项目110%B项目135%C项目125%D项目104%第五年各年投资什么项目，使第五年末资本总额为最大？OR149应用举例之四w例16动态生产计划问题 工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。设第月正常生产xj件，加班生产件yj，存储zj件。则：本期生产+上期库存-本期库存=本期需求OR150第三章 对偶问题与灵敏度分析w要求：了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 理解计算机输出的影子价格与灵敏度分 析的内容OR1513.1 对偶问题w3.1.1 对偶问题的提出 回顾例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？产品A产品B资源限制劳动力设备原材料 9 4 3 4 5 10 360 200 300单位利润 70 120OR152对偶模型w设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。出租收入不低于生产收入：9y1+4y2+3y3 70 4y1+5y2+10y3 120目标：=360y1+200y2+300y3出租收入越多越好？至少不低于某数OR153原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200 (3.1)4y1+5y2+10y3 120 (3.2)3X1+10X2 300 y1 0,y2 0,y3 0X10 X20OR1543.1.2对偶规则原问题一般模型：对偶问题一般模型：maxZ=CX min=Yb AX b YA C X 0 Y 0OR155对偶规则w原问题有m个约束条件，对偶问题有m个变量w原问题有n个变量，对偶问题有n个约束条件w原问题的价值系数对应对偶问题的右端项w原问题的右端项对应对偶问题的价值系数w原问题的技术系数矩阵转置后为对偶问题系数矩阵w原问题的约束条件与对偶问题方向相反w原问题与对偶问题优化方向相反OR156对偶规则.原问题 对偶问题目标函数 max min 目标函数约束条件 =变量无约束 变量符号 无约束 约束条件=OR157对偶规则简捷记法w原问题标准则对偶问题标准w原问题不标准则对偶问题不标准w例题2 max=7y1+4y2-2y3minZ=3x12x2-6x3+x5 2y1+y2-y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+2x3-x4 4 -4y1+2y2 -6 -x1+3x2 -x4+x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0;3y1 +y3=1 x4 0;x5无限制 y1 0y2 0y3 无约束 OR1583.1.3对偶问题的基本性质w对称性：对偶问题的对偶问题是原问题w弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图)w无界性：原问题无界，对偶问题无可行解w对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1OR1593.1.4对偶最优解的经济解释影子价格wZ=CX=Yb Z/b=(Yb)=YwZ=Yb=yibi的意义：Y是检验数的反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。w结合例题1讲解影子价格：y1=0:第一种资源过剩 y2=13.6：设备台时最紧张，每增加一个台时，利润增加13.6元。y3=5.2w影子价格所含有的信息：1、资源紧缺状况 2、确定资源转让基价参见：P40 3、取得紧缺资源的代价OR1603.2灵敏度分析w为什么进行灵敏度分析？w灵敏度分析的两把尺子：j=Cj-CBB-1pj 0；xB=B-1b 032.1 价值系数的灵敏度分析 Cj变化到什么程度可以保持最优基不变？用 （参看P96）例题4：87.5 C2 233.33；36 C1 96OR161灵敏度分析w右端项的灵敏度分析：bi变化到什么程度可以保持最优基不变？用尺度 xB=B-1b 0例题5：1 -3.12 1.16 360 B-1b=0 0.4 -0.2 200 0 0 -0.12 0.16 b3 b3的变化范围：227.586 b3 400OR162其它形式的灵敏度分析 新产品的分析：新产品的分析：在资源结构没有变化的条件下，是否生产这种新 产品，就看它的竞争力如何。例题6：新增一种C产品，单位利润110元，使用劳动力6工时，设备5台时，原材料7公斤，问要否调整产品结构？先算检验数j=Cj-CBB-1pj 6=C6-YP6=110-（0，13.6，5.2）（6，5，7）T =110-104.4=5.6 大于零，有利可图，将P6左乘B-1，加入到末表之中，继续迭代，直到求得最优解。OR1633.3用计算机进行灵敏度分析w例题7 参见P102OR164习题课：wP782.10（1）唯一最优解：H3 0，H5 0，H1 0（2）无穷多最优解：H3=0，H1 0，H5 0，H20 或 H5=0，H1 0，H3 0，H40（3）无界解：H50，H4 0，H1 0，H3 0（4）退化最优解：H1=0，H3 0，H5 0（5）非最优解，X1进基，X2出基：H1 0，H30，H20，5H2H17OR165习题课：wP792.11w1、对 2、错，可能有最优解 3、对w4、对 5、错 6、错 7、错在“可行”w8、对 9、错 OR166习题课：wP812.16w设白天电视广告X1个，黄金时间电视广告X2个，广播广告X3个，杂志广告X4个wmaxZ=40X1+90X2+50X3+2X4 8X1+15X2+6X3+3X4 16 30X1+40X2+20X3+X4 200 8X1+15X2 10 X1 3 X2 2 X3 5 X3 10 X4 5 X4 10 X j0 j=1、2、3、4OR167习题课：wP812.17w设A产品生产X1单位，B产品生产X2单位，C产品销毁X3单位wmaxZ=5X1+10X2+3（2X2-X3）-1X3w2X1+3X2 200w3X1+4X2 240w2X2-X3 10 X1、X2、X3 0OR168习题课：wP1073.2w1、对，根据若对偶性w2、对，同上w3、对，同上w4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度w5、对，根据强对偶定理OR169习题课wP1073.5 注：目标函数为最大化w1、这是线性规划的逆运算w对偶问题最优解：wY1=4、Y2=2、Y3=0、Y4=4、Y5=0OR170习题课wP1093.8w1、原问题的最优解：X1=6，X5=10，其余为零;对偶问题最优解：Y1=2,Y2=0wC1的变化范围：以C1代入末表，C1 1w右端项变化范围：xB=B-1b 0wb1-6，b2-10