[管理学]整数规划.ppt

整数规划,回顾：线性规划模型,前面指出，线性规划在生产实践中有重要作用，能够解决许多优化问题； 用单纯性算法能方便地对线性规划问题求解,已知： 两种货物装葙 每种货物装葙利润 体积限制 重量限制 决策变量:两种货物各多少箱 Max Z =利润最大？ 箱数不能为分数,另一类现实问题,实践中的其他问题举例,背包问题：背包的容积一定，现有多种物品待装，各物品的价值、体积已知，求最优配装方案，使得在不超过背包的容量的前提下装入物品的价值最大。 选址问题：某商场在全市有数个连锁店，拟建立n个仓库对所有连锁店供货，有数个地点作为被选点。问在何处建设仓库使得各仓库到所有连锁店的总距离最小。 投资决策问题：现有一定的资金，有数个可以考虑的投资项目。每个项目需要的资金和利润已知。问如何选择投资项目，使得获得的利润最大。,分析,以上问题的特点是：变量为整数 背包问题：对每一件物品进行取舍，装或者不装； 选址问题：对每一个被选点有两种选择，在这里建或者不在这里建； 投资决策问题：对每一个考虑的项目，投资或者不投资。 这类问题无法用线性规划求解！因为线性规划的解可能包含小数部分,整数规划模型,分析,整数规划模型反映了上述例子的特征，适宜解决这类问题； 整数规划与线性规划相比，增加了变量部分或全部为整数的条件。,.,.,.,.,.,o,(0,6),(0,2.6),(4,1),(4.8,0),(6.5,0),X1,X2,甲货物运输的箱数 乙货物运输的箱数 Max Z = 20X1+10X2 每箱利润 5X1 + 4X2 =0 , X2 =0 X1, X2 整数（箱数不能为分数）,目标函数等值线,线性规划的最优解(4.8,0) 整数规划的最优解(4,1),整数规划求解,可以想到的解法 枚举法：解决多数问题工作量太大！ 邻近点法： 优点： 简单，易操作； 若原问题的最优解很大，对找邻近点的误差不敏感，则成立； 缺点：有时候不成立。,邻近点法的反例,原问题的最优解（2.25，3.75） 最优值：z=41.25 利用邻近点法： （2，3） z=34 （3，3） z=39 （2，4） 无解 （3，4） 无解 实际上：本问题的最优解（0，5） 最优值：z=40,启示,邻近点法虽然不成立，但是给我们一个很好的思路！ 不要硬碰硬的去直接解决整数规划！ 先解决它所对应的线性规划，从其最优解出发，逐渐向整数规划的最优解靠拢,分枝定界法的原理：,1、分枝,松弛问题的可行域,增加x13,增加x14,L1,L2,x13,x14,父问题,子问题,结论1 ：（IP）的最优解一定在某个子问题中,父问题的最优值,3 ：子问题中的整数解都是（IP）的可行解,子问题的最优解,2 ：子问题的可行域,父问题的可行域,2、定界,1、（LP）的最优值是(IP)的最优值的上界,IP,松弛问题L0,L1,L2,通过对（L0）分枝，使（IP）的最优值 的上界不断下降，,L3,L4,L5,L6,下界不断上升，,上界=下界,得最优值,分枝定界法的基本思路：,不断降低（IP）最优值的上界，提高下界， 当上界等于下界时，得到最优解,通过对松弛问题的分枝，,分枝定界法计算过程：,上界,x1x*01,x1x*01+1,当所有的子问题均被关闭或剪枝后,目标函数值最大的整数解既为所求的最优解,x13,x14,z=30x1+20 x2,4x1+x2=16.5,2x1+3x2=14.5,x22,x23,x12,x13,如何选择分枝的节点及分枝变量？,1、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点， 提高搜索效率。,方法：,（1）深探法：,（2）广探法：,最后打开的节点最先选择,选择有最大目标函数值的节点继续向下分枝,2、分枝变量选择的原则：,寻找那些对问题影响最大的变量首先分枝,（1）按目标函数系数选择：,选择目标函数系数绝对值最大的变量首先分枝,（2）按非整数变量选择：,选择与整数值相差最大的非整数变量进行分枝,（3）按人为给定的顺序选择,第3节 割平面解法,割平面解法的思想 首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解整数线性规划问题。 若得到非整数的最优解，则增加能割去非整数解的线性约束条件(或称为割平面)，使得由原可行域被切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。 割平面方法就是指出怎样找到适当的割平面(不见得一次就找到)，使切割后最终得到这样的可行域，它的一个整数极点恰好是问题的最优解。 以下仅讨论纯整数线性规划的情形。,第3节 割平面解法,例3 求解 目标函数 max z=x1+x2 约束条件： -x1+x21 3x1+x24 (5-3) x1，x20 x1，x2 整数 ,第3节 割平面解法,先不考虑条件，求得相应的线性规划的最优解为： x1=34，x2=74，max z=104,最优解是图5-5中域R的极点A，但不符合整数约束条件。,第3节 割平面解法,现设想，如能找到像CD那样的直线去切割域R(图5-6)，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R的一个极点。,如在域R上求解，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。,图5-6,第3节 割平面解法,在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束： x1+x2+x3 =1 3x1+x2 +x4=4 不考虑条件，用单纯形表解题，见表5-2。,第3节 割平面解法,从表5-2的最终计算表中，得到非整数的最优解： x1=3/4，x2=7/4，x3=x4=0，max z=5/2,第3节 割平面解法,由于目前得到的解不满足整数最优解要求，需要考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。 可从最终计算表中得到非整数变量对应的关系式：,第3节 割平面解法,为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和 (1+0)x1+(-1+3/4)x3+1/4x4=0+3/4 x2+(3/4)x3+(1/4)x4=1+3/4 然后将整数部分与分数部分分开，移到等式左右两边，得到：,第3节 割平面解法,现考虑整数条件 要求x1、x2都是非负整数，于是由条件、可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在等式右边的()内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件可由下式所代替： 即 3x3 x4 3 ,第3节 割平面解法,这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。 引入松弛变量x5，得到等式 3x3 x4+x5= 3 将这新的约束方程加到表5-2的最终计算表，得表5-3。,第3节 割平面解法,这从表5-3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。 选择x5为换出变量，计算,第3节 割平面解法,将x3做为换入变量，再按原单纯形法进行迭代，得表5-4。,第3节 割平面解法,注意：新得到的约束条件 3x3 x4 3 如用x1、x2表示，由、式得 3(1+x1 x2)+(4 3x1 x2)3 x21 这就是(x1，x2)平面内形成的新的可行域，即包括平行于x1轴的直线x2=1和这直线下的可行区域，整数点也在其中，没有切割掉,见图5-7。,图5-7,第3节 割平面解法,求一个切割方程的步骤为： (1) 令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到,其中iQ (Q指构成基变量号码的集合) kK (K指构成非基变量号码的集合),第3节 割平面解法,(2) 将bi和ik都分解成整数部分N与非负真分数f之和，即 bi=Ni+fi，其中0fi1 ik=Nik+fik，其中0fik1 (5-5) 而N表示不超过b的最大整数。例如： 若b=2.35，则N=2，f=0.35 若b= 0.45，则N= 1,f=0.55 代入(5-4)式得,第3节 割平面解法,(3) 现在提出变量(包括松弛变量)为整数的条件(当然还有非负的条件)。 这时，上式由左边看必须是整数，但由右边看，因为0fi1，所以不能为正，即 这就是一个切割方程。 由(5-4)式，(5-6)式，(5-7)式可知： 切割方程(5-7)式真正进行了切割，至少把非整数最优解这一点割掉了。 没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(5-7)式的缘故。,实例： 已知：1 项目A1.Ak产生的利润, 2 项目A1.Ak需要的投资量 3 总投资额 选择哪些项目使总利润达到最大？,0-1整数规划,互相排斥的计划：,（三点中最多选两点）,（两点中至少选一点）,（两点中至少选一点）,决策变量：投资项目Ai or not,投资项目Ai利润,0-1整数规划建模,一、投资场所的选择 例 京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 且xj 为0-1变量，i = 1,2,3,10,互相排斥的约束条件： 用车运的体积约束 用船运的体积约束,如果有m个互相排斥的约束条件(型)： i1x1+i2x2+inxnbi，i=1，2，,m 为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,，m)和一个充分大的常数M，且下面这一组m+1个约束条件 i1x+i2x2+inxnbi+yiM i=1,2,，m (5-13) y1+y2+ym=m 1 (5-14) 就合于上述的要求。这是因为，由于(5-14)式，m个yi中只有一个能取0值，设yi*=0，代入(5-13)式，就只有i=i*这个约束条件起作用，而别的式子都是多余的。,固定费用的问题 在讨论线性规划时，有些问题是要求使成本为最小。这时，通常设固定成本为常数，不必在线性规划模型中明显列出。但有些固定费用(固定成本)问题不能用一般线性规划来描述，可改变为混合整数线性规划来解决。,例5 某工厂为生产某种产品，有几种生产方式供选择。如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令 xj表示采用第j种方式时的产量； cj表示采用第j种方式时每件产品的变动成本； kj表示采用第j种方式时的固定成本。 为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为,在构成目标函数时，为了统一在一个问题中讨论，引入0-1变量yj，令,于是，目标函数为 min z=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3),(5-15)式的规定可由以下3个线性约束条件表示： xjyjM，j=1,2,3 (5-16) 其中M是个充分大的常数。 (5-16)式说明 当xj0时，yj必须为1； 当xj=0时，只有yj为0时才有意义。 所以，(5-16)式完全可以代替(5-15)式。,某公司拟生产窗和玻璃门，其中下属的工厂A生产门框，工厂B生产窗框，工厂C生产玻璃并进行组装。 每扇门需要工厂A1小时、工厂C3小时；每扇窗需要工厂B 2小时、工厂C2小时； 工厂A每周生产时间为40小时，工厂B每周生产60小时，工厂C每周生产80小时。 门的单位利润为300元，窗的单位利润为500元。 求门与窗的最优生产数量使利润最大？,例,延伸1：生产启动成本 对于每一种产品，在开始生产之前需要为安装生产设备支出一次性的准备成本，门和窗的准备成本分别为700元、1200元。,延伸2：产品互斥 公司决定不同时生产两种产品,延伸3：加入2选1约束 公司新建1个工厂D与C功能相同，每周可生产时间为100小时，每扇门和窗分别需要2小时、4小时。 公司决定工厂C与D只有1个用于生产门和窗，问最大利润目标下应如何选取？,选课问题,某学校规定，管理学专业的学生毕业时必须至少学习过2门数学课、3门经济学课和2门计算机课。这些课程的编号、名称、学分、所属类别、先修课要求如表所示。问毕业时学生最少可以学习这些课程中的哪些课程？,分析,用xi =1或0表示各课程（按照编号）是否选择，目标函数为选修的课程数最少： Min z =x1+x2+x3+x4+x5+x6+x7+x8+x9 约束条件1：各类型课程数量要求 x1+x2+x3+x4+x5=2 x3+x5+x6+x8+x9=3 x4+x6+x7+x9=2,约束条件2：先修课程要求-=0 如数据结构x4的先修课程是计算机程序设计x7，则若x4=1，必有x7=1，可以表示为x4 =x7 2x3-x1-x2=0 x4-x7=0 2x5-x1-x2=0 x6-x7=0 x8-x7=0 2x9-x1-x2=0,二、固定成本问题 例高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容器即 xi = 0 时）。 引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 为0-1变量，i = 1,2,3,三、分布系统设计 例7某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?,解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0（当Ak 没被选中时),k =2,3,4,5这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+ 3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 其中前4项为固定投资额，后面的项为运输费用。 s.t. x11+ x12+ x13 30 ( A1 厂的产量限制) x21+ x22+ x23 10y2 ( A2 厂的产量限制) x31+ x32+ x33 20y3 ( A3 厂的产量限制) x41+ x42+ x43 30y4 ( A4 厂的产量限制) x51+ x52+ x53 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij 0，i = 1,2,3,4,5； j = 1,2,3， yk 为0-1变量，k =2,3,4,5。,例1,某商业公司为给4个新建居民区供货，欲从3个可供选择的地点中选择2个建立商品批发仓库。每个仓库到每个居民区的运输货物成本以及仓库建造费用如下表所示。假设仓库建造费用每年按照10%折合。 试研究成本最低的仓库建点及运输方案。,数据表,解,设每年从第i个仓库向第j个居民区运送货物xij万吨。yi表示是否建造第i个仓库。 Min 1.5x11+0.7x12+2.1x13+1.6x14+0.8x21 +1.5x22+1.7x23+2.2x24+1.2x31+2.3x32 +0.9x33+1.1x34+0.85y1+1.0y2+0.9y3,S.t. x11+x21+x31=1.2 x12+x22+x32=0.4 x13+x23+x33=0.6 x14+x24+x34=1.3 x11+x12+x13+x14-1.8y1=0 x21+x22+x23+x24-2.3y2=0 x31+x32+x33+x34-2.1y3=0 y1+y2+y3=2 Yi=0或1,隐枚举法基本思想：隐枚举法是分枝定界法思想的延伸。通过放松主约束条件（而非变量符号限制条件）求得最优解，再检查是否满足约束条件，再经过分枝与剪枝等工作迭代出最优解。,0-1规划的解法隐枚举法,Max Z = 3X12X2 5X3 X1 + 2X2 X3 =2 （1） X1 + 4X2 + X3 =4 （2） X1 + X2 =3 （3） 4X2 + X3 =6 （4） X1, X2 , X3 0 或者1 （5）,解：观察（X1, X2 , X3 ）（1，0，0） 满足约束（1）（5） 相应 Z = 3 增加一个约束 , 目标值=3 3X12X2 5X3 =3 （*）称为过滤条件（Filtering Constraint ） 对于其他解，目标值低于3的一律不考虑,0-1整数规划求解,对于其他解，目标值低于3的一律不考虑 于是最优解（X1, X2 , X3 ）（1，0，1） Max Z = 8,Max Z = 2X2 3X1 5X3 目标函数按系数递增（2，3，5） 约束条件也按上面决定的顺序 2X2 3X1 5X3 =3 （*） 2X2 X1 X3 =2 （1） 4X2 + X1 X3 =4 （2） X2 X1 =3 （3） 4X2 + X3 =6 （4） X1, X2 , X3 0 或者1 （5）,解：变量（X1, X2 , X3 ）按下面顺序容易更早发现最优解： （0，0，0） （0，0，1） （0，1，0） （0，1，1） .,改进过滤条件，用： 3X12X2 5X3 =5 （*） 为过滤条件 对于其他解，目标值低于5的一律不考虑,再改进过滤条件，用： 3X12X2 5X3 =8 （*） 为过滤条件,对于其他解，目标值低于8 的一律不考虑,Max Z = 2X2 3X1 5X3 目标函数按系数递增（2，3，5） 约束条件也按上面决定的顺序 2X2 3X1 5X3 =3 （*） 2X2 X1 X3 =2 （1） 4X2 + X1 X3 =4 （2） X2 X1 =3 （3） 4X2 + X3 =6 （4） X1, X2 , X3 0 或者1 （5）,解：变量（X1, X2 , X3 ）按下面顺序容易更早发现最优解：（0，1，1）,对应目标函数系数（2，3，5）负系数的Xi 取0，正系数的Xi 取1 这时目标函数达到最大值，但不一定满足约束条件 如果满足约束条件，则不必检验其他解，一步直达。,指派问题一般模型,指派矩阵,指派问题例题,注意到： 1 从人来看，如果乙不作日语，损失特别大6 2 从事来看，如果英语不分配给甲，损失特别大5,原理：从人的角度思考考虑人最适合的工作 从工作的角度思考.考虑工作最适合的人,各行都减去这一行的最小值，得到的0表示这个0所在的行对应的人最适合的工作是这个0所在的列对应的事,这一列有三个0，表示这一列的事有三个人适合作,行最小值,指派问题第一步:各行元素该行行最小各列元素该列列最小 本题有n个独立的0元素则已得最优解,各列都减去这一列的最小值，得到的0表示这个0所在的列行对应的事最适合的人是这个0所在的行对应的人,甲 俄 乙 日 丙 英 丁 德,列最小值,有三个人适合英文 为什么确定丙英,各列都减去这一列的最小值,每行至少一个0,各行都减去这一行的最小值,每列至少一个0,某列0的个数特别少，是什么意思？,某行0的个数特别少，是什么意思？,某列0的个数特别多，是什么意思？,某行0的个数特别多，是什么意思？,指派问题的匈牙利法： 第一步:各行元素该行行最小， 各列元素该列列最小 若有n个独立的0元素则已得最优解，本题有n个独立的0元素,列仅一个零表示这个工作只适合一个人,行仅一个零表示这个人只适合一个工作,甲 俄 乙 日 丙 英 丁 德,颜色表示“确定”,指派问题的匈牙利法： 第一步:各行元素该行行最小，各列元素该列列最小 本题没有n个独立的0元素，转第二步,第二步完成后，我们把注意力集中在没有分配工作的人戊及其特长上-第5行没有颜色表示戊没有分配工作,第三步：对没有 画圈 的第5行加 ;对已加 的行中的零元素所在第1列加 表示戊适合作这列确定的事A 对加 的列中有颜色 的元素所在第3行加 表示A事所确定的人丙可能调整 重复上面,丙只合适一件事情A，确定 丙A