优化问题与规划问题.ppt

《优化问题与规划问题.ppt》由会员分享，可在线阅读，更多相关《优化问题与规划问题.ppt（56页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、3.6 3.6 优化问题与规划模型优化问题与规划模型第一页，编辑于星期六：十五点 五十九分。综合问题综合问题第二页，编辑于星期六：十五点 五十九分。一个城郊的社区计划更新消防站。一个城郊的社区计划更新消防站。原来的消防站在旧城中心。原来的消防站在旧城中心。规划要将新的消防站设置得更科学合理规划要将新的消防站设置得更科学合理在前一个季度收集了火警反应时间的资料：在前一个季度收集了火警反应时间的资料：平均要用平均要用3.23.2分钟派遣消防队员；分钟派遣消防队员；消防队员到达火灾现场的时间（行车时间）消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。依赖于火灾现场的距离。行车时间的资料列

2、于表行车时间的资料列于表1 1第三页，编辑于星期六：十五点 五十九分。距离距离1.22 3.485.103.394.131.752.951.300.762.521.661.84时间时间2.628.356.443.516.522.465.021.731.144.562.903.19距离距离3.194.113.094.961.643.233.074.264.402.422.96时间时间4.267.005.497.643.093.885.496.825.534.303.55表表1 1 行车时间行车时间第四页，编辑于星期六：十五点 五十九分。从社区的不同区域打来从社区的不同区域打来的求救电话频率的数的

3、求救电话频率的数据列于图据列于图1 1。其其中中每每一一格格代代表表一一平平方方英里，英里，格格内内的的数数字字为为每每年年从从此此区区域域打打来来的的紧紧急急求求救救电电话的数量。话的数量。30142121123253301285210010 63131023111第五页，编辑于星期六：十五点 五十九分。1）求反应时间。）求反应时间。消防队对离救火站消防队对离救火站r英里处打来的一个求救电英里处打来的一个求救电话需要的反应时间估计为话需要的反应时间估计为d分钟。分钟。给出消防队对求救电话的反应时间的模型给出消防队对求救电话的反应时间的模型d(r)2）求平均反应时间。）求平均反应时间。设设社社

4、区区位位区区域域0,6 0,6内内，(x,y)是是新新的的消消防防站的位置。站的位置。根根据据求求救救电电话话频频率率，确确定定消消防防队队对对求求救救电电话话的平均反应时间的平均反应时间z=f(x,y)第六页，编辑于星期六：十五点 五十九分。3）求新的消防站的最佳位置。）求新的消防站的最佳位置。即确定函数即确定函数f(x,y)的极小值点。的极小值点。首先，首先，第七页，编辑于星期六：十五点 五十九分。3.6 优化问题与规划模型优化问题与规划模型 优化问题：与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法：运筹学 运筹学主要分支：线性规划、非线性规划、动态规划、图与网络分析、存

5、贮论、排队伦、对策论、决策论。第八页，编辑于星期六：十五点 五十九分。6.1 线性规划线性规划 1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.第九页，编辑于星期六：十五点 五十九分。1.问题问题例1 家具生产的安排家具生产的安排 一.家具公司生产桌子和椅子，用于生产的 劳力共计450个工时，木材共有4立方米 每张桌子要使用15个工时，0.2立方木材 售价80元。每张椅子使用10个工时，0.05立方木材 售价45元。问为达到最大的收益，应如何安排生产？第十页，编辑于星期六：十五点 五十九分。分析：1.求什么

6、？生产多少桌子？生产多少椅子？2.优化什么？收益最大 3.限制条件？原料总量 劳力总数x1x2Max f=80 x1+45 x20.2 x1+0.05 x2 415 x1+10 x2 450第十一页，编辑于星期六：十五点 五十九分。模型I：以产值为目标取得最大收益.设：生产桌子 x1张,椅子 x2张,(决策变量)将目标优化为：max f=80 x1+45x2 对决策变量的约束：0.2x1+0.05x24 15x1+10 x2 450,x1 0,x2 0,第十二页，编辑于星期六：十五点 五十九分。规划问题规划问题：在约束条件下求目标函数的最优值点。规划问题规划问题包含3个组成要素:决策变量、目标

