管理运筹学课件第4章 整数规划与分配问题

管理运筹学课件 5
2012-10-30
4.1.2 分枝定界法的基本思路*
0 1 2 3 4 5 6 7 8 x2
分枝定界法(Branch and Bound Method)用于求解整数规划问题 ，是在20世纪60年代初，由Land Doig和Dakin等人提出的。
【例4.1】 用图解法求解整数规划
2012-10-30
地点
A1
A2
A3
A4
A5
A6
A7
建点成本
估计利润
1 设 : xi 0
20 20 25 24 22 24 23
30 30 35 34 38 40 45
i = 1 ，， ， 2 7 当 Ai 未 被 选 中 ， 当 Ai 被 选 中 ，
数学模型为：
m ax z 30 x1 30 x 2 35 x 3 34 x 4 38 x 5 40 x 6 45 x 7 20 x1 20 x 2 25 x 3 24 x 4 22 x 5 24 x 6 23 x 7 ≤ 100 x1 x 2 x3 ≤ 2 (东 区 ) s.t. x 4 + x5 ≥ 1 (西 区 ) x6 + x7 ≥ 1 (南 区 ) xi 0 或 1
x1 x 2 x 3 x 4 x 5 x 6 3 (1) x5 x6 ≥ 1 x 2 x5 ≤ 1
x1 x 2 ≤ 1
(2) (3)
(4 )
身高/厘米 193 191 187 186 180 185
位置 中锋 中锋 前锋 前锋 后卫 后卫
x2 x6≤ 1 x4 x6 ≤ 1
2012-10-30 管理运筹学课件 6
4.2.1 0-1规划的概念


0-1规划是一种特殊类型的整数规划，即决策变量只取0或 1。0-1规划在整数规划中占有重要地位，许多实际问题， 例如指派问题、选址问题、送货问题都可归结为此类规划。 求解0-1规划的常用方法是隐枚举法，对各种特殊问题还 有一些特殊方法，例如求解指派问题用匈牙利方法就比较 方便。 0-1规划的数学模型为：
2012-10-30
(1 ) (2 ) (3 ) (4 ) (5 )
管理运筹学课件
4.1.1 整数规划的基本概念


整数规划（integer programming，IP）是指一 类要求问题中的全部或一部分变量为整数的数学 规划。 在整数规划中，依决策变量的取值不同，又可进 一步划分： 如果所有变量都限制为整数，则称为纯整数规划 （Pure Integer Programming，PIP）； 如果仅一部分变量限制为整数，则称为混合整数 规划（Mixed Integer Programming，MIP）； 变量取二进制的整数规划则称为0-1规划（Binary Integer Programming，BIP）。
管理运筹学课件
m in w x 2 x 3 3 x1 5 x1 0 x1 2 + x1 1 0或1
m ax z 4
8
4.2.4 0-1变量在数学建模中的应用
2012-10-30
管理运筹学课件
9
案例4-1 球队队员筛选
某校篮球队准备从以下6名预备队 员中选拔3名为正式队员，并使平 均的身高尽可能高。这六名预备队 员情况如表所示。 队员的挑选要满足下列条件： (1) 6位预备队员选3名。 (2) 至少补充1名后卫人员。 (3) B或E中间最多入选1名。 (4) 最多补充1名中锋。 (5) 无论B或D入选，F都不能入选。 预备队员 A B C D E F
x1 0 解 得 x2 1 x 0 3 x1 1 x2 0 x 1 3
目标系数升序排序 2 x 2 x3 4 x x 3 s.t. 2 x 2 x1 , x 2 , x 3
m ax (m in ) z C X A X ≥ ( ,≤ )b s .t . X 取 0或 1
7
2012-10-30
管理运筹学课件
4.2.2 隐枚举法简介
1.化成标准形式 (1)目标函数:min ,cj>0 (2)目标若max,目标系数 改变符号,变为min; (2)若cj<0,令yj=1-xj使其 变正; (3)目标函数中,变量按目 标系数从小到大排列,约 束条件中也跟着相应改 变. 2.令标准化后的0-1问题 所有变量为0,若满足约束, 即为最优,否则转下步. 3.按目标函数中排列顺序 依次令各变量分别取1或 0,进行枚举.
x1~ 6 0 或 1
(5)
管理运筹学课件
10
案例4-2 选址问题
某公司在城市东、西、 南三区拟建立门市部。 计划有7个位置(点) Aj(j=1,…,7)可供选择。 规定： 在东区，由A1,A2,A3 三个点至多选两个； 在西区，由 A4,A5 两 个点至少选一个；在 南区，由A6,A7 两个 点至少选一个。设各 位置建点的成本与预 计利润见表，若建点 总成本控制在100万 元以内，试问应该选 取哪几个点可使年利 润为最大？。
管理运筹学课件 11
案例4-3 集合覆盖问题
某区有6个街道。这个区必须确定在什么地 方修建消防站。在保证至少有一个消防站 在每个街道的15min行驶时间内的情况下， 这个区希望修建的消防站最少。各街道间 行驶时间如表
目标 :消防站数目最少 m ax z x1 x 2 x 3 x 4 x 5 x 6
2012-10-30
0, 第 i 名 未 进 入 正 式 队 设 : xi 1, 第 i 名 进 入 正 式 队
m ax z 1 9 3 x1 1 9 1 x 2 1 8 7 x 3 1 8 6 x4 1 8 0 x5 1 8 5 x6
s.t.
2012-10-30
例 m ax z 3 x1 x 2 x 3 x1 2 x 2 x 3 2 x 4x x 4 2 3 s.t. 1 x + x2 3 1 x1 , x 2 , x 3 0 或 1 (1) (2) (3 )
改 变 c j 符 号 , 变 为 m in m in w 3 x1 x 2 x 3 x1 2 x 2 x 3 2 x 4x x 4 2 3 s.t. 1 x + x2 3 1 x1 , x 2 , x 3 0 或 1
m ax z 5 x1 6 x 2 3 x1 8 x 2 ≤ 4 0 4 x1 3 x 2 ≤ 2 4 x1 , x 2 ≥ 0 x ,x 取整数 1 2 (1)
②
解2 (3,31/8) 解1 (72/23,88/23)
解3 (4,8/3)
(2,9/2),z=34.5 ①
第4章 整数规划与分配问题
教学目标与要求



