运筹学第四章 整数规划ppt课件.ppt

《运筹学第四章 整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章：特殊的线性规划整数规划本章的主要内容：理解整数规划的基本概念掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的求解方法4.1整数规划问题的提出整数规划的应用背景4.1整数规划问题的提出决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢所谓整数规划，就是指决策变量有整数要求的数学规划问题。问题分类：纯整数规划、混合整数规划、0-1整数规划专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法应用举例1：投资问题5个投资项目；600万元资金，投资受到约束：(1)项目1、2和3至少一项被选

2、中；(2)项目3和4只能选一项；(3)项目5选中的前提是1必须被选中。问如何投资才能使收益最大？项目投资额(万元)期望收益(万元)121015023002103100604130805260180投资问题的数学模型：0－1规划设01变量为决策变量，即xi=1表示项目i被选中，xi=0表示项目i被淘汰，则模型可表示为应用举例2：背包问题目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大。例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。数据物品项目食品氧气冰镐绳索帐篷照相

3、器材通信设备重量(千克)55261224重要系数201518148410背包问题的数学模型解：设01变量表示携带物品i，表示不携带物品i，则问题可写为可通过计算每一物品的重要性系数和重量的比值ci/ai来解决。应用举例3：布点问题共同目标：满足公共要求，布点最少，节约投资费用。学校、医院、商业区、消防队等公共设施的布点问题。例：某市6个区，希望设置最少消防站以便节省费用。条件：必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。各区之间消防车行驶的时间见右表。请确定设站方案。地点一区二区三区四区五区六区一区0二区100三区16240

4、四区2832120五区271727150六区20102125140布点问题的数学模型：设01为决策变量，当表示i地区设站，表示i地区不设站。这样根据消防车15分钟赶到现场的限制，可得到如下模型4.2整数规划的求解方法分枝定界法、隐枚举法、匈牙利法4.2整数规划的求解方法在一般情况下，单纯形法求得的解并不能保证是整数最优解。例：求整数规划求解其松弛问题，很容易得出最优解为。整数规划图解法x2x11234567231AB图解法的启示A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解纯整数规划可行解是可行域中的整数

5、点非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解求解整数规划的分枝定界法思路：分枝和定界两部分：分枝：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解定界：松弛问题最优解——上界；IP问题的任意可行解——下界，不断减小上界和增加上界，最终的最优解。对于最大化问题对于最小化问题例1.求解整数规划A解：先不考虑整数要求，解相应的LP问题，得：是IP问题的上界,记作Z=0，是的一个下界。分枝定界法（续）(第一次分枝前）（第一次分枝后）B1B2子问题B1，子问题

6、B2，分枝定界法（续）因为Z1＞Z2，故将改为5.333，那么必存在最优整数解，得到，并且。继续对子问题B1和B2进行分枝。因为Z1＞Z2，因此先将B1再分为两枝。增加条件。前者称为子问题B3，后者称为子问题B4。在图中再舍去之间的可行域，再进行第二次迭代。得到的最优解为子问题B3，；子问题B4无可行解。分枝定界法（续2）因子问题B3的解中所有变量均为整数，因此它的目标函数值可取为，由于它大于，因此没有必要对子问题B2进行分枝。于是可以断定。子问题B3的解为最优整数解。该问题整数解的分枝树如下图所示。总结：分枝定界法的解题步骤1、不考虑整数约束，解

7、相应LP问题2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi≤[bi],xi≥[bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。4、不考虑整数要求，解分枝问题。若整数解的Z值>所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Goto34.3求解0－1规划隐枚举法0—1规划问题的求解方法某些问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。例投资方案的选择问题：600万元投资5个项目，求利润最大的方案？项目投资额项目收益约束条

8、件210160中选1项300210之中选1项15060选必先选13080260180求解0—1规划