7、函数、约束条件。当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,否则称为非线性规划问题。第十三页，编辑于星期六：十五点 五十九分。2.2.线性规划问题求解方法线性规划问题求解方法称满足约束条件的向量为可行解可行解,称可行解的集合为可行域可行域,称使目标函数达最优值的可行解为最优解最优解.图解图解 法：法：(解两个变量的线性规划问题)在平面上画出可行域（凸多边形），计算目标函数在各极点(多边形顶点)处的值比较后，取最值点为最优解。第十四页，编辑于星期六：十五点 五十九分。命题 1 线性规划问题的可行解集是凸集 可行解集：线性不等式组的解 0.2x1+0.05x2=415x1+10

8、 x2=450第十五页，编辑于星期六：十五点 五十九分。命题2 线性规划问题的目标函数(关于不同的目标值是一族平行直线,目标值的大小描述了直线离原点的远近第十六页，编辑于星期六：十五点 五十九分。命题3 线性规划问题的最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).第十七页，编辑于星期六：十五点 五十九分。单纯形法单纯形法:通过确定约束方程组的基本解,并计算相应目标函数值,在可行解集的极点中搜寻最优解.1.模型的标准化 正则模型:决策变量:x1,x2,xn.目标函数:Z=c1x1+c2x2+cnxn.约束条件:a11x1+a1n

9、xnb1,am1x1+amnxnbm,第十八页，编辑于星期六：十五点 五十九分。模型的标准化 10.引入松弛变量将不等式约束变为等式约束 若有 ai1x1+ainxnbi,则引入xn+i 0,使得 ai1x1+ainxn+xn+i=bi 若有 aj1x1+ajnxnbj,则引入xn+j 0,使得 aj1x1+ajnxn-xn+j=bj.且有 Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m.第十九页，编辑于星期六：十五点 五十九分。20.将目标函数的优化变为目标函数的极大化.若求 min Z,令 Z=Z,则问题变为 max Z.30.引入人工变量,使得所有变量均为非负.若 xi 没

10、有非负的条件,则引入 xi 0 和 xi0,令 xi=xi xi,则可使得问题的全部变量均非负.第二十页，编辑于星期六：十五点 五十九分。标准化模型 求变量 x1,x2,xn,max Z=c1x1+cnxn,s.t.a11x1+a1nxn=b1,am1x1+amnxn=bm,x1 0,xn 0,第二十一页，编辑于星期六：十五点 五十九分。定义:若代数方程AX=B的解向量有n-m个分量为零,其余m个分量对应A的m个线性无关列,则称该解向量为方程组的一个基本解.在一个线性规划问题中,如果一个可行解也是约束方程组的基本解,则称之为基本可行解命题 4 一个向量 x 是线性规划问题可行解集的一个极点,当

11、且仅当它是约束方程的一个基本可行解.第二十二页，编辑于星期六：十五点 五十九分。一般线性规划的数学模型及解法：min f=cTxs.t.Ax b A1x=b1 LB x UBMatlab求解程序x,f=linprog(c,A,b,A1,b1,LB,UB)第二十三页，编辑于星期六：十五点 五十九分。模型 II.在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。设每立方木材和每个工时投入“成本”分别为 y1 y2(决策变量)则目标函数为：g=4y1+450y2对决策变量的约束 0.2y1+15y2 80 0.05y1+10y2 45 y1 0,y2 0 得 y1=100（元/m3），

12、y2=4（元/工时）第二十四页，编辑于星期六：十五点 五十九分。3.对偶问题对偶问题：A 是m n 矩阵，c 是 n 1向量，b 是 m 1向量 x 是 n 1向量,y 是 m 1向量问题max f=cTxs.t.Ax b xi 0,i=1,2,n.对偶问题min f=bTys.t.ATy cyi 0,i=1,2,m.第二十五页，编辑于星期六：十五点 五十九分。对偶定理对偶定理:互为对偶的两个线性规划问题,若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解 第二十六页，编辑于星期六：十五点 五十九分。模型I 给出了生产中的产品的最优分

13、配方案模型 II 给出了生产中资源的最低估价.这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出 的贡献确定的估价,被称为“影子价格影子价格”.第二十七页，编辑于星期六：十五点 五十九分。例2.生产5种产品P1,P2,P3,P4,P5 单价为550,600,350,400,200.三道工序:研磨、钻孔、装配。所需工时为 P1 P2 P3 P4 P5 I 12 20 0 25 15 II 10 8 16 0 0 III 20 20 20 20 20各工序的生产能力（工时数）288 192 384如何安排生产，收入最大。第二十八页，编辑于星期六：十五点 五十九分。模型：设 xi

