9299.net
大学生考试网 让学习变简单
当前位置:首页 >> >>

管理运筹学:管理科学方法讲义【谢家平编著】_图文

管理运筹学:管理科学方法讲义【谢家平编著】_图文

管理运筹学
-管理科学方法

教材与参考书籍
? 教材:
? 谢家平编著.管理运筹学:管理科学方法, 中国人民大学出版社,2010

? 参考书:
? 费雷德里克. 数据、模型与决策,中国财政经济出版社,2001

2

OR:SM

讲授提纲
? ? ? ? ? ? ? ? ? ? ? ? ?
3

绪 论 第一章 线性规划 第二章 线性规划讨论 第三章 对偶规划 第四章 整数规划 第五章 目标规划 第六章 动态规划 第七章 网络分析 第八章 网络计划 第九章 决策分析 第十章 方案排序 第十一章 库存控制 第十二章 排队理论

静态规划

淡化数学算法 计算机求解

动态优化 离散优化

随机优化
OR:SM

考核方式
? 结课考试:
? 笔试 每章一题 70%

? 案例研究:
? 选择合适方法结合企业实际进行应用 20%

? 平时成绩:
? 上课情况 10%

4

OR:SM

管理运筹学的称谓
? 管理运筹学是一门研究如何最优安排的学科。 ? Operations Research
? 日本译作“运用学” ? 香港、台湾译为“作业研究” ? 我国译作“运筹学”
? 源于古语“运筹帷幄之中,决胜千里之外” ? 取“运筹”二字,体现运心筹谋、策略取胜

? Management Science 管理科学
? 运用数学、统计学和运筹学中的量化分析原理和方法,建 立数学模型/计算机仿真,给管理决策提供科学依据。

5

OR:SM





? ? ? ? ? ?

一、发展历史 二、学科作用 三、学科性质 四、工作程序 五、学科体系 六、学习要求

6

OR:SM

一、发展历史
1. 早期的运筹思想
? 齐王赛马 ? 沈括运军粮 ? 渭修皇宫 ? 科学管理

2. 军事运筹学阶段
? 20世纪40年代诞生于英美 ? 1940年,英国为对付德国空军的空袭,使用了雷达,但没有科学布 局,效果不好。为解决这个问题,成立运筹学小组,称 Operational Research,意为作战研究。 ? 美国和加拿大也在军队设立运筹学小组,称Operations Research, 协助指挥官研究战略及战术问题。

3. 管理运筹学阶段
? 战后许多从事运筹学研究的科学家转向了民用问题的研究,使运筹 学在企业管理方面的应用得到了长足进展。
7 OR:SM

二、学科作用 理念的重要性
? 企业的成功要素中:
? 观念意识更新 ? 人文文化 ? 技术优势 47% 35% 18%

? 决策意识的科学性
? 成功决策 ? 正确决策
8 OR:SM

二、学科作用
1. 量化管理的重要性
? 管理科学是对与定量因素有关的管理问题通过应用科学 的方法进行辅助管理决策的一门学科。
? 目的:用科学方法分析管理问题,为管理者决策提供依据 ? 目标:在企业经营内外环境的限制下,实现资源效用最大

? 定性到定量分析,数量界限的重要性:量变引起质变
组织中存 在的问题 定性分析 评价与评估 定量分析 量化管理是第一步,它导致控制,并最终实现改进 如果不能量化某些事情,那么就不能理解它 如果不能理解它,那么就不能控制它 如果不能控制它,那么就不能改进它 ——H. James Harrington
9 OR:SM

决策

二、学科作用
2. 量化思考使人理性
? 冰淇淋实验: ? 一杯A有70克,装在50克的杯子里,看上去要溢出了 ? 一杯B是80克,装在100克的杯子里,看上去还没装满
单独凭经验判断时,在相同的价格上,人们普遍选择A

? 听一场音乐会:网络订票的票价500元,不去可退票 ? 情况1:在你马上要出发的时候,发现你把最近的价值 500元的电话卡弄丢了。你是否还会去听这场音乐会?

实验表明,大部分的回答者仍旧会去听 ? 情况2:假设昨天花500元钱买一张今晚的音乐会取票单。 在你出发时,发现把票单丢了。如果去听音乐会,就必 须再花500元钱买张票,去还会不去? 结果却是,大部分人回答说不去了
10 OR:SM

二、学科作用
3. 量化分析辅助决策
160,000

盈亏平衡分析
Revenue = 900 x Profit

120,000 Cost = 50,000 + 400 x

80,000

Fixed cost

Loss 40,000

0

40

80 120 160 Break-even point = 100 units

200

x

? ? ? ? ? ?
11

利润:I = ( P – Cm – Ch ) Q 策略1 ↑ ↑ ? ? ? ? 策略2 ↑ ? ? ? ↑ ? 策略3 ↑ ? ↓ ? ? ? 策略4 ↑ ? ? ↓ ? ? 策略5 ↑ ? ? ? ? ↓

F
差异化,领先者战略 规模化,大规模市场 机械化,第一利润源 技能化,第二利润源 信息化,第三利润源
OR:SM

二、学科作用
? 量化辅助决策案例:盈亏平衡分析
? 例:某企业
总销售额 物料成本 员工工资 管理费用 1100万元 700万元 200万元 100万元

? 现在利润=100万元,目标利润150万元 ? 利润实现的方法有:
? 将销售收入增加100% ? 将员工工资减少 25%

? 将管理费用减少 50%
? 将物料成本减少 7.1%
12 OR:SM

二、学科作用
4. 决策意识的重要性
甲 H 18 设备数 E F G G G4 F 10 裝配 G7 B G10 H7 C G 14 H 14 G20 乙 H6 F 10 裝配 E6 E 24

生产计划决策

H 10 G7

一星期工作5天, 每天正常 工作8小时 ? 一周作业费用:11000 (直接人工成本与间接费用) ? 直接人工成本:10/1h (一台机器需一位作业人员) ? 间接费用:人工成本2.5倍
?

H 13

E 15







原料 直接工时 直接人工 间接費用
A D

65

95

65 65分 10 25 100 170 70
OR:SM

65分 95分 12 30 107 173 66 14 35 144 233 89

H

H

总成本 售价 利润

13

二、学科作用
?决策的科学性?方案 一
甲 单位产品总成本 单位产品售价 单位产品利润 市场每周需求
107
173 66


144
233 89


100
170 70

40

80

40

? 甲产品产量40, 乙产品 80, 丙产品 40 ? 利润=40×66+80×89+40×70=12560

? 人员有限如何实现?采取什么薪酬制度?
? 计件工资制,让员工自愿加班

14

OR:SM

二、学科作用
?决策的科学性?方案 二
原料 运营费用 售价 市场每周需求 甲 65
173

乙 95 11000
233

丙 65
170

40

80

40

? ? ? ? ?

甲产品产量 40, 乙产品 80, 丙产品 40 总收入=40×173+80×233+40×170=32360 原料成本=40×65+80×95+40×65=12800 营运费用=11000 总利润=32360-12800-11000=8560

? 人员有限如何实现?采取什么薪酬制度?
? 岗位工资制(定岗定员),让员工自觉加班
15 OR:SM

二、学科作用
? 决策的科学性?产能符合计算
产品 市场需求 E 0 30 15 3000 2400 单位产品设备工时消耗 F G 10 31 20 21 0 21 2000 3760 2400 4800 H 31 13 24 3240 4800

40 甲 80 乙 40 丙 需求产能 可用产能

? 乙与丙哪一个产品比较赚钱?
甲 乙
144 233

E是瓶颈


100 170

总成本 售价 利润
16

107 173

66

89

70
OR:SM

二、学科作用
? 方案 三:计时工资,且以单位利润率高低为决策意识。
? 乙比较赚钱, 假如80个全部生产 ? 需用E产能2400分钟,但是E只有2400分钟可用 ? 因此只能生产80个乙 (2400/30),而丙无法生产

? ? ? ?

方案:甲产品 40个,乙产品80个,丙产品0个 总收入=40×173+80×233+0×170=25560 原料=40×65+80×95+0×65=10200 ,营运费用=11000 利润=25560-10200-11000=4360

? 方案 四:计时工资,但以占用瓶颈资源大小为决策意识。
? 丙比较赚钱, 优先生产40个 ? 需用E产能600(40ⅹ15)分钟 ? 剩下1800分钟, 可生产60个乙 (1800/30) ? 方案:甲产品 40个,乙产品 60个,丙产品 40个 ? 总收入=40×173+60×233+40×170=27700 ? 原材料=40×65+60×95+40×6540=10900 ,营运费用=11000 ? 利润=27700-10900-11000=5800
17 OR:SM

三、学科性质
1. 研究对象
? 经济和管理活动中能用“数量关系”描述的 ? 如运营、规划与组织管理问题 ? 解决的理论模型和优化方法实践

2. 学科特点
? 强调科学性和定量分析 ? 强调应用性和实践性 ? 强调从整体上进行把握

18

OR:SM

四、工作程序
管理运筹学的步骤: 明确问题环境分析

识别问题
确定目标制定准则 量化分析 控制 建立模型 软件求解 收集资料数量关系 结构分析数学模型 算法求解方案优选

结果分析
管理者制定决策: 确定方案 管理者

解的分析 是
制定决策方案选择 方案实施持续改进



实施方案

19

OR:SM

五、学科体系
1. 管理问题
需求预测 产品的市场需求量有多大,需求类别如何,对企业盈利有何影响? 生产计划 在有限资源约束下,生产什么,生产多少,获利最大? 资源配置 需要哪些资源,如何进行最优配置,资源紧缺性如何,以什么代价获取? 作业排序 作业的重要次序如何,作业的顺序安排如何? 市场营销 广告预算、媒介选择、产品定价、销售计划等如何安排?

运输问题 最佳运输线路是哪条?物流配送集载如何优化?物流设施布局如何设置?
设施选址 运营点如何选择,需要哪些运作设施,设施如何布局? 库存控制 应保持多大库存量,何时应进行订货,订货批量多少为宜? 项目规划 项目完工工期多长为宜,哪些作业起关键性作用,资源如何分配? 设备更新 设备运转状况如何演进,运行可靠性如何,何时和如何更新或改造? 人力资源 人员需求预测,技能要求,编制与任务指派,绩效测评,留用多长时间? 财务资金 资金投放的数量,从何处进行融资,资金成本是多少? 排队问题 队列多长,有无容量限制,多少服务台为宜,能提供什么水平的服务?
20 OR:SM

五、学科体系
2. 学科内容
模型类型 线性规划 整数规划 目标规划 动态规划 网络分析 网络计划 管理决策 方案排序 库存模型 统计方法 排队理论 仿真模拟
21

解决的典型办法 在线性目标和约束条件间取得最优化结果 在线性目标和约束条件间寻求整数决策最优 在相对立的目标间寻得多目标妥协的满意解 寻求多阶段动态系统的整体决策优化问题 寻求网络路径、流量分布、网络瓶颈及其改进 用各种作业和结点的网络排列来说明项目实施计划 依据决策准则权衡比较备选方案的决策结果 综合各方案的优势与不足寻求多指标排名次序 寻求订货、存储和缺货等库存成本降至最低的经济批量 从一个抽样得到普遍结果的推论和曲线拟合 分析正在等待的队列特点及其运行指标 动态观察复杂的管理问题的行为,模拟管理系统的结构关系
OR:SM

五、学科体系
3. 学科应用
? 管理既是科学又是艺术
? 低层管理的科学成分较多,高层管理的艺术成分较多 ? 运营管理需较多管理科学,人力资源管理需较多管理艺术 ? 例行管理需要较多管理科学,例外管理需要较多管理艺术
问题导向 技术支持

M: 管理决策问题
管理者: 制定决策 战略决策 营销决策 生产安排 财务分析 人力资源 方案优选 ……

MC: 定量解决方法
应用统计 线性规划 整数规划 目标规划 网络计划 网络分析 决策分析 动态规划 ……

方案选择依据

管理科学: 运用合理的 分析来改善 决策的制定

22

OR:SM

六、学习要求
1. 学科地位

管理专业课 管理运筹学 管理学科基础 技术科学 数学

战略、运营、营销、财务、人力…

离散、连续,静态、动态的方法…
经济学原理、管理学、行为科学… 加工技术、工程技术、信息技术… 高等数学、概率统计、线性代数…

23

OR:SM

六、学习要求
行业
经济学

企业A

企业B

企业C

企业战略、公司治理

商务1

商务2

商务3

会计学 财务管理

职能a

职能b

职能c

运营管理 市场营销 质量管理 项目管理 ……
人力资源管理 组织行为学

信息管理 流程管理 物流管理 供应链管理 ……

管理 科学 方法 支持

小组i
24

小组ii

小组iii

OR:SM

六、学习要求
2. 如何学习
? ? ? ? ? 重点在结合实际的应用 发挥自己管理实践经验丰富和理论联系实际的能力 强化结合实际问题建立管理优化模型的能力 强化解决问题的方案或模型的解的分析与应用能力 充分借用管理运筹学教学软件

25

OR:SM

第1 章 线性规划
内容提要 Sub title
?第一节

线性规划的一般模型 ?一、线性规划的三个要素 ?二、线性规划模型的特征 ?三、线性规划的图解方法 ?四、线性规划解的可能性 ?第二节 线性规划的单纯形法 ?一、线性规划的标准型式 ?二、线性规划之解的概念 ?三、单纯形法的基本原理

26

OR:SM

第一节 线性规划的一般模型
一、线性规划的三个要素
? 决策变量 ? 决策问题待定的量值 ? 取值要求非负 ? 约束条件 ? 任何管理决策问题都是限定在一定的条件下求解 ? 把各种限制条件表示为一组等式或不等式称约束条件 ? 约束条件是决策方案可行的保障 ? 约束条件是决策变量的线性函数 ? 目标函数 ? 衡量决策优劣的准则,如时间最省、利润最大、成本最低 ? 目标函数是决策变量的线性函数 ? 有的目标要实现极大,有的则要求极小
27 OR:SM

第一节 线性规划的一般模型
二、线性规划模型的举例
1、生产计划问题
例. 某厂生产甲乙两种产品,生产工艺路线为:各自的零部件分别在 设备A、B加工,最后都需在设备C上装配。经测算得到相关数据如表 所示。应如何制定生产计划,使总利润为最大。 产品 工时消耗 工时成本 生产能力 h 设备 甲 乙 元/h A 2 0 20 16 B 0 2 15 10 C 3 4 10 32 据市场分析,单位甲乙产品的销售价格分别为73和75元,试确定 获利最大的产品生产计划。

28

