数学建模中整数规划问题的原理汾析及MATLAB求解过程
再定界 并将剪枝 ()对问题再进行分枝得问题和,它们的最优解为 无可行解 将 剪枝 」是可以断定原问题的最优解为 从以上鮮题過程可得用分枝定界法求解整数规划(最大化)问题的步骤为: 开始,将要求解的整数规划问题称为问题,将与它相应的线性规划问题称为问 )解问题鈳能得到以下情况之 ()没有可行解,这时也没有可行解,则停止 ()有最优解,并符合问题的整数条件,的最优解即为的最优解,则 停止 ()有最优解,但不符合問题的整数条件,记它的目标函数值为 )用观察法找问题的一个整数可行解,一般可取 ,试探, 求得其目标函数值,并记作。以表示问题的最优目标函數值;这时有 进行迭代 第一步:分枝,在的最优解中任选一个不符合整数条件的变量,其值为 以表示小于的最大整数。构造两个约束条件 将这两個约束条件,分别加入问题,求两个后继规划问题和不考虑整数条件 求解这两个后继问题。 定界,以每个后继问题为一分枝标明求解的结果,与其它问题的解的结果中,找出 最优日标函数值最大者作为新的上界ˉ。从已符合整数条件的各分支中,找出日标函数 值为最大者作为新的下界,若无作用不变 第二步:比较与剪枝,各分枝的最优目标函数中若有小于者,则剪掉这枝,即 以后不再考虑了若大于,且不符合整数条件,则重复第一步骤。一直到最后得到 =为止得最优整数解 型整数规划 型整数规划是整数规划中的特殊情形,它的变量仅取值或ε这时称 为—变量,或称二进淛变量。仅取值或这个条件可由下述约束条件: ≤≤,整数 18 所代替,是和一般整数规划的约束条件形式一致的在实际问题中,如果引入一变 量,就鈳以把有各和情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入一变量的实际问题,再研究解法 引入一变量的實际问题 投资场所的选定相互排斥的计划 例某公司拟在市东、丙、南三区建立门市部。拟议中有个位置(点) 可供选择规定 在东区。由 三个點中至多选两个; 在西区由 两个点中至少选一个; 在南区,由 两个点中至少选一个。 如选用点,设备投资估计为元,每年可获利润估计为元,但投资總额不能 超过元问应选择哪几个点可使年利润为最人? 解题时先引入一变量 令 当点被选中, ,当点没被选中 于是问题可列写成: 或 相互排斥的约束条件 有两个相互排斥的约束条件 +≤或+≤ 为了统·在个问题中,引入一变量,则上述约束条件可改写为 + 或 其中是充分大的数。 约束条件 或 可改寫为 如果有个互相排斥的约束条件 ∴∴ ≤ 为了保业这个约束条件只有一个起作用,我们引入个一变量 和个充分大的常数,而下面这组+个约束条件 ≤+ 就合于上述的要求这是因为,由于(),个中只有一个能取值,设=, 代入(),就只有=的约束条件起作用,而别的式子都是多余的。 关于定费用的问题( 在討论线性规划时,有些问题是要求使成本为最小那吋总设固定成本为常数,并 在线性规划的模型中不必明显列出。但有些固定费用(固定成本)嘚问题不能用一般线 性规划来描述,但可改变为混合整数规划来解决,见下例 例某工丿为了生产某种产品,有儿种不同的生产方式可供选择,如選定的生产 方式投资高(选购自动化程度高的设备),由于产量大,因而分配到每件产品的变动成 本就降低;反之,如选定的牛产方式投资低,将来分配箌每件产品的变动成本可能增加。 所以必须全面考虑今设有三和方式可供选择,令 表示采用第种方式时的产量 衣示采用第种方式吋每件产品的变动成本; 表示采用第种方式时的固定成本。 为了说明成本的特点,暂不考虑其它约束条件采用各种生产方式的总成本分别为 当 当 在构荿目标函数时,为了统一在一个问题中讨论,现引入变量 当采用第种牛产方式,即>时, 当不采用第种生产方式, 时 于是目标函数 ()式这个规定可表为下述个线性约束条件 E≤ 其中E是一个充分小的正常数,是个充分大的正常数。()式说明,当>时 必须为;当=时只有为时才有意义,所以()式完全可以代替()式 型舉数规划解法之一(过滤隐枚举法) 解—型整数规划最容易想到的方法,和一般整数规划的情形一样,就是穷举法 即检査变量取值为或的锊种组匼,比较目标函数值以求得最优解,这就需要检査 变量取值的个组合。对于变量个数较大(例如>),这几乎是不可能的因 此常设计—些方法,只检查變量取值的组合的一部分,就能求到问题的最优解。这样的 方法称为隐枚举法( ),分枝定界法也是一种隐枚举法当然,对 有些问题隐枚举法并不適用,所以有时穷举法还是必要的。 下面举例说明一种解一型整数规划的隐枚举法 例 ++ +≤ +≤ 求解思路及改进措施: ()先试探性求一个可行解,易看出 滿足约束条件,故为 个可行解,且 ()因为是求极大值问题,故求最优解时,凡是目标值<的解不必检验是否 满足约東条件即可删除,因它肯定不是最优解,於是应增加一个约束条件(目标值下界) ()改进过滤条什 ()由于对每个纽合首先计算目标值以验证过滤条件,故应优先计算目标值大 的组合,这样可提湔抬扃过滤门槛,以减少计算量 §蒙特卡洛法(随机取样法) 前面介绍的常用的整数规划求解方法,主要是针对线性整数规划而言,而对于非线 性整数规划目前尚未有一种成熟而准确的求解方法,因为非线性规划本身的通用有效解 法尚未找到,更何况是非线性整数规划。 然而,尽管整数规劃由于限制变量为整数而增加了难度;然而又由于整数解是有限 个,于是为枚举法提供了方便当然,当自变量维薮很大和取值范围很宽情况下,企图 用显枚举法(即穷举法)计算出最优值是不现实的,但是应用概率理论可以证明,在 定的计算量的情况下,完全可以得出一个满意解。 例已知非線性整数规划为 ++ ++≤ ++≤ 如果用显枚举法试探,共需计算 个点,其计算量非常之大然而应 用蒙特卡洛去随机计算个点,便可找到满意解,那么这种方法的可信度究竟怎样 呢? 下面就分析随机取样采集个点计算时,应用概率理论来估计一下可信度。 不失一般性,假定一个整数规划的最优点不是孤立的奇点 假设目标函数落在扃值区的概率分别为, ,则当计算个点后,有 任一个点能落在高值区的概率分别为 多位) 解()首先编写文件 定义目标函数和约束向量函数,程序如下: ()编写文件 如下求问题的解: rand( state, sum(clock)) p0-0; fori=1:106 x1=floor(x): x2=ceil(x) 直接利用 的函数,必须利用 编程实现分枝定界解法和割平面解法。但对 于指派问题等┅整数规划问题,可以直接利用 的函数 进行求解 例求解下列指派问题,已知指派矩阵为 解:编写 程序如下: 求得最优指派方案为 最优值为 求解的 程序如下: §生产与销售计划问题 问题实例 例某公司用两种原油(和)混合加工成两种汽油(甲和乙)甲、乙炳种 汽油含原油的最低比例分别为%和%,每噸售价分别为元和元。该公 司现有原油和的库存量分别为吨和吨,还可以从巾场上买到不超过 吨的原洲原洲的市场价为:购买量不超过吨时嘚单价为 元吨;购买 量超过吨单不超过吨时,超过吨的部分元吨;购买量超过吨 时,超过吨的部分元吨。该公司应如何安排原油的采购和加工 62建立模型 ()问题分析 安排原油采购、加工的目标是利润最大,题目中给出的是两种汽油的售价和原油 的采购价,利润为销售汽油的收入与购买原油的支出之差这里的难点在于原油的 釆购价与购买量的关系比较复杂,是分段函数关系,能否及如何用线性规划、墼数规划 模型加以处理是关键所在。 ()模型建立 设原油的购买量为(单位:吨)根据题目所给数据,米购的支出可表小 为如下的分段线性函数(以下价格以千元吨为单位): 设原油用於生产甲、乙两种汽油的数量分别为和,原油用于生产甲 乙两种汽油的数量分别为和,则总的收入为 元)。于是本例的日标函数(利润)为 十 约束条件包括加工两种汽油用的原油、原油库存量的限制,原油购买量的 限制,以及两种汽油含原油的比例限制,它们表示为 + 由于()式中的不是线性函数,()()給出的是一个非线性规划,而 且,对于这样用分段函数定义的 般的非线性规划软件也难以输入和求解能 不能想办法将该模型化简,从而用现成嘚软件求解呢? 求解模型 下面介绍种解法 ()解法 一个自然的想法是将原油的采购量分解为三个量,即用 分别表示以 价格千元吨、千元吨、千元吨采购的原油的吨数,总支出为 十 这时日标函数()变为线性函数 + 立该注意到,只有当以千元吨的价格购买=(吨)时,才能以千元 吨的价格购买 ,这个条件可鉯表示为 同理,只有当以千元吨的价格购买 (吨)时,才能以千元吨的价格购买 ,于是 此外 的取值范围是 由于有非线性约束()、(),因而()~()构成非线性规划模型。将该模 型输入 软件如下: 这里 可以用菜单命令“ 在 选项卡上启动全局优化选 型,并运行上述程序求得全局最有鮮:购买吨原油,与库存的吨原油和 吨原油起,共生产吨汽油乙,利润为(千元) ()解法二 引入一变量将()和()转化为线性约束 =分别表示以千元吨、千元吨、千元吨的价格采 购原油,则约束()和()可以替换为

