经济学整数规划课件

第四章

整数规划与分配问题

整数规划的特点及作用

分配问题与匈牙利法

分枝定界法与割平面法

应用举例

第四章

整数规划与分配问题

整数规划的特点及作用

分配问题与匈牙利法

分枝定界法与割平面法

应用举例

整数规划的特点及作用模型实例特点松弛问题整数线性规划模型整数线性规划类型1.纯整数线性规划：2.混合整数线性规划：3.0－1型整数线性规划：人员安排问题投资组合问题物资运输问题人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060x1210—1470x2314—1860x3418—2250x4522—0220x5602—0630x6最少需要多少护士？

minz=x1+x2+x3+x4+x5+x6x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x6＋x1≥60

xj

正整数,j=1,2,…6设x1,x2,…,x6为各班新上班人数人员安排问题物资运输问题工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij(i,j=1,2,3,4).B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量3504003001501200工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少？再引入一个0-1变量y证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资组合问题

现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j=1,2,...,n）。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？模型变量—每个项目是否投资约束—总金额不超过限制＋3个附加条件目标—总收益最大模型特征—变量整数性要求来源

问题本身的要求引入的逻辑变量的需要性质—可行域是离散集合模型的特点模型的特点与线性规划的关系整数规划松弛问题可行解是松弛问题的可行解最优值不会优于其松弛问题的最优值解的特点解的特点注释最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于顶点，枚举法不可取第四章

整数规划与分配问题

整数规划的特点及作用

分配问题与匈牙利法

分枝定界法与割平面法应用案例

设某公司准备派n个工人x1,x2,…,xn,去作n件工作y1,y2,…,yn.已知工人xi去作工作yj的效率为wij(i,j=1,2,…,n).现问：如何确定一个分派工人去工作的方案，使得工人们的工作总效率达到最大？分派方案应该满足下述两个条件：任一个工人都不能去做两件或两件以上的工作任一件工作都不能同时接受两个或两个以上的工人去做分配问题的提出分配问题若干项工作或任务需要若干个人去完成。由于每人的知识、能力、经验的不同，故各人完成不同任务所需要的时间（或其他资源）不同。问应指派哪个人完成何项工作，可使完成所有工作所消耗的总资源最少？标准形式下的分配问题n个人n件事每件事必有且只有一个人去做每个人必做且只做一件事数学模型cij：第i人做第j事的费用xij＝1若指派第i人做第j事0若指派第i人不做第j事总费用：每件事必有且只有一个人去做i，j＝1,...,nj＝1,...,n每个人必做且只做一件事i＝1,...,n数学模型j＝1,...,ni＝1,...,ns.t.线性规划问题运输问题0-1型整数规划问题匈牙利解法1955年W.W.kuhn(库恩)提出的，利用了2个定理，该定理是由匈牙利数学家D.Konig(康尼格)证明的。系数矩阵(效率矩阵)解矩阵(决策变量矩阵)定理：设指派问题的系数矩阵为C=(cij),若将该矩阵的某一行（或某一列）的各个元素都减去同一个常数k（k可正可负），得到新的系数矩阵C'＝（c'ij）,则以C'为系数矩阵的新指派问题于与原指派问题的最优解相同，但其最优值比原最优值减少k。推论：若将指派问题的系数矩阵每一行及每一列分别减去各行及各列的最小元素，则新指派问题与原指派问题有相同的最优解。相关定理步骤1：把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。此时每行及每列中肯定都有0元素了。定义：在系数矩阵C中，有一组处在不同行不同列的零元素，称为独立零元素组，其中每个元素称为独立零元素。最优解步骤2：确定独立零元素，并对所有零元素做标记。（1）逐行检验对只有一个未标记的零元素的行，用记号O将该零元素圈起，然后将被圈起的零元素所在列的其他未标记的零元素用记号/划去。重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。（2）逐列检验与行检验类似：对只有一个未标记的零元素的列，用记号O将该零元素圈起，然后将被圈起的零元素所在行的其他未标记的零元素用记号/划去。这时可能出现下述三种情况：1.每一行均有圈0出现，圈0的个数恰好等于n2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。3.不存在未被标记过的零元素，但圈0的个数<n可进行指派：令圈0位置的决策变量取值为1，其他为0再对每行、每列中有两个未被标记过的零元素任选一个，加上圈，然后给同列、同行的其他未被标记的零元素加/，然后再进行行、列检验，可能出现情况1或3。作最少直线覆盖当前所有零元素，以增加独立零元素的个数定理：系数矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少线数。由匈牙利数学家D.Konig(康尼格)所证明例：分别求下列矩阵中的独立零元素的最多个数。45独立零元素的个数最多：对不含圈0的行打；在打的行中，对所有零元素所在列打；在所有打的列中，对圈0所在行打；重复2,3步，直到不能打为止。对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集。步骤3：继续变换系数矩阵，以增加独立零元素的个数。在未被直线覆盖过的元素中找出最小元素，将打行的各元素减去这个最小元素，将打列的各元素加上这个最小元素（以避免打行中出现负元素），这样就增加了独立零元素的个数。再返回步骤2。非标准形式的指派问题1.最大化指派问题2.人数和事数不等3.一个人可做几件事(一件事由几个人来做)4.某事一定不能由某人做设最大化指派问题系数矩阵C=(cij)，其中最大元素为m。令矩阵C'＝(m-cij)。若人少事多，则添上一些虚拟的人，对应的费用系数取0若人多事少，则添上一些虚拟的事，对应的费用系数取0将该人化作相同的几个人来接受指派将相应的费用系数取作足够大的数M练习教材P110例2.