OR:SM

第一节 线性规划的一般模型
(1)决策变量:设x1为甲产品的产量,x2为乙产品的产量。
(2)约束条件:生产受设备能力制约,能力需求不能突破有效供给量。
? 设备A的约束条件表达为

2 x1 ≤16
? 同理,设备B的加工能力约束条件表达为 2x2 ≤10 ? 设备C的装配能力也有限,其约束条件为 3x1+ 4x2 ≤32

综上的LP模型:

max Z ? 3x1 ? 5 x2 ?2 x1 ? 16 ?2 x ? 10 ? 2 s.t. ? ?3x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?
OR:SM

(3)目标函数:目标是企业利润最大化
max Z= 3x1 +5x2

(4)非负约束:甲乙产品的产量为非负
x1 ≥0, x2 ≥0
29

第一节 线性规划的一般模型
二、线性规划模型的举例
2、物资运输问题
例:某产品商有三个供货源A1、A2、A3,其经销商有4个(需求 市场)B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及 从Ai 到Bj 的单位运费为Cij。为发挥集团优势,公司要统一筹划运 销问题,求运费最小的调运方案。

销地 产地 A1 A2 A3 销量

B1
6 7 3 20

B2
3 5 2 30

B3
2 8 9 10

B4
5 4 7 40

产量
50 20 30

30

OR:SM

第一节 线性规划的一般模型
(1)决策变量:设从Ai到Bj的运输量为xij, (2)目标函数:运费最小的目标函数为
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件:产量之和等于销量之和,故要满足:
? 供应平衡条件

x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30
x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40
xij≥0 (i=1,2,3;j=1,2,3,4)
OR:SM

? 销售平衡条件

? 非负性约束
31

第一节 线性规划的一般模型
二、线性规划模型的举例
3、产品配比问题
例:用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。

? 决策变量:取45%和92%的硫酸分别为 x1 和 x2 吨 ? 约束条件: ? x1 ? x2 ? 100 ? ?0.45x1 ? 0.92x2 ? 0.8 ? 100 ? 非负约束:
x1 ≥0, x2 ≥0

? 求解二元一次方程组得解
32 OR:SM

第一节 线性规划的一般模型
若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢?

? 取这5种硫酸分别为 x1、x2、x3、x4、x5 ,有 ? x1 ? x2 ? x3 ? x4 ? x5 ? 100 ? ?0.3x1 ? 0.45x2 ? 0.73x3 ? 0.85x4 ? 0.92x5 ? 0.8 ? 100 ? 有多少种配比方案? ? 何为最好? 若5种硫酸价格分别为400, 700, 1400, 1900, 2500元/t,则:

min Z ? 400 x1 ? 700 x2 ? 1400 x3 ? 1900x4 ? 2500x5 ? x1 ? x2 ? x3 ? x4 ? x5 ? 100 ? s.t. ?0.3x1 ? 0.45 x2 ? 0.73x3 ? 0.85 x4 ? 0.92 x5 ? 0.8 ?100 ? x ? 0, j ? 1, 2,...5 ? j
33 OR:SM

第一节 线性规划的一般模型
三、线性规划模型的特征
1、模型隐含假定
(1)线性化假定
? 函数关系式f(x)= c1x1+c2x2+… +cnxn,称线性函数。 ? 建模技巧:将非线性的函数进行分段线性化。

(2)同比例假定
? 决策变量变化引起目标函数和约束方程的改变量比例。

(3)可加性假定
? 决策变量对目标函数和约束方程的影响是独立于其他变量的。 ? 目标函数值是决策变量对目标函数贡献的总和。

(4)连续性假定
? 决策变量取值连续。

(5)确定性假定
? 所有参数都是确定的,不包含随机因素。
34 OR:SM

第一节 线性规划的一般模型
三、线性规划模型的特征
2、一般数学模型
? 用一组非负决策变量表示的一个决策问题; ? 存在一组等式或不等式的线性约束条件; ? 有一个希望达到的目标,可表示成决策变量的极值线性函数。

max(min) Z ? c1 x1 ? c2 x2 ? ? ? cn xn ?a11 x1 ? a12 x2 ? ? ? a1n xn ? (?, ?)b1 ?a x ? a x ? ? ? a x ? (?, ?)b 2n n 2 ? 21 1 22 2 ? s.t. ? ???? ?a x ? a x ? ? ? a x ? (?, ?)b mn n m ? m1 1 m 2 2 ? x1 , x2 ,? xn ? 0 ?
35 OR:SM

第一节 线性规划的一般模型
四、线性规划的图解方法
1、线性规划的可行域
可行域:满足所有约束条件的解的集合, 即所有约束条件共同围城的区域。
x2
maxZ= 3x1 +5 x2 2 x1 ≤16 2x2 ≤10 S.t. 3x1 +4 x2 ≤32 x1 ≥0, x2 ≥0
9 2x1 =16

D
5

C B

2x2 =10

3

0
36

4

8A

10 3x1 +4 x2 =32
OR:SM

x1

第一节 线性规划的一般模型
四、线性规划的图解方法
2、线性规划的最优解
目标函数 Z= 3x1 +5 x2 代表以 Z 为参数的一族平行线。
x2
8

D
5 3

2x1 =16

C

2x2 =10

Z=30 Z=15
4

B Z=37
8A

0
37

10

x1

3x1 +4 x2 =32
OR:SM

第一节 线性规划的一般模型
四、线性规划的图解方法
3、线性规划解的特性
? 由线性不等式组成的可行域是凸多边形(凸多边形是凸集)
?凸集定义:集合内部任意两点连线上的点都属于这个集合

a

b

c

d

? 可行域有有限个顶点。 ? 目标函数最优值一定在可行域的边界达到,而不可能在 其区域的内部。

38

OR:SM

第一节 线性规划的一般模型
五、线性规划解的可能性
1、唯一最优解:只有一个最优点 2、多重最优解:无穷多个最优解 当市场价格下降到74元,其数学模型变为
x2
8

max Z ? 3x1 ? 4 x2 ?2 x1 ? 16 ?2 x ? 10 ? 2 s.t. ? ?3x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?

2x1 =16
5

D

C

2x2 =10 B Z=32 A x1
OR:SM

2

Z=24 Z=12

0
39

4

8

10

3x1 +4 x2 =32

第一节 线性规划的一般模型
五、线性规划解的可能性
3、无界解:可行域无界,目标值无限增大 (缺乏必要约束)

max Z ? 3 x1 ? 5 x2 ? 2 x1 ? 16 s.t. ? ? x1 , x2 ? 0

40

OR:SM

第一节 线性规划的一般模型
五、线性规划解的可能性
4、没有可行解:线性规划问题的可行域是空集 (约束条件相互矛盾)
x2

目标冲突 利害冲突

目标强冲突 利害弱冲突

max Z ? 3 x1 ? 5 x2 ? x1 ? x2 ? 5 ? s.t. ?3 x1 ? 4 x2 ? 24 ?x , x ? 0 ? 1 2
4 2 6

8

O

2

4

6

8

x1
OR:SM

41

第二节 线性规划的一般模型
一、线性规划的标准型式
1、标准型表达方式
(1)代数式
max Z ? ? c j x j
j ?1 n

(2)向量式
max Z ? CX ? n ?? p j x j ? b s.t. ? j ?1 ?x ? 0 ? j

? n ?? aij x j ? bi s.t. ? j ?1 ?x ? 0 ? j

(3)矩阵式

max Z ? CX ?AX = b ? ?X ? 0
42

A:技术系数矩阵,简称系数矩阵; B:可用的资源量,称资源向量; C:决策变量对目标的贡献,称价值向量; X:决策向量。
OR:SM

第二节 线性规划的一般模型
一、线性规划的标准型式
2、标准型转换方法
(1)如果极小化原问题minZ=CX,则令 Z'=-Z,转为求 maxZ'=-CX (2)若某个bi<0,则以-1乘该约束两端,使之满足非负性的要求。 (3)对于≤型约束,则在左端加上一个非负松弛变量,使其为等式。

(4)对于≥型约束,则在左端减去一个非负剩余变量,使其为等式。 (5)若某决策变量xk无非负约束,令xk=x'k-x"k ,(x'k≥0,x"k ≥0) 。

max Z ? 3x1 ? 5 x2 ? 0 x3 ? 0 x4 ? 0 x5 ? 16 ?2 x1 ? 0 x2 ? x3 ?0 x ? 2 x ? x4 ? 10 ? 1 2 s.t. ? ? x5 ? 32 ?3x1 ? 4 x2 ? x1 , x2 , x3 , x4 , x5 ? 0 ?
43 OR:SM

第二节 线性规划的一般模型
二、线性规划之解的概念
1、线性规划解之关系
基矩阵:一个非奇异的子矩阵(线性无关)。 ? 矩阵A中任意m列的线性无关子矩阵B ,称为一个基。 ? 组成基B的列为基向量,用Pj表示(j=1,2,…,n) 。 基变量: ? 与基向量Pj 相对应的m个变量xj称为基变量 ? 其余的n - m个变量为非基变量 基解:令所有非基变量等于零,得出基变量的唯一解 。
x3 x4 x5

?1 B ? ?0 ? ?0 ?
44

0 1 0

0? 0? ? 1? ?

? 基变量是x3, x4, x5 ? 非基变量是x1, x2 ? 令非基变量x1=x2=0,得到一个基解 x3=16,x4=10, x5=32
OR:SM

第二节 线性规划的一般模型
二、线性规划之解的概念
1、线性规划解之关系
可行解:满足约束条件AX=b, X≥0的解。 可行基:可行解对应的基矩阵。 基可行解:满足非负性约束的基解称为基可行解。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 非 可 行 解
45

可 行 解

基 可 行 解

基 解

OR:SM

第二节 线性规划的一般模型
二、线性规划之解的概念
2、线性规划基本原理
定理1. 若线性规划问题存在可行域,则其可行域一定是凸集。 定理2. 线性规划问题的基可行解对应可行域的顶点。 定理3. 若可行域有界,线性规划的目标函数一定可以在可行域 的顶点上达到最优。 定理4. 线性规划如果有可行解,则一定有基可行解;如果有最 优解,则一定有基可行解是最优解。

46

OR:SM

第二节 线性规划的一般模型
二、线性规划之解的概念
3、线性规划解题思路
? 先找到一个初始基可行解,也就是找到一个初始可 行基,想办法判断这个基可行解是不是最优解。 ? 如果是最优解,就得到这个线性规划问题的最优解; ? 如果判断出不是最优解,就想法由这个可行基按一 定规则变化到下一个可行基,然后再判断新得到的基 可行解是不是最优解; ? 如果还不是,再接着进行下一个可行基变化,直到 得到最优解。

47

OR:SM

maxZ=3x1 +5x2 +0x3 +0x4+0x5 2x1 +x3 =16 2x2 +x4 =10 3x1 + 4x2 +x5 =32 x3 =16-2x1 x4 =10-2x2 x5 = 32-3x1 -4 x2 maxZ=3x1 +5x2 +0x3 +0x4+0x5 x3 =16 x4 =10-2x2 ? 0 x5 = 32-4 x2 ? 0
48

?2 1 ? ? 16 ? ? ? ? ? 2 1 ? X ? ? 10 ? ? ? 3 4 1? ? 32 ? ? ? ? ?

X ? ? 0 0 16 10 32?

T

无关
x2 ? 5 x2 ? 8
OR:SM

第二节 线性规划的一般模型
三、单纯形法的基本原理
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32
Cj
CB XB x3 x4 x5

3

5
x2 0 2 4 5

0
x3 1 0 0 0

0
x4 0 1 0 0

0
x5 0 0 1 0

b
16 10 32 0
m

x1 2 0 3 3

比 值
-

0
0 0

10/2=5 32/4=8

检验数?j

' ? j ? C j ? ? CB ? aij

49

i ?1

i

OR:SM

第二节 线性规划的一般模型
三、单纯形法的基本原理
Cj CB 0 5 XB x3 3 5 0 0 0

b
16 5 12

x1
2 0 3 3

x2
0 1 0 0 0

x3
1 0 0 0 1

x4
0 1/2 -2 -5/2 4/3

x5
0 0 1 0 -2/3

比 值
5
4

x2
x5

0

检验数?j
0
5 3 x3 x2 8

0

5
4

0
1 0

1
0 0

0
0 0

1/2
-2/3 -1/2

0
1/3 -1
OR:SM

x1

检验数?j
50

最优解 :X*=(4,5,8,0,0)T,Z*=37

第二节 线性规划的一般模型
三、单纯形法的基本原理
? 单纯形的管理启示
x2 X1=(0,5,10,0,12)T 9
5

D

X1=(4,5,8,0,0)T 2x1=16 C(4,5) B

2x2 =10

X0=(0,0,10,10,32)T 0
4 8

A
12

x1

51

企业管理过程也是如此,把现有方案作为初始方案,找到最急需要 改进的某个问题和改进方向,一次做好某个主要问题的解决与改进; 一次只解决和改进一个问题的难度最小;解决之后,再寻求可以改 进的其它地方,再次改进,不断地追求完美。 OR:SM

3x1 +4 x2 =32

最优解解释
max Z ? 3 x1 ? 4 x2 (1) ? 2 x1 ? 16 ? 2 x ? 10 (2) ? 2 s.t. ? (3) ?3 x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?

最优解 :X*=(4,5,8,0,0)T 松弛变量解释 X3=8, 设备A有8小时富裕 X4=0,条件(2)等式成立,设备B是瓶颈设备 X5=0,条件(3)等式成立,设备C是瓶颈设备
52 OR:SM

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
53

**********************最优解如下************** 目标函数最优值为 : 37 变量 最优解 相差值 --------------------x1 4 0 x2 5 0 约束 松弛/剩余变量 对偶价格 -------------------------1 8 0 2 0 .5 3 0 1 目标函数系数范围 : 变量 下限 当前值 上限 ---------------------------x1 0 3 3.75 x2 4 5 无上限 常数项数范围 : 约束 下限 当前值 上限 ---------------------------1 8 16 无上限 2 4 10 16 3 20 32 44
OR:SM

第2 章 线性规划讨论
内容提要 Sub title
?第一节 目标函数的描述技巧
?计件工资 ?岗位工资 ?计时工资

?第二节 线性规划的适用层次 ?第三节 线性规划的典型案例 ?第四节 线性规划灵敏度分析
?价值系数的变动分析

?资源数量的变动分析
54 OR:SM

第一节 目标函数的描述技巧
一、计件工资
?

计件工资体系,目标是企业利润最大化:

