第五章整数规划jssk运筹学.ppt
《第五章整数规划jssk运筹学.ppt》由会员分享,可在线阅读,更多相关《第五章整数规划jssk运筹学.ppt(73页珍藏版)》请在三一文库上搜索。
1、运 筹 学 Operations Research,Chapter 5 整数规划 Integer Programming,1. 整数规划的数学建模 2. 整数规划的求解算法 3. 案例分析,2019年8月27日星期二,第五章 整数规划,第一节 整数规划的数学模型及解的特点 第二节 解纯整数规划的割平面法 第三节 分枝定界法 第四节 0-1型整数规划 第五节 指派问题,2019年8月27日星期二,在求解线性规划问题时,得到的最优解可能是分数或小数,但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数线性规划(Integer linear Programming) 。,第
2、一节 整数规划的数学模型及解的特点,2019年8月27日星期二,例1 某服务部门各时段(每2h为一时段)需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间,使服务部门服务员总数最少。,设xi表示第i时段开始上班的人数,2019年8月27日星期二,例2 现有资金总额为B,可供选择的投资项目n个,项目j所需投资额和预期收益分别为aj和cj,此外,由于种种原因,有三个附加条件:(1)若选择1,则必须选择2,反之则不一定;(2)项目3和4至少选择一个;(3)项目5、6、7中恰好选择2个。应该如何选择项目,才能使总预期收益最大?,设第i个项目为xi,则其有两种状态,选择
3、投资(记为1)和不选择投资(记为0)。,2019年8月27日星期二,例3 工厂A1和A2生产某种物资。由于该种物资供不应求,故需再建一家工厂,相应的方案有A3和A4两个。这种物资的需求地有B1B4四个。各工厂的生产能力、各地年需求量、各厂至各需求地的单位运费cij见下表。工厂A3或A4开工后,每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设A3还是A4,才能使每年的总费用(即全部物资运费和新工厂生产费用之和)最少。,2019年8月27日星期二,设xij表示第i个工厂供应给第j个需求的地的产量,y表示是否建设A3工厂(取1表示建设A3工厂,取0表示不建设A3工厂),2019年
4、8月27日星期二,【例4】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作,每个岗位一个人。经考核四人在不同岗位的成绩(百分制)如表53所示,如何安排他们的工作使总成绩最好。,表53,2019年8月27日星期二,【解】此工作分配问题可以采用枚举法求解,即将所有分配方案求出,总分最大的方案就是最优解。本例的方案有 4!432124种,当人数和工作数较多时,方案数是人数的阶乘,计算量非常大。用01规划模型求解此类分配问题显得非常简单。,设,数学模型如下: 目标函数为,2019年8月27日星期二,每项工作只能安排一人,约束条件为,变量约束:,要求每人做一项工作,约束条件为,2019年8月27
5、日星期二,引例,某厂拟用火车装运甲、乙两种货物集装箱,每箱的体积、重量、可获利润以及装运所受限制如下:,问两种货物各装运多少箱,可使获得利润最大?,2019年8月27日星期二,是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢?,设甲、乙两种货物装运箱数分别为x1和x2。显然,x1、x2 都要求为整数,于是可建立整数规划模型: Max z20x1+10x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2为整数 (5),2019年8月27日星期二,此例可解得x1=4.8,x2=0,凑整为x1=5,x2=0,这就破坏了条
6、件(2),因而不是可行解;如截断小数变为x1=4,x2=0,这当然满足所有约束条件,但不是最优解,因为对x1=4,x2=0有z80,而对x1=4,x2=1(也是可行解)有z90。,2019年8月27日星期二,整数规划的数学模型,若要求所有 xj 的解为整数,称为纯整数规划 若要求部分 xj 的解为整数,称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的,最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解,2019年8月27日星期二,第二节 割平面法,2019年8月27日星期二,考虑纯整数规划问题:,设其中aij和bi皆为整数(若不为整数时,可乘
7、上一个倍数化为整数)。,2019年8月27日星期二,割平面法是R.E.Gomory于1958年提出的一种方法,它主要用于求解纯整数规划。割平面法是用增加新的约束来切割可行域,增加的新约束称为割平面方程或切割方程。其基本思路为: 若其松弛问题的最优解X*不满足整数约束,则从X*的非整分量中选取一个,用以构造一个线性约束条件,将其加入原松弛问题中,形成一个新的线性规划,然后求解之。若新的最优解满足整数要求,则它就是整数规划的最优解;否则重复上述步骤,直到获得整数最优解为止。,2019年8月27日星期二,为最终获得整数最优解,每次增加的线性约束条件应当满足两个基本性质: (1)已获得的不符合整数要求
8、的LP最优解不满足该线性约束条件,从而不可能在以后的解中出现; (2)凡整数可行解均满足该线性约束条件,因而整数最优解始终被保留在每次剩余的线性规划可行域中。,2019年8月27日星期二,例1 用割平面法求解整数规划问题,步骤1:标准化其松弛问题B0,2019年8月27日星期二,引进一个割平面来缩小可行域,割平面要切去松弛问题的非整数最优解而又不要切去问题的的任一个整数可行解。,用单纯形法求解:,2019年8月27日星期二,步骤2:求一个割平面方程,1)在最终表上任选一个含有不满足整数条件基变量的约束方程。如选x1,则含x1的约束方程为,2)将所选择的约束方程中非基变量的系数及常数项进行拆分处
9、理。具体规则是:将上述系数和常数项均拆分成一个整数加上一个非负真分数(纯小数)之和。则(3)式变为:,2019年8月27日星期二,3)将上述约束方程(4)重新组合。组合的原则是:将非负基变量系数及常数项中的非负真分数移到等号右端,将其他部分移到等号左端,即得:,等式左端实际上由三部分组成,常数项的整数部分,基变量及非基变量(含松弛变量或剩余变量),前两部分都是整数或应取整数,而松弛变量x3、x4由松弛问题标准型知,也应取非负整数(对于这一点,当原问题的约束方程组中的系数或常数项中有非整数时,要求将约束方程先化为成整数系数及整数常数项,然后再标准化,就可满足)。,2019年8月27日星期二,很明
10、显,(5)左端为整数,右端1,则有其右端0,即,4)将割平面方程加到松弛问题的约束方程中,构成新的松弛问题并求解(对偶单纯形法)。,2019年8月27日星期二,割平面方程,2019年8月27日星期二,1、本题注只用一次割平面就求得了最优解,但大多数问题中不是只用一、二次割平面就能求得整数最优解。若一次割平面不能求得整数最优解,则按步骤2中的4个步骤,在松弛问题的最终单纯形表中找出第二个割平面方程,将此割平面方程加到伴随规划中,过程伴随规划,再用对偶单纯形法(单纯形法)求解。若求得了整数最优解,则停止计算,否则继续再作割平面,缩小可行域,直到求得整数最优解为止。,注意:,2019年8月27日星期
11、二,2、实际解题时,经验表明若从最终单纯形表中选择具有最大分数部分的非整分量所在行构造割平面约束,往往可以提高“切割”效果,减少“切割”次数。 3、在用割平面法解整数规划时,常会遇到收敛很慢的情形,因此实际中通常不单独使用。,2019年8月27日星期二,第三节 分枝定界法,2019年8月27日星期二,分枝定界法(branch and bound method)是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题,也可用于混合整数规划问题,而且便于用计算机求解,所以很快成为解整数规划的最主要的方法。 分枝定界法的主要思路是:首先求解整数规划的松弛问题,如果
12、求得的最优解不符合整数条件,则增加新约束缩小可行域;将原整数规划问题分枝分为两个子规划,再解子规划的松弛规划通过求解一系列子规划的伴随规划及不断地定界,最后得到原整数规划问题的整数最优解。,2019年8月27日星期二,分枝定界法的思路:,1. 求整数规划的松弛问题最优解;,2. 若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下一步;,3. 任意选一个非整数解的变量xi,在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题,称为分枝。新的松弛问题具有特征:当原问题是求最大值时,目标值是分枝问题的上界;当原问题是求最小值时,目标值是分枝问题的下界;,2019年8月27日星期
13、二,分枝定界法的思路:,4. 检查所有分枝的解及目标函数值,若某分枝的解是整数并且目标函数值大于(max)等于其它分枝的目标值,则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于(max)整数解的目标值,需要继续分枝,再检查,直到得到最优解。,2019年8月27日星期二,步骤1:用单纯形法求解松弛问题,得到最优解及最优值。,步骤2:分枝。,例2 解整数规划问题,41/910/3, 优先选择B1分枝。,2019年8月27日星期二,无可行解,61/14(B12)10/3(B2), 优先选择B12分枝。,2019年8月27日星期二,410/3,所以B2无需分枝。,2019年8月27日星期二,【
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 整数 规划 jssk 运筹学
链接地址:https://www.31doc.com/p-3453643.html