物流运筹学-整数规划

《物流运筹学-整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章整数规划一般整数规划问题整数规划的解法0—1规划指派问题物流资源分配问题知识目标掌握整数规划的基本形式；掌握分枝定界法计算过程；理解割平面法；掌握0—1规划的标准形式；了解0—1变量的应用；掌握0—1规划的匈牙利解法。技能目标能够结合实际情况建立整数规划模型，并可利用分枝定界法求解；能够应用0—1规划建模并求解，安排人员工作。第一节一般整数规划问题什么是整数规划问题？整数规划的一般形式：第二节整数规划的解法割平面法分枝定界法例3-5割平面法基本思想：求原问题对应松弛问题最优解，如果不是原问题的可行解，则通过引入线性约束条件（即割平面），使松弛

2、问题的可行域逐步缩小（即切掉一部分），每次切割掉的是松弛问题的非整数解的一部分，但不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即为原问题的最优解。其本质是利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。例3-6其最优解为=（1,1）最优值为=1割平面法的求解步骤步骤1：求解原问题的松弛问题，得最优解，若满足整数约束，则即为最优解，否则进入下一步；步骤2：分解其中一个非整分量，构造一个新的线性约束条件，加入原松弛问题中，形成新的线性规划；步骤3：求解新线性规划问题，得，若为整数则为原问题的最优解，否则进

3、入步骤2。按某非整分量构造的约束条件需满足以下两个条件：（1）当前最优解不满足该约束，即使得该最优解不会再出现在松弛问题可行解中；（2）所有整数可行解均满足该约束，即新增约束条件后，仍保留了原松弛问题的所有整数解。分枝定界法基本思想：求原问题的对应的松弛问题，其最优解若不是原问题的可行解，则通过附加线性不等式约束（整型），将松弛问题分枝变为若干子问题，即对每一个非整变量附加两个互相排斥（不交叉）的整型约束，即得两个子问题，继续求解定界，重复下去，直到得到最优解为止。例3-7用分枝定界法求解：分枝定界法求解步骤步骤1：求解原问题的松弛问题（用LP表示

4、），得最优解，若满足整数约束，则即为最优解，否则进入下步。步骤2：分枝。任选的一个不为整的分量，设为（其中为整数部分，为小数部分），据此得两个约束条件，这样就将LP的可行域分割成两个不相交的子集。将这两个约束分别加入LP得两个新问题，即两个分枝LP1和LP2。步骤3：定界。设LP的最优值为，则它是IP最优值的上界，任取IP的一个可行解，对应目标值记为，它是的下界（初次下界可以取“”），即有：分枝定界法求解步骤步骤4：解每一分枝，并根据不同情况采取以下步骤：（1）若无可行解，则将该分枝剪掉，不再考虑。（2）若是整数解且其最优值，则该分枝的解就是原整数

5、规划问题的最优解，结束。（3）若是整数解，但最优值，则取为新的下界，该枝关闭。（4）若是非整数解且，则该分枝中不包含原问题的最优解，该枝关闭。（5）若是非整数解，，且又是平行各分枝中的最大目标函数值，则取为新的上界，同时将该枝视为新的LP，回到步骤2。步骤5：各分枝均已查清，对应最优目标值的解即是原问题的最优解。第三节0—1规划如果整数规划问题中的所有决策变量仅限于取0或者1两个值，则称此问题为0—1整数规划，简称0—1规划，其变量称为0—1变量。如果整数规划问题中的部分决策变量为0—1变量，则称为0—1混合整数规划。0—1规划的求解列举法隐枚举法

6、隐枚举法第四节指派问题指派问题的标准形式价值系数效率矩阵决策变量指派问题求解——匈牙利法推论：若将指派问题的效率矩阵每一行及每一列分别减去各行及各列的最小元素，则得到的新指派问题与原指派问题有相同的最优解。定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。定理1设指派问题的效率矩阵为，若将该矩阵的某一行（或某一列）的各个元素都减去同一常数（可正可负），得到新的效率矩阵，则以为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优值减少。每行减掉其所在行最小值，然后每列再减其所在列最

7、小值指派指派方案最优值为5＋6＋6＋5=22例3-12（1）对中所有不含◎元素的行打√，如第3行。（2）对打√的行中，所有打×零元素所在的列打√，如第1列。（3）对所有打√列中◎元素所在行打√，如第2行。（4）重复上述（2）、（3）步，直到不能进一步打√为止。（5）对未打√的每一行划一直线，如第1、3、5行。对已打√的每一列划一纵线，如第1列，既得到覆盖当前0元素的最少直线数。在未被直线覆盖过的元素中找最小元素，将打√行的各元素减去这个最小元素，将打√列的各元素加上这个最小元素（以避免打√行中出现负元素），这样就增加了零元素的个数。最优指派方案是：

8、让小组1完成任务3；小组2完成任务2；小组3完成任务1；小组4完成任务4；小组5完成任务5总成本7＋9＋6＋6＋6=34非