运筹学基础-整数规划(2).ppt

3、利用EXCEL求解整数规划　 利用EXCEL求解整数规划的步骤　 利用EXCEL求解整数规划的步骤　 利用EXCEL求解整数规划的步骤　 【引例】背包问题 §4.2　0－1规划 1、用计算机模拟穷举法 列举法列表 2、隐枚举法（略） 隐枚举法的步骤是： 【例 2 】求解 0-1 规划最优解 求解过程：下面各图中红字为固定变量。 求解过程可用图表示如下： 3、利用EXCEL计算0－1型整数规划 0－1型整数规划练习 二、分配问题 指派问题的解法－－匈牙利法 基本原理 定理1：如果从效率矩阵{aij}m?m中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵{bij}m?m的任务分配问题的最优解等价于原问题的最优解。 证明：略 定理2：若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 证明：略 匈牙利算法的基本思路： 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零 指派问题的解法－－匈牙利法 变换过程中的三种可能情况： 第②种情况：较多的零 第③种情况：较少的零 变换： 两点说明 利用EXCEL求解指派问题的步骤　 补充题 补充练习题 补充练习题： 补充练习题： 2.如果效率矩阵的数字表示每人每天能完成的翻译字数，问题就变成如何分配任务，使四个人每天完成的任务量为最大。 9 13 15 4 11 16 14 13 8 14 4 15 7 9 10 2 7 3 1 12 5 0 2 3 8 2 12 1 9 7 6 14 整数规划 解决方法是：①找出全部数据的最大值，构造一个新的效率矩阵，其值为：maxaij-aij ②然后按求目标最小的匈牙利法求解 0 1 6 min 整数规划 7 3 1 12 5 0 2 3 8 2 12 1 9 7 6 14 1 6 2 0 11 5 0 2 3 7 1 11 0 3 1 0 8 3 0 0 0 min 3 2 0 11 2 0 2 3 4 1 11 0 0 1 0 8 (0) (0) (0) (0) Max Z＝15+15+16+7＝53（产量） 甲→R、乙→E、丙→G、丁→J 根据线性规划模型建立计算模板 其它同线性规划求解 整数规划 1.分配问题甲、乙、丙、丁完成A、B、C、D、E五项任务、要求： （1）E必须完成，其他四项任选三项； （2）其中一人完成两项，其他每人完成一项 （3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定四人中丙或丁完成两项任务。其他每人完成一项 问：三种情况下如何安排，总时间最少？ 整数规划 2.某班组4名工人做4件工作，计划工时如下 14 19 21 18 A4 11 10 13 9 A3 2 8 6 5 A2 2 7 5 4 A1 B4 B3 B2 B1 单耗工时 工作 （小时/件） 工人 如何安排工作可使总工时最省？ 整数规划 1、根据线性规划模型建立计算模板 maxZ= 40x1 +90x2 9x1 +7x2 ≤56 7x1 +20x2 ≤70 　　　　　x1 ≥0, x2 ≥0 　　　　　x1, x2 整数 整数规划 利用“工具栏”之“规划求解”求解 整数规划 整数规划 最优解为： x1=4,x2=2 maxZ=340 整数规划 　　一个旅行者的背包最多只能装 16 千克的物品。待装的有 5 件物品，其重量和价值见下表： 30 6 5 16 9 12 12 价值（元） 20 4 3 4 3 重量（千克） 合计 4 3 2 1 物品编号 　　他应在背包中携带哪几样物品可使携带的价值最大？试将该问题归结为数学问题。 解：以x1, x2 , x3, x4, x5表示旅行者携带的第 1、2、…、5 件物品的件数。 各xi只能取1或者0：xi =1表示携带该件物品，xi =0 表示不携带该件物品。 问题归结为: 　　 maxZ= 12x1+12x2 +9x3 +16x4 +30x5 　　　　3x1 +4x2+3x3 +4x4 +6x5 ≤16 　　　　x1 , x2 , x3 ,x4 ,x5 =0或 1 整数规划 　　此时决策变量只取 0 或 1 值。只取 0 或 1 值的变量称为0-1变量，决策变量为 0-1 变量的线性规划称为 0-1 规划。 0-1 规划的求解