运筹学春总复习.docx
《运筹学春总复习.docx》由会员分享，可在线阅读，更多相关《运筹学春总复习.docx（15页珍藏版）》请在冰点文库上搜索。
运筹学春总复习
运筹学期末总复习
第1章线性规划及其对偶问题
●数学建模
建模步骤：
（1）科学选择决策变量
（2）找出所有约束条件
（3）明确目标要求
（4）非负变量的选择
●单纯形法：
【例题1】某旅馆在不同时段所需服务员数如表所示：
每班服务员从开始上班到下班连续工作8小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员？
（列出该问题线性规划模型，不求解）
时间段
最少服务员数
1
06:
00~10:
00
20
2
10:
00~14:
00
30
3
14:
00~18:
00
25
4
18:
00~22:
00
30
5
22:
00~02:
00
10
6
02:
00~06:
00
10
【例题2】用单纯形法求解线性规划问题：
（1）
（2）
【练习1】某厂利用原料A、B生产甲、乙、丙3种产品，已知生产单位产品所需原料数、单件利润及有关数据如表所示，试建立该问题线性规划模型，并用单纯形法求解。
甲
乙
丙
原料拥有量
A
B
6
3
3
4
5
5
45
30
单件利润
4
1
5
【练习2】求解LP
（1）
（2）
第2章整数规划与分配问题
●0-1变量的用法及建模
理解0-1变量的用途，其中
（1）-（4）重点掌握
（1）n中取k：
n中至少取k，改为
n中最多取k，改为
（2）变量取离散数值：
（3）选甲必须选乙，选乙不一定选甲：
或1
（4）选了甲或乙，丙就不能入选，选了丙，甲、乙都不能入选
（5）两个约束条件只需满足一个：
或
式中：
M为任意大正数
（6）n个约束条件中满足k个：
（7）若
，则
；否则
，
，
或
（8）对
可表述为：
【例题1】某公司有5000万元可用于投资，有6个投资方案，其投资额、安排员工数和年利润额如表所示：
方案
投资额（万元）
可安排员工数（人）
年利润额（万元）
1
2000
50
150
2
2000
60
200
3
3500
100
150
4
1000
20
100
5
4000
100
200
6
1500
50
100
要求：
（1）投资额不超过5000万元；
（2）至少安排150人员就业；
（3）年利润额尽可能地多。
试建立该问题0-1规划数学模型（不求解）
【例题2】某企业接受订货，产品需求量为6000公斤，可由3种设备进行生产，其成本与产量如下：
设备
设备调整费（元）
生产成本（元/公斤）
生产能力（公斤）
A
B
C
2000
2500
3000
6
5
4
3000
4000
5000
企业如何组织生产才能使总成本最小？
试列出该问题的整数规划数学模型（不求解）。
【例题3】集合覆盖问题。
某区有城区有10个街道，欲建消防站，有下列6个地点可供选择，在规定时间可到达的地点如下表。
问应设几个，可以以最少数量的消防站可满足消防任务的需要（建模，不求解）。
备选校址代号
覆盖的居民小区编号
A
B
C
D
E
F
1,5,7
1,2,5,8
1,3,5
2,4,5
3,6,8
4,6,8
【例题4】
【练习1】某校排球队准备从以下8名预备队员中选拔4名正式队员，并使平均身高尽可能高。
这8名预备队员情况如下表所示。
预备队员
号码
身高（厘米）
位置
A
B
C
D
E
F
G
H
1
2
3
4
5
6
7
8
197
194
189
196
188
180
183
185
主攻
主攻
副攻
副攻
二传
二传
接应
接应
要求：
（1）8名预备队员选4名；
（2）最多补充1名主攻；
（3）最多补充1名副攻；
（4）至少补充1名二传；
（5）至少补充1名接应；
（6）A和E只能入选1名；
（7）无论B或D入选，A都不能入选。
（建立数学模型，不求解）
●匈牙利法
【例题6】用匈牙利法求解分配问题：
（1）
（2）
【练习2】用匈牙利法求解分配问题：
（1）
（2）
【例题7】某公司准备资金600万元（以100万元为单位），有四项可选择投资的工程A、B、C、D。
现决定每项工程至少要投资100万元。
各项工程投资不同资金后可获得的期望利润如下：
分配的
投资金额
利润
工程A
工程B
工程C
工程D
100
150
167
164
158
200
169
189
190
185
300
185
204
226
215
试确定如何安排对各项工程的投资数，可使获得的总期望利润最大？
第3章运输问题
●数学模型
1.产销平衡运输问题数学模型
2.产销不平衡的运输问题标准化
●表上作业法
【例题1】
（1）由表上作业法求最优解；
（2）单位运价c11在什么范围变动，最优基不变？
【例题2】标准化如下运输问题。
【练习1】求下题最优解，最优解唯一吗？
第4章目标规划
【例题】某公司通过混合牛肉、猪肉、羊肉和水淀粉生产香肠，下表给出数据资料：
该公司需要生产200公斤香肠，并按优先顺序制订下列目标：
【练习】某公司计划生产甲、乙两种产品，它们分别要经过设备A和设备B两道工序的加工，其所需工时定额如下表：
产品
工序
甲
（小时/千克）
乙
（小时/千克）
有效工时
（小时）
设备A
设备B
5
2
3
7
80
72
单位盈利
100元/千克
120元/千克
系统约束：
两种设备已满负荷，不能加班。
目标要求：
P1：
盈利达到150元，并尽可能地超过；
P2：
两种产品的产量之和尽可能超过10千克；
P3：
产品乙不少于6千克。
试建立此问题的数学模型（不求解）
第6章图与网络模型
●基本方法
最小支撑树的避圈法与破圈法。
最短路的dijkstra标号算法。
最大流的Ford-Fulkerson标号算法。
中国邮路问题：
结论1:
若无奇点,则邮递员可以走遍所有街道,做到每条街道只走一次而不重复.
结论2:
（1）有奇点的连线的边最多重复一次;
（2）在该网络图的每个回路上,有重复的边的长度不超过回路总长的一半.
【例题1】用避圈法或破圈法求下图所示最小支撑树。
【例题2】用dijkstra标号算法求上图所示从v1到v12的最短路。
【例题3】求解上图中国邮路问题。
【例题4】求v1到v8最大流。
【练习1】
（1）求下图最小支撑树；
（2）求下图v1到v7最短路；（3）求下图中国邮路问题。
【练习2】求例4中从v1到v8最短路问题。
第8章对策论
矩阵对策最优纯策略：
超优原则或最大最小原则
【练习】求赢得矩阵A的最优纯策略。
第9章决策分析
不确定型决策：
乐观主义准则、悲观主义准则、等概率准则、乐观系数法、最小后悔值准则
【例题】已知面对四种自然状态的三种备选行动方案的公司收益如下表所示。
自然状态
方案
N1
N2
N3
N4
S1
15
8
0
-6
S2
4
14
8
3
S3
1
4
10
12
假定不知道各种自然状态出现的概率请分别用乐观准则、悲观准则、乐观系数准则（取α=0.6）、等概率准则和最小后悔值准则选择最优行动方案：
【练习】根据以往的资料，一家面包店所需要的面包数（即面包当天的需求量）分布如下：
销售量（个）
180
240
300
360
概率
0.2
0.3
0.3
0.2
如果一个面包当天没销售掉，则在当天结束时以0.10元处理给饲养场，新面包的售价为每个1.00元，每个面包的成本为0.50元。
要求：
（1）列出收益矩阵并用期望值法对面包生产量进行决策。
（2）若概率分布未知，试用乐观准则、悲观准则、等概率准则和最小后悔值准则进行决策。
升级会员 