24隐枚举法(运筹学)ppt课件

线性规划通常解决下列两类问题：
（1）当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源 （如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标 （2）在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多 、利润最大.）
线性规划问题的数学模型
例1.1 如图所示，如何截取x使铁皮所围成的容积最 大？
(2)
x j 0, j 1,2,, n (3)
求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。
线性规划问题的数学模型
Page 27
可行解：满足约束条件②、③的解为可行解。所有可行解 的集合为可行域。
最优解：使目标函数达到最大值的可行解。
绪论
本章主要内容： （1）运筹学简述 （2）运筹学的主要内容 （3）本课程的教材及参考书 （4）本课程的特点和要求 （5）本课程授课方式与考核 （6）运筹学在工商管理中的应用
运筹学简述
Page 2
运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹
学称之为管理科学(Management Science)。运筹学所研究的 问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案” 故有人称之为最优化技术。
Page 3
运筹学的主要内容
Page 4
数学规划（线性规划、整数规划、目标规划、动态 规划等） 图论 存储论 排队论 对策论 排序与统筹方法 决策分析
本课程的教材及参考书
Page 5
❖选用教材 ➢ 《运筹学基础及应用》胡运权主编 哈工大出版社
❖参考教材 ➢ 《运筹学教程》胡运权主编 （第2版）清华出版社 ➢ 《管理运筹学》韩伯棠主编 （第2版）高等教育出版社 ➢ 《运筹学》(修订版) 钱颂迪主编 清华出版社

高中信息技术--枚举算法
例1:一天小明回家看见妈妈好像有什么心事，于是小明关心地询问妈妈，怎么回 事？妈妈告诉小明，她不小心将单位的记录账目的单据碰到了污迹，现在很难 认出，这个数字是：113702?,怎么办？小明想了一想后，问妈妈这数有什么特点？ 妈妈说：“这数是144的整数倍”，马上，小明就帮助妈妈解决了这个问题。
、、、
i <=9
F
T
4650796
结束
4651706
4651716
千位数为1 ， 十位数从0——9一一枚举：
4651726
4651736 、、、
十位数从0—9 一一枚举
4651796
、、、、、、
千位数为9 ， 十位数从0——9一一枚 举：
4659706
4659716 4659726 4659736 、、、
4659796
j=j+1 Байду номын сангаас=i+1
提高题（模糊数据二）：模糊数字是465？7？6，它是144的
整数倍 。
开始
第二步：根据条件，找出真正的解
千位数为0 ， 十位数从0——9过一遍：
千位数为1 ， 十位数从0——9过一遍：
4650706
4650716 4650726 4650736 、、、
4650796 4651706
第二步：根据条件，检验出真正的解
开始
开始
i=0
i<=9 T
X=1137020+i
F 结束
F X mod 144=0
T
输出X
i=0
int(x/144)=x/144
i<=9 F T
或者
X=1137020+i

*** × ** ----------
**** **** ---------*****
15
h
❖分析：实际上，只要知道乘数和被乘 数就可以写出乘法算式，所以我们可 以枚举乘数与被乘数的每一位。然后 再判断是不是满足条件即可。计算量 是45=1024，对于计算机来说，计算量 非常小。
16
h
例4 时钟问题（IOI94-4）
也叫局部枚举）
12
h
例2 谁是第几名
❖在某次数学竞赛中, A、B、C、D、E五名学生被取 为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名？
❖条件1: 你如果认为A, B, C, D, E 就是这些人的 第一至第五名的名次排列, 便大错。因为:
没猜对任何一个优胜者的名次。
也没猜对任何一对名次相邻的学生。
▪ 来自若干个连续的段，每一个段中取一个分值； ▪ 每一个分值是所在段中最大的； ▪ 起点段和终点段任意，但途经段的分值和最大。
30
h
❖ 设Li为第I个段中的分值最大的段。即Li=Max{L1I， L2I，……，LMI}（1≦I≦N – 1）。例如对于样 例数据： L1=Max（-50，17，-42）=17； L2=Max（-47，-19，-3）=-3； L3=Max（36，-34，-43）=36； L4=Max（-30，-13，34）=34； L5=Max（-23，-8，-45）=-8；
3
h
枚举法的定义
❖所谓枚举法，指的是从可能的解的集 合中一一枚举各元素，用题目给定的 检验条件判定哪些是无用的，哪些是 有用的。能使命题成立的，即为解。
4
h
❖ 示例中的解变量有3个：A，B，C。其中 解变量A的可能取值范围A∈{1， … ，3}

– 无穷多个最优解。若将例1中的目标函数变为 max z=50x1+50x2，则线段BC上的所有点都代表 了最优解；
– 无界解。即可行域的范围延伸到无穷远，目标 函数值可以无穷大或无穷小。一般来说，这说 明模型有错，忽略了一些必要的约束条件；
– 无可行解。若在例1的数学模型中再增加一个约 束条件4x1+3x2≥1200，则可行域为空域，不存在 满足约束条件的解，当然也就不存在最优解了。
• 交叉学科 --涉及经济、管理、数学、工程和系统等 多学科
• 开放性 --不断产生新的问题和学科分支
• 多分支 --问题的复杂和多样性
2
运筹学的主要内容
线性规划
数 非线性规划
学
整数规划
规
动态规划
划
多目标规划
学
双层规划
最优计数问题
科
组 合
网络优化
内
优 排序问题 化 统筹图
容
对策论
随 排队论
机 优 化
13
组织 宝洁公司 法国国家铁路
应用
Interface 每年节支 期刊号 （美元）
重新设计北美生产和分销系统以 1-2/1997 2亿 降低成本并加快了市场进入速 度
制定最优铁路时刻表并调整铁路 1-2/1998 1500万更多
日运营量
年收入
Delta航空公司 IBM
进行上千个国内航线的飞机优化 配置来最大化利润
负。当某一个右端项系数为负时，如 bi<0，则把该 等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2… -ain xn = -bi。
30
例：将以下线性规划问题转化为标准形式
则该极小化问题与下面的极大化问题有相同的最优解，