【教学目标】 通过本章学习，了解求解整数规划“分枝定界法”的其中思路，掌握 0-1变量在数学建模中的应用；熟练掌握“匈牙利法”，至少掌握一 种软件求得整数规划及分配问题的最优解。 【知识结构】
变量取整的 LP 整数规划
整 数 规 划 与 分 配 问 题
2012-10-30
管理运筹学课件
3
导入案例——集装箱托运计划
某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的 利润以及托运所受到的限制如表4-1所示。问怎样安排托运计划，可 使利润最大？
货物 甲 乙 每箱体积/米3 3 8 每箱质量/50千克 4 3 每箱利润/百元 5 6
托运限制
40
约 束 : 少 于 10min到 达 各 消 防 站 至 少 存 在 1个 x1 + x 2 ≥ 1 x + x2 x6 ≥ 1 1 x +x ≥ 1 3 4 s .t . x 3 + x 4 x 5 ≥ 1 x +x x ≥ 1 5 6 4 x 2 + x5 x6 ≥ 1 x1~ 6 = 0 或 1
0 1 2 3 4 5 6ቤተ መጻሕፍቲ ባይዱ7 8 9 10 11 12 13 14 x1
解7 (2,4),z=34 解4 (3,3),z=33
( 2 ) 解5 (8/3,4),z=37.33
5x1+6x2=30
解6 (4,2),z=32
(6) 先对“解2”分枝定界：“解2”的坐标为(3,31/8)，分别添加 x2≤3， (4) 剪枝：上述有三个区域的整数解分别为“解4”X=(3,3)，z=33； (3) 再对“解3”分枝定界：“解3”的坐标 ， 为非整数，添加x2≤2 (2) 对“解1”分枝定界：选取x1 进行分枝定界：在原模型的基础上， (5) 对“解5”分枝定界：“解5”的坐标(8/3,4)， 为非整数，添加x1≤2 解 (1) 绘制直角坐标系，图示约束条件，图示目标函数一根基线 “解6”X=(4,2)，z=32；“解7”X=(2,4)，z=34。相比较，目标值最大 （ x1≥3为非可行域），优化结果为X=(2,17/4)，再添加x2=4 （x2 ≥3为非可行域），优化结果为X=(9/2,2)，z=34.5；再添加x1 x2≥4，优化结果 “解4”，X=(3,3)，z=33，为可行解；“解5”， 分别添加x1≤3,x1≥4 。优化结果 “解2” ，X=(3,31/8)，z=38.25； (z=30)，使其平行移动，求得非整数最优解。该解的坐标为 和x2=5 。 的为34，对应的最优方案 。 求得整数解(2,4)，目标值34；整数解(0,5)，目标值30，取(2,4)。如图 =4,x1 ≥5 。解得整数解X=(4,2)，z=32和非整数解X=(21/4,1)，目标值 X=(8/3,4)，z=37.33，为非可行解。 “解3”，X=(4,8/3)，z=36，均为非整数（非可行解）。 (72/23,88/23)，不在网格线的交叉点上，非整数解（非可行解）。 “解7”。 z=31.25；整数解目标值大于非整数解，取(4,2)，得“解6”。 演示：利用WinQSB,ExcelORM+规划求解,ExcelORM+Lingo求例4.1