资源描述：
《优化问题与规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§3.6优化问题与规划模型综合问题一个城郊的社区计划更新消防站。原来的消防站在旧城中心。规划要将新的消防站设置得更科学合理在前一个季度收集了火警反应时间的资料：平均要用3.2分钟派遣消防队员；消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。行车时间的资料列于表1距离1.223.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时
2、间4.267.005.497.643.093.885.496.825.534.303.55表1行车时间从社区的不同区域打来的求救电话频率的数据列于图1。其中每一格代表一平方英里，格内的数字为每年从此区域打来的紧急求救电话的数量。30142121123253301285210010631310231111）求反应时间。消防队对离救火站r英里处打来的一个求救电话需要的反应时间估计为d分钟。给出消防队对求救电话的反应时间的模型d(r)2）求平均反应时间。设社区位区域[0,6][0,6]内，(x,y)是新的消防站的位置。根据求救电话频率，确定消防队对求救电话的平均反应
3、时间z=f(x,y)3）求新的消防站的最佳位置。即确定函数f(x,y)的极小值点。首先，§3.6优化问题与规划模型优化问题：与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法：运筹学运筹学主要分支：线性规划、非线性规划、动态规划、图与网络分析、存贮论、排队伦、对策论、决策论。6.1线性规划1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.1.问题例1家具生产的安排一.家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米每张桌子要使用15个工时
4、，0.2立方木材售价80元。每张椅子使用10个工时，0.05立方木材售价45元。问为达到最大的收益，应如何安排生产？分析：1.求什么？生产多少桌子？生产多少椅子？2.优化什么？收益最大3.限制条件？原料总量劳力总数x1x2Maxf=80x1+45x20.2x1+0.05x2≤415x1+10x2≤450模型I：以产值为目标取得最大收益.设：生产桌子x1张,椅子x2张,(决策变量)将目标优化为：maxf=80x1+45x2对决策变量的约束：0.2x1+0.05x2≤415x1+10x2≤450,x1≥0,x2≥0,规划问题：在约束条件下求目标函数的最优值点。规划问
5、题包含3个组成要素:决策变量、目标函数、约束条件。当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,否则称为非线性规划问题。2.线性规划问题求解方法称满足约束条件的向量为可行解,称可行解的集合为可行域,称使目标函数达最优值的可行解为最优解.图解法：(解两个变量的线性规划问题)在平面上画出可行域（凸多边形），计算目标函数在各极点(多边形顶点)处的值比较后，取最值点为最优解。命题1线性规划问题的可行解集是凸集可行解集：线性不等式组的解0.2x1+0.05x2=415x1+10x2=450命题2线性规划问题的目标函数(关于不同的目标值是一族平行直线,目标
6、值的大小描述了直线离原点的远近命题3线性规划问题的最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).单纯形法:通过确定约束方程组的基本解,并计算相应目标函数值,在可行解集的极点中搜寻最优解.模型的标准化正则模型:决策变量:x1,x2,…,xn.目标函数:Z=c1x1+c2x2+…+cnxn.约束条件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,模型的标准化10.引入松弛变量将不等式约束变为等式约束若有ai1x1+…+ainxn≤bi,则引入xn+i≥0,使得ai1x1+…
7、+ainxn+xn+i=bi若有aj1x1+…+ajnxn≥bj,则引入xn+j≥0,使得aj1x1+…+ajnxn-xn+j=bj.且有Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.20.将目标函数的优化变为目标函数的极大化.若求minZ,令Z’=–Z,则问题变为maxZ’.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,则可使得问题的全部变量均非负.标准化模型求变量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,……
8、am1x1+…+amnx
