优化问题与规划模型的讲解.ppt

优化问题与规划模型的讲解.ppt

《优化问题与规划模型的讲解.ppt》由会员分享，可在线阅读，更多相关《优化问题与规划模型的讲解.ppt（56页珍藏版）》请在冰点文库上搜索。

3.63.6优化问题与规划模型优化问题与规划模型综合问题综合问题一个城郊的社区计划更新消防站。

一个城郊的社区计划更新消防站。

原来的消防站在旧城中心。

原来的消防站在旧城中心。

规划要将新的消防站设置得更科学合理规划要将新的消防站设置得更科学合理在前一个季度收集了火警反应时间的资料：

在前一个季度收集了火警反应时间的资料：

平均要用平均要用3.23.2分钟派遣消防队员；分钟派遣消防队员；消防队员到达火灾现场的时间（行车时消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。

间）依赖于火灾现场的距离。

行车时间的资料列于表行车时间的资料列于表113.554.305.536.825.493.883.097.645.497.004.26时间时间2.962.424.404.263.073.231.644.963.094.113.19距离距离3.192.904.561.141.735.022.466.523.516.448.352.62时间时间1.841.662.520.761.302.951.754.133.395.103.481.22距离距离表表11行车时间行车时间从社区的不同区域打从社区的不同区域打来的求救电话频率的来的求救电话频率的数据列于图数据列于图11。

其中每一格代表一平其中每一格代表一平方英里，方英里，格内的数字为每年从格内的数字为每年从此区域打来的紧急求此区域打来的紧急求救电话的数量。

救电话的数量。

11132013136100012582103352321121241031）求反应时间。

）求反应时间。

消防队对离救火站消防队对离救火站r英里处打来的一个求救英里处打来的一个求救电话需要的反应时间估计为电话需要的反应时间估计为d分钟。

分钟。

给出消防队对求救电话的反应时间的模型给出消防队对求救电话的反应时间的模型d（r）2）求平均反应时间。

）求平均反应时间。

设社区位区域设社区位区域0,60,6内，内，（x,y）是新的消是新的消防站的位置。

防站的位置。

根据求救电话频率，确定消防队对求救电话根据求救电话频率，确定消防队对求救电话的平均反应时间的平均反应时间z=f（x,y）3）求新的消防站的最佳位置。

）求新的消防站的最佳位置。

即确定函数即确定函数f（x,y）的极小值点。

的极小值点。

首先，首先，3.6优化问题与规划模型优化问题与规划模型优化问题：

与最大、最小、最长、最短等等有关的问题。

解决最优化问题的数学方法：

运筹学运筹学主要分支：

线性规划、非线性规划、动态规划、图与网络分析、存贮论、排队伦、对策论、决策论。

6.1线性规划线性规划1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.1.问题问题例1家具生产的安排家具生产的安排一.家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米每张桌子要使用15个工时，0.2立方木材售价80元。

每张椅子使用10个工时，0.05立方木材售价45元。

问为达到最大的收益，应如何安排生产？

分析：

1.求什么？

生产多少桌子？

生产多少椅子？

2.优化什么？

收益最大3.限制条件？

原料总量劳力总数x1x2Maxf=80x1+45x20.2x1+0.05x2415x1+10x2450模型I：

以产值为目标取得最大收益.设：

生产桌子x1张,椅子x2张,（决策变量）将目标优化为：

maxf=80x1+45x2对决策变量的约束：

0.2x1+0.05x2415x1+10x2450,x10,x20,规划问题规划问题：

在约束条件下求目标函数的最优值点。

规划问题规划问题包含3个组成要素:

决策变量、目标函数、约束条件。

当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,否则称为非线性规划问题。

2.2.线性规划问题求解方法线性规划问题求解方法称满足约束条件的向量为可行解可行解,称可行解的集合为可行域可行域,称使目标函数达最优值的可行解为最优解最优解.图解法：

图解法：

（解两个变量的线性规划问题）在平面上画出可行域（凸多边形），计算目标函数在各极点（多边形顶点）处的值比较后，取最值点为最优解。

命题1线性规划问题的可行解集是凸集可行解集：