max Z ? 66x1 ? 89x2 ? 70x3
计件工资制薪酬体系下,工作时间不会完全受每天8小时工 作时间约束,但有产品市场需求约束,如下:
?

产品甲:

x1 ? 40

产品乙:
产品丙: 非负性约束
?

x2 ? 80 x3 ? 40
x1 , x2 , x3 ? 0

经软件求解,得到最优解为Z=12560,产品甲x1=40,产品乙 x2=80,产品丙x3=40。
55 OR:SM

第一节 目标函数的描述技巧
二、岗位工资
? ?

岗位工资制薪酬体系,以计时工资制为基础,实行定岗定员。 总收入=173x1+233x2+170x3,
原料成本=65x1+95x2+65x3,营运费用=11000, 则目标函数为maxZ= 108x1+138x2+105x3-11000

?

岗位工资制薪酬体系下,工作时间也不会完全受每天8小时工作 时间约束,但有产品市场需求约束,如下:
产品甲:

x1 ? 40

产品乙:
产品丙: 非负性约束
?

x2 ? 80 x3 ? 40
x1 , x2 , x3 ? 0

经软件求解,得到最优解为Z=8560,x1=40,x2=80,x3=40。
OR:SM

56

第一节 目标函数的描述技巧
三、计时工资
? ?

目标函数为 市场需求约束

max Z ? 108x1 ? 138x2 ? 105x3 ?11000
产品甲: 产品乙: 产品丙:

x1 ? 40

x2 ? 80 x3 ? 40

?

设备能力约束

设备E: 设备F: 设备G:

0x1 ? 30x2 ? 15x3 ? 2400 10x1 ? 20x2 ? 0x3 ? 2400 31x1 ? 21x2 ? 21x3 ? 4800 31x1 ? 13x2 ? 24x3 ? 4800

设备H:
?
57

经软件求解,得到最优解为Z=5800,x1=40,x2=60,x3=40。
OR:SM

第二节 线性规划的适用层次
计划链的层次
? 产值计划 或 利润计划 ? 绝对数量 或 增长幅度 ? 期限:年度 单位:万元 ? 大类产品年度生产计划 当前条件 ? 确定产品的品种和数量 ? 期限:年度 单位:万台
库存管理
物料需求计划MRP 能力需求计划
CRP
预测

经营计划 销售计划 生产计划大纲 主生产计划MPS

? 大类产品销售收入或台套 ? 产品品种和数量如何确定 ? 期限:年度 单位:万台
粗能力计划

物料清单

? 具体产品在具体 时段的出产计划 ? 合同订单和预测 转换为生产任务

? 将产品出产计划 转换成物料需求表

不可行

可行否
成 品 、 在 制 品 信 息 可行

外购计划
定单

车间作业计划

供应商 58

作业统计与控制 OR:SM

第三节 线性规划的典型案例
? 配送中心选择
例:某企业存在两个供货源(产地),已知原有供货源每月的供货 能力是5万台产品,新增供货源的生产能力可以满足产品的需求,且 两个货源的价格相同。 有三个区域目标市场(销地或销售商),各销地每月的市场需求量 为5万台、10万台、5万台。 在分销渠道中,拟定在2个地点中选址设立分销中心,执行产品的 转运任务。各地之间的单位运输物流成本(由距离和运输方式决定)

59

OR:SM

第三节 线性规划的典型案例

决策变量:设从供货源到分销中心的运输量为 xij ,从分销中 y jk 心到需求市场的运输量为 。选址规划在于二者的实际取值。 ? 如果 x11 ? x21 ? 0 ,则不设臵分销中心; 反之,则设臵,其规模为 x11 ? x21 x ? x22 ? 0 ,则不设臵分销中心; ? 如果 12 反之,则设臵,其规模为 x12 ? x22
?

目标函数:各条路段上的实际运输量乘以物流运输的单位费用 之总和最小,即
?

min Z ? 2x11 ? 5x12 ? 4x21 ? 2x22 ? 3 y11 ? 4 y12 ? 5 y13 ? 2 y21 ? 2 y22 ? 3 y23
?

存在供应能力约束、市场需求约束、配送中转约束,如下:

60

OR:SM

第三节 线性规划的典型案例

?

供应能力平衡约束:

x11 ? x12 ? 50000 x21 ? x22 ? 150000
y11 ? y21 ? 50000 y12 ? y22 ? 100000 y13 ? y23 ? 50000

?

市场需求平衡约束

?

配送中心不存留产品

x11 ? x21 ? y11 ? y12 ? y13 x12 ? x22 ? y21 ? y22 ? y23

?

所有变量大于等于零
x11 , x12 , x21, x22 , y11, y12 , y13 , y21, y22 , y23 ? 0

61

OR:SM

第四节 线性规划灵敏度分析
一、灵敏度分析的必要性
? 线性规划研究的是一定条件下的最优化问题
? 资源环境和市场条件是可变的 ? 基础数据往往是测算估计的数值

? 灵敏度分析的概念
? 灵敏度分析又称敏感性分析或优化后分析
? 研究基础数据发生波动后对最优解的影响
? 最优解对数据变化的敏感程度 ? 在多大的范围内波动才不影响最优基

? 灵敏度分析解决的问题:
? 价值系数C在什么范围变化而最优基B不变 ? 资源系数B在什么范围变化而最优解X不变

62

OR:SM

线性规划软件求解的灵敏度分析
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
63

**********************最优解如下************************* 目标函数最优值为 : 37 变量 最优解 相差值 --------------------x1 4 0 x2 5 0 约束 松弛/剩余变量 对偶价格 -------------------------1 8 0 2 0 .5 3 0 1 目标函数系数范围 : 价值系数C的变动范围 变量 下限 当前值 上限 ---------------------------x1 0 3 3.75 x2 4 5 无上限 常数项数范围 : 资源系数B的变动范围 约束 下限 当前值 上限 ---------------------------1 8 16 无上限 2 4 10 16 3 20 32 44

灵敏度分析

OR:SM

第四节 线性规划灵敏度分析
一、价值系数的变动分析

? 参数Cj的变化范围:价值系数Cj变化影响检验数
? 非基变量Cj的变化范围
? 非基变量Cj变化,只影响它自己的检验数

? j ' ? C j ? ?C j ? CB B?1Pj ? 0
?C j ? CB B ?1 Pj ? C j ? ?? j
Cj CB 0 5 3
64
*

? ?C j ? ?? * j
5 x2 0 1 0 0 x3 1 0 0 0 x4 4/3 1/2 -2/3 0 x5 -2/3 0 1/3

3

XB x3 x2 x1

b
8 5 4

x1 0 0 1

比 值

检验数?j

0

0

0

-1/2

-1
OR:SM

第四节 线性规划灵敏度分析
一、价值系数的变动分析
? 基变量CBl的变化范围
Cj C1 5 0 0 0

CB
0 5 C1

XB
x3 x2 x1

b
8 5 4

x1
0 0 1 0

x2
0 1 0 0

x3
1 0 0 0

x4
4/3 1/2 -2/3 2C1/3-5/2

x5
-2/3 0 1/3 -C1/3

比 值

检验数?j

?j ?0
65

15 ? 0 ? c1 ? 4
OR:SM

第四节 线性规划灵敏度分析
二、右端常量的变动分析

? 参数bi的变化范围
第r个约束的右端项为br,增量?br,其它数据不变。新的基解为
? 0 ? ? a1r * ?br ? ? b1* ? ? a1r * ? ? ? ? * ? ? *? ? *? ? ? ? ? a2 r ?br ? ?1 ?1 ?1 ?1 ? b2 ? ? ?b ? a2 r ? X B ' ? B (b ? ?b) ? B b ? B ? ?br ? ? B b ? ? ? ?? ? r ? ? ? ? ? ? ? ? ? ? *? ? *? ? a * ?b ? ?b ? ?a ? ? ? ? r ? ? mr ? m ? ? mr ? ? 0 ? ? ?

只要X'B≥0 ,则可保持最优基不变。

66

bi* air* ? 0 ? ?br ? ? * air bi* * air ? 0 ? ?br ? ? * air

b b * * max{? i * | air ? 0} ? ?br ? min{? i * | air ? 0} i i air air
OR:SM

*

*

第3 章 对偶规划
内容提要 Sub title
第一节 对偶规划的数学模型
? 对偶问题的提出 ? 对偶规划的性质

第二节 对偶规划的经济解释
? 影子价值的内涵 ? 影子价值的应用

第三节 资源定价的决策案例

67

OR:SM

生产计划问题
例. 某厂生产甲乙两种产品,生产工艺路线为:各自的零部件分别在 设备A、B加工,最后都需在设备C上装配。经测算得到相关数据如表 所示。应如何制定生产计划,使总利润为最大。 产品 工时消耗 生产能力 h 设备 甲 乙 A 2 0 16 B 0 2 10 C 3 4 32 据市场分析,单位甲乙产品的盈利水平分别为3和5元,试确定获 利最大的产品生产计划。

68

OR:SM

第一节 线性规划的一般模型
(1)决策变量:设x1为甲产品的产量,x2为乙产品的产量。
(2)约束条件:生产受设备能力制约,能力需求不能突破有效供给量。
? 设备A的约束条件表达为

2 x1 ≤16
? 同理,设备B的加工能力约束条件表达为 2x2 ≤10 ? 设备C的装配能力也有限,其约束条件为 3x1+ 4x2 ≤32

综上的LP模型:

max Z ? 3x1 ? 5 x2 ?2 x1 ? 16 ?2 x ? 10 ? 2 s.t. ? ?3x1 ? 4 x2 ? 32 ? x1 , x2 ? 0 ?
OR:SM

(3)目标函数:目标是企业利润最大化
max Z= 3x1 +5x2

(4)非负约束:甲乙产品的产量为非负
x1 ≥0, x2 ≥0
69

第一节 对偶规划的数学模型
一、对偶问题的提出
? 若上例中该厂的产品平销,现有另一企业想租赁其设备。厂方 为了在谈判时心中有数,需掌握设备台时费用的最低价码,以 便衡量对方出价,对出租与否做出抉择。 ? 在这个问题上厂长面临着两种选择:自行生产或出租设备。首 先要弄清两个问题: ? ①合理安排生产能取得多大利润? ? ②为保持利润水平不降低,资源转让的最低价格是多少?

? 问题 ①的最优解:x1=4,x2=5,Z*=37。

70

OR:SM

第一节 对偶规划的数学模型
一、对偶问题的提出 出让定价
? 假设出让A、B、C设备所得利润分别为y1、y2、y3 ? 原本用于生产甲产品的设备台时,如若出让,不应低于 自行生产带来的利润,否则宁愿自己生产。于是有 2y1+0y2+3y3≥ 3 ? 同理,对乙产品而言,则有 0y1+2y2+4y3≥ 5 ? 设备台时出让的收益(希望出让的收益最少值) minw =16y1+10y2+32y3 ? 显然还有 y1,y2,y3≥0
71 OR:SM

第一节 对偶规划的数学模型
一、对偶问题的提出
例1的对偶问题的数学模型

maxZ= 3x1 +5 x2 2x1 ≤16 2x2 ≤10 S.t. 3x +4 x ≤32 1 2 x1 , x2 ≥0
? ? ? ?
72

minw =16y1+10y2+32y3 2y1+ 0y2+ 3y3≥ 3 S.t. 0y + 2y + 4y ≥ 5 1 2 3 y1,y2,y3≥0

对偶问题的最优解: y1=0,y2=1/2,y3=1,W* =37 两个问题的目标函数值相等并非偶然 前者称为线性规划原问题,则后者为对偶问题,反之亦然。 对偶问题的最优解对应于原问题最优单纯型法表中,初始基 变量的检验数的负值。
OR:SM

第一节 对偶规划的数学模型
二、对偶规划的性质
1、对称性定理 对偶问题的对偶问题是原问题。 根据对偶规划,很容易写出对偶问题的对偶问题模型。 2、 最优性定理 设 X , Y 分别为原问题和对偶问题的可行解,且 C X ? bT Y 则 X , Y 分别为各自的最优解。 3. 对偶性定理 若原问题有最优解,那么对偶问题也有最优解,而且 两者的目标函数值相等。 4. 互补松弛性 最优解的充分必要条件是 Y * X s ? 0 ,Ys X * ? 0
73 OR:SM

线性规划软件求解的灵敏度分析
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
74

**********************最优解如下************** 目标函数最优值为 : 37 变量 最优解 相差值 --------------------x1 4 0 x2 5 0 约束 松弛/剩余变量(XS) 对偶价格(Y*) -------------------------1 8 0 2 0 .5 3 0 1 目标函数系数范围 : 变量 下限 当前值 上限 ---------------------------x1 0 3 3.75 x2 4 5 无上限 常数项数范围 : 约束 下限 当前值 上限 ---------------------------1 8 16 无上限 2 4 10 16 3 20 32 44
OR:SM

第二节 对偶规划的经济解释
一、影子价值的内涵

Z ? ? c j x j ? ? b i yi ? w
j ?1 i ?1

n

m

?Z ? yi ?bi

? 左边是资源bi每增加一个单位对目标函数Z的贡献; ? 对偶变量 yi在经济上表示原问题第i种资源的边际价值。 ? 对偶变量的值 yi*表示第i种资源的边际价值,称为影子价值。 ? 若原问题价值系数Cj表示单位产值,则yi 称为影子价格。 ? 若原问题价值系数Cj表示单位利润,则yi 称为影子利润。 ? 影子价格=资源成本+影子利润
75 OR:SM

第二节 对偶规划的经济解释
一、影子价值的内涵
? 影子价格不是资源的实际价格,反映了资源配置结构,
? 其它数据固定,某资源增加一单位导致目标函数的增量。

?

对资源i总存量的评估:购进 or 出让 对资源i当前分配量的评估:增加 or 减少 ? 第一,影子利润说明增加哪种资源对经济效益最有利 ? 第二,影子价格告知以怎样的代价去取得紧缺资源 ? 第三,影子价格是机会成本,提示资源出租/转让的基价 ? 第四,利用影子价格分析新品的资源效果:定价决策 ? 第五,利用影子价格分析现有产品价格变动的资源紧性 ? 第六,可以帮助分析工艺改变后对资源节约的收益 ? 第七,可以预知哪些资源是稀缺资源而哪些资源不稀缺

76

OR:SM

第三节 资源定价的决策方案
例:某厂生产甲乙产品,(1)如何安排每周的利润为最大?
甲 原材料 (kg) 设备 (工时) 电力 (度) 销售价格(元) 9 4 3 390 乙 4 5 10 352 资源成本 20 50 1 资源拥有量 360 200 300

