数学建模-数学规划模型.ppt

第二章数学规划模型 数学规划论起始20世纪30年代末 50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视 七八十年代是数学规划飞速发展时期 无论是从理论上还是算法方面都得到了进一步完善 时至今日数学规划仍然是运筹学领域中热点研究问题 从国内外的数学建模竞赛的试题中看 有近1 2的问题可用数学规划进行求解 数学规划模型的一般表达式 为目标函数 为约束函数 为约束函数 为可控变量 为已知参数 为随机参数 数学规划分为线性规划 非线性规划 动态规划 随机规划 整数规划 分式规划 几何规划 目标规划 平衡规划 参数规划 多目标规划等十几种 当然这么多规划其中亦有交叉 又可经过组产生新的规划 每一种规划有专著问世 第一节线性规划模型 1 目标函数是决策变量的线性函数 2 约束条件都是决策变量的线性等式或不等式 MATLAB命令命令输入格式及线性规划模型如下 其中 x0是算法迭代的初始点 nEq表示等式约束的个数 三 建模举例营养配餐问题 每种蔬菜含有的营养素成份是不同的 从医学上知道 每人每周对每种营养成分的最低需求量 某医院营养室在制定下一周菜单时 需要确定表6 1中所列六种蔬菜的供应量 以便使费用最小而又能满足营养素等其它方面的要求 规定白菜的供应一周内不多于20千克 其它蔬菜的供应在一周内不多于40千克 每周共需供应140千克蔬菜 为了使费用最小又满足营养素等其它方面的要求 问在下一周内应当供应每种蔬菜各多少千克 表2 3 问题分析与模型建立 设分别表示下一周内应当供应的青豆 胡萝卜 菜花 白菜 甜菜及土豆的量 费用目标函数为 约束条件 铁的需求量至少6个单位数 磷的需求量至少25个单位数 维生素A的需求量至少17500个单位 维生素C的需求量至少245个单位 烟酸的需求量至少5个单位数 每周需供应140千克蔬菜 即 0 x1 400 x2 400 x3 400 x4 200 x5 400 x6 40 问题是满足营养素要求的条件下 所需费用最小 是一个线性规划模型 利用Matlab软件编程序 营养配餐ch21 文件名 ch21mc 5 5 8 2 6 3 A 1 1 1 1 1 1 1 0 45 0 45 1 05 0 40 0 50 0 50 10 28 59 25 22 75 415 9065 2550 75 15 235 8 3 53 27 5 8 0 30 0 35 0 60 0 15 0 25 0 80 b 1 140 6 25 17500 245 5 xLB zeros 6 1 xUB 40 40 40 20 40 40 nEq 1 x0 0 ones 6 1 x lp c A b xLB xUB x0 nEq disp 青豆需要的份数 x 1 disp 胡罗卜需要的份数 x 2 disp 菜花需要的份数 x 3 disp 白菜需要的份数 x 4 disp 甜菜需要的份数 x 5 disp 土豆需要的份数 x 6 执行后输出青豆需要的份数ans 40胡罗卜需要的份数ans 40 0000菜花需要的份数ans 0 白菜需要的份数ans 20 0000甜菜需要的份数ans 0土豆需要的份数ans 40最小费用ans 560 0000 背景 0 1规划是数学规划的组成部分 起始20世纪30年代末 七八十年代是数学规划飞速发展时期 无论是从理论上还是算法方面都得到了进一步完善 时至今日数学规划仍然是运筹学领域中热点研究问题 从国内外的数学建模竞赛的试题中看 有近1 2的问题可用数学规划进行求解 其中利用0 1规划及0 1型变量的数学建模问题也为数不少 如98年的 投资的收益和风险 2004年的 DVD在线租赁 等问题 下面我们就来学习0 1规划 0 1型变量在数学建模中的应用 2 20 1规划 0 1型变量在数学建模中的应用1 0 1规划数学规划模型的一般表达式 整数规划中决策变量只取0或1的特殊情况是0 1规划 下面通过几个例子说明0 1规划在实际问题中的应用 例2 1背包问题有几件物品 编号为1 2 n 第件重为kg 价值为元 今有一位装包者欲将这些物品装入一包 其质量不能超过kg 问应装入哪几件价值最大 解引入变量 将物品装包 不将物品装包于是得问题的模型为取0或1 i 1 2 n背包问题看似简单 但应用很广 例如某些投资问题即可归入背包问题模型 此类问题可以描述为 投资问题 设有总额为元的资金 投资几项事业 第项事业需投资元 利润为元 问应选择哪些项投资总利润为最大 例2 2某钻井队要从以下10个可供选择的井位中确定5个钻井探油 使总的钻探费用为最小 若10个井位的代号为 相应的钻探费用为 并且井位选择要满足下列限制条件 1 或选和 或选 2 选择了或就不能选 反之亦然 3 在中最多只能选两个 试建立其数学模型 解引入变量选择不选择于是以上问题的数学模型为 投资的收益和风险 这是1998年全国大学生数学建模竞赛的A题问题如下 市场上有n种资产 股票 债券 Si i 1 n 供投资者选择 某公司有数额为M的一笔相当大的资金可用作一个时间的投资 公司财务分析人员对这n种资产进行了评估 估算出在这一时期内购买Si有平均收益率为ri 并预测出购买Si的风险损失率为qi 考虑到投资越分散总的风险越小 公司确定 当用这笔资金购买若 干种资产时 总体风险可用所投资的Si中最大的一个风险来度量 购买Si要付交易费 费率为pi 并且当购买额不超过给定值ui时 交易费按购买ui计算 不买当然无须付费 另外 假定同期银行存款利率是r0 且既无交易费又无风险 r0 5 1 已知n 4时的相关数据如下 试给该公司设计一种投资组合方案即用给定的资金M 有选择地购买若干种资产或存银行生息 使净收益尽可能大 而总体风险尽可能小 2 试就一般情况对以上问题进行讨论 利用以下数据进行计算 在AD边等距地设置7个波源Ri i 1 7 BC边对等地安放7个接收器Sj j 1 7 记录由Ri发出的弹性波到达Sj的时间 ij秒 见表2 3 2 0 1型变量在数学建模中的应用1 空洞探测问题1 1问题的提出这是2000年全国大学生数学建模竞赛的D题 山体 隧洞 坝体等的某些内部结构可用弹性波测量来确定 一个简化问题可描述为 一块均匀介质构成的矩形平板内有一些充满空气的空洞 在平板的两个邻边分别等距地设置若干波源 在它们的对边对等地安放同样多的接收器 记录弹性波由每个波源到达对边上每个接收器的时间 根据弹性波在介质中和空气中不同的传播速度 来确定板内空洞的位置 现考察如下的具体问题 一块240 米 240 米 的平板 如图2 1 在AB边等距地设置7个波源Pi i 1 7 CD边对等地安放7个接收器Qj j 1 7 记录由Pi发出的弹性波到达Qj的时间tij 秒 见表2 2 在AD边等距地设置7个波源Ri i 1 7 BC边对等地安放7个接收器Sj j 1 7 记录由Ri发出的弹性波到达Sj的时间 ij秒 见表2 3 已知弹性波在介质和空气中的传播速度分别为2880 米 秒 和320 米 秒 且弹性波沿板边缘的传播速度与在介质中的传播速度相同 1 确定该平板内空洞的位置 2 只根据由Pi发出的弹性波到达Qj的时间tij i j 1 7 能确定空洞的位置吗 讨论在同样能够确定空洞位置的前提下 减少波源和接受器的方法 1 2模型的假设及符号说明 1 模型的假设 波源和接收器的设置仅按图中的设置来考虑 不考虑其它情况 在图中的一个小方格要么全是空气 要么全 是介质 2 符号说明n 1 x轴方向等距地放置波源Pi i 1 7 的个数 相应地n是x轴方向的方格数 已知的n 6 m 1 y轴方向等距地放置波源Ri i 1 7 的个数 相应地m是y轴方向的方格数 已知的m 6 d1 x轴方向方格的边长 已知的 d1 40米 d2 y轴方向方格的边长 已知的 d2 40米 tij i 0 6 j 0 6 由波源Pi发生的弹性波到达接收器Qj的时间 pij i 0 6 j 0 6 波线PiQj经历的介质的总长度 qij i 0 6 j 0 6 波线PiQj经历的空洞的总长度 v1 弹性波在介质中的传播速度 已知的v1 2880米 秒 v2 弹性波在空气中的传播速度 已知的v2 320米 秒 1 3问题的分析及数学模型 1 问题的分析这是一个反问题 不妨先看它正问题 已知空洞的位置及弹性波在介质和空气中的传播速度 求由波源Pi发出的弹性波到达接收器Qj的时间tij 为了求出tij 可先算出波线PiQj经历的每个小方格的长度 根据该方格是介质还是空洞 分别除以波在介质和空气中的传播速度 对经历的所有方格求和 即得tij 上述的正问题等价于 算出波线PiQj经历的各个小方格的长度 根据该方格是介质还是空洞 分别乘以0和1 对经历的所有方格求和 即可得到波线PiQj经历的空洞的长度 反问题可以这样求解 先由波源Pi发出的弹性波到达接收器Qj的时间tij及弹性波在介质和空气中的传播速度 算出波线PiQj经历的空洞的总长度 再由PiQj经历的每个方格的长度 即可解出每个方格是介质还是空洞 即是0还是1 2 数学建模建立坐标系如图2 2 X Y轴上分别等距地放置n 1 m 1个波源 本题n m 6 将平板划分为个方格 则1 波线PiQj经历的介质的总长度pij和空洞的总长度qij满足下面两个式子 1 2 6 7 8 12 31 32 36 3 4 5 13 如图2 2 2 波线PiQj的方程为 3 直线方程 3 与的交点可算出 从而求得PiQj经历的每个方格长度 3 将个方格如图示顺序排列 第i个方格的特征量记为 4 全体方格的特征向量记为 4 由AB至CD的波线PiQj共条 其中n 1条PiQj是无用的 去掉无用波线后n n 1 条波线PiQj的顺序按 排列 每条波线经历的各个方格的长度排成一行向量 于是得到条波线经历mn个方格的长度矩阵5 将1 得到的波线PiQj经历空洞的总长度qij 按照4 中波线的顺序构成空洞长度 列 向量 则应有 5 6 完全类似地处理波线RkSl 得到m m 1 条波线经历mn个方格的长度矩阵和空洞长度 列 向量 构造 则 6 当Rank A mn时可求出该方程最小二乘意义下的解 7 7 取适当的 8 取的小方格为介质 小方格为空洞 其余的 如果有的话 无法确定 2 3 4模型求解 空洞探测ch23 m 文件名 ch23 m 计算PiQj在每个格子中的线段长度 clearn 1 fori 0 6forj 0 6ai i aj j ifi jaj j 1 ifaj 7break endendChudian ai 0 Modian aj 6 Dianwei ai 0 pp form 1 6 x Chudian 1 Modian 1 Chudian 1 m Chudian 2 Modian 2 Chudian 2 Dianwei Dianwei x m endifaj aip aj aj ai ai p endifabs aj ai 2fork aj 1 ai 1 y Chudian 2 Modian 2 Chudian 2 k Chudian 1 Modian 1 Chudian 1 pp pp k y endend Jiaodian Dianwei pp hang lie size Jiaodian aa Jiaodian 1 bb unique aa hang1 lie1 size bb Zuobiao forii 1 hang1forjj 1 hangifJiaodian jj 1 bb ii Zuobiao ii Jiaodian jj break end end end forpp 1 hang1 1d sqrt sum Zuobiao pp Zuobiao pp 1 2 ifj i distance PQ n ceil Zuobiao pp 1 1 fix Zuobiao pp 1 2 6 d elseifZuobiao pp 2 0distance PQ n ceil Zuobiao pp 1 1 d elsedistance PQ n ceil Zuobiao pp 1 1 fix Zuobiao pp 2 6 d endendend ifn 2ifdistance PQ n distance PQ n 1 distance PQ n elsen n 1 endelsen n 1 endendend 计算矩阵A1的秩A1 distance PQ disp 矩阵A1的秩 rank A1 计算RiSj在每个格子中的线段长度 n 1 fori 0 6forj 0 6ai i aj j ifi jaj j 1 ifaj 7break end endChudian 0 ai Modian 6 aj Dianwei 0 ai pp form 1 6y Chudian 2 Modian 2 Chudian 2 m Chudian 1 Modian 1 Chudian 1 Dianwei Dianwei m y endifaj aip aj aj ai ai p endifabs aj ai 2 fork aj 1 ai 1 x Chudian 1 Modian 1 Chudian 1 k Chudian 2 Modian 2 Chudian 2 pp pp x k endendJiaodian Dianwei pp hang lie size Jiaodian aa Jiaodian 2 bb unique aa hang1 lie1 size bb Zuobiao forii 1 hang1forjj 1 hangifJiaodian jj 2 bb ii Zuobiao ii Jiaodian jj break end end end forpp 1 hang1 1d sqrt sum Zuobiao pp Zuobiao pp 1 2 ifj idistance RS n ceil Zuobiao pp 1 fix Zuobiao pp 2 6 d elseifZuobiao pp 1 1 6distance RS n fix Zuobiao pp 1 2 6 d else distance RS n ceil Zuobiao pp 1 1 fix Zuobiao pp 2 6 d endendendifn 2ifdistance RS n distance RS n 1 distance RS n elsen n 1 end elsen n 1 endendend 对矩阵进行合并操作 计算系数矩阵AA distance PQ distance RS disp 矩阵A的秩 rank A 首先输入时间矩阵 并给出b b1 0 08950 19960 20320 41810 49230 5646 0 09890 44130 43180 47700 52420 3805 0 30520 41320 41530 41560 35630 1919 0 32210 44530 40400 17890 07400 2122 0 34900 45290 22630 19170 17680 1810 0 38070 31770 23640 30640 22170 1031 0 43110 33970 35660 19540 07600 0688 b2 0 06020 08130 35160 38670 43140 5721 0 07530 28520 43410 34910 48000 4980 0 34560 32050 40930 42400 45400 3112 0 36550 32890 42470 32490 21340 1017 0 31650 24090 32140 32560 18740 2130 0 27490 38910 58950 30160 20580 0706 0 44340 49190 39040 07860 07090 0914 lie1 lie2 fori 1 7m b1 i n b2 i lie1 lie1 m lie2 lie2 n endb lie1 lie2 计算方程Ax b最小二乘意义下解x A b tushi fori 0 5pp x i 6 1 i 1 6 tushi tushi pp endx tushi disp 输出结果X x 进行空洞判断a 0 11 b 0 11 fori 1 6forj 1 6iftushi i j belse xx i j 1 endendendxx执行后输出矩阵A1的秩ans 29矩阵A的秩ans 36输出结果X x 0 00980 01800 00580 00700 01810 01370 01450 12330 13250 01400 01370 01250 02030 11960 12040 02170 11550 01740 02550 01280 12730 12460 01730 00740 01270 12710 01450 01340 00690 01340 00540 01590 01340 00750 01850 0173 取 0