第六章-整数规划讲义.ppt

例6.1：某造船厂在年度计划中准备生产甲、乙两种型号的小型船舶。该厂下年度的订单和产能十分充足，船舶所需要的A原料和B部件属于紧缺物资，供应量严格受限，而其他原材料和零部件也基本能够保证供应。两种物资的供应量，两种船舶的利润，以及生产中的相关技术数据见下表。问该造船厂在年度计划中如何安排两种船舶的产量，使得企业的利润最大。 用单纯形表求解，迭代得最优单纯性表如下表： 最优解 ，对应下图中的A点。 二、算法 一、0-1整数规划的应用实例与建模 设 表示扩建工厂的变量； 表示扩建仓库的变量； 表示更新机器的变量； 表示研制新产品的变量。由此可得下列模型： 二、0-1规划的解法 0-1整数规划是整数规划的一种特殊形式，当然可以用割平面法和分支定界法求解。同时根据变量仅取0、1两个值的特点，可以构造求解0-1规划的特殊方法。下面介绍求解0-1整数规划的一种隐枚举法。 要应用这种算法，0-1规划模型必须是下述标准型： 具体计算步骤如下： 第四步 检验解是否可行。 1．如可行，计算并记下这个可行解的z值，停止分支（因继续分支，即使得到可行解，由于目标函数的系数均为非负数，所以目标函数值也比记下的z值大，不会是最优解）； （1）若子问题都检验过，转第七步，（2）否则转第六步。 2．如不可行，进行第五步。 第五步 将子问题固定变量的值代入第一个不等式约束条件，并令不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0，这就是左端所能取得最小值。 1．若此最小值大于右端值，则称此子问题为不可行子问题，不再往下分支， （1）若子问题都检验过，转第七步，（2）否则，转第六步； 2．若此最小值小于右端值，则依次检验下一个不等式约束方程，直至所有的不等式约束方程都通过， （1）若子问题都检验过，转第七步，（2）否则，转第六步。 第六步 定出尚未检验过的另一个子问题的解，进行第三步至第五步， 1．若所有子问题都停止分支，计算停止，目标函数值最小的可行解就是最优解； 2．否则，转第七步。 第七步 检查有无自由变量。 1．若有，转第二步； 2．若没有，计算停止，目标函数值最小的可行解就是最优解。 第五节 指派问题 一、 指派问题的标准形式和数学模型 二、 指派问题的匈牙利算法 一、指派问题的标准形式和数学模型 在实际当中，我们经常遇到这样的问题：有n项不同的任务需要完成，而恰好有n个人（或n台设备）可以分别完成其中的一项任务，但由于任务的性质和个人的专长不同，不同的人去完成不同的任务所产生的效率就不一样。那么，应派哪一个人去完成哪一项任务才能使总的效率最高？这类问题就称为指派问题。 首先我看一个例子： 这是一个指派问题。对于指派问题，必须具有以下条件：（1）每项任务只能分配给一个单位或一个人去完成；（2）每个单位或人只能接受其中一项任务。设（ ）为第i个人做第j项任务的费用，由组成的系数矩阵称为效率矩阵 。例6.6的效率矩阵为： 一般指派问题的数学模型如下： 二、指派问题的匈牙利算法 定理6.1 如果对效率矩阵 的任一行（列）各元素分别减去该行（列）的最小元素，得到新矩阵 ，则以B为系数矩阵的指派问题的最优解 和原问题的最优解相同。 定理6.2 设 是一个效率矩阵，若可行解 的n个1所对应的n个 都等于0，则 是最优解。 定理6.3 设矩阵C中一部分元素为0，一部分元素不为0，则画去C中所有0元素所需要的最少直线数等于C中不同行不同列上0元素的个数。 第六节 用Excel求解整数规划 案例 供应链整合 指派问题的匈牙利算法，设效率矩阵为C： 第一步：把C的每一行减去该行的最小数，再把每一列减去该列的最小数，得到新矩阵B；第二步：按前面指出的规则圈数画线。若所画直线等于n，则问题已解决，否则转下一步；第三步：在未画去的各数中找出最小的一个，设为d，然后将未画去的各数都减去d，而对位于两直线交叉处的各数则都加上d。这样，又得到一个新矩阵，对此矩阵再重复第二步。 用Excel求解例6.4，参数设置的选择如图所示。 完成所有参数输入选择后，按“求解”就得到0-1规划的解，如下图所示。 例6.7．5人翻译5种外文的速度（印刷符号/小时）如下表6-9所示。若规定每人专门负责一个语种的翻译工作，那么，试解答下列问题： （１）应如何指派，使总的翻译效率最高？ （２）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？ 800 600 300 500 1000 戊 500 900 600 800 400