(2)如果企业可以不生产,那资源出让如何定价?

一、最优生产决策
max Z ? 7 x1 ? 12x2 ?9 x1 ? 4 x2 ? 360 ?4 x ? 5 x ? 200 ? 1 2 s.t.? ?3x1 ? 10x2 ? 300 ? x1 , x2 ? 0 ?
77

X * ? (20, 24,84,0,0)T

OR:SM

第三节 资源定价的决策方案
二、资源获利决策
如果决策者考虑自己不生产甲乙两种产品,而把原拟用于生产 这两种产品的原材料、设备工时、电量资源全部出售给外单位, 或者做代加工,则应如何确定这三种资源的价格。 设原材料的单位出让获利为y1,设备工时的单位出让获利为y3, 电量的单位出让获利为y2 。 出让决策的线性规划模型:

min w ? 360 y1 ? 200 y2 ? 300 y3 ?9 y1 ? 4 y2 ? 3 y3 ? 7 ? s.t. ? 4 y1 ? 5 y2 ? 10 y3 ? 12 ?y , y , y ? 0 ? 1 2 3
* y1 ? 0 y* ? 1.36 y* ? 0.52 2 3

Z * ? 428

y* ? 0, y* ? 0 4 5
OR:SM

78

第4 章 整数规划
内容提要 Sub title
第一节 整数规划问题
? 纯整数规划 ?0-1规划 ?混合整数规划

第二节 整数规划求解
? 分枝定界法

第三节 整数规划应用

79

OR:SM

第一节 整数规划问题

? 线性规划的决策变量取值可以是任意非负实数,但许多 实际问题中,只有当决策变量的取值为整数时才有意义
? 例如,产品的件数、机器的台数、装货的车数、完成工作的人 数等,分数或小数解显然是不合理的。

? 要求全部或部分决策变量的取值为整数的线性规划问题, 称为整数规划(Integer Programming)。
? 全部决策变量的取值都为整数,则称为全整数规划(All IP)

? 仅要求部分决策变量的取值为整数,则称为混合整数规划 (Mixed IP)
? 要求决策变量只取0或1值,则称0-1规划(0-1 Programming)
80 OR:SM

第一节 整数规划问题
一、纯整数规划
例:某企业利用材料和设备生产甲乙产品,其工艺消耗系 数和单台产品的获利能力如下表所示:
资源 产品 甲 乙 现有量

A
B 单台利润

2
5 6

1
7 5

9
35

问如何安排甲、乙两产品的产量,使利润为最大。 解:设x1为甲产品的台数,x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整数
81 OR:SM

第一节 整数规划问题
二、0-1规划
序号
物品 重量

1
食品 5

2
氧气 5

3
冰镐 2

4
绳索 6

5
帐篷 12

6
相机 2

7
设备 4

重要性系数

31

15

18

14

8

4

10

登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。 解:对于每一种物品无非有两种状态,带或者不带,不妨设 不带此种物品 ?0 xj ? ? ?1 带此种物品 0-1规划的模型: max Z ? 31 x1 ? 15x 2 ? 18x 3 ? 14x 4 ? 8 x 5 ? 4 x 6 ? 10x 7 20
?5 x1 ? 5 x 2 ? 2 x 3 ? 6 x 4 ? 12x 5 ? 2 x 6 ? 4 x 7 ? 25 ? ? x j ? 0或1 ( j ? 1,2, ? 7)
82 OR:SM

第一节 整数规划问题
三、混合整数规划
例:某产品有n个区域市场,各区域市场的需求量为 bj吨/月;现拟 在m个地点中选址建生产厂,一个地方最多只能建一家工厂;若选 i 地建厂,生产能力为 ai吨/月,其运营固定费用为Fi元/月;已知址i至j 区域市场的运价为cij元/吨。如何选址和安排调运,可使总费用最小? 解:选址建厂与否是个0-1型决策变量, m m n 假设 yi =1,选择第 i 址建厂, min Z ? ? yi Fi ? ? ? cij xij i ?1 i ?1 j ?1 yi=0,不选择第 i 址建厂; ? n 计划从 i 址至区域市场 j 的运输 i ? 1, 2,..., m ? ? xij ? yi ai 运量xij为实数型决策变量。 ? j ?1
? m ? s.t. ? ? xij ? b j ? i ?1 ? xij ? 0 ? ? yi ? 0,1 ? j ? 1, 2,..., n

83

OR:SM

第二节 整数规划求解
一、舍入化整法
? 为了满足整数解的要求,自然想到“舍入”或“截尾”处理,以

得到与最优解相近的整数解。 ? 这样做除少数情况外,一般不可行,因为化整后的解有可能超出 了可行域,成为非可行解;或者虽是可行解,却不是最优解。
不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题 对于例1的数学模型,不考虑整数约束的最优解:

x1 *=28/9, x2 * =25/9,Z * =293/9
舍入化整 x1 =3, x2 =3,Z =33,不满足约束条件5x1 +7 x2 ≤35,非可行解; x1 =3, x2 =2,Z =28,满足约束条件,是可行解,但不是最优解; x1 =4, x2 =1,Z =29,满足约束条件,才是最优解。
84 OR:SM

第二节 整数规划求解
二、穷举整数法
x2
5 4 3

2x1 + x2 =9

? ? ? ?
1

? ? ?
2

? (3,3) ? ?
3
(3 1 7 ,2 ) 9 9

2
1

?
4

5x1 +7 x2 =35

x1

对于决策变量少,可行的整数解又较少时,这种穷举法有时是 可行的,并且也是有效的。 但对于大型的整数规划问题,可行的整数解数量很多,用穷举 法求解是不可能的。例如,指派问题 。
85 OR:SM

第二节 整数规划求解
三、分支定界法

? 不考虑整数限制,先求出相应线性规划 的最优解, ? 若求得的最优解符合整数要求,则是原IP的最优解; ? 若不满足整数条件,则任选一个不满足整数条件的变量来 构造新的约束,在原可行域中剔除部分非整数解。 ? 依次在缩小的可行域中求解新构造的线性规划的最优解, 直到获得原整数规划的最优解。 ? 定界的含义: ? IP是在相应的LP基础上增加整数约束 ? IP的最优解不会优于相应LP的最优解 ? 对MaxZ,相应LP的Z*是原IP的上界
86 OR:SM

第二节 整数规划求解
LP 0 :

三、分支定界法

上界: 32 下界: 0

x1 ? 3

1 7 5 , x2 ? 2 , Z ? 32 9 9 9

5 9

x1≤3
LP1 : 6 2 x1 ? 3, x2 ? 2 , Z ? 32 7 7

x1 ≥4
LP2 : x1 ? 4, x2 ? 1, Z ? 29
上界: 32 下界: 29 2 7

x2≤2
LP3 : x1 ? 3, x2 ? 2, Z ? 28

x2 ≥3
LP 4: x1 ? 2 4 4 , x2 ? 3, Z ? 31 5 5
上界: 31 下界: 29 4 5

x1≤2
LP5: 4 6 x1 ? 2, x2 ? 3 , Z ? 29 7 7

x1 ≥3
LP 6: 无可行解
上界: 29 下界: 29 6 7

x2≤3
LP7: x1 ? 2, x2 ? 3, Z ? 27

x2 ≥4
LP8: 2 2 x1 ? 1 , x2 ? 4, Z ? 28 5 5
上界: 29 下界: 29

87

OR:SM

第三节 整数规划应用
一、生产基地规划
例:某公司拟建设A、B两种类型的生产基地若干个,两种类型的生产基地 每个占地面积,所需经费,建成后生产能力及现有资源情况如下表所示。问 A、B类型基地各建设多少个,可使总生产能力最大?
A 占地(万平米) 费用(万元) 生产能力(百件/年) 2 5 20 B 5 4 10 资源限制 13 24

解:设A、B两类基地各建设 x1,x2 个,则其模型为:

max Z ? 20x1 ? 10x 2 ?2 x1 ? 5 x 2 ? 13 ? ?5 x1 ? 4 x 2 ? 24 ? x , x ? 0且为整数 ? 1 2

88

OR:SM

第三节 整数规划应用
二、人员安排规划
某服务部门各时段(每2小时为一时段)需要的服务人数如表: 时段 1 2 3 4 5 6 7 8 服务员最少数目 10 8 9 11 13 8 5 3 按规定,服务员连续工作8小时 (4个时段)为一班。请安排服务员 的工作时间,使服务员总数最少. 解:设第j 时段开始时上班的服务 员人数为xj 第 j 时段来上班的服务员将在第j+3 时段结束时下班,故决策变量有 x1,x2,x3,x4,x5 。
89

min Z ? x1 ? x2 ? x3 ? x4 ? x5 ? 10 ? x1 ? x ?x ?8 2 ? 1 ? x1 ? x2 ? x3 ?9 ? x1 ? x2 ? x3 ? x4 ? 11 ? x2 ? x3 ? x4 ? x5 ? 13 ? ? ? x3 ? x4 ? x5 ? 8 ? x4 ? x5 ? 5 ? ? x5 ? 3 ? ? x1 , x2 , x3 , x4 , x5 ? 0, ? ? x1 , x2 , x3 , x4 , x5皆为整数 OR:SM ?

s.t.

第三节 整数规划应用
三、项目投资选择
有600万元投资5个项目,收益如表,求利润最大的方案?
项目 I II III IV V 投资额 210 300 150 130 260 项目收益 160 210 60 80 180 项目 I、II、III 中选 1 项 项目 III、IV 之中选 1 项 选项目 V 必先选项目 I 约束条件

?1 xj ? ? ?0

选中第j个项目投资

不 选中第j个项目投资

max Z ? 160x1 ? 210x2 ? 60x3 ? 80x4 ? 180x5 ?210x1 ? 300x2 ? 150x3 ? 130x4 ? 260x5 ? 600 ? ? x1 ? x2 ? x3 ? 1 ? ? x3 ? x 4 ? 1 ?x ? x 1 ? 5 ? x1 , x2 , x3 , x4 , x5 ? 0或1 ?

90

OR:SM

91

OR:SM

? ***********最优解如下**********

? ? ? ? ? ? ? ? ? ? ? ? ? ?
92

目标函数最优值为 : 420 变量 最优解 -------------x1 1 x2 0 x3 0 x4 1 x5 1 约束 松弛/剩余 --------------1 0 2 0 3 0 4 0
OR:SM

第三节 整数规划应用
四、互斥约束问题
? 例如关于煤资源的限制,其约束条件为: 4 x1 ? 5x2 ? 200
? 企业也可以考虑采用天然气进行加热处理:

3x1 ? 5x2 ? 180

? 这两个条件是互相排斥的。引入0—1变量y,令

?1 采用煤加热约束起作用 y?? 作用 ?0 采用天燃气加热约束起 ? 互斥问题可由下述的条件来代替,其中M是充分大的数。

4 x1 ? 5 x2 ? 200? (1 ? y) M 3x1 ? 5 x2 ? 180? yM

93

OR:SM

?例:某厂生产甲乙产品,(1)如何安排每周的销售额为最大?
甲 原材料 (公斤) 机时 (小时) 煤 (公斤) 天然气 (升) 销售价格(元) 9 5 4 3 390 乙 4 2 5 5 352 资源拥有量 360 220 200 180

max Z ? 390 x1 ? 352 x2 ?9 x1 ? 4 x2 ? 360 ? ?5 x1 ? 2 x2 ? 220 ? s.t. ?4 x1 ? 5 x2 ? 200 ? (1 ? y ) M ?3x ? 5 x ? 180 ? yM 2 ? 1 ? x1 , x2 ? 0; y ? 0或1 ?
94 OR:SM

? ? ? ? ? ? ? ? ? ? ? ? ? ?
95

M=10000 最优解如下 目标函数最优值为 : 31680 变量 最优解 -------------x1 0 x2 90 x3 1 约束 松弛/剩余 --------------1 0 2 40 3 89750 4 9730

? M=100000 ? 最优解如下 ? 目标函数最优值为 : 31680 ? 变量 最优解 ? -------------? x1 0 ? x2 90 ? x3 1 ? 约束 松弛/剩余 ? --------------? 1 0 ? 2 40 ? 3 899750 ? 4 99730
OR:SM

第三节 整数规划应用
五、租赁生产问题
服装公司租用生产线拟生产T恤、衬衫和裤子。 每年可用劳动力8200h,布料8800m2。 T恤 衬衫 裤子 假设:yj=1,要租用生产线j 3 2 6 劳动力 yi=0,不租用生产线j 0.8 1.1 1.5 布料 250 400 600 售价 第j 种服装生产量xj 100 180 300 可变成本 15 10 生产线租金(万) 20
max Z ? 150x1 ? 220x 2 ? 300x3 ? 200000 1 ? 150000 2 ? 100000 3 y y y ?3x1 ? 2 x 2 ? 6 x3 ? 8200 ?0.8 x ? 1.1x ? 1.5 x ? 8800 ? 1 2 3 s.t.? ? x1 , x 2 , x3 ? 0, 且取整数 ? y , y , y ? 0或1 ? 1 2 3
x1 ? M 1 y1 x2 ? M 2 y 2

x3 ? M 3 y 3
OR:SM

96

第三节 整数规划应用
六、任务指派问题
甲乙丙丁四个人,ABCD四项任务,如何指派总时间最短?
时间 人员 任务

A 3 6 2 9

B 5 8 5 2

C 8 5 8 5

D 4 4 5 2

甲 乙 丙 丁

? 一项任务只由一个人完成
x11 ? x21 ? x31 ? x41 ? 1 x12 ? x22 ? x32 ? x42 ? 1 x13 ? x23 ? x33 ? x43 ? 1 x14 ? x24 ? x34 ? x44 ? 1

解: 引入0-1变量xij ,

xij =1:任务j指派人员i去完成
xij =0:任务j不派人员i去完成

? 一人只能完成一项任务
x11 ? x12 ? x13 ? x14 ? 1 x21 ? x22 ? x23 ? x24 ? 1 x31 ? x32 ? x33 ? x34 ? 1 x41 ? x42 ? x43 ? x44 ? 1
OR:SM

min Z ? 3x11 ? 5x12 ? 8x13 ? 4 x14 ? 6 x21 ? 8x22 ? 5x23 ? 4 x24
97

?2 x31 ? 5x32 ? 8x33 ? 5x34 ? 9 x41 ? 2 x42 ? 5x43 ? 2 x44

98

OR:SM

? 最优解如下 工作 ? 人 1 2 3 4 ? -------- ----- ----- ----- ----? 1 0 0 0 1 ? 2 0 0 1 0 ? 3 1 0 0 0 ? 4 0 1 0 0 ? 此指派问题的最优值为: 13
99 OR:SM