14、 生产 Pi 的件数。则max Z=550 x1+600 x2+350 x3+400 x4+200 x5。s.t.12 x1+20 x2+0 x3+25 x4+15 x5 288 10 x1+8 x2+16 x3+0 x4+0 x5 192 20 x1+20 x2+20 x3+20 x4+20 x5 384 xi 0有解 x1=12，x2=7.2，x3=x4=x5=0 Z=10920第二十九页，编辑于星期六：十五点 五十九分。1.如果增加三个工序的生产能力，每个工序的单位增长会带来多少价值？2.结果表明与 P1,P2相比 P3,P4,P5，定价低了.价格提到什么程度,它们才值得生产?对偶问题有

15、解:w1=6.25,w2=0,w3=23.75 Zopt=6.25288+0192+23.75384X3的成本:0 6.25+16 0+20 23.75=475350第三十页，编辑于星期六：十五点 五十九分。4.非线性规划非线性规划 min z=f(z)s.t.A1xb1,A2x=b2,c1(x)0,c2(x)=0 LB x UBMATLAB 程序程序 x,z=fmincon(fun,x0,A1,b,A2,b2,LB,UB,nonlcon）第三十一页，编辑于星期六：十五点 五十九分。例例3.某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水

16、泥日用量水泥日用量di(单位：吨）单位：吨）建两个日储量建两个日储量e为为20吨的料场，需要确定料场位置吨的料场，需要确定料场位置(xj,yj)和运量和运量cij，使总吨公里数最小。，使总吨公里数最小。第三十二页，编辑于星期六：十五点 五十九分。第三十三页，编辑于星期六：十五点 五十九分。min z=f(z)s.t.A1xb1,A2x=b2,c1(x)0,c2(x)=0 LB x UBMATLAB 程序程序 x,z=fmincon(fun,x0,A1,b,A2,b2,LB,UB,nonlcon）第三十四页，编辑于星期六：十五点 五十九分。用随机搜索算法确定初始点：用随机搜索算法确定初始点：在可

17、行域在可行域0.5,8.75 0.75,7.75内简单地选内简单地选取取n个随机的的点，个随机的的点，计算目标函数在这些点的值，选择其中计算目标函数在这些点的值，选择其中最小的点即可。最小的点即可。然后，可采用然后，可采用Matlab求最值点程序求出求最值点程序求出精确的最小值点精确的最小值点:求函数求函数fun在在x0点附近点附近的最小值点的最小值点 第三十五页，编辑于星期六：十五点 五十九分。随机搜索程序的为代码算法算法：随机搜索法随机搜索法变量：变量：xl=x的下限的下限 xu=x的上限的上限 yl=y的下限的下限 yu=y的上限的上限 N=迭代次数迭代次数 xm=极小点极小点x的近似值

18、的近似值 ym=极小点极小点y的近似值的近似值 zm=极小点极小点f(x,y)的近似值的近似值输入：输入：xl，xu，yl，yu过程：开始过程：开始 xrandomxlrandomxl，xuxu yrandomyl yrandomyl，yuyu zmf(x,y)zmf(x,y)对对n=1到到N循环循环 开始开始 xrandomxl，xu yrandomyl，yu zf(x,y)若若zzm，则，则 xmx ymy zm z 结束结束 结束结束输出：输出：xm，ym，zm第三十六页，编辑于星期六：十五点 五十九分。5.0-1规划 如果要求决策变量只取0 或 1的线性规划问题,称为整数规划.0-1

19、约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进问题的 第三十七页，编辑于星期六：十五点 五十九分。例4 背包问题背包问题 一个旅行者的背包最多只能装 6 kg 物品.现有4 件物品 重量为 2 kg,3 kg,3 kg,4 kg,价值为 1 元,1.2元,0.9元,1.1元.应携带那些物品使得携带物品的价值最大?建模:记xj：旅行者携带第 j 件物品的件数,xj=0,1.约束条件 2x 1+3x 2+3x 3+4x 4 6 求xj使目标函数 f=x1+1.2x2+0.9x3+1.1x4最大.第三十八页，编辑于星期六：十五点 五十九分。用Lingo 软件求解0-1规划Linear In

20、teractive and General OptimizerModel:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x40表示每件第 j 类仪器的科学价值;aj0表示每件第 j 类仪器的重量.每类仪器件数不限,但装载件数只能是整数.飞船总载荷不得超过数 b.设计一种方案,使得被装载仪器的科学价值之和最大.第四十三页，编辑于星期六：十五点 五十九分。建模 记 xj 为第 j 类仪器的装载数.求 各种仪器的装载数量 xj（整数）在约束条件 jaj xj b 下,使得目标函数 f=j cj xj达到最大值.第四十四页，编辑于星期六：十五点 五十九分。7

21、.用Lindo软件求解整数规划Linear Interactive and Discrete optimizermax 3x1+2x2st2x1+3x2=142x1+x2=9endgin x1gin x2(或者用 gin 2)求 整数 x1,x2Max Z=3x1+2x2s.t.2x1+3x2142x1+x2 9第四十五页，编辑于星期六：十五点 五十九分。8.规划问题的建模艺术规划问题的建模艺术将实际问题归结为线性规划模型是一个探将实际问题归结为线性规划模型是一个探索创造的过程。索创造的过程。第四十六页，编辑于星期六：十五点 五十九分。例7 钢材截短钢材截短 有一批钢材,每根长7.3米.现需做

22、100套短钢材.每套包括长2.9米,2.1米,1.5米的各一根.至少用掉多少根钢材才能满足需要,并使得用料最省.第四十七页，编辑于星期六：十五点 五十九分。解:可能的截法和余料第1种 7.3-(2.92+1.51)=0第2种 7.3-(2.91+2.12)=0.2第3种 7.3-(2.91+1.52)=1.4第4种 7.3-(2.91+2.11+1.51)=0.8第5种 7.3-(2.12+1.52)=0.1第6种 7.3-(2.13)=1第7种 7.3-(2.11+1.53)=0.7第8种 7.3-(1.54)=1.3第四十八页，编辑于星期六：十五点 五十九分。设按第i种方法截 xi 根钢材

23、(决策变量).目标函数f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8约束条件2x1+x2+x3+x4 1002x2+x4+2x5+3x6+x7 100 x1+2x3+x4+2x5+3x7+4x8 100 xi 0,i=1,8 第四十九页，编辑于星期六：十五点 五十九分。用Matlab程序解得 x1=40 x2=20 x5=30,f=7 （实际上应要求xi 为正整数。这是一个整数规划问题）。第五十页，编辑于星期六：十五点 五十九分。例 8 存储问题存储问题有5种药品 S=1,2,3,4,5 要存放,有些药品不能存放在一起,能存放在一起存放的药品为的 =1,2,1

24、,3,5,2,4,5,3,1,4,5不同的组合所需的存放费用费用不同其中第 i 种组合的存储费用为 cj,求这五种药品费用最低 的储存方案。第五十一页，编辑于星期六：十五点 五十九分。令xi 为存储组合 i 的决策变量:xi=1 时存储第 i 个组合,否则 xi=0求存储方案x=(x1,x2,x3,x4,x5,x6)在约束条件 x1+x2 +x51 x1+x3 1 x2 +x4 1 x3+x6 1 x2 +x3+x6 1 xi0，1，i=1,2,6,下使得目标函数 f=cixi 最小.第五十二页，编辑于星期六：十五点 五十九分。习题 一 资源的最优配置策略资源的最优配置策略某工厂有1000台机

25、器,生产两种产品 A,B,若投入 y 台机器生产A 产品,则纯收入为 5y.若投入 y 台机器生产B 产品,则纯收入为 4y.又知,生产A 种产品机器的年折损率为20%,生产B 种产品机器的年折损率为10%,问在5年内如何安排各年度的生产计划,才能使总收入最高.第五十三页，编辑于星期六：十五点 五十九分。习题二 一家出版社准备再某市开设两个销售点，向七个区的大学生售书。每个区的大学生数量（千人）如图。每个销售点只能向本区和一个相邻区的大学生售书。这两个销售点应该设在何处，才能使所供应的学生数量最大。34 29 56 42 21 18 71第五十四页，编辑于星期六：十五点 五十九分。习题三 混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据 4位运动员的4种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。蛙泳 蝶泳 自由泳 仰泳 甲 99 60 59 73 乙 79 65 93 87 丙 67 93 63 81 丁 56 79 86 76 第五十五页，编辑于星期六：十五点 五十九分。第五十六页，编辑于星期六：十五点 五十九分。