线性不等式组的解0.2x1+0.05x2=415x1+10x2=450命题2线性规划问题的目标函数（关于不同的目标值是一族平行直线,目标值的大小描述了直线离原点的远近命题3线性规划问题的最优解一定在可行解集的某个极点上达到（穿过可行域的目标直线组中最远离（或接近）原点的直线所穿过的凸多边形的顶点）.单纯形法单纯形法:

通过确定约束方程组的基本解,并计算相应目标函数值,在可行解集的极点中搜寻最优解.1.模型的标准化正则模型:

决策变量:

x1,x2,xn.目标函数:

Z=c1x1+c2x2+cnxn.约束条件:

a11x1+a1nxnb1,am1x1+amnxnbm,模型的标准化10.引入松弛变量将不等式约束变为等式约束若有ai1x1+ainxnbi,则引入xn+i0,使得ai1x1+ainxn+xn+i=bi若有aj1x1+ajnxnbj,则引入xn+j0,使得aj1x1+ajnxn-xn+j=bj.且有Z=c1x1+c2x2+cnxn+0xn+1+0xn+m.20.将目标函数的优化变为目标函数的极大化.若求minZ,令Z=Z,则问题变为maxZ.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入xi0和xi0,令xi=xixi,则可使得问题的全部变量均非负.标准化模型求变量x1,x2,xn,maxZ=c1x1+cnxn,s.t.a11x1+a1nxn=b1,am1x1+amnxn=bm,x10,xn0,0.max,xbxAtsxcZxT求定义:

若代数方程AX=B的解向量有n-m个分量为零,其余m个分量对应A的m个线性无关列,则称该解向量为方程组的一个基本解.在一个线性规划问题中,如果一个可行解也是约束方程组的基本解,则称之为基本可行解命题4一个向量x是线性规划问题可行解集的一个极点,当且仅当它是约束方程的一个基本可行解.一般线性规划的数学模型及解法：

minf=cTxs.t.AxbA1x=b1LBxUBMatlab求解程序x,f=linprog（c,A,b,A1,b1,LB,UB）模型II.在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。

设每立方木材和每个工时投入“成本”分别为y1y2（决策变量）则目标函数为：

g=4y1+450y2对决策变量的约束0.2y1+15y2800.05y1+10y245y10,y20得y1=100（元/m3），y2=4（元/工时）3.对偶问题对偶问题：

A是mn矩阵，c是n1向量，b是m1向量x是n1向量,y是m1向量问题maxf=cTxs.t.Axbxi0,i=1,2,n.对偶问题minf=bTys.t.ATycyi0,i=1,2,m.对偶定理对偶定理:

互为对偶的两个线性规划问题,若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解模型I给出了生产中的产品的最优分配方案模型II给出了生产中资源的最低估价.这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出的贡献确定的估价,被称为“影子价影子价格格”.例2.生产5种产品P1,P2,P3,P4,P5单价为550,600,350,400,200.三道工序:

研磨、钻孔、装配。

所需工时为P1P2P3P4P5I122002515II1081600III2020202020各工序的生产能力（工时数）288192384如何安排生产，收入最大。

模型：

设xi生产Pi的件数。

则maxZ=550x1+600x2+350x3+400x4+200x5。

s.t.12x1+20x2+0x3+25x4+15x528810x1+8x2+16x3+0x4+0x519220x1+20x2+20x3+20x4+20x5384xi0有解x1=12，x2=7.2，x3=x4=x5=0Z=109201.如果增加三个工序的生产能力，每个工序的单位增长会带来多少价值？

2.结果表明与P1,P2相比P3,P4,P5，定价低了.价格提到什么程度,它们才值得生产?

对偶问题有解:

w1=6.25,w2=0,w3=23.75Zopt=6.25288+0192+23.75384X3的成本:

06.25+160+2023.75=4753504.非线性规划非线性规划minz=f（z）s.t.A1xb1,A2x=b2,c1（x）0,c2（x）=0LBxUBMATLAB程序程序x,z=fmincon（fun,x0,A1,b,A2,b2,LB,UB,nonlcon）例例3.某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为（ai,bi）（单位：

公里单位：

公里）,水泥日用量水泥日用量di（单位：

单位：

吨）吨）ia1.258.750.55.7537.25b1.250.754.7556.57.75d3547611建两个日储量建两个日储量e为为20吨的料场，需要确定料场位吨的料场，需要确定料场位置置（xj,yj）和运量和运量cij，使总吨公里数最小。