第三节 整数规划应用
七、设施选址问题
? 拟定在2个地点中选址设立分销中心,执行产品的仓储和转运, 一个分销中心拟定设立一个仓库W1、W2。 ? 若设立仓库W1,建设成本为10万元,最大库容为20万台,单位 产品的月库存成本为2元; ? 若设立仓库W2建造成本为20万元,最大库容为25万台,单位产 品的月库存成本为3元。 ? 如何选址和安排调运,建造费用+运输费用+仓储费用为最小? 解:设从供货源Si到分销中心Wj的运输量为xij,从分销中心 到需求市场Rk的运输量为yjk。仓库选址决策引入0-1变量wj :
?1 拟规划建立仓库 W j wj ? ? ?0 不规划建立仓库 W j
100 OR:SM

第三节 整数规划应用
七、设施选址问题
min Z ? 2 x11 ? 5x12 ? 4 x21 ? 2 x22 ? 3 y11 ? 4 y12 ? 5 y13 ? 2 y21 ? 2 y22 ? 3 y23 ?10w1 ? 20w2 ? 2( x11 ? x12 ) ? 3( x21 ? x22 )
? 供应能力平衡约束: ? 市场需求平衡约束:

x11 ? x12 ? 50000 x21 ? x22 ? 150000

y11 ? y21 ? 50000 y12 ? y22 ? 100000 y13 ? y23 ? 50000
x11 ? x12 ? 200000w1 x21 ? x22 ? 250000w2

? 仓储能力限制约束:

? 分销中心不存留产品: x11 ? x21 ? y11 ? y12 ? y13 x12 ? x22 ? y21 ? y22 ? y23 ? 所有变量大于等于零: x11 , x12 , x21, x22 , y11, y12 , y13 , y21, y22 , y23 ? 0
101 OR:SM

第5 章 目标规划
内容提要 Sub title
第一节 多目标规划问题 第二节 目标规划数学模型 ?目标的期望值 ?正负偏差变量 ?目标达成函数 ?目标优先级别 第三节 目标规划的图解法 第四节 目标规划单纯形法 第五节 目标规划应用案例
102 OR:SM

第一节 多目标规划问题
一、线性规划的局限性
?

线性规划的局限性
? 只能解决一组线性约束条件下,某一目标而且只能是一个目标 的最大或最小值的问题

?

实际决策中,衡量方案优劣考虑多个目标
? 生产计划决策,通常考虑产值、利润、满足市场需求等 ? 生产布局决策,考虑运费、投资、供应、市场、污染等

?

?

这些目标中,有主要的,也有次要的;有最大的,有最小的; 有定量的,有定性的;有互相补充的,有互相对立的,LP则 无能为力 目标规划(Goal Programming)
多目标线性规划 ? 含有多个优化目标的线性规划

103

OR:SM

第一节 多目标规划问题
二、多目标规划的提出
例:甲乙产品的最优生产计划。
资源 产品 甲 乙 现有资源

设备A
设备B 设备C

2
0 3

0
2 4

16
10 32

单位利润

3

5

解:线规划模型: maxZ=3x1+5x2 2x1 ≤16 2x2 ≤10 3x1+4x2 ≤32 x1,x2 ≥0
这些目标之间 相互矛盾,一 般的线性规划 方法不能求解

? 根据市场需求/合同规定:
? 希望尽量扩大甲产品 ? 减少乙产品产量。

maxZ1=3x1+5x2

maxZ2=x1 minZ3=x2
2x1

? 又增加二个目标:
104

≤16 2x2 ≤10 3x1+4x2 ≤32 x1,x2 ≥0

OR:SM

第一节 多目标规划问题
三、多目标规划的解法
? 加权系数法:
? 为每一目标赋一权数,把多目标转化成单目标。 ? 但权系数难以科学确定。

? ?

优先等级法:
? 各目标按重要性归不同优先级而化为单目标。

有效解法:
? 寻求能照顾到各目标而使决策者感到满意的解。 ? 但可行域大时难以列出所有有效解的组合。

?

目标规划法:
? 对每一个目标函数引入正的或负的偏差变量; ? 引入目标的优先等级和加权系数。

105

OR:SM

第二节 目标规划的数学模型
一、目标期望值
? 每一个目标希望达到的期望值(或目标值、理想值)。 ? 根据历史资料、市场需求或上级部门的布臵等来确定。

二、偏差变量
? ? ? ? 目标的实际值和期望值之间可能存在正的或负的偏差。 正偏差变量dk+ 表示第k个目标超过期望值的数值; 负偏差变量dk- 表示第k个目标未达到期望值的数值。 同一目标的dk+ 和dk- 中至少有一个必须为零。

目标约束 ? 引入正负偏差变量,对各个目标建立目标约束(软约束)
? ? ckj x j ? d k ? d k ? E * ? j ?1 n

106

OR:SM

第二节 目标规划的数学模型

上例中要求: ? 目标一是利润最大,拟定利润目标是30; ? 目标二是减少乙产品产量但希望不低于4件; ? 目标三是甲产品产量希望不少于6件 ; ? 对各目标引入正、负偏差变量: 3x1+5x2 +d1-- d1+ = 30 x2 +d2- - d2+ =4 x1 +d3– -d3+ = 6

107

OR:SM

第二节 目标规划的数学模型
三、目标达成函数
目标达成函数:偏差变量之和为最小值。 ? 若要求尽可能达到规定的目标值 正负偏差变量dk+ , dk- 都尽可能小,即minSk=dk++dk? 若希望尽可能不低于期望值(允许超过) 负偏差变量dk- 尽可能小,不关心超出量dk+ :minSk= dk? 若允许某个目标低于期望值,但希望不超过 正偏差变量dk+尽可能小,不关心低于量dk- :minSk= dk+

四、优先等级权数
? ? ?

目标重要度不同,用优先等级因子Pk 表示第k等级目标。 优先等级因子Pk 是正的常数, Pk >> Pk+1 。 同一优先等级下目标的相对重要性赋以不同权数w。
OR:SM

108

第二节 目标规划的数学模型

例如 ? P1 级目标实现利润至少30元; ? P2级目标是甲乙产品的产量 假设:乙产品产量不少于4件比甲产品产量不少于6 件更重要,取其权重为2

minG= P1 d1- + P2(2d2- + d3+ ) 3x1+5x2 +d1-- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+ = 6 x1 , x2 ,dk- , dk+ ≥0(k=1,2,3)

109

OR:SM

第三节 目标规划的图解法
目标规划的图解法 ?首先,按照绝对约束画出可行域, ?其次,不考虑正负偏差变量,画出目标约束的边界线, ?最后。按优先级别和权重依次分析各级目标。
min G ? Pd1? ? P2 (2d 2 ? ? d3? ) 1 ?3x1 ? 5 x2 ? d1? ? d1? ? 30 ? ? ? ? x2 ? d 2 ? d 2 ? 4 ?x ? d ? ? d ? ? 6 3 ? 1 3 ?2 x ? 16 s.t. ? 1 ?2 x2 ? 10 ?3x ? 4 x ? 32 2 ? 1 ? x1 , x2 ? 0 ? ? ? ?dl , dl ? 0(l ? 1, 2,3) ? (1) (2) (3) (4) (5) (6) (7)

x2
6

x1=5, x2=4
d3? d3?
d2?

2x1 =16 2x2 =10

D 4

E

C H G

? d2

d1?

2
d1?

B
F A 3x1 +4 x2 =32 10

0
110

2

4

6

x1
OR:SM

软件求解

111

OR:SM

运算结果
? step 1 ? step 2

? ? ? ? ? ? ? ? ? ? ?

目标函数值为 : 0 变量 解 -------------x1 1.667 x2 5 d10 d1+ 0 d20 d2+ 1 d34.333 d3+ 0

相差值 -------0 0 1 0 0 0 0 0

? ? ? ? ? ? ? ? ? ? ?

目标函数值为 : .667 变量 解 -------------x1 5.333 x2 4 d10 d1+ 6 d20 d2+ 0 d3.667 d3+ 0

相差值 -------0 0 0 0 .667 1.333 0 1

112

OR:SM

第四节 目标规划的应用案例
一、无穷多满意解
计划生产两种产品,首先要充分利用设备工时而不加班;然

后考虑利润不低于100元。问应如何制定产品A、B的产量。

解:设x1,x2表示A、B产品的产量。两个等级的目标:
P1:充分利用电量限额,正负偏差之和为最小 ? ? P (d1 ? d1 ) 目标达成函数 1

10x1 ? 12x2 ? d1 ? d1 ? 66 P2 :利润额希望不能低于100元,负偏差最小 ? P2 d 2 目标达成函数

目标约束条件

?

?

目标约束条件
113

10x1 ? 20x2 ? d 2 ? d 2 ? 100
OR:SM

?

?

第四节 目标规划的应用案例
一、无穷多满意解
由于材料供应限量为8单位,所以有系统约束条件,如下
2 x1 ? x2 ? 8

该问题的目标规划模型如下,图解法求解如图
x2 B
(1) (2) (3)

min G ? P (d1? ? d1? ) ? P2 d 2 ? 1 ?10 x1 ? 12 x2 ? d1? ? d1? ? 66 ? ? ? ?10 x1 ? 20 x2 ? d 2 ? d 2 ? 100 s.t. ? ?2 x1 ? x2 ? 8 ? x , x ? 0, d ? , d ? , d ? , d ? ? 0 ? 1 2 1 1 2 2

D 4 2
d1?

G C
d1?
? d2

d2?

2
114

A

6

8

10

x1
OR:SM

115

OR:SM

运算结果
? ? ? ? ? ? ? ? ? ? step 1 目标函数值为 : 0 变量 解 -------------x1 1.5 x2 4.25 d10 d1+ 0 d20 d2+ 0

相差值 -------0 0 1 1 0 0

? ? ? ? ? ? ? ? ? ?

step

2 目标函数值为 : 0 变量 解 -------------x1 1.5 x2 4.25 d10 d1+ 0 d20 d2+ 0

相差值 -------0 0 1 1 0 0

116

OR:SM

第四节 目标规划的应用案例
二、加班时间问题
例:某音像店有5名全职售货员和4名兼职售货员,全职 售货员每月工作160小时,兼职售货员每月工作80小时。根 据记录,全职每小时销售CD25张,平均每小时工资15元, 加班工资每小时22.5元。兼职售货员每小时销售CD10张, 平均工资每小时10元,加班工资每小时10元。现在预测下 月CD销售量为27500张,商店每周开门营业6天,所以可能 要加班。每出售一张CD盈利1.5元。 商店经理认为,保持稳定的就业水平加上必要的加班, 比不加班就业水平要好,但全职销售员如果加班过多,就 会因为疲劳过度而造成效率下降,因此不允许每月加班超 过100小时,建立相应的目标规划模型。
117 OR:SM

第四节 目标规划的应用案例
二、加班时间问题
首先,确定目标约束的优先级。如下: P1:下月的CD销售量达到27500张; P2:全职售货员加班时间不超过100小时; P3:保持全体售货员充分就业,对全职的要比兼职的 加倍优先考虑; P4:尽量减少加班时间,对两种售货员区别对待,权 重由他们对利润的贡献而定。 其次,建立目标约束函数 (1)销售目标约束,设全体全职售货员下月的工作时 间x1,全体兼职售货员下月的工作时间 x2;达不到销售 目标的偏差d1-,超过销售目标的偏差 d1+。
min G1 ? Pd1? 1 25 x1 ? 10 x2 ? d1? ? d1? ? 27500
118 OR:SM

第四节 目标规划的应用案例
二、加班时间问题
(2)正常工作时间约束。设全体全职售货员下月的停工时间d2-, 加班时间d2+ ;全体兼职售货员下月的停工时间d3-,加班时间d3+。
min G3 ? P3 (2d 2 ? ? d3? ) x1 ? d 2 ? ? d 2 ? ? 800 x2 ? d3? ? d3? ? 320

(3)加班时间的限制。设全体全职售货员下月的加班不足100小时
的偏差d4-,加班超过100小时的偏差 d4+ 。

min G2 ? P2 d 4 ? x1 ? d 4 ? ? d 4 ? ? 900

两类售货员区别对待,权重比d2+:d3+ =1:3,另一加班目标约束为
min G4 ? P4 (d 2 ? ? 3d3? ) x1 ? d 2 ? ? d 2 ? ? 800
119

x2 ? d3? ? d3? ? 320

OR:SM

第四节 目标规划的应用案例
二、加班时间问题
第三,按目标的优先级,写出相应的目标规划模型:
min G ? Pd1? ? P2 d 4? ? P3 (2d 2? ? d 3? ) ? P4 (d 2? ? 3d 3? ) 1 ?25 x1 ? 10 x2 ? d1? ? d1? ? 27500 ? ? ? ? x1 ? d 2 ? d 2 ? 800 ? x ? d ? ? d ? ? 320 ? 3 3 s.t. ? 2 ? ? ? x1 ? d 4 ? d 4 ? 900 ?x , x ? 0 ? 1 2 ?dl ? , d l ? ? 0 l ? 1, 2,3, 4 ?

运用LINGO软件求解得 x1=900,x2=500,下月共销售CD盘27500 张,获利27500×1.5-800×15-100×22.5-500×10=22000。
120 OR:SM

第四节 目标规划的应用案例
三、目标管理方案
例:某公司准备生产甲、乙产品,据市场调查:甲产品的最大 市场需求3台,乙产品的最大市场需求2台。

在满足现有电力资源严格供给约束的前提下,该厂长考虑两 个目标:一是总利润不低于3600元;二是充分利用设备台时, 但尽量少加班。问应如何制定产品甲、乙的产量,试建立其目 标规划的数学模型。
121 OR:SM

第四节 目标规划的应用案例
三、目标管理方案
1. 利润期望优先
目标规划数学模型:
min G ? Pd1? ? P2 (d 2 ? ? d 2 ? ) 1 ?300 x1 ? 400 x2 ? d ? d ? 3600 ? ? ? ?30 x1 ? 60 x2 ? d 2 ? d 2 ? 360 ?5 x ? 5 x ? 60 2 ? 1 ? s.t. ? x1 ? 8 ?x ? 6 ? 2 ? x1 , x2 ? 0 ? ? ? ?dl , dl ? 0 l ? 1, 2 ?
? 1 ? 1

运用图解法进行求解

x2

10 8
D
4

d d1?

? 1

x1 =8 E
d2?

C B F G 6 A 10

x2 =6

d

? 2

x1 =8, x2 = 3
5x1 +5x2 =60 12 x1

