第四节0-1整数规划•0-1整数规划是线性规划及整数规划的一种特殊形式。•模型结构和形式是线性规划,只是决策变量取0或1。例1:投资场所的选定——相互排斥的计划某公司拟在城市的东、西、南三区建立分公司,待选位置有七个记为Ai。规定东区A1,A2,A3中至多选二个;西区A4,A5中至少选一个;南区A6,A7中至少选一个,选用Ai点时估计设备投资为bi元,每年可获利润估计为ci元,投资总额不能超过d元,问应选择哪几个点可使得年利润最大?7,...,1,10112..max76543217171iorxxxxxxxxdxbtsxcZiiiiiii例2:相互排斥的约束条件某厂拟采用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运(车运)所受限制如下表,如采用船运,其体积托运限制则为45,问两种货物托运多少箱,可使获得利润为最大?货物体积每箱(m3)重量每箱(吨)利润每箱(百元)甲424乙513托运(车运)限制206解:设x1,x2分别表示甲乙两种货物的托运箱数,则其整数规划数学模型为取整数,0,62)1(45542054.34max212121212121xxxxxxMyxxyMxxtsxxZ01y当采用船运方式当采用车运方式其中一般情况下,m个约束条件中选择q个约束条件:ai1x1+ai2x2+…+ainxnbi+yiM,i=1,2,…,my1+y2+…+ym=m-q其中yi是0,1变量,且只有q个取0。•0-1整数规划问题的解法若有n个决策变量,则可以产生2n个可能变量的组合,故完全枚举是不可能的.求解0-1整数规划问题的解法均是部分枚举法或称为隐枚举法(Implicitenumeration)基本思想:在2n个可能的变量组合中,往往只有一部分是可行解.只要发现某个变量组合不满足其中的某一约束条件时,就不必要检验其它的约束条件是否可行。若发现一个可行解,则根据它的目标函数值可以产生一个过滤条件(Filteringconstraint),对于目标函数值比它差的变量组合就不必再去检验它的可行性(类似分支定界法中的定界。实际上,隐枚举法是一种特殊的分支定界法)。在以后求解过程中,每当发现比原来更好的可行解,则依次替代原来的过滤条件(可减少运算次数,较快地发现最优解)。10,,6434422.523max3213221321321321orxxxxxxxxxxxxxtsxxxZ以例子说明上述求解方法例1:求解下述0-1整数规划问题解:求解过程见下表(x1,x2,x3)Z值约束条件过滤条件(0,0,0)0Z0(0,0,1)5Z5(0,1,0)-2×(0,1,1)3×(1,0,0)3×(1,0,1)8Z8(1,1,0)1×(1,1,1)6×所以,最优解为(x1,x2,x3)T=(1,0,1)T,最优值为8.注:当决策变量(x1,x2,x3)按(0,0,0),(0,0,1),(0,1,0),(0,1,1),...方式取值时,为了减少计算次数,通常将目标函数中的决策变量的顺序按其系数的大小重新排序,以使最优解能较早出现。对最大化问题,按从小到大的顺序排列;对极小化问题,则相反。例2:求解下述0-1整数规划问题10,,,53584612.73min4321421432143214321orxxxxxxxxxxxxxxxtsxxxxZ解:重新排序为10,,,55386412.37min4321412341234123412orxxxxxxxxxxxxxxxtsxxxxZ(x2,x1,x4,x3)Z值约束条件过滤条件(0,0,0,0)0×(0,0,0,1)-1×(0,0,1,0)1×(0,0,1,1)0×(0,1,0,0)3×(0,1,0,1)2×(0,1,1,0)4×(0,1,1,1)3Z3(1,0,0,0)7×(1,0,0,1)6×(1,0,1,0)8×(1,0,1,1)7×(1,1,0,0)10×(1,1,0,1)9×(1,1,1,0)11×(1,1,1,1)10×第五节指派问题(AssignmentProblem)1.标准指派问题的提法及模型指派问题的标准形式是:有n个人和n件事,已知第i个人做第j件事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一对应的指派方案,使完成这n件事的总费用最小。njiorxnixnjxtsxcZijnjijniijninjijij,,2,1,,10,,2,1,1,,2,1,1.min1111数学模型为:01ijx若指派第i个人做第j件事若不指派第i个人做第j件事(i,j=1,2,…,n)设n2个0-1变量其中矩阵C称为效率矩阵或系数矩阵。其解的形式可用0-1矩阵的形式来描述,即(xij)nn。标准的指派问题是一类特殊的整数规划问题,又是特殊的0-1规划问题和特殊的运输问题。1955年W.W.Kuhn利用匈牙利数学家D.Konig关于矩阵中独立零元素的定理,提出了解指派问题的一种算法,习惯上称之为匈牙利解法。2.匈牙利解法匈牙利解法的关键是指派问题最优解的以下性质:若从指派问题的系数矩阵C=(cij)的某行(或某列)各元素分别减去一个常数k,得到一个新的矩阵C’=(c’ij),则以C和C’为系数矩阵的两个指派问题有相同的最优解。(这种变化不影响约束方程组,而只是使目标函数值减少了常数k,所以,最优解并不改变。)对于指派问题,由于系数矩阵元素值均非负,故若能在系数矩阵中找到n个位于不同行和不同列的零元素(独立的0元素),则对应的指派方案总费用为零,从而一定是最优的。匈牙利法的步骤如下:步1:变换系数矩阵。对系数矩阵中的每行元素分别减去该行的最小元素;再对系数矩阵中的每列元素分别减去该列中的最小元素。若某行或某列已有0元素,就不必再减了(不能出现负元素)。步2:在变换后的系数矩阵中确定独立0元素(试指派)。若独立0元素已有n个,则已得出最优解;若独立0元素的个数少于n个,转步3。确定独立0元素的方法:当n较小时,可用观察法、或试探法;当n较大时,可按下列顺序进行•从只有一个0元素的行(列)开始,给这个0元素加圈,记作,然后划去所在的列(行)的其它0元素,记作。•给只有一个0元素的列(行)的0加圈,记作,然后划去所在行的0元素,记作。•反复进行,直到系数矩阵中的所有0元素都被圈去或划去为止。•如遇到行或列中0元素都不只一个(存在0元素的闭回路),可任选其中一个0元素加圈,同时划去同行和同列中的其它0元素。被划圈的0元素即是独立的0元素。•步3:作最少数目的直线,覆盖所有0元素(目的是确定系数矩阵的下一个变换),可按下述方法进行1)对没有的行打“”号;2)在已打“”号的行中,对所在列打“”3)在已打“”号的列中,对所在的行打“”号;4)重复2)3),直到再也找不到可以打“”号的行或列为止;5)对没有打“”的行划一横线,对打“”的列划一纵线,这样就得到覆盖所有0元素的最少直线数。步4:继续变换系数矩阵,目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素,然后在打“”行各元素中都减去这一元素,而在打“”列的各元素都加上这一最小元素,以保持原来0元素不变(为了消除负元素)。得到新的系数矩阵,返回步2。以例说明匈牙利法的应用。9107104106614159141217766698979712例1:求解效率矩阵如下的指派问题的最优指派方案。解:第一步:系数矩阵的变换(目的是得到某行或列均有0元素)910710410661415914121776669897971256360400892751000003220205第二步:确定独立0元素元素的个数m=4,而n=5,进行第三步。56360400892751000003220205第三步:作最少的直线覆盖所有的0元素,目的是确定系数矩阵的下一个变换。第四步:对上述矩阵进行变换,目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素,然后在打“”行各元素中都减去这一元素,而在打“”列的各元素都加上这一最小元素,以保持原来0元素不变(消除负元素)。得到新的系数矩阵。(它的最优解和原问题相同,为什么?)563604008927510000032202050000100100100000100000010由解矩阵可得指派方案和最优值为32。341404008110538000034202073.一般的指派问题在实际应用中,常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式,然后用匈牙利解法求解。•最大化指派问题设最大化指派问题系数矩阵C中最大元素为m。令矩阵B=(bij)=(m-cij),则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。•人数和事数不等的指派问题若人少事多,则添上一些虚拟的“人”。这些虚拟的人作各事的费用系数可取0,理解为这些费用实际上不会发生。若人多事少,则添上一些虚拟的“事”,做这些虚拟事的费用系数同样也取0。•一个人可做几件事的指派问题若某个人可做几件事,则可将该人看做相同的几个人来接受指派。这几个人作同一件事的费用系数当然都一样。•某事一定不能由某人做的指派问题若某事一定不能由某个人做,则可将相应的费用系数取做足够大的数M。练习:已知B1,B2,B3,B4,B5五个项目工程,先选择建设公司A1,A2,A3参加招标承建,建设费用如下表所示。允许每家建设公司至少承建一项,且至多承建二项工程。求使总费用最少的指派方案。工程公司B1B2B3B4B5A14871512A279171410A3691287