第4章 整数规划与分配问题

2015年4月11日星期六
0, 第i名未进入正式队 设 : xi 1, 第i名进入正式队
max z 193x1 191x2 187 x3 186 x4 180 x5 185 x6
s.t.
x1 x2 x3 x4 x5 x6 3 (1) x5 x6 ≥1 (2) x2 x5 ≤1 (3)
40
24
在实际中，许多要求变量取整的 数学模型，称为整数规划。本章 将讨论整数规划求解的基本思路、 0-1变量的用法、分配问题及匈 牙利法，以及利用Excel, Lingo, WinQSB求解的演示。
设 x1,x2表示两种货物装载数量 (整数)，依题意有如下数学模型：
max z 5 x1 6 x2 3 x1 8 x2 ≤ 40 4 x 3 x ≤ 24 1 2 x1 , x2 ≥ 0 x , x 取整数 1 2
第4章 整数规划与分配问题
重庆三峡学院 关文忠 /guanwenzhong
教学目标与要求



【教学目标】 通过本章学习，了解求解整数规划“分枝定界法”的其中思路，掌握 0-1变量在数学建模中的应用；熟练掌握“匈牙利法”，至少掌握一 种软件求得整数规划及分配问题的最优解。 【知识结构】
管理运筹学课件
2015年4月11日星期六
4.1.2 分枝定界法的基本思路*
0 1 2 3 4 5 6 7 8 x2
分枝定界法(Branch and Bound Method)用于求解整数规划问题 ，是在20世纪60年代初，由Land Doig和Dakin等人提出的。
【例4.1】 用图解法求解整数规划
2015年4月11日星期六
管理运筹学课件
导入案例——集装箱托运计划
某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的 利润以及托运所受到的限制如表4-1所示。问怎样安排托运计划，可 使利润最大？
货物 甲 乙 每箱体积/米3 3 8 每箱质量/50千克 4 3 每箱利润/百元 5 6
托运限制
2015年4月11日星期六
(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）。
x1 x2≤1 (4)
身高/厘米 193 191 187 186 180 185
位置 中锋 中锋 前锋 前锋 后卫 后卫
x2 x6≤ 1 x4 x6 ≤ 1
x1~6 0或1
(5)
管理运筹学课件
案例4-2 选址问题
某公司在城市东、西、 南三区拟建立门市部。 计划有7个位置(点) Aj(j=1,…,7)可供选择。 规定： 在东区，由A1,A2,A3 三个点至多选两个； 在西区，由 A4,A5 两 个点至少选一个；在 南区，由A6,A7 两个 点至少选一个。设各 位置建点的成本与预 计利润见表，若建点 总成本控制在100万 元以内，试问应该选 取哪几个点可使年利 润为最大？。
1, 第 i街道设消防站 设 : xi 0, 第i街道不设消防站
2015年4月11日星期六
约束 : 少于10min到达各 消防站至少存在1个
街道1 街道2 街道3 街道4 街道5 街道6 10 20 30 30 20 街道1 0 0 25 35 20 10 街道2 10 25 0 15 30 20 街道3 20 35 15 0 15 25 街道4 30 20 30 15 0 14 街道5 30 10 20 25 14 0 街道6 20
2015年4月11日星期六
例 max z 3 x1 x2 x3 x1 2 x2 x3 2 (1) x 4 x2 x3 4 (2) s.t. 1 x + x2 3 (3) 1 x1 , x2 , x3 0 或 1
改变c j 符号,变为 min min w 3 x1 x2 x3 x1 2 x2 x3 2 x 4 x2 x3 4 s.t. 1 x + x2 3 1 x1 , x2 , x3 0 或 1
x1 1 x1 1 x2 令 x2 x 1 x 3 3
目标系数升序排序 x3 3x1 5 min w x2 x1 0 x3 x1 0 2 x2 1 解得 x3 x1 2 x2 4 x2 s.t. x 0 x2 +x1 1 3 , x3 0或1 x1, x2
max(min) z CX AX ≥ (,≤)b s.t. X 取0或1
2015年4月11日星期六 管理运筹学课件
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,进行枚举.
变量取整的 LP 整数规划
整 数 规 划 与 分 配 问 题
变量取 0-1 的 LP 0-1 变量用法：添加特殊约束的 LP 数学模型 应用
分配问题数学模型
计算机求解
匈牙利法
2015年4月11日星期六
管理运筹学课件
本章主要内容
ቤተ መጻሕፍቲ ባይዱ



4.1 整数规划 4.1.1 整数规划的概念 4.1.2 分枝定界法的基本思路* 4.2 0-1规划 4.2.1 0-1规划的概念 4.2.2 0-1规划的隐枚举法简介* 4.2.4 0-1变量在数学建模中的用途 案例4-1 球队队员筛选 案例4-2 选址问题 案例4-3 集合覆盖问题 4.3 分配问题 4.3.1 分配问题数学模型 4.3.2 分配问题的解题方法——匈牙利法 案例4-4 任务分派 本章小结
max z 5 x1 6 x2 3 x1 8 x2 ≤ 40 (1) 解7 (2,4),z=34 4 x 3 x ≤ 24 (2) 1 2 解5 (8/3,4),z=37.33 x1 , x2 ≥ 0 解4 (3,3),z=33 x , x 取整数 1 2
②
解2 (3,31/8) 解1 (72/23,88/23)
管理运筹学课件
案例4-3 集合覆盖问题
某区有6个街道。这个区必须确定在什么地 方修建消防站。在保证至少有一个消防站 在每个街道的15min行驶时间内的情况下， 这个区希望修建的消防站最少。各街道间 行驶时间如表
目标 : 消防站数目最少 max z x1 x2 x3 x4 x5 x6
2015年4月11日星期六
地点
A1
A2
A3
A4
A5
A6
A7
建点成本
估计利润
20 20 25 24 22 24 23
30 30 35 34 38 40 45
1 设 : xi 0
i = 1， 2， ， 7 当Ai 未被选中，
当Ai 被选中，
数学模型为：
max z 30 x1 30 x2 35 x3 34 x4 38 x5 40 x6 45 x7 20 x1 20 x2 25 x3 24 x4 22 x5 24 x6 23x7 ≤ 100 ≤ 2 (东区) x1 x2 x3 s.t. x4 + x5 ≥ 1 (西区) x6 + x7 ≥ 1 (南区) xi 0 或 1
解3 (4,8/3)
(2,9/2),z=34.5 ①
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x1
5x1+6x2=30
解6 (4,2),z=32
(2) (3) (4) (6) (5)(1) 对“解 再对“解 剪枝：上述有三个区域的整数解分别为“解 先对“解 对“解 1” 5” 分枝定界：选取 3” 2” 分枝定界：“解 分枝定界：“解 x1 5” 2” 3” 进行分枝定界：在原模型的基础上， 的坐标 的坐标为 的坐标 (8/3,4) ， (3,31/8) 为非整数，添加 ， 4”X=(3,3) 为非整数，添加 ，分别添加 ，z=33 x2≤2 x2≤3 x1≤2 ；， 解 绘制直角坐标系，图示约束条件，图示目标函数一根基线 分别添加 x2≥4 （ “解 x2 x1≥3 6”X=(4,2) ，优化结果 ≥3 为非可行域），优化结果为 x1≤3,x1≥4 ，z=32 “解 。优化结果 ；“解 4”，X=(3,3) 7”X=(2,4) “解 ，X=(2,17/4) X=(9/2,2) z=33 2” ， ， z=34 ，为可行解；“解 X=(3,31/8) ， 。相比较，目标值最大 ，再添加 z=34.5 ， ；再添加 z=38.25 x2=4 5” 和 ， ； x1 x2=5 。 (z=30) ，使其平行移动，求得非整数最优解。该解的坐标为 “解34 X=(8/3,4) =4,x1 求得整数解 的为 3” ≥5 ，。解得整数解 ，对应的最优方案 ， X=(4,8/3) z=37.33 (2,4) ，目标值 ， ，为非可行解。 z=36 X=(4,2) 34 ，均为非整数（非可行解）。 。 ；整数解 ，z=32(0,5) 和非整数解 ，目标值 X=(21/4,1) 30，取(2,4) ，目标值 。如图 (72/23,88/23) ，不在网格线的交叉点上，非整数解（非可行解）。 z=31.25 “解 7”。 ；整数解目标值大于非整数解，取(4,2)，得“解6”。 演示：利用WinQSB,ExcelORM+规划求解,ExcelORM+Lingo求例4.1