2 0 2
0

4

122

OR:SM

第四节 目标规划的应用案例
1. 利润期望优先
?
? ?

满意解:x1 =8, x2 = 3 设备能力:需求:30?8+60 ?3=420,实际:360 实现目标P1和P2,降低甲乙产品的设备消耗:降低率(420-360)/360=17%, 甲产品的设备消耗降为30 ?(1-17%)=25, 乙产品的设备消耗降为60 ?(1-17%)=50。
生产部目标 甲产品的产量:8,成本:900 乙产品的产量:3,成本:1400 总利润:3600 单位甲:300 单位乙:400 技术部目标 甲的设备单耗25,需降低5工时 乙的设备单耗50,需降低10工时 销售部目标 甲产品的销量:8,单价:1200 乙产品的销量:3,单价:1800

123

OR:SM

第四节 目标规划的应用案例
三、目标管理方案
2. 设备工时优先
目标规划数学模型:
? min G ? Pd 2 ? P (d 2 ? ? d 2 ? ) 1 1

运用图解法进行求解

?300 x1 ? 400 x2 ? d ? d ? 3600 ? ? ? ?30 x1 ? 60 x2 ? d 2 ? d 2 ? 360 ?5 x ? 5 x ? 60 2 ? 1 ? s.t. ? x1 ? 8 ?x ? 6 ? 2 ? x1 , x2 ? 0 ? ? ? ?dl , dl ? 0 l ? 1, 2 ?
? 1 ? 1

x2

10 8
D
4

d d1?

? 1

x1 =8 E
d2?

C B F G 6 A 10

x2 =6

d

? 2

x1 =8, x2 = 2
5x1 +5x2 =60 12 x1

2 0 2
0

4

124

OR:SM

第四节 目标规划的应用案例
2. 设备工时优先
?
? ? ?

满意解:x1 =8, x2 = 2 利润总额300?8+400?2=3200,目标:3600 不能提价,就必须降低成本以增加利润,利润增长率为12.5% 甲产品的成本需要降为1200-300?(1+12.5%)=862.5元/台,降低幅度4.2% 乙产品的成本需要降为1800-400?(1+12.5%)=1350元/台,降低幅度3.6%
生产部目标 甲产品的产量:8,成本:862.5 乙产品的产量:2 ,成本:1350 总利润:3600 单位甲:337.5 技术部目标 保证设备的正常运行

单位乙:450

甲的设备单耗30 ,乙的单耗60
销售部目标 甲产品的销量:8,单价:1200 乙产品的销量:2 ,单价:1800

125

OR:SM

第7 章 网络分析
内容提要 Sub title
第一节 第二节 第三节 第四节 第五节 图论的概念 最小树问题 最短路问题 网络最大流 最小费用流

126

OR:SM

第7 章 网络分析
18世纪,哥尼斯堡城中有一条普雷格尔河,河上有七座桥将河中的 两个小岛与河岸连接起来。人们提出了这样的问题:一个散步者能否 从某地出发,走遍七桥且每座桥恰好经过一次,最后回到原地? 陆地A 岛C

A

·
岛D D · · B ·C

陆地B

1736年瑞士数学家欧拉将两岸和小岛抽象为四个点,将桥抽 象为七条边,此问题归结为一笔画问题。
127 OR:SM

第一节
一、图的内涵
1、图的定义

图论的概念

? 图论的图与一般几何图形或代数函数图形是完全不同的 ? 图论中的图:由一些点和连接点的线所组成的“图形” ? 点和线的位置是任意的 ? 线的曲直、长短与实际无关,代表的只是点与点之间的相互关系
? 例:表示苏州v1 、杭州v2 、上海v3 、南京v4仓储网点之间的物流运输线路关系 e5 e5 ·4 v ·4 v v2· v 2· e3 e1 e3 e4 · e4 e6 e6 e1 v1 e2 ·1 v e2 v3 · e3 ·3 v e2 e5

v1
128

·

e1

v2

·

e4

v3

·

e6

v4

·
OR:SM

第一节
一、图的内涵
2、图的分类

图论的概念

? 不带箭头的连线称为“边”,如公路运输线路; ? 带箭头的连线称为“弧”,如供排水的管道运输线路。

1、无向图

2、有向图

由点和边的集合所构成

由点和弧的集合所构成

? 链:无向网络中,前后相继点和边 ? 路径:有向网络图中,前后相继并? 的交替序列称为一条链。 方向一致的点弧序列称为一条路径。 ? 圈:闭合的链称为一个圈。 ? 回路:闭合的路径称为一个回路。
129 OR:SM

第二节

最小树问题

? 无圈的连通图就是一棵树。 ? 权数总和为最小的那棵支撑树,称为最小树。 ? 求解方法:
? ?

破圈法 避圈法

例:一家企业分别要在6间办公室铺设网线接入口,网线的可行 走线方式如下图所示,如何铺设网线才能使网线总长为最短?
v2 8 v1 2 v3 8 v4
OR:SM

4 5

v5 6

3

6 6

v6

最短网线总长度为最小树权之和2+3+4+6+6=21
130

第三节
一、双标号算法
狄克斯特拉(Dijkstra)算法
? ? ?

最短路问题

?

路权:弧(vi, vj)的权为wij;路权是路p中各条弧权之和 最短路:在所有从vs到vt 的路p中,求一条路权最短的路 算法说明: ? 1959年提出,目前公认的最短路算法 ? 适合于求解所有弧权wij ≥0的最短路问题 算法假设:有向图D是完备图 ? 图D中任意两点vi , vj 之间,恰有两条弧(vi , vj)和(vj , vi) ? 若vi→vj 不存在弧, 可设想一条从vi →vj 的弧, 权wij=+∞; ? 若vi → vj 有重复的弧,则保留弧权最小的弧

131

OR:SM

第三节
一、双标号算法
?

最短路问题

基本思路: ? 从始点vs 出发,逐步探寻,给每个点标号; ? 标号分永久标号P(vk)和临时标号T(vk) 两种:
? 永久标号P(vk) 是从点 vs → vk 的最短路权 ? 临时标号T(vk) 是从点 vs → vk 最短路权的上界

?

? 算法的每一步从临时标号集中选最小者变为永久标号; ? 经过逐次改变,就可以得到从点vs 到各点的最短路。 标号形式: ? 单标号法是对每一点赋予一个路权标号 ? 双标号法是对每一点赋予两个标号:路标、路权
OR:SM

132

第三节
一、双标号算法

最短路问题

例:用双标号法求下图网络最短路
v1

2 4

v5

3 7
vs

8 1
v4 vt

9

v2

1 3 2

7 6 1

10

4
v3

v6

133

OR:SM

vs

第三节
一、双标号算法
第一步:
(vs ,3) v1

最短路问题

2 4

(vs , ?) v5

3 7

8 1
(vs , ?)

(vs , 0)

vs

9

v2

(vs ,9)

1
3 2

v4

7 6
1

vt

(vs , ?)

10

4
v3 (vs ,10)

v6 (vs , ?)

134

OR:SM

第三节
一、双标号算法
第二步:
(vs ,3)
v1

最短路问题

(v1 ,5)

2 4

v5

3 7

8 1
(v1 , 7) v4

(vs , 0)

vs

9

v2

(vs ,9)

1
3 2

7 6
1

vt

(vs , ?)

10

4
v3 (vs ,10)

v6 (vs , ?)

135

OR:SM

第三节
一、双标号算法
第三步:
(vs ,3)
v1

最短路问题

(v1 ,5)
2 4
v5

3 7

8 1 (v5 , 6)
v4

(vs , 0)

vs

9

v2

(vs ,9)

1
3 2

7 6
1

vt

(v5 ,13)

10

4
v3 (vs ,10)

v6 (vs , ?)

136

OR:SM

第三节
一、双标号算法

最短路问题

最终:依此类推,重复上述标号过程。得最短路。
(vs ,3)
v1

(v1 ,5)
2 4
v5

3
7

8 1

(vs , 0)

vs

9

(vs ,9)
v2

(v5 , 6)
1 3
v4

7 6 1

vt

(v6 ,12)

10

4
v3

2

v6

(v4 ,9)
137

(v3 ,11)
OR:SM

第三节
二、最短路的应用
1、网络的中心

最短路问题

所谓网络的中心是指一个网络中,选择某一点,使之其 余各点到该中心点的距离之和为最小。 例:如果要在下表中6个销售点中选一个作为仓库所在地,应 该建在哪个经销点,使其余各销售点都离它较近?

138

OR:SM

第三节
二、最短路的应用
2、网络的重心

最短路问题

引进点的权系数,将权系数与最短距离阵各列对应元素加权 求和,再从中选择最小的即为网络重心。

139

OR:SM

第四节
一、相关概念与定理
1、弧容量与容量网络

网络最大流

对于有向图 D=(V,A),,弧 (vi , v j ) 的容量表示弧的最大流通能力。 在V中指定一点称为发点(记为vs ),另一点称收点(记为vt),其余点 叫中间点,这样的赋权有向图就称为一个容量网络,记N=(V,A,B)

弧的实际通过量称为该弧的流量。弧集A上的流量集合 f ? ?xij ? 称为网络上的流。 满足下述条件的流称为可行流。 ? ①容量限制:对每条弧 (vi , v j ) ? A ,都有 0 ? xij ? bij

2、弧的流量与可行流

?
140

②平衡条件:中间点流出量=流入量
OR:SM

第四节
一、相关概念与定理
3、前向弧与后向弧

网络最大流

μ是从vs 到vt 的链,方向从vs →vt ,则链μ上的弧分为两类 ? 前向弧:弧的方向与链μ的方向相同,记μ+ ? 后向弧:弧的方向与链μ的方向相反,记μ-

4、饱和弧与非饱和弧
( 弧 vi , v j ) 的流量 xij 与之容量 bij 比较: ? 满足 xij ? bij 的弧称为饱和弧,弧的流量不能再扩充; ? 满足 xij ? bij 的弧称为非饱和弧,弧的流量允许再被扩大。

5、零弧与非零弧
? 满足 xij ? 0 的弧称为零弧。由于 xij ? 0 , 所以弧的流量不能减小; ? 满足 xij ? 0 的弧称为非零弧。弧的流量可以被减小, 但要满足 xij ? 0。
141 OR:SM

第四节
一、相关概念与定理
6、流量可以扩充的路

f ? ?xij ?

网络最大流

①μ上的所有前向弧为非饱和弧,即满足 xij ? bij,可以扩充流量 ②μ上的所有后向弧为非零弧,即满足 xij ? 0,可以减少流量;

是一可行流,μ是从vs 到vt 的链,若链μ满足:

则称是一条关于可行流 f 的可扩充流量的路,亦称增广链。

7、流量可以扩充的路
可行流中,网络发点的流出量(或网络收点的流入量)就 是网络的流量。 一个容量网络的诸可行流中,网络流量最大的可行流,称 为最大流

142

OR:SM

第四节
二、求最大流标号法

网络最大流

1956年,福特和富尔克逊提出了寻求网络最大流的基本方法, 称为福特-富尔克逊算法(Fold-Fulkerson Algorithm)。

? 标号过程
? 给定可行流X={xij} ,标号判断有无增广链 ? ①先给vs 标上(vs, +),vs已标号尚未检查,其余未标号 ? ②取一个已标号但未检查的点vi进行检查,对未标号点vj : ? 前向弧(vi, vj)可以扩充流量(xij<rij) ? vj尚未标号,则给vj 标号(vi,+),vj 成为己标号尚未检查的点 ? 后向弧(vk, vi)可以减少流量(xki>0) ? vk尚未标号,则给vk 标号(vi, -),vk成为己标号尚未检查的点 ? vi 成为已标号已检查的点,在其标号下划横线 ? ③检查收点vt 是否已标号: ? vt被标上号则找到增广链,进行流量调整;否则转第②步 ? 若所有标号都已检查,vt又未标号,则不存在增广链
143 OR:SM

第四节
二、求最大流标号法
? 流量调整过程

网络最大流

? 反向追踪找出vs 到vt 的增广链μ ? 计算增广链μ上可调整的流量θ
?rij ? xij ? ? ? min? ? xij ?
? xij ? ' xij ? ? xij ? ? ?x ?? ? ij

(vi , v j ) ? ? ? ? ? ? (vi , v j ) ? ? ? ? ?
(vi , v j ) ? ? (vi , v j ) ? ? ? (vi , v j ) ? ? ?

? 调整可行流的流量,得新的可行流xij ′

? 抹去所有标号,对新的可行流X ′ ={xij′},重新进入标号过程
144 OR:SM

第四节
二、求最大流标号法

网络最大流

例:下图表示了企业所处的供应市场(v1和v2)、配送中心(v3 和v4、以及销售市场(v5、v6和 v7)组成的网络,各弧上括号里的 前一个数字表示弧的容量,后一个数字是目前的实际流量。 试求这个供应-销售网络的最大流方案。
(4,4)
v1

(10,6)

v5

v3

(5,5) (4,3) (15,9)
v6

(6,3)
v4

v2

(6,6)
145

v7
OR:SM

第四节
二、求最大流标号法

网络最大流

供应-销售网络的可行流
(4,4)
v1 v5

(10,6)

v3

(5,4) (5,5) (10,8)

(15,6)
vs

(4,3) (15,9)

v6

vt

(6,3)
v4

(12,12)
v2

(8,6) (6,6)
v7

146

OR:SM

第四节
二、求最大流标号法

网络最大流

供应-销售网络的可扩充路
(+ v s ,9)
v1

(+ v1 ,4) (10,6)
v3

(4,4)

v5

(5,4) (5,5) (+ v 6 ,2)
v6

(15,6) (+ v s ,∞) v s (12,12)
v2

(10,8)

(4,3) (15,9)

vt

(6,3)
v4

(+ v 4 ,3) (8,6)
v7

(- v3 ,3)

(+ v 2 ,3) (6,6)

147

OR:SM

第四节
二、求最大流标号法

网络最大流

调整后的可行流
(4,4)
v1 v5

(10,8)

v3

(5,4) (5,5) (10,10)

(15,8)
vs

(4,1) (15,11)

v6

vt

(6,5)
v4

(12,12)
v2

(8,6) (6,6)
v7

最大流量为 f ? ? xs1 ? xs 2 ? x5t ? x6t ? x7t ? 20
148 OR:SM

第四节
三、网络的瓶颈识别
1、截集-截量与最小截集

网络最大流

? 截集: ? 对于网络N=(V,A,R),将V分为两个非空集合S和S',使 发点vs∈S,收点vt∈S' ? 所有起点属于S而终点属于S'的弧的集合称为截集 (S,S') ? 截量:截集(S,S') 中所有弧的容量之和 r(S,S') ? 最小截集:截量最小的截集

