管理运筹学
课件
超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载
第4章_整数规划与分配问题[全文]
第4章 整数规划与分配问题 管理运筹学课件
教学目标与要求
【教学目标】
通过本章学习,了解求解整数规划“分枝定界法”的其中思路,掌握0-1变量在数学建模中
的应用;熟练掌握“匈牙利法”,至少掌握一种软件求得整数规划及分配问题的最优解。
【知识结构】
管理运筹学课件
本章主要内容
43>.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 分配问题的解题
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
——匈牙利法
案例4-4 任务分派
本章小结
管理运筹学课件
导入案例——集装箱托运
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
某厂拟用集装箱托运甲、乙两种货物,每箱的体积、质量、可获得的利润以及托运所受到的
限制如
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
4-1所示。问怎样安排托运计划,可使利润最大,
24
40
托运限制
5
6
4
3
3
8
甲
乙
每箱利润/百元
每箱质量/50千克
每箱体积/米3
货物
设 x1,x2表示两种货物装载数量(整数),依题意有如下数学模型:
在实际中,许多要求变量取整的数学模型,称为整数规划。本章将讨论整数规划求解的基本思路、0-1变量的用法、分配问题及匈牙利法,以及利用Excel, Lingo, WinQSB求解的演示。 管理运筹学课件
4.1.1 整数规划的基本概念
整数规划(integer programming,IP)是指一类要求问题中的全部或一部分变量为整数的数学规划。
在整数规划中,依决策变量的取值不同,又可进一步划分: 如果所有变量都限制为整数,则称为纯整数规划(Pure Integer Programming,PIP); 如果仅一部分变量限制为整数,则称为混合整数规划(Mixed Integer Programming,MIP); 变量取二进制的整数规划则称为0-1规划(Binary Integer Programming,BIP)。
管理运筹学课件
4.1.2 分枝定界法的基本思路*
【例4.1】 用图解法求解整数规划
分枝定界法(Branch and Bound Method)用于求解整数规划问题,是在20世纪60年代初,由Land Doig和Dakin等人提出的。
解 (1) 绘制直角坐标系,图示约束条件,图示目标函数一根基线(z=30),使其平行移动,求得非整数最优解。该解的坐标为(72/23,88/23),不在网格线的交叉点上,非整数解(非可行解)。
?
(2) 对“解1”分枝定界:选取x1 进行分枝定界:在原模型的基础上,分别添加x1?3,x1?4 。优化结果 “解2” ,X=(3,31/8),z=38.25;“解3”,X=(4,8/3),z=36,均为非整数(非可行解)。
(3) 先对“解2”分枝定界:“解2”的坐标为(3,31/8),分别添加 x2?3,x2?4,优化结果 “解4”,X=(3,3),z=33,为可行解;“解5”,X=(8/3,4),z=37.33,为非可行解。 (4) 再对“解3”分枝定界:“解3”的坐标 , 为非整数,添加x2?2 (x2 ?3为非可行域),优化结果为X=(9/2,2),z=34.5;再添加x1 =4,x1 ?5 。解得整数解X=(4,2),z=32和非整数解X=(21/4,1),目标值z=31.25;整数解目标值大于非整数解,取(4,2),得“解6”。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x1
0 1 2 3 4 5 6 7 8 x2
?
(2,9/2),z=34.5
解3 (4,8/3)
解1 (72/23,88/23)
解2 (3,31/8)
5x1+6x2=30
解4 (3,3),z=33
解5 (8/3,4),z=37.33
解6 (4,2),z=32
(5) 对“解5”分枝定界:“解5”的坐标(8/3,4), 为非整数,添加x1?2 ( x1?3为非可行域),优化结果为X=(2,17/4),再添加x2=4 和x2=5 。求得整数解(2,4),目标值34;整数解(0,5),目标值30,取(2,4)。如图“解7”。
解7 (2,4),z=34
(6) 剪枝:上述有三个区域的整数解分别为“解4”X=(3,3),z=33;“解6”X=(4,2),z=32;“解
7”X=(2,4),z=34。相比较,目标值最大的为34,对应的最优方案 。
演示:利用WinQSB,ExcelORM+规划求解,ExcelORM+Lingo求例4.1
管理运筹学课件
4.2.1 0-1规划的概念
0-1规划是一种特殊类型的整数规划,即决策变量只取0或1。0-1规划在整数规划中占有重要地位,许多实际问题,例如指派问题、选址问题、送货问题都可归结为此类规划。求解0-1规划的常用方法是隐枚举法,对各种特殊问题还有一些特殊方法,例如求解指派问题用匈牙利方法就比较方便。
0-1规划的数学模型为:
管理运筹学课件
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,进行枚举.
管理运筹学课件
4.2.4 0-1变量在数学建模中的应用
管理运筹学课件
案例4-1 球队队员筛选
中锋
中锋
前锋
前锋
后卫
后卫
193
191
187
186
180
185
A
B
C
D
E
F
位置
身高/厘米
预备队员
某校篮球队准备从以下6名预备队员中选拔3名为正式队员,并使平均的身高尽可能高。这六名预备队员情况如表所示。 队员的挑选要满足下列条件: (1) 6位预备队员选3名。 (2) 至少补充1名后卫人员。 (3) B或E中间最多入选1名。 (4) 最多补充1名中锋。 (5) 无
论B或D入选,F都不能入选。
管理运筹学课件 案例4-2 选址问题 某公司在城市东、西、南三区拟建立门市部。计划有7个位置(点) Aj(j=1,„,7)可供选择。
规定:
在东区,由A1,A2,A3 三个点至多选两个;在西区,由 A4,A5 两个点至少选一个;在南区,
由A6,A7 两个点至少选一个。设各位置建点的成本与预计利润见表,若建点总成本控制在
100万元以内,试问应该选取哪几个点可使年利润为最大,。
45
40
38
34
35
30
30
估计利润
23
24
22
24
25
20
20
建点成本
A7
A6
A5
A4
A3
A2
A1
地点
数学模型为: 管理运筹学课件 案例4-3 集合覆盖问题
20
30
30
20
10
0
街道1
10
20
35
25
0
10
街道2 20
30
15
0
25
20
街道3 25
15
0
15
35
30
街道4 14
0
15
30
20
30
街道5 0
14
25
20
10
20
街道6 街道6 街道5 街道4 街道3 街道2 街道1 某区有6个街道。这个区必须确定在什么地方修建消防站。在保证至少有一个消防站在每个
街道的15min行驶时间内的情况下,这个区希望修建的消防站最少。各街道间行驶时间如
表
管理运筹学课件
4.3.1 分配问题数学模型
37
34
30
29
38
42
39
29
33
33
29
26
37
43
33
30
仰泳
蛙泳
蝶泳
自由泳
赵
李
王
张
项目
在管理活动中,人们会经常遇到这样的问题,某单位有n(n>1) 项工作任务,需要 m(n>1)
个人去完成,并且每个人只干一件工作,每项工作都必须有人干,通过权衡,合理分派任务,
使总的消耗(或收益)达到最小(或最大)的0-1规划问题,称为分配问题(Assignment Problem,
AP)
导入案例
运动项目分配问题
某游泳队有四名运动员,其平时训练成绩(s/50m)如表所示。问如何安排可使总成绩最好,
人员
任务
效率矩阵cij 管理运筹学课件 4.3.1 分配问题数学模型
管理运筹学课件 4.3.2 匈牙利法 管理运筹学课件 4.3.2 匈牙利法 【例4.7】 用匈牙利法求引例中的最小化分配问题。
?
?
?
?
?
?
管理运筹学课件
4.3.2 匈牙利法
【例4.8】 用匈牙利法求引例中的最小化分配问题。 k=2
最优方案:
,其余=0,最优值z=34
管理运筹学课件
案例4-4 任务分派
管理运筹学课件
案例4-4 任务分派
(2)其中有一个人完成两项,其他每人完成一项; (3)任务A由甲或丙完成,任务C由丙或丁完成,任务E由甲、乙或丁完成,且规定4人
中丙或丁完成两项任务,其他每人完成一项。 (1)任务E必须完成,其他4项中可任选3项完成; 管理运筹学课件
本章小结
管理运筹学课件