第五章整数规划课件.pptVIP

 Chapter 4整数规划integer programming 上海工程技术大学——管理学院 学习目标 通过本章对整数规划问题的学习、研究，了解整数规划在实际生产生活中所起到的重要作用。了解掌握指派、选址等整数规划问题，熟练掌握整数规划问题的数学模型，能够运用分枝定界法求解整数规划问题的最优方案及其最大利润。Matlab语言则具有计算功能强、使用简便、其程序可读性好的特点，因此运用MATLAB能很好地解决运筹学问题。因此，在本章中，将在分枝定界法的基础上，要求掌握Matlab软件求解最优方案的方法，并会操作使用与实际运用。 本章提要 Content 整数规划数学模型 分枝定界法 割平面法 0-1型整数规划 指派问题 整数规划的MATLAB实现 习题 整数规划问题的提出 在线性规划问题中,它的解都假设为具有连续型数值.但是在许多实际问题中,决策变量仅仅在取整数值时才有意义,比如变量表示的是工人的数量,机器的台数,货物的箱数,装货的车皮数等等. 实际问题中经过“四舍五入”处理得到的解可能不是原问题的可行解,有的虽是原问题的可行解,但却不是整数最优解.因而有必要研究整数规划问题的解法. 整数规划数学模型 例1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下： 问两种货物各装运多少箱，可使获得利润最大？ 设甲、乙两种货物装运箱数分别为和。显然，、都要求为整数,于是可建立整数规划模型如下： 那么，怎么建立这个整数规划问题的模型呢？ 整数规划的一般模型 分枝定界法 在20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝定界法. 分枝定界法的主要思路是首先求解整数规划的伴随规划 , 如果求得的最优解不符合整数条件,则增加新约束——缩小可行域;将原整数规划问题分枝——分为两个子规划,再解子规划的伴随规划……通过求解一系列子规划的伴随规划及不断地定界 .最后得到原整数规划问题的整数最优解 . 我们用一个例题来具体介绍 例2 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 ×103, 乙种每幢地0.4×103.该公司拥有土地3×103. 计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应计划甲、乙两种类型宿舍各建多少幢时,能使公司获利最大 ? 解：设计划甲种宿舍建 幢,乙种宿舍建 幢， 则本题数学模型为 : 将约束条件的系数化为整数，可以得到： 求解步骤如下： 计算原问题目标函数值的初始上界 计算原问题目标函数值的初始下界 增加约束条件将原问题分枝 分别求解一对分枝 修改上、下界 结束准则 本例的求解过程与结果可用右图来描述 。 割平面法 用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。 割平面法的具体求解步骤如下： 对于所求的整数规划问题，先不考虑整数约束条件，求解相应的松弛问题 如果该问题无可行解或已取得整数最优解，则运算停止；前者表示原问题也无可行解，后者表示已求得整数最优解。如果有一个或更多个变量取值不满足整数条件，则选择某个变量建立割平面。 增加为割平面的新约束条件，用灵敏分析的方法继续求解，返回1。 割平面法的求解步骤可以用下图来表示： 0-1型整数规划 0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件 ，因此0-1规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。 例: 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置 （i=1,2, …,7）可供选择。规定：(1)在东区、、三个点中至多选两个；(2)在西区、两个点中至少选一个；(3)在南区、两个点中至少选一个。 如选用点，设备投资估计为元，每年可获利润估计为元，但投资总额不超过B元。问应选择哪几个点可使年利润为最大？ 引入0-1变量（i=1,2,…,7）,令