，使总吨公里数最小。

2,1,6,.,1,.）（）（min612121612/122jecidctsbyaxcjijiiijjjiijijijminz=f（z）s.t.A1xb1,A2x=b2,c1（x）0,c2（x）=0LBxUBMATLAB程序程序x,z=fmincon（fun,x0,A1,b,A2,b2,LB,UB,nonlcon）用随机搜索算法确定初始点：

用随机搜索算法确定初始点：

在可行域在可行域0.5,8.750.75,7.75内简单地内简单地选取选取n个随机的的点，个随机的的点，计算目标函数在这些点的值，选择其中计算目标函数在这些点的值，选择其中最小的点即可。

最小的点即可。

然后，可采用然后，可采用Matlab求最值点程序求出求最值点程序求出精确的最小值点精确的最小值点:

求函数求函数fun在在x0点附点附近的最小值点近的最小值点随机搜索程序的为代码算法算法：

随机搜索法随机搜索法变量：

变量：

xl=x的下限的下限xu=x的上限的上限yl=y的下限的下限yu=y的上限的上限N=迭代次数迭代次数xm=极小点极小点x的近似值的近似值ym=极小点极小点y的近似值的近似值zm=极小点极小点f（x,y）的近似的近似值值输入：

输入：

xl，xu，yl，yu过程：

开始过程：

开始xrandomxlrandomxl，xuxuyrandomylyrandomyl，yuyuzmf（x,y）zmf（x,y）对对n=1到到N循环循环开始开始xrandomxl，xuyrandomyl，yuzf（x,y）若若zzm，则，则xmxymyzmz结束结束结束结束输出：

输出：

xm，ym，zm5.0-1规划如果要求决策变量只取0或1的线性规划问题,称为整数规划.0-1约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进问题的例4背包问题背包问题一个旅行者的背包最多只能装6kg物品.现有4件物品重量为2kg,3kg,3kg,4kg,价值为1元,1.2元,0.9元,1.1元.应携带那些物品使得携带物品的价值最大?

建模:

记xj：

旅行者携带第j件物品的件数,xj=0,1.约束条件2x1+3x2+3x3+4x46求xj使目标函数f=x1+1.2x2+0.9x3+1.1x4最大.用Lingo软件求解0-1规划LinearInteractiveandGeneralOptimizerModel:

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（整数）在约束条件jajxjb下,使得目标函数f=jcjxj达到最大值.7.用Lindo软件求解整数规划LinearInteractiveandDiscreteoptimizermax3x1+2x2st2x1+3x2=142x1+x2=9endginx1ginx2（或者用gin2）求整数x1,x2MaxZ=3x1+2x2s.t.2x1+3x2142x1+x298.规划问题的建模艺术规划问题的建模艺术将实际问题归结为线性规划模型是一个探索创造的过程。

例7钢材截短钢材截短有一批钢材,每根长7.3米.现需做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根钢材（决策变量）.目标函数f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8约束条件2x1+x2+x3+x41002x2+x4+2x5+3x6+x7100x1+2x3+x4+2x5+3x7+4x8100xi0,i=1,8用Matlab程序解得x1=40x2=20x5=30,f=7（实际上应要求xi为正整数。

这是一个整数规划问题）。

例8存储问题存储问题有5种药品S=1,2,3,4,5要存放,有些药品不能存放在一起,能存放在一起存放的药品为的=1,2,1,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+x51x1+x31x2+x41x3+x61x2+x3+x61xi0，1，i=1,2,6,下使得目标函数f=cixi最小.习题一资源的最优配置策略资源的最优配置策略某工厂有1000台机器,生产两种产品A,B,若投入y台机器生产A产品,则纯收入为5y.若投入y台机器生产B产品,则纯收入为4y.又知,生产A种产品机器的年折损率为20%,生产B种产品机器的年折损率为10%,问在5年内如何安排各年度的生产计划,才能使总收入最高.习题二一家出版社准备再某市开设两个销售点，向七个区的大学生售书。

每个区的大学生数量（千人）如图。

每个销售点只能向本区和一个相邻区的大学生售书。

这两个销售点应该设在何处，才能使所供应的学生数量最大。

71182142345629习题三混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。

如何根据4位运动员的4种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。

蛙泳蝶泳自由泳仰泳甲99605973乙79659387丙67936381丁56798676