[工学]建模培训-线性规划.ppt

规划理论及模型 一、引言 二、线性规划模型 线性规划模型的形式 运输问题的数学模型为： 运输问题举例 设要从甲地调出物资2000吨，从乙地调出物资 背包问题 有 n 个物品，编号为1, 2, …, n，第 i 件物品 指派问题 有n 项任务，由 n 个人来完成，每个人必须 四、非线性规划模型 事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的. 为了利用线性的知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型. 非线性规划问题的标准形式为： 工程造价问题 要建造容积为1500立方米的长方形仓库，已知每平方米墙壁、屋顶和地面的造价分别为4元、6元、12元，基于美学考虑，要求宽度应为高度的2倍，试建立使造价最省的数学模型。 五、多目标规划模型  在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高. 这一类问题统称为多目标最优化问题或多目标规划问题。多目标规划问题与前面讲的规划问题的主要区别在于：目标函数不止一个，而是若干个。 规 划 模 型 举 例 多目标规划的求解 如何装运，使本次飞行获利最大？ 三个货舱最大载重(吨),最大容积(米3) 例1 货机装运 ? 重量（吨） 空间( 米3/吨） 利润（元/吨） 货物1 18 480 3100 货物2 15 650 3800 货物3 23 580 3500 货物4 12 390 2850 三个货舱中实际载重必须与其最大载重成比例 前仓： 10；6800 中仓： 16；8700 后仓： 8；5300 飞机平衡 决策变量 xij--第i 种货物装入第j 个货舱的重量(吨） i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓) 模型假设 每种货物可以分割到任意小； 每种货物可以在一个或多个货舱中任意分布； 多种货物可以混装，并保证不留空隙； 模型建立 （2）货舱容积 目标函数(利润) 约束条件 （1）货舱重量 10；6800 16；8700 8；5300 货仓限制 约束条件 （4）平衡要求 （3）货物重量 货物2：前仓10,后仓5； 货物3: 中仓13, 后仓3； 货物4: 中仓3。 模型求解 最大利润约121516元 货物~供应点 货舱~需求点 重量限制 空间限制 平衡要求 运输问题 运输问题的扩展 输入Lindo求解 若丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？ 如何选拔队员组成4?100米混合泳接力队? 例2 混合泳接力队的选拔 ? 甲 乙 丙 丁 戊 蝶泳 1’06”8 57”2 1’18” 1’10” 1’07”4 仰泳 1’15”6 1’06” 1’07”8 1’14”2 1’11” 蛙泳 1’27” 1’06”4 1’24”6 1’09”6 1’23”8 自由泳 58”6 53” 59”4 57”2 1’02”4 5名候选人的百米成绩 穷举法：组成接力队的方案共有5!=120种。 目标函数 若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划模型 cij(秒)~队员i 第j 种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 cij i=1 i=2 i=3 i=4 i=5 j=1 66.8 57.2 78 70 67.4 j=2 75.6 66 67.8 74.2 71 j=3 87 66.4 84.6 69.6 83.8 j=4 58.6 53 59.4 57.2 62.4 每种泳姿有且只有1人 模型求解 最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0; 成绩为253.2(秒)=4’13”2 输入LINDO求解 ? 甲 乙 丙 丁 戊 蝶泳 1’06”8 57”2 1’18” 1’10” 1’07”4 仰泳 1’15”6 1’06” 1’07”8 1’14”2 1’11” 蛙泳 1’27” 1’06”4 1’24”6 1’09”6 1’23”8 自由泳 58”6 53” 59”4 57”2 1’02”4 甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳. 丁蛙泳c43 =69.6?75.2，戊自由泳c54=62.4