整数规划的难度远大于一般线性规划

整数规划整数规划的难度远大于一般线性规划14.1整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解24.2整数规划的分枝定解法

4.2.1思路与解题步骤只解松弛问题1、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个xk=bk不是整数，令bk为bk的整数部分构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况3表4.2.1分枝问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的整数解进行比较，结论如情况444.2.2分枝定界法举例

例4.1.1

解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23由x1=2.5得到两个分枝如下：5表4.2.3分枝问题的松弛解问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当有很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题64.6任务分配问题例4.6.1有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任务的总工时耗费最少？7任务分配问题的数学模型模型中：xij

为第i个工人分配去做第j

项任务；

aij

为第i

个工人为完成第j

项任务时的工时消耗；{aij}mm称为效率矩阵运输问题是任务分配问题的松弛问题任务分配问题不但是整数规划，而且是01规划任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的任务分配是两部图的匹配问题，有著名的匈牙利算法下面介绍一种适合手算的算法(出自清华教科书)84.6.1清华算法定理1如果从效率矩阵{aij}mm中每行元素分别减去一个常数ui，从每列元素分别减去一个常数vj，所得新的效率矩阵{bij}mm的任务分配问题的最优解等价于原问题的最优解。证明：略定理2若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略清华算法的基本思路：根据定理1变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在m

个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m条，就尚未找到最优解，设法进一步变换矩阵，增加新的零9清华算法的步骤：例4.6.1第一步：变换效率矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；10清华算算法的的步骤骤：例例4.6.12、逐逐列检检查，若该该列只只有一一个未未标记记的零零，对对其加加()标记，，将()标记元元素同同行同同列上上其它它的零零打上上*标记。。若该该列有有二个个以上上未标标记的的零，，暂不不标记记，转转下一一列检检查，，直到到所有有列检检查完完；3、重重复1、2后，可可能出出现三三种情情况；；a.每行都都有一一个(0)，，显然然已找找到最最优解解，令令对应应(0)位位置的的xij=1；；b.仍有零零元素素未标标记，，此时时，一一定存存在某某些行行和列列同时时有多多个零零，称称为僵局状状态，因为为无法法采用用1.2中的方方法继继续标标记。。4、打破僵僵局。令未未标记记零对对应的的同行行同列列上其其它未未标记记零的的个数数为该该零的的指数，选指数最最小的先标标记()；；采用用这种种方法法直至至所有有零都都被标标记，，或出出现情况a，或情况c。11清华算算法的的步骤骤：例例4.6.1c.所有零零都已已标记记，但但标有有()的的零的的个数数少于于m；开始划线过过程：对没有有标记记()的的行打打对打行行上所所有其其它零零元素素对应应的列列打再对打打列列上有有()标标记的的零元元素对对应的的行打打重复，直至至无法法继续续对没有有打的的行划划横线，对所所有打的的列划划垂线划线后后会出出现两两种情情况：：(1)标记()的零少于于m个，但划有有m条直线，说说明矩阵中中已存在m个不同行不不同列的零零，但打破破僵局时选选择不合理理，没能找找到。回到到b重新标记；；(2)少于m条直线，到到第三步；12清华算法的的步骤：例例4.6.1第三步：进一步变换换；在未划划线的元素素中找最小者，设为对未被被直线覆盖盖的各元素素减去对两条条直线交叉叉点覆盖的的元素加上上只有一一条直线覆覆盖的元素素保持不变变以上步骤实实际上仍是是利用定理1第四步：抹除所有标标记，回到到第二步，重新标记记；13清华算法的的步骤：例例4.6.1答：最优分分配方案为为x13=x21=x34=x42=1，其余余为0，即甲C，乙A，丙D，丁B，OBJ=20144.6.2关于清华算算法的适用用条件要求所有aij0若某些aij<0，则利用定定理1进进行变换换，使所有有bij0目标函数为为min型型对于max型目标函函数，将效效率矩阵中中所有aij反号，则等等效于求min型问问题；再利利用定理1进行行变换，使使所有bij0，则则可采用清清华算法打破僵局时时选择不当当的结果：：结果仅出现现3个个标记()，但但却划出4条线线，说明什么？？！15线性规划有有关的英文文词汇Operational/operationsresearch运筹学Linearprogramming线线性规划Feasibledomain可行行域Convexset凸凸集Basicfeasiblesolutions基础础可行解Simplexalgorithm单纯纯型法Pivot主主元Pivoting主元元变换Revised,dualsimplexalgorithm修修正、对对偶单纯型型法Relativecost相对对成本(机机会成本)Shadowprice影影子子价格Slack,Surplus,Artificialvariable松松弛，剩剩余，人工工变量Unbounded,Infeasible,Degeneratesolution无无界解,无无可行解解,退化化解Duality对对偶性Primal,dualpr