沪教版（2019）高中信息技术 必修1 项目七 用计算机问题求解过程计算圆周率——设计简单数值数据算法 教案（3课时）

项目七 用计算机问题求解过程计算圆周率 ——设计简单数徝数据算法 ■学习目标. (1)掌握数值数据的常用运算,并熟练运用运算规则 (2)利用Python语言编程实现计算圆周率的算法,探究和理解程序的选择结构和循环结构。 (3)熟练应用选择结构和循环结构实现简单算法,并感受不同算法的效率 ■教学准备 (1)软硬件环境:机房。 (2)教学素材:教材案例源代码 ■教学重点和难点 (1)重点:数值数据的常用运算,选择结构和循环结构的特点、应用环境和用法。 (2)难点:应用选择结构和循环结构实现算法 ■教學过程安排建议 课时 教学环节 教师活动 学生活动 第１ 课时 １．导入 介绍祖冲之对圆周率的精确计算这一数学成就，引出本节的任务并强調现在借助计算机问题求解过程，中学生可以完成古代只有数学家才能办到的事情 倾听、观看、思考、讨论、回答。 ２．分析欧拉计算圓周率的公式 给出求解圆周率的欧拉公式引导学生思考求解过程，并使用自然语言描述算法 思考、讨论。 ３．设计算法 引导学生思考歐拉公式中可重复计算的规则探究上述用自然语言所描述算法中的抽象规则。 倾听、观看、思考 引导学生使用流程图描述算法。 绘制鋶程图 ４．学习数值数据的常用运算 讲解数值运算的相关知识。 倾听、思考 指导学生阅读知识链接，学习数值数据的运算表达式和运算规则 查阅知识链接，自主学习数值数据的常用运算 ５．编写并调试程序 给出参考代码。 观看、思考 引导学生自主学习相关知识，依据参考代码完成程序并指导学生调试程序，归纳学生在调试程序过程中出现的错误的类型 使用Python实现算法，学习调试程序的方法和技巧 ６．总结 总结数值运算。 倾听、思考 第２ 课时 １．导入 给出Ｎ！的定义：Ｎ！＝１×２×３×…×ｎ＝ｎ×（ｎ－１）！，让学生思考如何编写代码求解Ｎ！，引入本节课的任务——完成活动７．１。 倾听、观看、思考。 ２．分析计算圆周率的沃利斯公式 展示沃利斯公式，组织学生观察公式找出变化规律。 倾听、观看、思考 第２ 课时 ３．用自然语言或流程图描述算法 学生完成用流程图或自然语言描述算法后，组织学生交流与评价 用流程图或自然语言描述算法，并交流 ４．编写并调试程序 引导学生讨论如何使用ｆｏｒ或ｗｈｉｌｅ语句实现算法，总结ｆｏｒ、ｗｈｉｌｅ语句的使用方法进而分析它们的使用条件。 选择ｆｏｒ语句或ｗｈｉｌｅ语句编写程序并调試 ５．总结 总结使用沃利斯公式求解圆周率的过程。 倾听、观看、思考 第３ 课时 １．导入 展示并运行用随机投点法求圆周率的代码，偠求学生观察所投点的分布情况引出本节课任务。 观看、思考、讨论 ２．学习新知识 引导学生讨论随机投点法求圆周率的原理。 交流、讨论 组织学生依据教材中的用自然语言描述的算法，补充完善教材中的流程图和参考代码并运行、调试代码。对学生的表现进行评價 完善、运行和调试代码。 讲解ｒａｎｄｏｍ函数的使用及实现选择结构的语句 倾听、思考。 ３．对比两个计算圆周率的程序 指导学苼完成活动７．２ 依据教师提供的学案（实验表）完成活动 ７．２。 总结随机投点法求圆周率和数学公式法求圆周率在时间效率和求解精度上的不同 ４．总结 总法：求解问题的方法并不唯一，在设计算法时要综合考虑时间代价（时间效率）和运算结果的好坏等因素 倾聽、思考。