6.4+0-1型整数规划

运筹学(OperationsResearch)Chapter6整数线性规划§6.1整数线性规划问题的提出§6.2分支定界解法§6.3割平面解法§6.40-1型整数线性规划§6.5指派问题本章主要内容：Page3§6.40-1型整数线性规划Page43.4.10-1变量及其应用0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象，它所反映了离散变量间的逻辑关系以及约束条件的互斥关系等，它可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。决策变量仅取值0或1的一类特殊的整数规划称为0-1规划。0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和指派问题等方面。§6.40-1型整数线性规划Page51.投资场所的选定——相互排斥的计划例6.9某公司拟在市东、西、南三区建立门市部，拟议中有7个位置(点)Ai(i=1,2,,7)可供选择。规定：–在东区，由A1，A2，A3三个点中至多选两个；–在西区，由A4，A5两个点中至少选一个；–在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?§6.40-1型整数线性规划Page6解：先引入0-1变量xi(i=1,2，…,7),11270iii,Axi,,,.,A被选用令，没有被选用§6.40-1型整数线性规划则建立模型：71123456721101iiiibxBxxxxxxxx约束条件或71iiimaxzcxPage72.相互排斥的约束条件§6.40-1型整数线性规划1212121212max2010(1)5424(2)2513(3),0(4),(5)zxxxxxxxxxx为整数.本章例6.1中今设运货有车运和船运两种方式，下面是用船运时关于体积的限制条件为127345(6)xx车运的体积限制这两个条件是互相排斥的。为了统一在一个问题中，引入0-1变量y，令Page8于是(2)式和(6)式可由下述条件(7)式和(8)式来代替：§6.40-1型整数线性规划可验证,当y=0时，(7)式就是(2)式，而(8)式自然成立；当y=1时，(8)式就是(6)式，而(7)式是多余的。10,y,采用船运方式采用车运方式127345+(1)(8)xxyM125424+(7)xxyMM其中是充分大的数.Page9121212121212max2010(1)5424+(7)7345+(1)(8)2513(3),0(4),(5)zxxxxyMxxyMxxxxxx整.Page10就合于上述的要求。这是因为，由于(6-14)式，m个yi中只有一个能取0值，设yi*=0，代入(6-13)式，就只有i=i*这个约束条件起作用，而别的式子都是多余的。§6.40-1型整数线性规划1122,i1,2,,iiinniaxaxaxbm如果有m个互相排斥的约束条件(≤型)：为了保证这m个约束条件只有一个起作用，引入m个0-1变量yi(i=1,2,…，m)和充分大的常数M，且下面这一组m+1个约束条件1122,1,2,,iiinniiaxaxaxbyMim121,1,2,,myyymimPage11为了选修课程门数最少，应学习哪些课程？例6.14选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数Page12决策变量目标函数选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机91iiminzx123452xxxxx356893xxxxx46792xxxx10129i,ix,ii,,,.选修课号为的课程令，不选修课号为的课程§6.40-1型整数线性规划Page13最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分21模型求解（LINDO）§6.40-1型整数线性规划Page14在讨论线性规划时，有些问题是要求使成本为最小。这时，通常设固定成本为常数，不必在线性规划模型中明显列出。但有些固定费用(固定成本)问题不能用一般线性规划来描述，可改变为混合整数线性规划来解决。§6.40-1型整数线性规划3.固定费用的问题Page15例6.10某工厂为生产某种产品，有几种生产方式供选择。如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为,01,2,3.0,0jjjjjjkcxxPjx，§6.40-1型整数线性规划Page16为了统一在一个问题中讨论，引入0-1变量§6.40-1型整数线性规划1,,0(15)0,,0jjjjxyjx采用第种生产方式即不采用第种生产方式即约束条件不是线性的，但是可以把它用一个线性约束条件等价地表示为：,1,2,3.iiyMjMx其中是充分大的常个数.0-1jy注意量变当xj＞0时，yj必须为1；当xj=0时，只有yj为0时才有意义。所以上式完全可以代替(15)式。Page17111122223333min()()()zkycxkycxkycx则目标函数为,1,2,3..01,1,2,3.iiixyMjstyj或§6.40-1型整数线性规划Page18①穷举法，即检查变量取值为0或1的每一种组合，并比较目标函数值以求得最优解。这就需要检查变量取值的2n个组合。当变量个数n较大(例如n＞10)时，这几乎是不可能的。②隐枚举法(implicitenumeration):在此基础上，通过加入一定的条件，就能较快的求得最优解。只需要检查变量取值组合中的一部分，就能求到问题的最优解。分枝定界法就是一种隐枚举法。隐枚举法是一种简单方便，常用于手算或求解小规模问题的方法。§6.40-1型整数线性规划6.4.2求解0-1型整数线性规划的方法Page19§6.40-1型整数线性规划1231231231213123max32522(1)44(2).3(3)46(4),,=01(5)zxxxxxxxxxstxxxxxxx或例6.11求解下列0－1规划问题解一:（穷举法）Page20§6.40-1型整数线性规划(x1,x2,x3)约束条件满足条件？z值①②③④（0,0,0）0000√0（0,0,1）-1101√5（0,1,0）2410√-2（0,1,1）1511×（1,0,0）1110√3（1,0,1）0211√8（1,1,0）3524×（1,1,1）2625×3个变量共有23个可能的解,4个约束条件，共需32次运算。1231231231213123max32522(1)44(2).3(3)46(4),,=01(5)zxxxxxxxxxstxxxxxxx或Page211）先通过试探的方法找一个可行解。易看出(x1,x2,x3)=(1,0,0)就是合于①～④条件的，算出相应的目标函数值z=3。2)下面来求最优解。对于极大化问题，当然希望z≥3，于是增加一个约束条件§6.40-1型整数线性规划解二：（隐枚举法）则原问题的线性约束条件就变成了5个。1233253xxx◎称为过滤条件Page22§6.40-1型整数线性规划（x1,x2,x3）约束条件满足条件？z值◎①②③④（0,0,0）0×（0,0,1）5-1101√5（0,1,0）-2×（0,1,1）31511×（1,0,0）31110√3（1,0,1）80211√8（1,1,0）1×（1,1,1）626×最优解为:(x1，x2，x3)=(1,0,1),maxz=8，只作了24次运算.1233253xxxPage23改进过滤性条件，在计算过程中随时调整右边常数。价值系数按递增(不减)排列。以上两种方法可减少计算量。还可以继续改进，使得计算的次数更少？§6.40-1型整数线性规划Page24解三：（继续改进）§6.40-1型整数线性规划在计算过程中，若遇到z值已超过条件◎右边的值，应改变条件◎，使右边为迄今为止最大者，然后继续作。1233255xxx◎′这种对过滤条件的改进，更可以减少计算量。例如，当点(0，0，1)时因z=5(＞3)，所以应将条件◎换成Page25凡是目标函数值小于5的组合不必讨论，如下表。（x1,x2,x3）约束条件满足条件？z值◎′①②③④（0,0,0）0×（0,0,1）5-1101√5（0,1,0）-2×（0,1,1）3×（1,0,0）3×（1,0,1）80211√8（1,1,0）1×（1,1,1）626ק6.40-1型整数线性规划Page26解四：§6.40-1型整数线性规划123213325235zxxxxxx−2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0,0,0)(0,0,1),(0,1,0),(0,1,1)，….。这样最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化。2132132132132113123max235235322(1)44(2).3(3)46(4),,=01(5)zxxxxxxxxxxxxstxxxxxxx◎或Page27§6.40-1型整数线性规划（x2,x1,x3）约束条件满足条件？z值◎①②③④（0,0,0）0×（0,0,1）5-1101√5（x2,x1,x3）约束条件满足条件？z值◎′①②③④（0,1,0）3×（0,1,1）80211√8改进过滤性条件z51233255xxxPage28改进过滤性条件z8最优解(x2,x1,x3)=（0，1，1）,z=8,只计算了16次（x2,x1,x3）约束条件满足条件？z值◎〞①②③④（1,0,0）-2×（1,0,1）3×（1,1,0）1×（1,1,1）6ק6.40-1型整数线性规划Page29练习：用隐枚举法求解0—1规划问题（0,1,1,0,0）§6.40-1型整数线性规划1234512345123452345min571033542263220.2101(1,2,,5)jzxxxxxxxxxxxxxxxstxxxxxj或Page30小结学习要点：1.掌握一般整数规划问题概念及模型结构；2.掌握分支定界法原理。3.能够用分支定界法求解一般整数规划问题。Theend,thankyou!