2、最大流-最小截量定理
? 网络中,任一可行流的流量恒不超过任一截集的截量, 称为流量-截量定理。 ? 最小截量的大小影响总流量的提高
149 OR:SM

第五节
一、调整法求解步骤

最小费用流

? 先不考虑费用问题,求得任一可行流X ? 据此构造赋权有向图W(X)
? 弧(vi, vj)的流量可以增加,则照原方向画弧,标上费用cij ? 弧(vi, vj)的流量可以减少,则照反方向画弧,标上费用-cij ? 在赋权有向图W(X)中寻找负回路(总权为负值的回路): ? 若没有负回路,则得到最小费用流 ? 若存在负回路,则调整与负回路相对应的弧上的流量
? 顶点是原网络N的顶点 ? 弧权根据可行流X确定

? 计算调整量θ,进行流量调整
? 若弧(vi,vj)与负回路方向一致,则其流量调整为xij +θ ? 若弧(vi,vj) 与负回路方向相反,则其流量调整为xij -θ

? 赋权有向图→寻找负回路→调整流量…直到没有负回路
150 OR:SM

第五节
二、调整法应用举例

最小费用流

例:下图表示了企业所处的供应市场(v1和v2)、配送中心 (v3和v4、以及销售市场(v5、v6和 v7)组成的网络。 弧旁的数字为 (bij , xij ) cij ,分别表示弧的容量、实际流量、费用。 试求这个供应-销售网络流的最小费用流
(4,4)
v1

(10,8) 5 6

v5

v3

10
(5,5) 10 1
v6

(5,4)

(15,8) 30
vs

(10,10) 1 1 (8,6)

(4,1)

vt

35 (12,12)
v2
151

(6,5) 8
v4

(15,11) 4

3 (6,6)

v7
OR:SM

第五节
二、调整法应用举例
1、赋权有向图 W ( f1 )

最小费用流

-10
v1 v3

v5

1 -1

30 -30
vs

-10 6

-6
4 -4

v6

-35
v2 v4

8 -8 -3
v7

-1
1 -1

vt

2、寻找负回路
? 在赋权有向图 W ( f1 ) 中,寻找总权数为负的回路 ? 选取负权绝对值大的那条负回路进行流量分布调整
152 OR:SM

第五节
二、调整法应用举例
3、调整弧流量

最小费用流

(4,4)
v1

(10,9)
5 6

v5

v3

10 (5,5) 10 1
v6

(5,4)

(15,9) 30
vs

(10,10) 1 1 (8,6)

(4,0)

vt

35 (12,11)
v2

(6,5) 8
v4

(15,11) 4

3 (6,6)

v7

? 重复上述步骤,直至找不到负回路 ? 最小费用为各弧上流量和单位费用的乘积之和,从左向右依次为 9?30+11?35+9?5+6?0+11?4+4?10+5?10+5?8+6?3+4?1+10?1+6?1=912。
153 OR:SM

第8 章 网络计划
内容提要 Sub title
第一节 网络图的绘制 第二节 关键路线法 ? 结点的时间参数 ? 作业的时间参数 ? 时差与关键路线 第三节 计划评审技术 第四节 网络计划优化 ? 缩短工程工期 ? 工期-费用优化 ? 工期-资源优化 第五节 缓冲时间设置
154 OR:SM

第8 章 网络计划
? 网络计划的发展历程
? ? ?

关键路线法(Critical Path Method,CPM ) 计划评审技术(Program Evaluation and Review Technique,PERT ) 图示评审技术(Graphic Evaluation and Review Technique,GERT )

?

风险评审技术(Venture Evaluation Review Technique,VERT )

? 网络计划技术的特性
网络计划技术只不过是反映和表达项目计划安排的一种方法, 是被项目施工技术所决定的,它只能适应项目施工方法的要求。 是把工程进度安排通过网络的形式直观地反映出来。

155

OR:SM

第一节

网络图的绘制

一、网络计划的图示形式
? 工序(作业):一项需要人财物或时间等资源的相对独立的活动过程
? 在网络图中用箭线“→” 表示, ? 前面直接相连工序称紧前工序,

? 直接相连的后继工序为紧后工序。

? 结点(事项):相邻工序的分界点
? 一般用圆圈来表示,每个结点编上顺序号, ? 结点既不消耗人力、物力,也不占用时间。

? 网络图
? 由工序、事项及时间参数所构成的有向图即为网络图。 ? 箭线表示工序,结点为工序间相互关系的网络图,称箭线式网络 ? 结点表示工序,箭线为工序间相互关系的网络图,称结点式网络
156 OR:SM

第一节

网络图的绘制

一、网络计划的图示形式
1、箭线式网络图
1 A 2 B 5 3

i

N-作业名称 t-作业时间

2

j C 3 4

D 5 E 5 5

2、结点式网络图
i N t

i-作业序号
N-作业名称 t-作业时间

1 2

2 5

3 5 6 0

4 3
157

5 5
OR:SM

第一节
? 工序表示的规定

网络图的绘制

二、箭线式网络图的规则
? 一条箭线和它的相关事项只能代表一道工序,不能代表多道工序, ? 两个结点之间只能有一条箭线相连。

? 不允许出现缺口与回路
? 网络图中只能有一个始点和一个终点,使得自网络图的始点经由任何路径都 可以到达终点。

? 虚工序
? 虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。 ? 不消耗时间、费用和资源,一般用虚箭线表示。

? 方向的规定
? 网络图是有方向的,工序应按工艺流程顺序或工作逻辑关系从左向右排列。

? 编号的规定
? 编号应从始结点开始,按照时序依次从小到大对结点编号,直到终结点。 ? 编号时不允许箭头编号小于箭尾编号。
158 OR:SM

第一节
三、箭线式网络图举例

网络图的绘制

某工程的工程一览表
工序 紧前工序 工序时间 a -6 b -3 c -4 4 b 3 1 4 3
159 OR:SM

d a 4

e a,c 5

f b 10

g b,d,e 8

f 10 d 4 e 5 5 g 8 6

a 6 c

2

第二节
一、结点的时间参数
? 结点的最早时间tE(j)

关键路线法

? tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。 ? 从始点事项开始,自左向右,顺着箭线方向逐个计算 。

?t E (1) ? 0 ? ?t ( j ) ? max{t (i ) ? t (i, j )} E ?E i ?

? 结点的最迟时间 tL(j)
? 指以该结点为结束的各道工序最迟必须完工的时刻,否则将会影 响后续工序按时开工,以至推迟整个工程的完工时间。 ? 从终点开始,从右向左,逆箭线方向逐个计算。

?t L (n) ? t E (n) ? ?t (i ) ? min{t ( j ) ? t (i, j )} L ?L j ?
160 OR:SM

第二节
一、结点的时间参数
计算结点时间参数
3

关键路线法

9 4

b

f 3 6 2 d 4 e 5 11 11 g 8 6 10 19

0 0 1

6 a 6 c

19

4
3 6
161

5

6
OR:SM

第二节
二、作业的时间参数

关键路线法

? 最早可能开工时间tES(i, j)

? 一个作业必须在其各紧前作业都完工后才能开工, ? 作业最早可能开工时间等于其箭尾事项的最早时间。 ? tES(i, j)= tE(i) ? 从最早可能开工时间开工,完成本作业的时间 。 ? tEF(i, j)= tES(i, j) +t(i, j)

? 最早可能完工时间 tEF(i, j)
? 最迟必须开工时间 tLS(i, j)

? 在不影响工程如期完工的前提下,作业最迟必须开工的时刻。 ? 等于它的箭头事项的最迟时间减去本作业的作业时间 tLS(i, j)= tL( j) - t(i, j) ? 在不影响工程如期完工的前提下,作业最迟必须完工的时刻 。 ? tLF(i, j)= tLS(i, j) +t(i, j) = tL( j)
OR:SM

? 最迟必须完工时间 tLF(i, j)
162

第二节
三、时差与关键路线

关键路线法

? 时差又称宽裕时间:不影响如期完成任务的条件下,各道工序可以机 动使用的一段时间。 ? 总时差R(i, j):不影响其紧后工序最迟必须开工的前提下,本工序最 早可能完工时间可以推迟的时间。 ? R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j) ? 单时差r(i, j):不影响其紧后工序最早可能开工的前提下,本工序最早 可能完工时间可以推迟的时间。 ? r(i, j)= tE( j) -tE(i) -t(i, j) ? 总时差为零的工序称为关键工序;关键工序组成关键路线。 tES tLS tEF r(i,j) tLF

tES
R(i,j)

tLS

tEF

tLF

163

OR:SM

第二节
三、时差与关键路线
路线
1 2 3

关键路线法

路线的组成
①→④→⑥ ①→④→⑤→⑥ ①→②→⑤→⑥

路线长度
3+10=13 3+0+8=11 6+4+8=18

3 4 b

9

4
5

①→②→③→⑤→⑥
①→③→⑤→⑥

6+0+5+8=19
4+5+8=17

f 3 6 2 d 4 e 5 3 5 11 11 g 8 6 10 19 19

0 0 1

6 a 6 c 4

6
164

6
OR:SM

第二节
四、时间参数算例

关键路线法

计算作业最早开始时间、最迟开始时间、最早结束时间、 最迟结束时间以及时差,从表中寻找总时差与单时差都为 零的作业,即为关键作业,将其连接起来就是关键路线。
作业 a b c
t (i , j )
tES (i, j ) tEF (i, j ) tLS (i, j ) tLF (i, j ) R (i , j )

r (i , j )

关键 作业 a e g
OR:SM

6 3 4

0 0 0 6 6 3 11

6 3 4 10 11 13 19

0 6 2 7

6 9 6 11

0 6 2 1

0 0 2 1

d
e f g
165

4
5 10 8

6
9 11

11
19 19

0
6 0

0
0 0

第三节
一、作业时间估计

计划评审技术

? 工序时间的三种可能估计: ? 最乐观时间:在最理想的情况下完成工序所需时间a; ? 最悲观时间:在最不利的情况下完成工序所需时间b; ? 最可能时间:在正常情况下完成工序所需时间m。 ? 加权平均就是工序时间t
工序时间 t ?

二、计算期望工期
工期TE ? ? (
i

a ? 4m ? b b?a 2 ,方差 ? 2 ? ( ) 6 6

? 工程期望工期等于关键路线上各道工序的时间之和 。
ai ? 4mi ? bi b ? ai 2 ),方差? 2 ? ? ( i ) 6 6 i
Tk ? TE

? 设规定的工程完工时间为Tk,则完工时间的概率为 ? ( x) ?
166

?

OR:SM

第三节
三、PERT应用举例

计划评审技术

某项目的作业流程及其时间估计
作业 a b c 紧前作业 a,b 作业时间估计 乐观时间 3 2 1 悲观时间 可能时间 5 4 3 4 3 2 4 3 2 作业时间 期望 方差 1/9 1/9 1/9

d
e f g

a
c,d a e,f

3
2 7 2

11
10 13 10

4
9 10 6

5
8 10 6

16/9
16/9 1 16/9

若合同规定工期为20,求如期完工的概率;若要求有90%的把握如 期完工,求可接受的合同工期的为多少。
167 OR:SM

第三节
三、PERT应用举例
4 0 0 4

计划评审技术

a 4 b 3

2
f d 5 3
4 7 10

17 17

1

5 e 8 4
9
9

g 6

23 23

6

c 2

? 参数计算

? 工程期望工期 TE=23 ,关键工序的方差?2 =49/9,则 ? (x)=-1.29,查表知 P(x)=9.9% ? P(x)=90% ,查表知 ? (x)=1.3,则可接受的合同工期为TE+ ? ? (x) =26
168 OR:SM

第四节
一、缩短工程工期

网络计划优化

? ①改进工艺和技术装备,压缩关键工序的作业时间 ? ②合理组织平行作业、交叉作业 ? 平行作业指两道以上相互独立的工序同时进行 ? 交叉作业指将紧前工序完成的部分任务分期分批地转 入下道工序 ? ③利用时差,合理调配资源等途径实现

169

OR:SM

第四节
二、工期-费用优化

网络计划优化

1、工期与成本之间关系
? 工期的缩短与费用是密切相关的 ? 工程费用最低的完工时间(最低成本日程)
费用
直接费用 工程总费用

间接费用

极限完 工时间
170

最优完 工时间

正常完 工时间

时间
OR:SM

第四节
二、工期-费用优化

网络计划优化

? 寻求最低成本日程的思路:从网络计划的关键工序着手,对增加 直接费用做少的某些关键工序采取措施,缩短其作业时间。
直接 费用

极限完 工时间

正常完 工时间

时间

赶单位时间增加的直接 费用(费率) ?
171

赶进度极限完工费用 正常完工费用 正常完工作业时间 极限完工作业时间 OR:SM

第四节
2、工期-费用优化案例

网络计划优化

某工程作业流程及其费用统计资料
作业 A B C D E 紧前作业 B B 作业时间(天) 正常完工 3 5 5 6 5 极限完工 3 3 4 3 2 作业直接费用(万元) 正常完工 8 16 20 20 5 极限完工 8 19 23 23 8.6 费率 1.5 3 1 1.2

F
G H

E
D A 合计 间接费用

3
4 5

3
3 2

10
9 20 88 2万元/天

10
11 28

2 2

172

OR:SM

第四节

网络计划优化

方案I:各道作业正常完工
3 10 h

a 3

2

5

0 1 0

5 b d

11

11 g

15 6 15

3
5 5 5 c 5 10

4 6
e 5 12

4

f

3

工程费用=正常完工直接费用+间接费用=88+2×15=118万元。
173 OR:SM

第四节

网络计划优化

方案2:关键路线d上赶进度
3 8 h 2 5

a 3

0 1

5 b 3 5 5 5 c 5 4 e d

9 4

9
g 4 6

13

0

13

5
10

f 3

10

工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+2×1+2×13=116万元。
174 OR:SM

第四节

网络计划优化

方案3:关键路线b上赶进度
3 6 2 h 5

a 3

0 1

3 b 3 3 3 5 c 5 4 e d

7 4

7
g 4 6

11

0

11

5
8

f 3

8

工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+2×1+2×1.5+2×11=115万元。
175 OR:SM

第四节

网络计划优化
3

方案4:关键路线b、e上赶进度
8 h 2 5 a 3

0 1 0

3 b 3 d

6 4 3 e 4 5

6 g 4 6

10

3 3 c 5

10

f 3 7

7

