优化问题与规划问题.ppt

3 6优化问题与规划模型 综合问题 一个城郊的社区计划更新消防站 原来的消防站在旧城中心 规划要将新的消防站设置得更科学合理在前一个季度收集了火警反应时间的资料 平均要用3 2分钟派遣消防队员 消防队员到达火灾现场的时间 行车时间 依赖于火灾现场的距离 行车时间的资料列于表1 表1行车时间 从社区的不同区域打来的求救电话频率的数据列于图1 其中每一格代表一平方英里 格内的数字为每年从此区域打来的紧急求救电话的数量 1 求反应时间 消防队对离救火站r英里处打来的一个求救电话需要的反应时间估计为d分钟 给出消防队对求救电话的反应时间的模型d r 2 求平均反应时间 设社区位区域 0 6 0 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 80 x1 45x20 2x1 0 05x2 415x1 10 x2 450 模型I 以产值为目标取得最大收益 设 生产桌子x1张 椅子x2张 决策变量 将目标优化为 maxf 80 x1 45x2对决策变量的约束 0 2x1 0 05x2 415x1 10 x2 450 x1 0 x2 0 规划问题 在约束条件下求目标函数的最优值点 规划问题包含3个组成要素 决策变量 目标函数 约束条件 当目标函数和约束条件都是决策变量的线性函数时 称为线性规划问题 否则称为非线性规划问题 2 线性规划问题求解方法称满足约束条件的向量为可行解 称可行解的集合为可行域 称使目标函数达最优值的可行解为最优解 图解法 解两个变量的线性规划问题 在平面上画出可行域 凸多边形 计算目标函数在各极点 多边形顶点 处的值比较后 取最值点为最优解 命题1线性规划问题的可行解集是凸集可行解集 线性不等式组的解 0 2x1 0 05x2 4 15x1 10 x2 450 命题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 0 xn 1 0 xn 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 am1x1 amnxn bm x1 0 xn 0 定义 若代数方程AX B的解向量有n m个分量为零 其余m个分量对应A的m个线性无关列 则称该解向量为方程组的一个基本解 在一个线性规划问题中 如果一个可行解也是约束方程组的基本解 则称之为基本可行解命题4一个向量x是线性规划问题可行解集的一个极点 当且仅当它是约束方程的一个基本可行解 一般线性规划的数学模型及解法 minf cTxs t Ax bA1x b1LB x UBMatlab求解程序 x f linprog c A b A1 b1 LB UB 模型II 在不降低当前生产水平的前提下评估资源的贡献 使 成本 投入最低 设每立方木材和每个工时投入 成本 分别为y1y2 决策变量 则目标函数为 g 4y1 450y2对决策变量的约束0 2y1 15y2 800 05y1 10y2 45y1 0 y2 0得y1 100 元 m3 y2 4 元 工时 3 对偶问题 A是m n矩阵 c是n 1向量 b是m 1向量x是n 1向量 y是m 1向量 问题maxf cTxs t Ax bxi 0 i 1 2 n 对偶问题minf bTys t ATy cyi 0 i 1 2 m 对偶定理 互为对偶的两个线性规划问题 若其中一个有有穷的最优解 则另一个也有有穷的最优解 且最优值相等 若两者之一有无界的最优解 则另一个没有可行解 模型I给出了生产中的产品的最优分配方案模型II给出了生产中资源的最低估价 这种价格涉及到资源的有效利用 它不是市场价格 而是根据资源在生产中做出的贡献确定的估价 被称为 影子价格 例2 生产5种产品P1 P2 P3 P4 P5单价为550 600 350 400 200 三道工序 研磨 钻孔 装配 所需工时为P1P2P3P4P5I122002515II1081600III2020202020各工序的生产能力 工时数 288192384如何安排生产 收入最大 模型 设xi生产Pi的件数 则maxZ 550 x1 600 x2 350 x3 400 x4 200 x5 s t 12x1 20 x2 0 x3 25x4 15x5 28810 x1 8x2 16x3 0 x4 0 x5 19220 x1 20 x2 20 x3 20 x4 20 x5 384xi 0有解x1 12 x2 7 2 x3 x4 x5 0Z 10920 1 如果增加三个工序的生产能力 每个工序的单位增长会带来多少价值 2 结果表明与P1 P2相比P3 P4 P5 定价低了 价格提到什么程度 它们才值得生产 对偶问题有解 w1 6 25 w2 0 w3 23 75Zopt 6 25 288 0 192 23 75 384X3的成本 0 6 25 16 0 20 23 75 475 350 4 非线性规划minz f z s t A1x b1 A2x b2 c1 x 0 c2 x 0LB x UBMATLAB程序 x z fmincon fun x0 A1 b A2 b2 LB UB nonlcon 例3 某公司有6个建筑工地 位置坐标为 ai bi 单位 公里 水泥日用量di 单位 吨 建两个日储量e为20吨的料场 需要确定料场位置 xj yj 和运量cij 使总吨公里数最小 minz f z s t A1x b1 A2x b2 c1 x 0 c2 x 0LB x UBMATLAB程序 x z fmincon fun x0 A1 b A2 b2 LB UB nonlcon 用随机搜索算法确定初始点 在可行域 0 5 8 75 0 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过程 开始x random xl xu y random yl yu zm f x y 对n 1到N循环开始x random xl xu y random yl yu z f x y 若z zm 则xm xym yzm z结束结束输出 xm ym zm 5 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 4x4 6求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 x4 6 bin x1 bin x2 bin x3 bin x4 end 例5供货问题一家公司生产某种商品 现有n个客户 第j个客户需要货物量至少为bj 可在m各不同地点设厂供货 在地区i设厂的费用为di 供货能力为hi 向第j个客户供应单位数量的货物费用为cij 如何设厂与供货使总费用最小 模型 记xij为在地区i向第j个客户供货数量 记yi 1 在地区i设厂 记yi 0不在地区i设厂 求设厂和供货分配方案yi xij使得目标函数f yi jcijxij di 在约束条件 iyixij bj j 1 n jxij hi 0 I 1 mxij 0 yi 0 1 下达到最小 6 整数规划如果要求决策变量取整数 或部分取整数的线性规划问题 称为整数规划 例6 飞船装载问题设有n种不同类型的科学仪器希望装在登月飞船上 令cj 0表示每件第j类仪器的科学价值 aj 0表示每件第j类仪器的重量 每类仪器件数不限 但装载件数只能是整数 飞船总载荷不得超过数b 设计一种方案 使得被装载仪器的科学价值之和最大 建模记xj为第j类仪器的装载数 求各种仪器的装载数量xj 整数 在约束条件 jajxj b下 使得目标函数f jcjxj达到最大值 7 用Lindo软件求解整数规划LinearInteractiveandDiscreteoptimizer max3x1 2x2st2x1 3x2 142x1 x2 9endginx1ginx2 或者用gin2 求整数x1 x2MaxZ 3x1 2x2s t 2x1 3x2 142x1 x2 9 8 规划问题的建模艺术将实际问题归结为线性规划模型是一个探索创造的过程 例7钢材截短有一批钢材 每根长7 3米 现需做100套短钢材 每套包括长2 9米 2 1米 1 5米的各一根 至少用掉多少根钢材才能满足需要 并使得用料最省 解 可能的截法和余料第1种7 3 2 9 2 1 5 1 0第2种7 3 2 9 1 2 1 2 0 2第3种7 3 2 9 1 1 5 2 1 4第4种7 3 2 9 1 2 1 1 1 5 1 0 8第5种7 3 2 1 2 1 5 2 0 1第6种7 3 2 1 3 1第7种7 3 2 1 1 1 5 3 0 7第8种7 3 1 5 4 1 3 设按第i种方法截xi根钢材 决策变量 目标函数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 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 x5 1x1 x3 1x2 x4 1x3 x6 1x2 x3 x6 1xi 0 1 i 1 2 6 下使得目标函数f cixi最小 习题一资源的最优配置策略某工厂有1000台机器 生产两种产品A B 若投入y台机器生产A产品 则纯收入为5y 若投入y台机器生产B产品 则纯收入为4y 又知 生产A种产品机器的年折损率为20 生产B种产品机器的年折损率为10 问在5年内如何安排各年度的生产计划 才能使总收入最高 习题二一家出版社准备再某市开设两个销售点 向七个区的大学生售书 每个区的大学生数量 千人 如图 每个销售点只能向本区和一个相邻区的大学生售书 这两个销售点应该设在何处 才能使所供应的学生数量最大 习题三混合泳接力赛由蛙泳 蝶泳 自由泳 仰泳组成 如何根据4位运动员的4种游泳竞赛成绩安排混合泳接力队 以取得最佳成绩 蛙泳蝶泳自由泳仰泳甲99605973乙79659387丙67936381丁56798676