整数规划2（指派问题）

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

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

3、变量组合不满足其中的某一约束条件时, 就不必要检验其它的约束条件是否可行。 若发现一个可行解, 则根据它的目标函数值可以产生一个过滤条件(Filtering constraint), 对于目标函数值比它差的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。 在以后求解过程中, 每当发现比原来更好的可行解, 则依次替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。,以例子说明上述求解方法 例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整数规划问题,解：重新排序为,练习：求解下述整数规划问题,第五节 指派问题（Assignment Problem） 1. 标准指派问题的提法及模型 指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为cij（i，j=1，2，n），要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费

5、用最小。,数学模型为:,其中矩阵C称为效率矩阵或系数矩阵。,其解的形式可用0-1矩阵的形式来描述，即 (xij)nn。 标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。1955年W. W. Kuhn利用匈牙利数学家D. Konig关于矩阵中独立零元素的定理, 提出了解指派问题的一种算法, 习惯上称之为匈牙利解法。 2. 匈牙利解法 匈牙利解法的关键是指派问题最优解的以下性质：若从指派问题的系数矩阵C=（cij）的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C=（cij)，则以C和C为系数矩阵的两个指派问题有相同的最优解。（这种变化不影响约束方程组，

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

7、较大时，可按下列顺序进行 从只有一个0元素的行（列）开始，给这个0元素加圈，记作，然后划去所在的列（行）的其它0元素，记作。 给只有一个0元素的列（行）的0加圈，记作，然后划去所在行的0元素，记作。 反复进行，直到系数矩阵中的所有0元素都被圈去或划去为止。 如遇到行或列中0元素都不只一个（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中的其它0元素。被划圈的0元素即是独立的0元素。,步3：作最少数目的直线，覆盖所有0元素（目的是确定系数矩阵的下一个变换），可按下述方法进行 1） 对没有的行打“”号； 2） 在已打“”号的行中，对 所在列打“” 3）在已打“”号的列中，对所在

8、的行打“”号； 4）重复2）3），直到再也找不到可以打“”号的行或列为止； 5）对没有打“”的行划一横线，对打“”的列划一纵线，这样就得到覆盖所有0元素的最少直线数。,步4：继续变换系数矩阵，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保持原来0元素不变（为了消除负元素）。得到新的系数矩阵，返回步2。 以例说明匈牙利法的应用。,例1：求解效率矩阵如下的指派问题的最优指派方案。,解：第一步：系数矩阵的变换（目的是得到某行或列均有0元素）,第二步：确定独立0元素,元素的个数m=4，而n=5

9、，进行第三步。,第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。,第四步：对上述矩阵进行变换，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优解和原问题相同，为什么？）,由解矩阵可得指派方案和最优值为32。,3. 一般的指派问题 在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式，然后用匈牙利解法求解。 最大化指派问题 设最大化指派问题系数矩阵C中最大元素为m。令矩阵B=

10、(bij)=(m-cij), 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。 人数和事数不等的指派问题 若人少事多，则添上一些虚拟的“人”。这些虚拟的人作各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”,做这些虚拟事的费用系数同样也取0。 一个人可做几件事的指派问题 若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这几个人作同一件事的费用系数当然都一样。 某事一定不能由某人做的指派问题 若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数M。,练习：已知B1,B2,B3,B4,B5五个项目工程，先选择建设公司A1，A2，A3参加招标承建，建设费用如下表所示。允许每家建设公司至少承建一项，且至多