运筹学的 第五章 整数规划.ppt

整数规划（Integer Programming）问题的一般形式 整数规划与其松弛问题 5.3.1 混合整数规划的求解分枝定界方法 例 首先求解整数规划（IP）对应的松弛问题（LP），如果（LP）的最优解不是整数解，则逐次增加一个新约束（即割平面），它能割去松弛问题可行域中不含整数解的区域.逐次切割，直到得到一个整数最优极点（即整数解）为止。 整数规划的求解Gomory割平面方法 松弛问题的最优解 Gomory定理 例题求解 0-1规划的求解—隐枚举方法 4.5 指派问题与匈亚利法 指派问题的数学模型 指派问题的性质 第四步：调整效益矩阵，使之增加一些零元素： (1) 在没有被直线覆盖的元素中，找出最小元素； (2) 在没有被直线覆盖的元素中，减去最小元素； (3) 在直线交叉处的元素中，加上最小元素； (4) 被一条直线覆盖的元素不变. 一般指派问题 最大化指派问题 人数和工作数不等的指派问题 一个人可做几项工作的指派问题 某项工作一定不能由某人做的指派问题 例题：0-1规划的应用-项目投资预算 0-1规划的应用-工厂-销售点配置问题 指派问题实例 例题求解 最大化指派问题 人数和工作数不等的指派问题 一个人可做几项工作的指派问题 某项工作一定不能由某人做的指派问题 最大化指派问题 最大值 最小化指派问题 A1可同时做三项工作 A1不能做B4; A3不能做B3 没有找到整数解，继续做下去 5.3.3 整数规划的图解法 Max z = 20x1 +10x2 St. 5x1 +4x2 ? 24 2x1 +5 x2 ? 13 x1 ，x2 ?0 x1 ，x2 整数 x1 x2 6 4.8 2.6 6.5 * * * * * * * 5.3.4 整数规划的计算机求解 LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 90.00001 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 90.00000 VARIABLE VALUE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0 Max z = 20x1 +10x2 St. 5x1 +4x2 ? 24 2x1 +5 x2 ? 13 x1 ，x2 ?0 x1 ，x2 整数 Max 20x1 +10x2 st 5x1 +4x2 24 2x1 +5x2 13 end gin x1 x2 (或gin 2) 5.4 整数规划的应用 例5-2 投资场所的选择 某公司拟在城市的东、南、西、北四区建立门市部，拟议中有10个位置Ai （i = 1,2, …, 10）可供选择，并规定： 在东区，由A1 、A2 、A3 三个点中至多选两个； 在西区，由A4 、A5 两个点中至少选一个； 在南区，由A6 、A7 两个点中至少选一个； 在北区，由A8 、A9 、A10 三个点中至少选两个。 Ai 各点的设备投资及每年可获利润如下表所示： 但投资总额不能超过720万元。问应选择哪几个点可使年利润为最大？ A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 投资额