工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+2×1+2×1.5+1×(1+1.2)+2×11=115.2万元。
176 OR:SM

第四节
三、工期-资源优化
资源平衡准则:
?

网络计划优化

在压缩工程时间及费用的同时,要分别考量每道作业所需资

源的用量与供应能力及时间限制,以便确定每道作业可压缩时间 的限度及其进度安排。
? ?

优先保证关键路线上关键作业对资源的需求量。 对非关键作业要资源,利用时差调整非关键作业的开工时间

和完工时间,以达到与关键作业在占用资源的时间上错开,拉平 资源需要量的高峰。
?

当资源绝对受限制时,在保证不推迟或尽量少推迟工程完工

时间的前提下,全面统筹安排,最大限度地利用资源。

177

OR:SM

第四节
工序 a b

网络计划优化
c d e f g

每天只有13台设备可用,计划10天完成,试合理安排生产进度

紧前工序
作业时间 每天所需设备数

-3 13
3

-1 5

a
2 8

a
3 2

b,c
4 6

e,d
1 12

a
5 5

0

a 3 1 b 1

2 c 2

3

0

d 3 e 4 4

g 5 f 1
0

5

10 10

3

178

5 5 9 9 ? 所需工作日:3×13+1×5 +2×8 +3×2 +4×6 +1×12 +5×5=127 ? 10天完成,则平均每天所需机器12.7台,现有机器13台,适当安排可以完工

OR:SM

第四节
三、工期-资源优化
3、制定初始方案
工 序 a b 相关 结点 ①?② ①?③ 作业 最早 时间 开工 时间 3 1 0 0

网络计划优化

以最早开工时间,安排初始进度如表

总 时 差 0 4

工程进度
1
13 5 8 2 8 2 2 6 6 6 6 12 5 5 5 5 5

2
13

3
13

4

5

6

7

8

9

10

c
d e f g
179

②?③
②?④ ③?④ ④?⑤ ②?⑤

2
3 4 1 5

3
3 5 9 3

0
3 0 0 2

每天所需人数合计

18 13 13 15 15 13 11 11 6

12
OR:SM

第四节
三、工期-资源优化
工 序
a b c d

网络计划优化
4、调整开工时间
总 时 差
0 4 0 3
1
13

第一次调整
5 6 7 8 9 10

相关 结点
①?② ①?③ ②?③ ②?④

作业 最早 时间 开工 时间
3 1 2 3 0 0 3 3

工程进度
2
13

3
13

4

5
8 8 2 2 6 2 6 6 6 12 5 5 5 5 5

e
f g

③?④
④?⑤ ②?⑤

4
1 5

5
9 3

0
0 2

13 13 13 13 15 13 13 11 11 12 每天所需人数合计 非关键作业b延至第4天开工,非关键作业d和g延至第5天开工。
180 OR:SM

第四节
三、工期-资源优化
工 序
a b c d

网络计划优化
4、调整开工时间
总 时 差
0 4 0 3
1
13

第二次调整
5 6 7 8 9 10

相关 结点
①?② ①?③ ②?③ ②?④

作业 最早 时间 开工 时间
3 1 2 3 0 0 3 3

工程进度
2
13

3
13

4

5 8 8 2 2 2

e
f g

③?④
④?⑤ ②?⑤

4
1 5

5
9 3

0
0 2
5

6

6

6

6
12

5

5

5

5

每天所需人数合计
181

13 13 13 13 13 13 13 13 11 12 将非关键作业d延至第6天开工
OR:SM

第五节

缓冲时间设置

具体的思路是:削减每道作业的预估时间,不为单道作业设 置安全缓冲时间,而将节省的时间建立一个任务缓冲(某项任 务的总体安全时间)
182 OR:SM

第五节
4 6

缓冲时间设置
3 5 18

任务1

任务2

任务3

任务4 将每项任务的预 估时间减去一半, 然后将减去时间 的和的一半作为 项目缓冲,共用, 所需时间为原来 的3/4

1
2

2
3

3
1.5

4
2.5

项目缓冲

4.5

13.5

183

OR:SM

第五节

缓冲时间设置

考虑资源冲突,使制约因素(瓶颈资源)不受非制约因 素的影响,在每条衔接路径与关键路线汇合的地方插入衔 接时间缓冲,例如零件的供货缓冲时间
A1 A2 衔接 缓冲

C1

C2

C3

C4

项目缓冲

B1

B2

衔接 缓冲
OR:SM

184

第9 章 决策分析
内容提要 Sub title
第一节 决策分析概论 第二节 不确定性决策 第三节 风险型决策 ? 决策准则 ? 决策树法 ? 情报价值 第四节 贝叶斯决策 第五节 效用决策理论
? 悲观决策准则 ? 乐观决策准则 ? 乐观系数准则 ? 等可能性准则 ? 最小后悔准则

185

OR:SM

第一节 决策分析概论
一、决策要素
对于任何决策应包括以下几个基本决策要素:
?

决策目标 决策如果只有一个目标称为单目标决策,如果决策 行动方案 为了实现预订的目的,可以采取几种不同的行动 自然状态 决策环境可能出现的状态 损益矩阵 决策的结果或者是收益或者是损失 决策准则 比较、选择方案时的判决标准和评价规则 后果评估 通常采用损益或效用作为后果指标。

目标很多并形成目标体系,这类决策称为多目标决策。
? ? ? ? ?

186

OR:SM

第一节 决策分析概论
二、决策程序
方 案 实 施 与 控 制

确 定 决 策 目 标

预 测 自 然 状 态

拟 定 决 策 方 案

决 策 方 案 优 选

确定性决策:自然状态的信息是确知的 风险性决策:已知状态概率分布,但确知 不确定决策:未来状态信息全无
187 OR:SM

第一节 决策分析概论
三、决策分类
1. 按决策方法的性质分类
?定性决策和定量决策

2. 按决策问题的层次分类
?不同管理层级决定不同层次的管理问题, ?分成战略性决策、战术性决策和运作层决策。

3. 按决策出现的频率划分
?程序性决策和非程序性决策

4. 按自然状态的熟知度分
?按对自然状态的认识程度可分为

?确定性决策、风险性决策和不确定性决策。

188

OR:SM

第二节 不确定性决策
?

悲观准则
? 决策者对客观情况持悲观态度,将结果估计得比较保守 ? 基本想法是坏中求好

?

乐观准则
? 决策者总是对客观情况抱乐观的态度 ? 基本思路是好中求好

?

乐观系数准则
? 决策者对客观情况既不那么乐观,也不那么悲观的“折衷准则” ? 根据以往经验,确定乐观系数

?

等可能准则
? 把各种自然状态等同看待,认为各状态发生的概率相等 ? 求出各方案的损益期望,选其中的最优方案

?

后悔值准则
? 决策者制定决策后,若未能符合理想,必将后悔 ? 遗憾当初的选择不当,以“后悔值最小”为决策准则

189

OR:SM

第二节 不确定性决策
自然状态 ?1 需求大 30 ?2 需求小 -6

行动方案
大批量生产

悲观准则

乐观准则

等可能性

-6

30

(30-6)/2=12

中批量生产
小批量生产

20
10

-2
5

-2
5

20
10

(20-2)/2=9
(10+5)/2=7.5

190

OR:SM

第二节 不确定性决策
? 最小后悔准则
自然状态 ?1 需求大 ?2 ?1 需求小 需求大 ?2 需求小 11 7 0 最大后悔

行动方案 大批量生产
中批量生产 小批量生产 目标值

30
20 10 30

-6
-2 5 5

0 10 20

11
10 20

191

OR:SM

第三节 风险性决策
一、决策准则
? 最大可能准则
? 概率最大的状态发生的可能性最大 ? 决策实质上就变成了确定型的决策

? 期望值准则
? 根据益损期望值进行决策,最大期望收益,最小期望损失 ? 适于程序性的重复决策,且决策者可以承受一次决策损失

? 期望值与标准差准则
? 决策者希望尽可能回避风险, ? 标准差刻划各损益值数据与期望值偏离程度 ? 标准差越小则期望值实现的可靠性越大

192

OR:SM

第三节 风险性决策
二、决策树
1. 单级决策树
P(?1 ) ? 0.75

? a11 =30 ? a12 =-6 ? a21 =20

2

P(? 2 ) ? 0.25
P(?1 ) ? 0.75

A1 A2
1

3

P(? 2 ) ? 0.25 ? a =-2 22
P(?1 ) ? 0.75

A3
4

P(? 2 ) ? 0.25

? a31 =10
? a32 =5 结 损 果 益 结 值 点
OR:SM

决 策 结 点
193

方 案 分 枝

状 态 结 点

概 率 分 析

第三节 风险性决策
二、决策树
2. 序列决策树
开发新 产品 存银行 成功0.8 500 -1000 60 成功0.95 开发新 产品 存银行 存银行 8 失败0.05 500 -1000 60

4

失败0.2

2

5

不咨询
1

6 咨询 -10 3 宜开发 0.8 不宜开发 0.2
194

9

7

10

60
OR:SM

第三节 风险性决策
三、情报价值
1. 完全信息的价值
? ? ?

完全信息即对未来状态完全准确的预报信息。 完全信息下,风险型决策就变成了确定性决策。 获得全情报的成本应该小于全情报的价值。 自然状态 开发成功 0.8 开发失败 0.2 决策方案 500 -1000 开发新产品 60 60 用入存银行

2. 测算全信息价值

?

? ? 195

计算未获全信息的最大期望收益值。 ?开发新品的期望值:500?0.8 -1000?0.2=200 ?存入银行的期望值:60?0.8+60 ?0.2=60 计算全信息的期望值:500?0.8+60?0.2=412 二者之差(212)获得这项情报愿意付出代价的最高额
OR:SM

第四节 贝叶斯决策
一、先验概率和后验概率
例:某石油钻探队准备在一远景区勘探石油,根据预测估计 钻井出油的概率为0.3,可以自己钻探或是出租。 ? 自己钻探的费用为1000万元,出油可收入4000万元; ? 如果出租,租金为200万元,若有油租金再增加100万元。 为获更多情报,可以先做地震试验,再行决策。地震试验将 有油区勘测为封闭构造的概率为0.8;将无油区勘测为开放构造 的概率为0.6。地震试验费为300万元。试用决策树法进行决策。 由题意知,有油事件?1的概率P(?1)=0.3,无油事件?2的概率 P(?2)=0.7,这是先验概率; 后验概率则是封闭构造而有油的概率P(?1|I1)=0.8,开放构造而
无油的概率 P(?2|I2)=0.4。

196

OR:SM

第四节 贝叶斯决策
二、贝叶斯概率及其决策
?由联合概率公式知, ?由全概率公式知, ?又由贝叶斯公式知,

P( I k ,? j ) ? P(? j ) ? P( I k ? j )
P( I k ) ? ? P(? j ) ? P( I k ? j )
j

P(? j I k ) ?

P( I k ? j ) ? P (? j ) P( I k )

利用贝叶斯公式可以计算补充信息条件下的后验概率
状态 ? 有油 ?1 无油 ? 2 先验概率
P(? j )

条件概率
P(I1 ? j )

联合概率
P( I1 ,? j )

P(I2 ? j )

P( I 2 ,? j )

后验概率
P(? j I1 ) P(? j I2 )

0.3
0.7

0.8

0.6

0.24

0.06

0.46

0.13

0.2

0.4

0.28

0.42

0.54

0.87

197

OR:SM

第四节 贝叶斯决策
?

二、贝叶斯概率及其决策
P(?1)=0.3 自钻 不做 实验 4 P(?2)=0.7 P(?1)=0.3 出租 5 P(?2)=0.7 △ 3000 △-1000 △ 200 △ 300

? ? ? ? ? ? ? ? ?

2

1 自钻 做实验 封闭 3 开放 6 出租 9 8

结点4 0.3×3000+0.7×(-1000)=200 结点5 0.3×200+0.7×300=270 结点8 0.46×3000+0.54×(-1000)=840 结点9 0.46×200+0.54×300=252 结点10 0.13×3000+0.87×(-1000) =-480 结点11 0.13×200+0.87×300 =287 结点6 决策结点,期望值为840 结点7 决策结点,期望值为287 结点2 决策结点,期望值为270 结点3 840×0.52+287×0.48=574.56
△ 3000
?

P(?1)=0.46 P(?2)=0.54

△-1000
△ 200

结点1 做地震试验期望474.56, 不做地震试验期望270,

P(?1)=0.46
P(?2)=0.54 P(?1)=0.13 自钻 10 P(?2)=0.87 P(?1)=0.13 11 P(?2)=0.87 △ 300

决策结论:先进行地震试验, 如果地震试验是 封闭构造,则自钻 开放构造,则出租

△ 3000
△-1000

7

△ 200 △ 300

198

OR:SM

第五节 效用决策理论
一、效用与效用值
? ? ? ?

效用是主观性的 效用是多属性的 效用会因时而异 效用值是相对的

二、期望效用准则
1. 效用曲线
U(R) U(R) U(R)

风险规避 199

R

风险偏好

R

风险中性

R OR:SM

第五节 效用决策理论
二、期望效用准则
2. 效用决策
例:某公司是一个小型进出口公司,面临着两笔进口生意,项目 A和项目B,这两笔生意都需要现金支付。鉴于公司财务不善,公 司至多做A、B中的一笔生意,根据以往的经验,各自然状态商品 需求量大、中、小的发生概率以及在各自然状况下项目A或项目B 以及不做任何项目的收益都如下表所示(单位:万元)。
进出口生意收益值数据
自然状态 行动方案
A1

q1

需求量大 0.3 60 100 0

q2

需求量中 0.5 40 -40 0

q3 需求量小

0.2 -100 -60 0
OR:SM

(做项目A)

A2 (做项目B) A3(不做任何项目)
200

第五节 效用决策理论
二、期望效用准则
进出口生意效用值数据
自然状态 行动方案
A1

q1

需求量大 0.3
0.95

q2

需求量中 0.5
0.9

q3 需求量小

0.2 0

(做项目A)

A2 (做项目B) A3(不做任何项目)

1
0.75

0.55
0.75

0.4
0.75

计算各方案的效用期望值,如下: EU ( A1 ) =0.3?0.95+0.5?0.9+0.2?0=0.735, EU ( A2 ) =0.3?1+0.5?0.55+0.2?0.4=0.6555, EU ( A3 ) =0.3?0.75+0.5?0.75+0.2?0.75=0.75。 可见方案3的效用期望值为最大
201 OR:SM


网站首页 | 网站地图 | 学霸百科 | 新词新语
All rights reserved Powered by 大学生考试网
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com