第四章

整数规划与分配问题

整数规划的特点及作用

分配问题与匈牙利法

分枝定界法与割平面法应用举例

求解整数线性规划的分支定界法

“大事化小，小事化了”把一个规模较大的问题分解成若干个分支，逐支求解，然后找出原问题的解。算法思想算法步骤算例只解松弛问题1、在全部可行域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分支过程若松弛问题最优解中某个xk=bk

不是整数，令[

bk

]为bk

的整数部分构造两个新的约束条件

xk[bk

]和xk[

bk

]+1，分别加于原松弛问题，形成两个新的整数规划算法思想1.先放弃“整数”要求求出一个最优解,如是整数，结束。2.否则,以一个变量的取整值“分支”，分为两个(分别添加一个约束),再各求出其最优解。3.如得一整数解，将其目标函数的值添加为以后诸分支的约束[定界]。如此反复直到找到整数解，而且其余分支无可行解结束。分支的方法只解松弛问题1、在全部可行域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分支过程若松弛问题最优解中某个xk=bk

不是整数，令[

bk

]为bk

的整数部分构造两个新的约束条件

xk[bk

]和xk[

bk

]+1，分别加于原松弛问题，形成两个新的整数规划3、求解分支的松弛问题—定界过程设两个分支的松弛问题分别为问题1和问题2，它们的最优解有如下情况

定界界：当前得到的最好整数解的目标函数值分支后计算松弛的线性规划的最优解整数解目标值优于原有最好整数解的值则替代原有最好整数解劣于原有最好整数解的值则删除该分支非整数解目标值优于原有最好整数解的值则继续分支劣于或等于原有最好整数解的值则删除该分支

.若还未定界(还没有整数解)，则选取目标值较好的问题继续分支例2123123(3/2,10/3)x1=3/2,分为x1≤1与x1≥2SS2S1x1≤1x1≥2S2S1分别解之先放弃“整数”要求求出一个最优解。123123S1S2解S1,求出一个最优解(2,23/9),maxz=41/9解S2,求出一个最优解(1,7/3),maxz=10/3SS2S1x1≤1x1≥2(2,23/9)x2=23/9,分为x2≤2与x2≥3S12S11x2≤2x2≥3可行域为空S12S11123123S12(33/14,2)解S12,求出一个最优解(33/14,2),maxz=61/14SS2S1x1≤1x1≥2S12S11x2≤2x2≥3可行域为空10/361/14S122S121x1≤2x1≥3x1=33/14,分为x1≤2与x1≥3S121S122123123SS2S1x1≤1x1≥2S12S11x2≤2x2≥3可行域为空10/3S122S121x1≤2x1≥3S121S122解S121,求出一个最优解(3,1),maxz=4解S122,求出一个最优解(2,2),maxz=4(2,2)(3,1)44最优整数解为(3,1)和(2,2)最优值为4剪支分支问题解可能出现的情况表情况2,4,5找到最优解情况3在缩减的域上继续分支定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分支所得到的解进行比较，结论如情况4或5对0-1整数规划分支时注意求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。练习用分支定解法求解整数规划：maxz=3x1

