整数规划2（指派问题）.ppt

《整数规划2（指派问题）.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四节0-1整数规划0-1整数规划是线性规划及整数规划的一种特殊形式。模型结构和形式是线性规划，只是决策变量取0或1。例1：投资场所的选定——相互排斥的计划某公司拟在城市的东、西、南三区建立分公司，待选位置有七个记为Ai。规定东区A1,A2,A3中至多选二个;西区A4,A5中至少选一个;南区A6,A7中至少选一个,选用Ai点时估计设备投资为bi元,每年可获利润估计为ci元,投资总额不能超过d元,问应选择哪几个点可使得年利润最大?例2:相互排斥的约束条件某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运(车运)所受限制如下表,如采用船运,其体积托运限制则为4

2、5,问两种货物托运多少箱，可使获得利润为最大？解:设x1,x2分别表示甲乙两种货物的托运箱数,则其整数规划数学模型为当采用船运方式当采用车运方式其中一般情况下,m个约束条件中选择q个约束条件:ai1x1+ai2x2+…+ainxnbi+yiM,i=1,2,…,my1+y2+…+ym=m-q其中yi是0,1变量，且只有q个取0。0-1整数规划问题的解法若有n个决策变量,则可以产生2n个可能变量的组合,故完全枚举是不可能的.求解0-1整数规划问题的解法均是部分枚举法或称为隐枚举法(Implicitenumeration)基本思想:在2n个可能的变量组合中,往往只有一部分是可行

3、解.只要发现某个变量组合不满足其中的某一约束条件时,就不必要检验其它的约束条件是否可行。若发现一个可行解,则根据它的目标函数值可以产生一个过滤条件(Filteringconstraint),对于目标函数值比它差的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。在以后求解过程中,每当发现比原来更好的可行解,则依次替代原来的过滤条件(可减少运算次数,较快地发现最优解)。以例子说明上述求解方法例1:求解下述0-1整数规划问题解：求解过程见下表所以，最优解为（x1，x2，x3)T=(1,0,1)T,最优值为8.注：当决策变量(x1

4、,x2,x3)按(0,0,0),(0,0,1),(0,1,0),(0,1,1),...方式取值时,为了减少计算次数,通常将目标函数中的决策变量的顺序按其系数的大小重新排序,以使最优解能较早出现。对最大化问题,按从小到大的顺序排列；对极小化问题,则相反。例2：求解下述0-1整数规划问题解：重新排序为练习：求解下述整数规划问题第五节指派问题（AssignmentProblem）1.标准指派问题的提法及模型指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为cij（i，j=1，2，…，n），要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。数学

5、模型为:若指派第i个人做第j件事若不指派第i个人做第j件事(i,j=1,2,…,n)设n2个0-1变量其中矩阵C称为效率矩阵或系数矩阵。其解的形式可用0-1矩阵的形式来描述，即(xij)nn。标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。1955年W.W.Kuhn利用匈牙利数学家D.Konig关于矩阵中独立零元素的定理,提出了解指派问题的一种算法,习惯上称之为匈牙利解法。2.匈牙利解法匈牙利解法的关键是指派问题最优解的以下性质：若从指派问题的系数矩阵C=（cij）的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C’=（c’ij

6、)，则以C和C’为系数矩阵的两个指派问题有相同的最优解。（这种变化不影响约束方程组，而只是使目标函数值减少了常数k，所以，最优解并不改变。）对于指派问题，由于系数矩阵元素值均非负，故若能在系数矩阵中找到n个位于不同行和不同列的零元素（独立的0元素），则对应的指派方案总费用为零，从而一定是最优的。匈牙利法的步骤如下：步1：变换系数矩阵。对系数矩阵中的每行元素分别减去该行的最小元素；再对系数矩阵中的每列元素分别减去该列中的最小元素。若某行或某列已有0元素，就不必再减了（不能出现负元素）。步2：在变换后的系数矩阵中确定独立0元素（试指派）。若独立0元素已有n个，则已得出最优解；若

7、独立0元素的个数少于n个，转步3。确定独立0元素的方法：当n较小时，可用观察法、或试探法；当n较大时，可按下列顺序进行从只有一个0元素的行（列）开始，给这个0元素加圈，记作，然后划去所在的列（行）的其它0元素，记作。给只有一个0元素的列（行）的0加圈，记作，然后划去所在行的0元素，记作。反复进行，直到系数矩阵中的所有0元素都被圈去或划去为止。如遇到行或列中0元素都不只一个（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中的其它0元素。被划圈的0元素即是独立的0元素。步3：作最少数目的