数学规划概述.ppt

MATLAB优化工具箱能求解的优化模型 LINGO软件的求解过程 LINDO 公司软件产品简要介绍 历史悠久，理论成熟，应用广泛 运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比； 可加性：每个决策变量对目标和约束的影响独立于其它变量； 连续性：每个决策变量取连续值； 确定性：线性规划中的参数aij , bi , ci为确定值。 模型的标准化 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’’,则可使得问题的全部变量均非负. 对偶线性规划 原问题 max f=cTx s.t. Ax ? b xi ? 0,i=1,2,?,n. 对偶问题 min f=bTy s.t. ATy ? c yi ? 0, i=1,2,?,m. 对偶定理: 互为对偶的两个线性规划问题 若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等. 若两者之一有无界的最优解,则另一个没有可行解。 模型求解 报告窗口 保存文件 解： 一个旅行者的背包最多只能装 6 kg 物品. 现有4 件物品 重量为 2 kg , 3 kg, 3 kg, 4 kg, 价值为 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大? 用Lingo 软件求解0-1规划 Linear Interactive and General Optimizer Model: 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 非线性规划模型－选址问题 习题4 资源的最优配置策略 某工厂有1000台机器, 生产两种产品 A, B, 若投入 y 台机器生产A 产品, 则纯收入为 5y .若投入 y 台机器生产B 产品, 则纯收入为 4y . 又知, 生产A 种产品机器的年折损率为20%, 生产B 种产品机器的年折损率为10%, 问在5年内如何安排各年度的生产计划, 才能使总收入最高. 习题5 一家出版社准备再某市开设两个销售点，向七个区的大学生售书。每个区的大学生数量（千人）如图。 每个销售点只能向本区和一个相邻区的大学生售书。这两个销售点应该设在何处，才能使所供应的学生数量最大。 THE END 用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解（见例1） 对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解） ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． x1 x2 0 P o 6 9 Zmax 5 6 去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形 从LP最优解经过简单的 “移动”不一定能得到IP最优解 例 LINDO可用于求解线性纯整数规划或混合整数规划(IP)， 模型的输入与LP问题类似, 但需在END标志后定义整型变量。 0/1型的变量可由INTEGER（可简写为INT）命令来标识， 有以下两种可能的用法： INT vname INT n 前者只将决策变量vname标识为0/1型, 后者将当前模型中前n 个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定, 该顺序可由输出结