+2x2s.t.x1+0.5x2<=

4.52x1

+3x2<=14x1,x2≥0,且均取整数值解纯整数规划的割平面法－－1958年由R.E.Gomory首先提出算法思想算法步骤算例算法思想由松弛问题的可行域向整数规划的可行域逼近方法—引进线性约束条件(超平面)只切割问题的部分非整数解要求松弛问题非整数解删除整数解保留

例题：用割平面法求解下列整数规划maxz=3x1

+2x2s.t.x1+0.5x2<=

4.52x1

+3x2<=14x1,x2≥0,且均取整数值第1步.约束条件系数化成整数,

找出松弛问题maxz=3x1

+2x2s.t.2x1+x2<=

92x1+3x2<=14x1,x2≥0maxz=3x1

+2x2s.t.x1+0.5x2<=

4.52x1

+3x2<=14x1,x2≥0,且均取整数值G0单纯形法求解松弛问题，得到最终单纯形表如下：此时，若得到整数解，则结束；否则，按如下方法操作。第2步.找出非整数解变量中分数部分最大的一个基变量，并写出该行在最终表中的约束方程将上式所有常数分写成整数与正分数之和：分数移项到右端，整数项到左端：根据右端的变量取整及非负要求，分析得到：即：加上松弛变量之后得到Gomory

约束由于代入Gomory约束不等式得到即：加上松弛变量之后得到Gomory

约束123456781234567893x1+2x2=122x1+3x2=140x2

x1由于代入Gomory约束不等式得到2x1+2x2=11Gomory

约束只割去了松弛问题可行域的部分非整数解，原有的整数解全部保留类似灵敏度分析增加一个约束条件表中仍有非整数解，重复第2步，继续寻找GOMORY约束直到得到整数解对偶单纯形法迭代！算法步骤求松弛问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯形表中加入一行利用对偶单纯形算法求最优解选择具有最大小数部分的非整分量练习用割平面法解整数规划：第四章

整数规划与分配问题

整数规划的特点及作用

分配问题与匈牙利法

分枝定界法

割平面法

应用举例

包装箱代号123456容积（m3）0.080.10.120.150.200.25需求量（个）500550700900450400可变费用(元/个)5.08.010.012.116.318.2例1

红星日用化工厂为发运产品，下一年度需要6中不同容积的包装箱，每种包装箱的需求量及生产一个的可变费用如下表所示：由于生产不同容积包装箱需要进行专门配备，下料等，生产某一容积包装箱的固定费用均为1200元，又若某容积包装箱数量不够时，可用比它容积大的代替，试问该化工厂应定做哪几种代号的包装箱各多少个，才能使总费用最低。应用举例例2

春江市计划为新建的五个居民小区中的两个分别各设立一所小学，下表给出了各小区及期间的平均步行时间，及各个居民小区的学生人数，要求为该市提供决策建议，两所小学应分别建于哪两个居民小区，以及各居民小区学生应分别到哪所学校上学，使学生总的上学步行时间为最短小学位于该区小学生数至本区及其他区步行时间（min）1234512005201525102180204201525330015206251541602515254125350102515125应用举例例2

春江市计划为新建的五个居民小区中的两个分别各设立一所小学，下表给出了各小区及期间的平均步行时间，及各个居民小区的学生人数，要求为该市提供决策建议，两所小学应分别建于哪两个居民小区，以及各居民小区学生应分别到哪所学校上学，使学生总的上学步行时间为最短175042005250875035005192064040002400400044500750018006000450034500270036007203600220005000300040001000154321至j自i首先要找出该区小学生到可能设于各个区小学上学的步行总时间！应用举例例3

清远市下设八个区，下表中给出了救护车从一个区到另一个区的车程时间（min），该市模拟救护中心，要求各区离散救护中心的车程时间必须在8min之内，试为该市提供决策建议：至少建多少个救护中心，建于何处？127710616148

591078

41012877

3141711131210

21581413119818765432至从首先要找出救护中心建于该区是，救护车程8min以内所覆盖的区域应用举例例3

清远市下设八个区，下表中给出了救护车从一个区到另一个区的车程时间（min），该市模拟救护中心，要求各区离散救护中心的车程时间必须在8min之内，试为该市提供决策建议：至少建多少个救护中心，建于何处？首先要找出救护中心建于该区是，救护车程8min以内所覆盖的区域救护中心设于该区救护车