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

《运筹学第四章整数规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第四章整数规划课件.ppt（34页珍藏版）》请在三一办公上搜索。

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

2、项；(3)项目5选中的前提是1必须被选中。问如何投资才能使收益最大？,投资问题的数学模型：01规划,设01变量为决策变量，即xi=1表示项目i被选中，xi=0表示项目i被淘汰，则模型可表示为,应用举例2：背包问题,目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大。例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。,背包问题的数学模型,解：设01变量表示携带物品i，表示不携带物品i，则问题可写为可通过计算每一物品的重要性系数和重量的比值ci/ai来解决。,应用举例3：布点问题,共同目标：满足公共要求，布点最少，节约投

3、资费用。学校、医院、商业区、消防队等公共设施的布点问题。例：某市6个区，希望设置最少消防站以便节省费用。条件：必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。各区之间消防车行驶的时间见右表。请确定设站方案。,布点问题的数学模型：,设01为决策变量，当表示i地区设站，表示i地区不设站。这样根据消防车15分钟赶到现场的限制，可得到如下模型,4.2 整数规划的求解方法,分枝定界法、隐枚举法、匈牙利法,4.2 整数规划的求解方法,在一般情况下，单纯形法求得的解并不能保证是整数最优解。例：求整数规划求解其松弛问题，很容易得出最优解为。,整数规划图解法,x2,x1,1 2 3 4 5 6

4、 7,2,3,1,A,B,图解法的启示,A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解纯整数规划可行解是可行域中的整数点非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解,求解整数规划的分枝定界法,思路：分枝和定界两部分：分枝：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解定界：松弛问题最优解上界；IP问题的任意可行解下界，不断减小上界和增加上界，最终的最优解。对于最大化问题 对于最小化问题,例1.求解整数规划A解：先不考虑整数要求，解相应的LP问题，得：是I

5、P问题的上界,记作 Z=0，是的一个下界。,分枝定界法（续）,(第一次分枝前）（第一次分枝后）B1 B2子问题B1，子问题B2，,分枝定界法（续）,因为Z1 Z2，故将 改为5.333，那么必存在最优整数解，得到，并且。继续对子问题B1和B2进行分枝。因为Z1 Z2，因此先将B1再分为两枝。增加条件。前者称为子问题B3，后者称为子问题B4。在图中再舍去之间的可行域，再进行第二次迭代。得到的最优解为子问题B3，；子问题B4无可行解。,分枝定界法（续2）,因子问题B3的解中所有变量均为整数，因此它的目标函数值 可取为，由于它大于，因此没有必要对子问题B2进行分枝。于是可以断定。子问题B3的解 为最

6、优整数解。该问题整数解的分枝树如下图所示。,总结：分枝定界法的解题步骤,1、不考虑整数约束，解相应LP问题2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi bi,xi bi+1,分别加入到上一个LP问题，形成两个新的分枝问题。4、不考虑整数要求，解分枝问题。若整数解的Z值所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Go to 3,4.3 求解01规划,隐枚举法,01规划问题的求解方法,某些问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。例投资方案的选择问题：600万元投资5个

7、项目，求利润最大的方案？,求解01规划的隐枚举法,解：0 当项目未被选中 1 当项目被选中 max Z=160X1+210X2+60X3+80X4+180X5 210X1+300X2+150X3+130X4+260X5 600 X1+X2+X3=1 X3+X4=1 X5 X1 Xj=0或1 j=1，2,5增加过滤条件：160X1+210X2+60X3+80X4+180X5 240,建模：设xj=,用隐枚举法解例题：,(x1,x2,x3,x4,x5）,4.4 求解指派问题,匈牙利法,指派问题的描述及特点,问题描述：n项任务恰好由n个人完成。指派哪个人去完成哪项任务，才能使完成n项任务的总效率最高

8、(或所需总时间最小)。问题的特点：若从系数矩阵C的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵B，那么以B矩阵为系数矩阵求得的最优解和原系数矩阵求得的最优解相同。数学家库恩(W.W.Kuhn)提出指派问题的解法，称为匈牙利法。,指派问题举例1：,例:一份说明书，须译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人。问应指派何人去完成何工作，才使所需总时间最少？,minZ=CijXij Xij=1 i=1,n Xij=1 j=1,n Xij=0或1,指派问题解法匈牙利法,第一步 造0各行各列减其最小元素第二步 圈0寻找不同行不同列的0元素，圈之。所在行和列其

9、它0元素划掉 0 13 7 6 6 9 5 3 20 1 0,整数规划的求解方法,分枝定界法、隐枚举法、匈牙利法,指派问题举例2：,例 甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？,指派问题解法匈牙利法,解：第一步 造0各行各列减其最小元素 4 10 7 5-4 0 6 3 1 6 2 1 Cij=2 7 6 3-2 0 5 4 1 0 5 3 1 3 3 4 4-3 0 0 1 1 0 0 1 4 6 6 3-3 1 3 3 0 1 3 2-1 第二步 圈0寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉 第三步 打

10、无的行打，打行上0列打，打列上行打，打行上0列打,指派问题解法匈牙利法（续）,第四步 划线无行、打列划线第五步 造0直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，Go to 2 0 6 2 1-1 5 1 0 0 4 0 Cij=0 5 3 1-1 0 4 2 0 3 1 0 0 0 0 1 1 0 1 2 0 2 1 3 2 0 2 3 2 2 2 1+1 最优解：x13=1,x21=1,x32=1,x44=1 Z=15,相关问题：,非标准型的转化maxZ=CijXij minZ=(-Cij)Xij minZ=(M-Cij)Xij=CijXij M是足够大的常数，新问题的最优解就是原问题的最优解,