OPERATIONSRESEARCH运筹学怎样把事情做到最好.ppt

OPERATIONSRESEARCH运筹学,怎样把事情做到最好,第一章绪论,1.1题解Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本运用学港台作业研究中国大陆运筹学OperationalResearch原来名称，意为军事行动研究历史渊源,绪论,1.2运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang1917排队论Harris1920存储论Levinson1930零售贸易康脱洛维奇1939LP,绪论,1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队,绪论,1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题,1.3学科性质,应用学科Morse饲料IIx2kg;饲料IIIx3kg目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x150,x260,x350,x470,x540非负性要求：x10,x20,x30,x40,x50,例题3：人员安排问题,医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：,例题3建模,目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x270 x2+x360 x3+x450 x4+x520 x5+x630非负性约束：xj0,j=1,2,6,归纳：线性规划的一般模式,目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn约束条件：a11x1+a12x2+a13x3+a1nxn(=)b1a21x1+a22x2+a23x3+a2nxn(=)b2am1x1+am2x2+am3x3+amnxn(=)bn非负性约束：x10,x20,xn0,2.1.2线性规划图解法,由中学知识可知：y=ax+b是一条直线，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一条直线，以Z为参数的一族等值线。9x1+4x2360x1360/9-4/9x2是直线x1=360/9-4/9x2下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。,例1图示,.,9080604020,020406080100,x1,x2,9x1+4x2360,4x1+5x2200,3x1+10 x2300,A,B,C,D,E,F,G,H,I,Z=70 x1+120 x2,概念,概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形,结论,可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形,2.1.3线性规划的标准型,代数式maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmxj0j=1,2,n,线性规划的标准型,和式：maxZ=cjxjaijxj=bii=1,2,mxj0j=1,2,n,j=1,n,n,j=1,线性规划的标准型,向量式：maxZ=CXpjxj=bii=1,2,mxj0j=1,2,nC=(c1,c2,c3,cn)X=(X1,X2,X3,Xn)T,n,j=1,线性规划的标准型,矩阵式：maxZ=CXAX=bX0其中：b=(b1,b2,bm)Ta11a12.a1nA=a21a22a2nam1am2amn,标准型的特征,目标函数极大化约束条件为等式决策变量非负,非标准型转化为标准型,目标函数极小化转为极大化：minZ=max(Z)，一个数的极小化等价于其相反数的极大化。不等式约束的转化：aijxjbi加入松弛变量aijxjbi减去剩余变量非正变量：即xk0则令xk=xk自由变量：即xk无约束，令xk=xkx”k,非标准型转化举例之一,maxZ=70X1+120X2maxZ=70X1+120X29X1+4X23609X1+4X2+X3=3604X1+5X22004X1+5X2+x4=2003X1+10X23003X1+10X2+x5=300X10X20Xj0j=1,2,5,非标准型转化举例之二,minZ=x1+2x2-3x3maxZ=x12x2+3(x3x”3)x1+x2+x39x1+x2+x3x”3+x4=9-x1-2x2+x32x12x2+x3x”3-x5=23x1+x2-3x3=53x1+x23(x3x”3)=5x10 x20 x3无约束x10 x20 x30 x”30 x40 x50,2.1.4基可行解,基的概念：如前所述LP标准型和式：maxZ=cjxjaijxj=bixj0j=1,2,n矩阵式：maxZ=CXAX=bX0约束方程的系数矩阵A的秩为m，且m0=bL/aLk。这时原基变量XL=0，由基变量变成非基变量，aLk处在变量转换的交叉点上，称之为枢轴元素,j0,单纯形法解题举例,单纯形表的格式：,2.2.3单纯形法的计算步骤,找到初始可行基，建立单纯形表计算检验数，若所有j0则得最优解，结束。否则转下步若某K0而PK0，则最优解无界，结束。否则转下步根据maxj=K原则确定XK进基变量；根据规则：=minbi/aikaik0=bL/aLk确定XL为出基变量以aLk为枢轴元素进行迭代，回到第二步,2.3单纯形法的进一步探讨,2.3.1极小化问题直接求解：检验数的判别由所有j0即为最优，变为所有j0则为最优。人工变量法之一：大M法人工变量价值系数M例人工变量法之二：构造目标函数，分阶段求解例2.3.2无穷多最优解情形：非基变量检验数j=02.3.3退化解的情形：有两个以上值相等,2.3.4单纯形法的计算机求解,程序说明应用举例例题1例题2,2.5LP应用举例之一,例13合理下料问题料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。,应用举例之二,例14混合配方问题A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量。,应用举例之三,例15.滚动投资问题兹有100万元闲钱，投资方向有四：,第四年,第一年,第二年,第三年,A项目110%,B项目135%,C项目125%,D项目104%,第五年,各年投资什么项目，使第五年末资本总额为最大？,应用举例之四,例16动态生产计划问题工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。设第月正常生产xj件，加班生产件yj，存储zj件。则：本期生产+上期库存-本期库存=本期需求,第三章对偶问题与灵敏度分析,要求：了解LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容,3.1对偶问题,3.1.1对偶问题的提出回顾例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？,对偶模型,设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。出租收入不低于生产收入：9y1+4y2+3y3704y1+5y2+10y3120目标：=360y1+200y2+300y3出租收入越多越好？至少不低于某数,原问题与对偶问题之比较,原问题：对偶问题：maxZ=70X1+120X2min=360y1+200y2+300y39X1+4X23609y1+4y2+3y3704X1+5X2200(3.1)4y1+5y2+10y3120(3.2)3X1+10X2300y10,y20,y30X10X20,3.1.2对偶规则,原问题一般模型：对偶问题一般模型：maxZ=CXmin=YbAXbYACX0Y0,对偶规则,原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反,对偶规则,.,对偶规则简捷记法,原问题标准则对偶问题标准原问题不标准则对偶问题不标准例题2max=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y332x1+x2-4x3+x4+3x57y1+3y32x1+2x3-x44-4y1+2y2-6-x1+3x2-x4+x5=-2y1-y2-y30 x1，x2，x30;3y1+y3=1x40;x5无限制y10y20y3无约束,3.1.3对偶问题的基本性质,对称性：对偶问题的对偶问题是原问题弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值(鞍型图)无界性：原问题无界，对偶问题无可行解对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1,3.1.4对偶最优解的经济解释影子价格,Z=CX=YbZ/b=(Yb)=YZ=Yb=yibi的意义：Y是检验数的反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。结合例题1讲解影子价格：y1=0:第一种资源过剩y2=13.6：设备台时最紧张，每增加一个台时，利润增加13.6元。y3=5.2影子价格所含有的信息：1、资源紧缺状况2、确定资源转让基价参见：P403、取得紧缺资源的代价,3.2灵敏度分析,为什么进行灵敏度分析？灵敏度分析的两把尺子：j=Cj-CBB-1pj0；xB=B-1b03.2.1价值系数的灵敏度分析Cj变化到什么程度可以保持最优基不变？用（参看P96）例题4：87.5C2233.33；36C196,灵敏度分析,右端项的灵敏度分析：bi变化到什么程度可以保持最优基不变？用尺度xB=B-1b0例题5：1-3.121.16360B-1b=00.4-0.220000-0.120.16b3b3的变化范围：227.586b3400,其它形式的灵敏度分析,新产品的分析：在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。例题6：新增一种C产品，单位利润110元，使用劳动力6工时，设备5台时，原材料7公斤，问要否调整产品结构？先算检验数j=Cj-CBB-1pj6=C6-YP6=110-（0，13.6，5.2）（6，5，7）T=110-104.4=5.6大于零，有利可图，将P6左乘B-1，加入到末表之中，继续迭代，直到求得最优解。,3.3用计算机进行灵敏度分析,例题7参见P102,习题课：,P782.10（1）唯一最优解：H30，H50，H10（2）无穷多最优解：H3=0，H10，H50，H20或H5=0，H10，H30，H40（3）无界解：H50，H40，H10，H30（4）退化最优解：H1=0，H30，H50（5）非最优解，X1进基，X2出基：H10，H30，H20，,5,H2,H1,7,习题课：,P792.111、对2、错，可能有最优解3、对4、对5、错6、错7、错在“可行”8、对9、错,习题课：,P812.16设白天电视广告X1个，黄金时间电视广告X2个，广播广告X3个，杂志广告X4个maxZ=40X1+90X2+50X3+2X48X1+15X2+6X3+3X41630X1+40X2+20X3+X42008X1+15X210X13X22X35X310X45X410Xj0j=1、2、3、4,习题课：,P812.17设A产品生产X1单位，B产品生产X2单位，C产品销毁X3单位maxZ=5X1+10X2+3（2X2-X3）-1X32X1+3X22003X1+