数模第二次培训

数模电子协会数模部第二次培训 分支定界法0 1整数规划数模论文写作 2020 4 18 分支定界法对有约束条件的最优化问题 其可行解为有限数 的所有可行解空间恰当地进行系统搜索 这就是分枝与定界内容 通常 把全部可行解空间反复地分割为越来越小子集 称为分枝 并且对每个子集内的解集计算一个目标下界 对于最小值问题 这称为定界 在每次分枝后 凡是界限超出已知可行解集目标值的那些子集不再进一步分枝 这样 许多子集可不予考虑 这称剪枝 这就是分枝定界法的主要思路 2020 4 18 设有最大化的整数规划问题A 与他相应的线性规划为问题B 从解问题B开始 若其最优解不符合A的整数条件 那么B的最优目标函数定是A的最有目标函数z 的上界 记作Z1 而A的任意可行解的目标函数值将是z 的一个下界Z2 分枝定界法就是将B的可行域分成子区域的方法 逐步减小Z1和增大Z2 最终求到z 2020 4 18 例题求解下述整数规划Maxz 40 x1 90 x2约束条件9x1 7x2 567x1 20 x2 70 x1 x2 0且为整数解 i 先不考虑整数限制 即解相应的线性规划B 得最优解为 x1 4 8092x2 1 8168z 355 8779可见它不符合整数条件 2020 4 18 这时z是问题A的最优目标函数值z 的上界 记作z1 而x1 0 x2 0显然是问题A的一个整数可行解 这时z 0 是z 的一个下界 记作z2 即0 z 356 ii 因为x1 x2当前均为非整数 故不满足整数要求 任选一个进行分枝 设选x1进行分枝 把可行集分成2个子集 x1 4 8092 4 x1 4 8092 1 5因为4与5之间无整数 故这两个子集的整数解必与原可行集合整数解一致 这一步称为分枝 这两个子集的规划及求解如下 2020 4 18 问题B1 Maxz 40 x1 90 x2约束条件9x1 7x2 567x1 20 x2 700 x1 4 x2 0最优解 x1 4 x2 2 1 z 349问题B2 Maxz 40 x1 90 x2约束条件9x1 7x2 567x1 20 x2 70 x1 5 x2 0最优解为 x1 5 x2 1 57 z 341 4再定界 0 z 349 2020 4 18 iii 对问题B1再进行分枝得问题B11和B12 它们的最优解为B11 x1 4x2 2 z 340B12 x1 1 43x2 3 z 327 14再定界340 z 341 并将B12剪枝 iv 对问题B2再进行分枝得问题B21和B22 它们的最优解为B21 x1 5 44x2 1 z 308B22无可行解将B21 B22剪枝 所以原问题最优解 x1 4 x2 2 z 340 2020 4 18 分支定界法求整数规划 最大化 问题的步骤为 要求解的整数规划问题称为A 对应的线性规划问题称为B i 解问题B有以下情况 a B无可行解 则A也无可行解 停止解题让老师去解 b B有最优解且符合A的整数条件 则B的最优解就是A的最优解 c B有最优解 但不符合A的整数条件 记下它的目标函数值Z1 ii 观察随意得出一个A的整数可行解极为Z2 用z 表示A的最有目标函数值 z2 z z1进行迭代计算 2020 4 18 第一步 分枝 在B的最优解中任选一个不符合整数条件的变量xj其值为bj用 bj 表示小于bj的最大整数 构造两个约束条件xj bj 和xj bj 1将这两个约束条件加入问题B 求两个后继规划问题B1和B2 不考虑整数条件求解这两个后继问题 定界 以每个后继问题为一分枝表明求解结果 与其它问题的求解结果中 找出最优目标函数值作为新的上界 在符合整数条件的分支中找出目标函数值最大的作为新的下界 没有就下界不变 2020 4 18 第二步 比较与剪枝 各分枝的最有目标函数中有小于Z2的就剪掉这些枝条不再考虑 大于Z2但不符合整数条件的就重复第一步 一直到z Z2为止 得到最优解x j j 1 2 n 2020 4 18 0 1整数规划0 1整数规划是变量只能xj取值0或1的整数规划 这种变量xj称为0 1变量 或称二进制变量 xj仅取值0或1这个条件表示为0 xj 1 整数来代替 这样就和整数规划的约束条件形式一致 在实际问题中 如果引入0 1变量 就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了 先介绍引入0 1变量的实际问题 再研究解法 2020 4 18 投资场所的选定 相互排斥的计划例4某公司拟在市东 西 南三区建立门市部 拟议中有7个位置 点 Ai i 1 2 7 可供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问应选择哪几个点可使年利润为最大 先引入0 1变量xi i 1 2 7 令xi 1 Ai点被选中 0 Ai点没被选中 2020 4 18 x1 x2 x3 2x4 x5 1x6 x7 1xi 0或1 2020 4 18 相互排斥的约束条件有两个相互排斥的约束条件5x1 4x2 24或7x1 3x2 45 为了统一在一个问题中引入0 1变量y 则上述约束条件可改写为 5x1 4x2 24 yM7x1 3x2 45 1 y My 0或1M是一个充分大的数约束条件x1 0或500 x1 800可改写500y x1 800yy 0或1 2020 4 18 如果有m个相互排斥的约束条件 ai1x1 ainxn bii 1 2 m为了保证这m个约束条件只有一个起作用 我么引入m个0 1变量yi i 1 2 m 和一个充分大的常熟M 而虾米那这一组m 1个约束条件ai1x1 ainxn bi yiMi 1 2 my1 ym m 1就符合上述要求了 2020 4 18 关于固定费用的问题在讨论线性规划时 有些问题是要求使成本为最小 那时总设固定成本为常数 并在线性规划的模型中不必明显列出 但有些固定费用 固定成本 的问题不能用一般线性规划来描述 但可改变为混合整数规划来解决 见下例 2020 4 18 某工厂为了生产某种产品 有几种不同的生产方式可供选择 如选定的生产方式投资高 选购自动化程度高的设备 由于产量大 因而分配到每件产品的变动成本就降低 反之 如选定的生产方式投资低 将来分配到每件产品的变动成本可能增加 所以必须全面考虑 今设有三种方式可供选择 令xj表示采用第j种方式时的产量 cj表示采用第j种方式时每件产品的变动成本 kj表示采用第j种方式时的固定成本为了说明成本的特点 暂不考虑其它约束条件 采用各种生产方式的总成本分别为Pj kj cjxj 当xj 00 当xj 0j 1 2 3 2020 4 18 在构成目标函数时 为了统一在一个问题中讨论 现引入0 1变量yj 令yj 1 当采用第j种生产方式 即xj 0时 0 当不采用第j种生产方式 即xj 0时 于是目标函数minz k1y1 c1x1 k2y2 c2x2 k3y3 c3x3 对于yj的约束可以用yj U xj yj M j 1 2 3 来表示其中U是一个充分小的正常数 M是个充分大的正常数 2020 4 18 0 1型整数规划解法之一 过滤隐枚举法 解0 1型整数规划最容易想到的方法 和一般整数规划的情形一样 就是穷举法 即检查变量取值为0或1的每一种组合 比较目标函数值以求得最优解 这就需要检查变量取值的2n个组合 对于变量个数n较大 例如n 100 这几乎是不可能的 因此常设计一些方法 只检查变量取值的组合的一部分 就能求到问题的最优解 这样的方法称为隐枚举法 ImplicitEnumeration 分枝定界法也是一种隐枚举法 当然 对 有些问题隐枚举法并不适用 所以有时穷举法还是必要的 2020 4 18 国赛论文写作论文一般结构摘要问题重述模型假设与符号说明问题分析及模型建立模型检验模型优缺点模型推广参考文献好的论文 准确 科学性条理 逻辑性简洁 数学美创新 与众不同使用 实际问题要求 2020 4 18 摘要重中之重 决定论文档次的地方 务必写好 主要三个方面 1 针对什么问题 一句话 2 采取什么方法 引起阅卷老师注意的地方 不能太粗也不能太细 3 得到了什么结果 简明扼要 生动 公式要简单 必要时可以采用小图表 单独成页 字数一定控制在一页内语言精简 用词准确 阐述细致具体的方法 突出重点 特点列出主要结论 写出三至五个关键词 2020 4 18 问题重述一般是把原问题复制粘贴换成自己的话说一遍合理增减有印象分模型假设和符号说明需要简明扼要 准确清楚1假设太多 阅卷老师记不住 也会显得模型的局限性太大 归纳出一些重要的假设 一般3 5条 有些不是很重要的假设在论文中适当提一下就好2假设要数学化 重视逻辑性要求3设计好符号 让人看起来清楚 用表格的形式把所用的符号及意义列出来 2020 4 18 问题分析说清楚建模的思路 有些简单的事情往往是最重要的 一定要说清楚刚刚开始的原始想法很重要 最好写出来推导时 公式若很长可以考虑放在附录里一般要求设计2 3个模型 最好是一个简单的 再对模型进行改建 得到第二个模型 2020 4 18 模型求解1模型的定性线性 非线性连续 离散或混合时变 非时变2模型求解利用现成的软件手工解出来一定要回答实际问题模型检验如果是统计类的直接带数据如果是优化类的直接进行比较优化后的结果也可以加上灵敏度分析 2020 4 18 模型优缺点客观 实事求是提出一些新的思路 使问