优化问题与规划问题.ppt

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