1、(Integer Programming,IP)|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题|要求一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规划，则该整数规划为整数线性规划。（integer linear programming）|纯整数线性规划，混合整数线性规划，01型整数线性规划。|某财团有 万元的资金，经过考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 万元 ，问应如何选择项
2、目使得5年后总收益最大？Bnjjcjbnj.,2,1|变量每个项目是否投资|约束总金额不超过限制|目标总收益最大njxBxbtsxcjnjjjnjjj.,2,1;0,1.max11|某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。
3、物品12345678910体积200350500430320120700420250100价格1545100705075200902030|变量变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中3,2,1,17.,2,1;0,1jixij|约束约束 包裹容量限制：必带物品限制：选带物品限制：|目标函数目标函数 未带物品购买费用最小3,2,1;171jrxcjijii7.,2,
4、1;131ixjij17.,2,8;131ixjij)1(min31178jijiixp)1(min31178jijiixp17.,2,8;131ixjij3,2,1;171jrxcjijii7.,2,1;131ixjij3,2,1,17.,2,1;0,1jixijs.t.n特征特征变量整数性要求；n来源来源 问题本身的要求；引入的逻辑变量的需要；n性质性质可行域是离散集合；|一般整数规划模型|0-1整数规划模型|混合整数规划模型整数线性规划线性数学问题模型的一般形式为nj=1nj=112max(min)=(=)(1,2,.,).0(1,2,.,),.,iji jjijncxa xb imst
5、xjnx xx或或，或中全部取整数nj=1nj=1max(min)=(=)(1,2,.,).=01(1,2,.,)ijijjijcxa xb imstxjn或或，或，nj=1nj=112max(min)=(=)(1,2,.,).0(1,2,.,),.,iji jjijnc xa xb imstxjnx xx或或，或中部分取整数|现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,，n)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰
6、好选择两个。应当怎样选择投资项目，才能使总预期收益最大?属于 0-1规划问题|令|问题模型为：1(1,2,.,)0jjxjnj对项目 投资对项目 不投资njxxxxxxxxBxatsxczjnjjjnjjj.,2,1;0,121.max765431211为整数整数规划问题：jxXbAXtsCXz0.max0.maxXbAXt sCXz（IP）问题的松弛问题的可行解域）（IP1松弛问题的可行解域若松弛问题无可行解，无可行解则IP的最优值）（IP2松弛问题的最优值松弛问题的最优值是原整数规划的目标函数值的上界。，个整数解若松弛问题可以找到一X)3(最优值的下界的目标函数值是则IPX为整数解）若松弛
7、问题的最优解（*4X的最优解也是则IPX*|最优解不一定在顶点上达到|最优解不一定是松弛问题最优解的邻近整数解|整数可行解远多于顶点，枚举法不可取|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题割平面法的基本思想：若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总
8、可以在有限次后得到IP的最优解.割平面法|由松弛问题的可行域向整数规划的可行域逼近|方法利用超平面切除|要求整数解保留 松弛问题最优值向最优解逼近|目标得到的新的可行域的某个整数坐标的极点恰好是问题的最优解 iNjijbfaf非基变量下标集合ijijijijijijbfbbafaan符号*表示不超过“*”的最大整数，f(*)表示“*”的非负真分数。|Gomory约束为整数：对整数规划问题jxXbAXtsCXzIP0.max0.max0XbAXtsCXzL其松弛问题不是整数解的最优解设00XL0,0,00100mibbbX不妨设是非基变量是基变量，即nmmixxxxx,11是分数其中0ibL0的
9、最优单纯形表：x1 xi xmxm+1 xm+j xn解检0 0 01 m+j nz-z0 x11 0 0a1m+1 a1m+j a1nb10 xi0 1 0aim+1 aim+j ainbi0 xm0 0 1amm+1 amm+j amnbm0所在行的方程为：0ib011ininjmjimmimibxaxaxax源方程0,0,001000mibbbXL 的最优解设是分数0,ib011ininjmjimmimibxaxaxax对源方程：00iifb100ifjimjimfa10 jimf01ijmmnjjimibxax 001)(iijmjimjimmnjifbxfax 0011iijmmnj
10、jimjmmnjjimifbxfxax jmmnjimijmmnjjimiixffxabx11010010jmmnjjimixff令-对应于生成行i的割平面01)(ijmmnjjimfxf即1.松弛问题的非整数最优解不满足上式2.松弛问题的整数可行解满足上式|求解整数线性规划121212121212ma x3-3-2351 0.25,0,zxxxxxxstxxxxxx为整数第一步：解整数规划问题的松弛问题，见表5-3，x1=13/7，x2=9/7；4cj3-1000cBxBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122
11、/7cj-zj00-5/70-3/7表 5-3|第二步：写出割平面方程，选择第一行产生割平面约束，-6/72/7x-1/7x-53cj3-10000cBxBibix1x2x3x4x5x63-100 x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/70001cj-zj-5/200-5/70-3/703-100 x1x2x3X515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4cj-zj000-1/40-17/4表 5-4|类似地，写出割平面方程，选择第四行产生割平面
12、约束，-3/41/4x-1/4x-64cj3-1000 00cBxBibix1x2x3x4x5x6x73-1000 x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-4cj-zj-100000-4-1表 5-5原整数规划问题的最优解为，x1=1,x2=2,max z=1四、割平面计算步骤：第一步：用单纯刑法解整数问题IP的松弛问题L0若L0没有最优解，则IP没有最优解。停止若L0有最优解X0:(1)X0是整数解，则X0也是IP的最优解，停止(2)X0不是整数解，转第二步第二步：求割平面方程，的一个非整数分量任选00ibX所在的行的数据
13、，的最优单纯型表中由00ibL011)(ijmmnjimfxf得割平面：011ijmmnjimfsxf即第三步：将割平面加到L0得L1第四步：解L1在L0的最优单纯型表中增加一行一列，得L1的单纯型表，用对偶单纯刑法求解，若其解是整数解，则该解也是原整数规划的最优解否则将该解记为X0，返回第二步|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法分支定界法|0-1型整数规划|指派问题 分支定界法(branch and bound method)是一种隐枚举法(implicit enumeration)或部分枚举法，它不是一种有效算法，是枚举法基础上的改进。分支定界法的关键是分支和
14、定界。分支 求解放松问题 舍弃 变界 分支最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好|分枝定界法的基本思路：通过对松弛问题的分枝，不断降低（IP）最优值的上界，提高下界，当上界等于下界时，得到最优解。是不超过 的最大整数 rbrbIPIZ最优值松弛问题L00LZ最优值0LIZZ L1L21LZ最优值2LZ最优值01LLZZ02LLZZ1,LIZZ2LIZZ或通过对（L0）分枝，使（IP）的最优值的上界不断下降，L3L4L5L6是整数解的最优解若某个00*iiXL的可行解是则)(*0IPXiIiZCX0*,有,*0ikkCXZL的最优值若的下界即找到IZ,*kCX将下界改为0
15、,iL关闭是整数解最优解kX*)1(剪枝：的最优值若0*ikkCXZL:kL讨论子问题0*iCXkL关闭,不是整数解最优解kX*)2(分枝继续对kL下界不断上升，上界=下界得最优值|当前得到的最好整数解的目标函数值|分支后计算放松的线性规划的最优解|整数解且目标值优于原有最好解的值则替代原有最好解；|整数解且目标值劣于原有最好解的值则 删除该分支其中无最优解；|非整数解且目标值优于原有最好解的值则继续分支；|非整数解且目标值劣于原有最好解的值则删除该分支其中无最优解；|例6 求解下述整数规划1212121212max951141412.3,0,zxxxxxxs tx xx x为整数|第一步：舍
16、弃整数要求，用单纯形法求解，得X(0)=(3/2,10/3),点 A,目标函数值z(0)=29/6（上界），（0，0）显然是一个可行解，目标函数值0（下界）12121211212max9511414123.1,0,zxxxxxxs txxxxx为整数|第二步，由于x1,x2都不是整数，分解成子问题（分支）。先考虑x1，x1=3/2。12121211212max9511414123.2,0,zxxxxxxs txxxxx为整数（1）（2）X(1)=(2,23/9),B点z(1)=41/9X(2)=(1,7/3),C点,z(2)=10/3(新下界)|第三步，由于z(2)z(1)z(0),z(1)=
17、41/9代替z(0)成为新的上界。此时，问题（2）已探明，结束。问题（1）需继续分支。121212121212max9511414123.23,0,zxxxxxxstxxx xx x为整数（3）（4）无可行解，删去（剪枝）X(4)=(33/14,2),D点，z(4)=61/14121212121212max9511414123.22,0,zxxxxxxstxxx xx x为整数|第四步，由于z(2)z(4)z(0),问题（1）需继续分支。121212121212max9511414123.33,0,zxxxxxxs txxx xx x为整数（5）（6）X(6)=(2,2),F点,z(6)=41
18、21212121212max9511414123.22,0,zxxxxxxstxxx xx x为整数X(5)=(3,1),E点,z(5)=4得到原整数规划问题的最优解。S0Ax1=3/2,x2=10/3 z=29/6S2Bx1=2,x2=23/9 z=41/9S4Dx1=33/14,x2=2 z=61/14S3无可行解S1Cx1=1,x2=7/3 z=10/3S6Ex1=3,x2=1 z=4S5Fx1=2,x2=2 z=41x11x21x31x22x22x3初始分支为可行解集，确定初始界是停止当前最好解为最优解判定是否分支集空是按非整数变量分支并加入分支集判定是否为整数解判定最优值是否优于当前
19、界否判定最优值是否优于当前界是否以最优解替代当前最好解最优值替代当前界是否选一分支写出并求解放松问题，同时从分支集中删除该分支否|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划型整数规划|指派问题一、决策问题与0-1变量件事是否做第决策变量ixiix10做第i件事不做第i件事ni,2,1n件事中必须做k件并只做k件事kxxxn21n件事中最多做k件事kxxxn21n件事中至少做k件事nxxx21k做第i件事的充要条件是做第j件事jixx 做第i件事的充要条件是不做第j件事jixx1只在做了第i件事前提下才考虑是否做第j件事ijxx例 8 有三种资源被用于生产
20、三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见表5-6。要求制订一个生产计划，使总收益最大。|求解设xj是第 j 种产品的产量，j=1,2,3；再设1(0)=0(=0)jjjxyx若生产第j种产品 即若不生产第j种产品 即123123213123123111222333123123max456-100-150-20024850023430023100s.t.y,01,0zxxxyyyxxxxxxxxxxM yxM yxM yyyx xx或且为整数其中约束条件 如何理解？111xM y|隐枚举法（适合于变量个数较少的0-1规划）|例 10 求解0-1整合规划1
21、0,6434422s.t.52-3max3213221321321321或xxxxxxxxxxxxxxxxz（5.14a）（5.14b）（5.14d）（5.14c）|解：约束条件(x1,x2,x3)abcdz(0,0,0)0（初始滤值）(0,0,1)5（新滤值）(0,1,0)-2(0,1,1)-3(1,0,0)-3(1,0,1)8（最后过滤值）(1,1,0)-1(1,1,1)-6最优解231 0 1,max81xxxzTT（,）（,）|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题（指派问题（assignment problem）n模型 10,2,
22、1,1,2,1,1min1111或ijnjijniijninjijijxnixnjxxczCij为第i人做第j事的费用事人做第，若不指派第事人做第，若指派第jijixij01令一般称矩阵C=(cij)nn为指派问题的系数矩阵。|性质：假定C=(cij)为指派问题的价值系数矩阵。现将它的某一行（或某一列）的各元素都减去一个常数k，得到一新矩阵 。若以C代替C作为该指派问题的价值系数矩阵，而构成一新的指派问题，则这个分派问题的最优解与原指派问题的最优解相同。ijC=(C)第1步：把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。4 8 7 15 127 9 17 1
23、4 106 9 12 8 76 7 14 6 106 9 12 10 6C例12系数矩阵4 8 7 15 120 3 0 11 87 9 17 14 100 1 7 7 36 9 12 8 70 2 3 2 16 7 14 6 100 0 5 0 46 9 12 10 60 2 3 4 0CC此时每行及每列中肯定都有0元素了。第2步：确定独立零元素，并作标记。（1）首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理。若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理。（2）在按行处理时，若某行有
24、独立0元素，把该0元素标记为a，把该0所在的列中的其余0元素标记为b；否则，暂时越过本行，处理后面的行。把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b。（3）在按列处理时，若某列有独立0元素，把该0元素标记为a，把该0所在的行中的其余0元素标记为b；否则，暂时越过本列，处理后面的列。把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b。（4）重复上述过程，即得到独立零元素（标
25、记a的“0”）abbabba0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 0ab第3步：若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤：（1）对没有标记a的行作标记（2）在已作标记 的行中，对标记b所在列作标记（3）在已作标记 的列中，对标记a 所在的行作标记（4）对没有标记 的行划线，对有标记 的列划线0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 40 2 3 4 0第4步：在未被直线覆盖的所有元素中找出一个最小元素（Xmin），未被直线覆盖的行（或列）中所有元素都减去这个数。（注：若未被直线覆
26、盖部分是行数n工作人费用1 2 j nmnmjmminijiinjnjcccccccccccccccc212122222111121112imn+1 n+2 m 000000000000用匈牙利法求解工作人费用1 2 j nmnmjmminijiinjnjcccccccccccccccc212122222111121112imm+1 m+2 n 000000000000(b)mn用匈牙利法求解(3)一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问题（4）某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：充分大取费用系数ijc如在maxZ问题中，第k个人一定不能做第t件事，0ijc取效率系数
