管理运筹学复习要点Word下载.docx
《管理运筹学复习要点Word下载.docx》由会员分享，可在线阅读，更多相关《管理运筹学复习要点Word下载.docx（45页珍藏版）》请在冰点文库上搜索。
11
12
13
14
17
70
16
51
40
合计
5280
4410
4291
4080
5310
5191
4980
5072
4861
4650
4953
4742
4531
4320
剩余
220
1090
1209
1420
190
309
520
428
639
850
547
758
969
1180
设按14种方案下料的原材料的根数分别为X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,可列出下面的数学模型：
minf＝X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14
2X1＋X2＋X3＋X4≥80
X2＋3X5＋2X6＋2X7＋X8＋X9＋X10≥420
X3＋X6＋2X8＋X9＋3X11＋X12＋X13≥350
X4＋X7＋X9＋2X10＋X12＋2X13＋3X14≥10
X1，X2，X3，X4，X5，X6，X7，X8，X9，X10，X11，X12，X13，X14≥0
（3）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：
B1
B2
B3
产量/件
A1
200
A2
300
销量/件
150
应如何调运，使得总运输费最小？
此运输问题的线性规划的模型如下
minf=6X11+4X12+6X13+6X21+5X22+5X23
约束条件：
X11+X12+X13=200
X21+X22+X23=300
X11+X21=150
X12+X22=150
X13+X23=200
Xij≥0（i=1,2;
j=1,2,3）
（4）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：
500600
应如何组织运输，使得总运输费为最小？
这是一个产大于销的运输问题，建立一个假想销地B4，得到产销平衡如下表：
B4
100
600600
（5）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运输单价如下表所示：
250
650500
这是一个销大于产的运输问题，建立一个假想销地A3，得到产销平衡如下表：
A3
650650
（6）某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱。
需要供应四个地方的销售，这四地的产品需求分别为400箱、250箱、350箱、200箱。
三个分厂到四个销地的单位运价如下表所示：
甲
乙
丙
丁
1分厂
21
23
25
2分厂
15
30
19
3分厂
20
22
1应如何安排运输方案,使得总运费为最小?
2如果2分厂的产量从400箱提高到了600箱,那么应如何安排运输方案,使得总运费为最小?
3如果销地甲的需求从400箱提高到550箱,而其他情况都同①,那该如何安排运输方案,使得运费为最小?
解:
①此运输问题的线性规划的模型如下
minf=21X11+17X12+23X13+25X14+10X21+15X22+30X23+19X24+23X31+21X32+20X33+22X34
约束条件：
X11+X12+X13+X14=300
X21+X22+X23+X24=400
X31+X32+X33+X34=500
X11+X21+X31=400
X12+X22+X32=250
X13+X23+X33=350
X14+X24+X34=200
Xij≥0（i=1,2,3;
j=1,2,3,4）
②解：
这是一个产大于销的运输问题，建立一个假想销地戊，得到产销平衡如下表：
戊
产量/箱
（400）600
500
销量/箱
400
350
14001400
③解：
这是一个销大于产的运输问题，建立一个假想销地4分厂，得到产销平衡如下表：
4分厂
550
13501350
（7）整数规划的图解法
某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示：
货物
每件体积/立方英尺
每件重量/百千克
每件利润/百元
195
273
托运限制
1365
140
甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？
设X1,X2分别为甲、乙两种货物托运的件数，其数学模型如下所示：
maxz=2X1+3X2
约束条件：
195X1+273X2≤1365，
4X1+40X2≤140，
X1≤4，
X1,X2≥0，
X1,X2为整数。
（8）指派问题
有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示：
问应如何指派工作，才能使总的消耗时间为最少？
A
B
C
D
18
24
26
引入0—1变量Xij，并令
1，当指派第i人去完成第j项工作时；
Xij=
0，当不指派第i人去完成第j项工作时；
此整数规划的数学模型为：
minz=15X11+18X12+21X13+24X14+19X21+23X22+22X23+
18X24+26X31+17X32+16X33+19X34+19X41+21X42+23X43+17X44
X11+X12+X13+X14=1（甲只能干一项工作）
X21+X22+X23+X24=1（乙只能干一项工作）
X31+X32+X33+X34=1（丙只能干一项工作）
X41+X42+X43+X44=1（丁只能干一项工作）
X11+X21+X31+X41=1（A工作只能一个人干）
X12+X22+X32+X42=1（B工作只能一个人干）
X13+X23+X33+X43=1（C工作只能一个人干）
X14+X24+X34+X44=1（D工作只能一个人干）
Xij为0—1变量，（i=1,2,3，4;
（9）有优先权的目标规划的图解法
一位投资商有一笔资金准备购买股票，资金总额为90000元，目前可选的股票有A、B两种（可以同时投资于两种股票），其价格以及年收益率和风险系数
如下表所示：
股票
价格/元
年收益/（元/年）
风险系数
0.5
50
0.2
从表可知：
股票A的收益率为（3/20）×
100%=15%,股票B的收益率为（4/50）×
100%=8%,
A的收益率比B大，但同时A的风险也比B大，这符合高风险高收益的规律。
试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。
X1
设X1、X2分别表示投资商所购买的股票A和股票B的数量。
1.针对优先权最高的目标建立线性规划
4000
建立线性规划模型如下：
20X1+50X2≦90000
3000
mind1+
2000
1000
0.5X1+0.2X2-d1++d1-=700
X2
3X1+4X2-d2++d2-=10000
5000
X1,X2,d1+,d2-≧0
2.针对优先权次高的目标建立线性规划
0.5X1+0.2X2=700
mind2-
20X1+50X2≦90000
d1+=0
X1，X2，d1+，d1-，d2+，d2-≧0
3.目标规划模型的标准化
对于两个不同优先权的目标单独建立线性规划进行求解，为方便，把他们用一个模型来表达：
minP1（d1+）+P2（d2-）
约束条件：
20X1+50X2≦90000，
0.5X1+0.2X2-d1++d1-=700，
3X1+4X2-d2++d2-=10000，
X1，X2，d1+，d1-，d2+，d2-≧0。
（10）某工厂试对产品A、B进行生产，市场需求并不是很稳定，因此对每种产品分别预测了在销售良好和销售较差时的预期利润，这两种产品都经过甲、乙两台设备加工，已知产品A和B分别在甲和乙设备上的单位加工时间，甲、乙设备的可用加工时间以及预期利润如表所示，要求首先是保证在销售较差时，预期利润不少于5千元，其次是要求销售良好时，预期销售利润尽量达到1万元。
试建立目标规划模型。
可用时间
45
销售良好时的预期利润（元/件）
销售较差时的预期利润（元/件）
设工厂生产A产品X1件，生产B产品X2件。
按照生产要求，建立如下目标规划模型:
minP1（d1+）+P2（d2-）
4X1+3X2≦45，
2X1+5X2≦30
5X1+5X2-d1++d1-=50，
8X1+6X2-d2++d2-=100，
X1，X2，di+，di-≧0.i=1,2
（11）动态规划
石油输送管道铺设最优方案的选择问题：
如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;
C1、C2、C3;
D1、D2分别为可供选择的各站站点。
图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？
E
D2
D1
C3
C2
C1
B2
62
3
574
44
4154
5
第四阶段：
D1—E3；
D2—E4；
第三阶段：
C1—D1—E5；
C2—D2—E8；
C3—D1—E8；
C3—D2—E8；
第二阶段：
B1—C1—D1—E11；
B1—C2—D2—E11；
B2—C1—D1—E8；
B3—C1—D1—E9；
B3—C2—D2—E9；
第一阶段：
A—B1—C1—D1—E14；
A—B1—C2—D2—E14；
A—B2—C1—D1—E13；
A—B3—C1—D1—E13；
A—B3—C2—D2—E13；
最优解：
A―B2―C1―D1―E；
A―B3―C1―D1―E；
A―B3―C2―D2―E
最优值：
（12）最小生成树问题
某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，……，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。
请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。
V7
V4
V5
V6
V1
V2
V3
G
G1
①在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边[V1，V6]的权数10为最大，在G中去掉边[V1，V6]得图G1，如上图所示
G2
G3
②在G1中找到一个圈（V3，V4，V5，V7，V3），去掉其中权数最大的边[V4，V5]，
得图G2，如上图所示
③在G2中找到一个圈（V2，V3，V5，V7，V2），去掉其中权数最大的边
[V5，V7]，得图G3，如上图所示
G4
G5
④在G3中找到一个圈（V3，V5，V6，V7，V3），去掉其中权数最大的边
[V5，V6]，得图G4，如上图所示
⑤在G4中找到一个圈（V2，V3，V7，V2），去掉其中权数最大的边
[V3，V7]，得图G5，如上图所示
⑥在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。
这个最小生成树的所有边的总权数为3+3+3+1+2+7=19
（18,3）
（13）某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。
下图给出了配送中心到快餐店的交通图，图中V1，……，V7表示7个地名，其中V1表示配送中心，V7表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间（单位：
分钟）
（27,5）
（25,4）
（24,3）
（4,1）
（16,2）
（0,S）
5V2
6V2
8V2
7V2
2V2
12V2
16V2
18V2
4V2
（快餐店）
（配送中心）
①给起始点V1标号为（0，S）
②I={V1},J={V2，V3，V4，V5，V6,V7}，边的集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}={[V1，V2]，[V1，V3]}，并有
S12=L1+C12=0+4=4；
S13=L1+C13=0+18=18
min（S12,S13）=S12=4
给边[V1，V2]中的未标号的点V2标以（4，1），表示从V1到V2的距离为4，并且在V1到V2的最短路径上V2的前面的点为V1.
③这时I={V1，V2},J={V3，V4，V5，V6,V7}，边的集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}={[V1，V3]，[V2，V3]，[V2，V4]}，并有
S23=L2+C23=4+12=16；
S24=L2+C24=4+16=20；
min（S23,S24,S13）=S23=16
给边[V2，V3]中的未标号的点V3标以（16，2）
④这时I={V1，V2，V3},J={V4，V5，V6,V7}，边的集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}={[V2，V4]，[V3，V4]，[V3，V5]}，并有
S34=L3+C34=16+2=18；
S35=L3+C35=16+6=22；
S24=L2+C24=4+16=20
min（S34,S35,S24）=S34=18
给边[V3，V4]中的未标号的点V4标以（18，3）
⑤这时I={V1，V2，V3，V4},J={V5，V6,V7}，边的集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}={[V4，V6]，[V4，V5]，[V3，V5]}，并有
S46=L4+C46=18+7=25；
S45=L4+C45=18+8=26；
min（S46,S45,S35）=S35=24
给边[V3，V5]中的未标号的点V5标以（24，3）
⑥这时I={V1，V2，V3，V4，V5},J={V6，V7}，边的集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}={[V5，V7]，[V4，V6]}，并有
S57=L5+C57=22+5=27；
min（S57,S46）=S46=25
给边[V4，V6]中的未标号的点V6标以（25，4）
⑦这时I={V1，V2，V3，V4，V5，V6},J={V7}，边的集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}={[V5，V7]，[V6，V7]}，并有
S67=L6+C67=25+6=31；
min（S57,S67）=S57=27
给边[V5，V7]中的未标号的点V7标以（27，5）
⑧此时I={V1，V2，V3，V4，V5，V6，V7},J=空集，边集合{[Vi，Vj]︳Vi，Vj两点中一点属于I,而另一点属于J}=空集，计算结束。
⑨得到最短路。
从V7的标号可知从V1到V7的最短时间为27分钟。
即：
配送路线为：
V1→V2→V3→V5→V7
（14）最小生成树问题
某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图所示，其中V1，……，V8表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度，单位为公里，请设计一个输电网络，联通这8个居民点，并使总的输电线路长度为最短。
V8
G
①在图中找到一个圈（V1，V2，V5，V3）,并知在此圈上边[V1，V2]和
[V3，V5]的权数4为最大，在图中去掉边[V1，V2]；
②在图中找到一个圈（V3，V4，V8，V5，V3,V1），去掉其中权数最大的边
[V4，V8]；
③在图中找到一个圈（V3，V4，V5，V3），去掉其中权数最大的边[V4，V5]；
④在图中找到一个圈（V5，V2，V6，V7，V5），去掉其中权数最大的边
[V2，V6]；
⑤在图中找到一个圈（V5，V7，V8，V5），去掉其中权数最大的边[V5，V8]。
⑥在图中已找不到任何一个圈了，可知此即为图G的最小生成树。
这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18
（15）最大流问题
某地区的公路网如图所示，图中V1，……，V6为地点，边为公路，边上所赋的
权数为该段公路的流量（单位为千辆/小时），请求出V1到V6的最大流量。
第一次迭代：
选择路为V1→V3→V6。
弧（V3，V6）的顺流流量为5，决定了pf=5，改进的网络流量图如图所示：
第一次迭代
后的总流量
→5
5→
第二次迭代：
选择路为V1→V2→V5→V6。
弧（V1，V2）的顺流流量为6，决定了pf=6，改进的网络流量图如图所示：
第二次迭代
11→
→11
12
第三次迭代：
选择路为V1→V4→V6。
弧（V1，V4）的顺流流量为6，
决定了pf=6，改进
升级会员 