运筹学.docx
《运筹学.docx》由会员分享，可在线阅读，更多相关《运筹学.docx（19页珍藏版）》请在冰点文库上搜索。
运筹学
一、简答题：
1．用图解法解线性规划时，可行域（约束集合）与最优解之间的关系。
2．根据线性规划的互补松弛定理，安排生产的产品机会成本与利润之间的关系。
3．最小费用流问题，最短路问题，最大流问题和最小支撑树问题各自适合求解何种问题。
4．对于M/M/1/N/∞排队系统，稳态时顾客平均到达率为
，服务机构的平均服务率为
，系统的状态概率为Pi（i=0,1,…，N），与系统的有效到达率之间的关系。
5．风险性决策问题，各个收益准则的求解方法和特点及其应用对象。
6．基于蒙特卡罗法的系统模拟技术适用于对何种系统进行模拟，为什么。
7.运算问题表上作业发求解步骤和判断准则。
8.线性规划模型中，若某一变量的目标函数系数发生变化时，可行域，最优基和目标函数值的关系。
9.对待决策风险的态度有哪些？
回答某理财方案收益为x的效用为u（x），若u（x）对x边际递减，该方案对风险的态度是什么？
10.请简述影子价格的定义。
11．在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？
12.写出影子价格的数学表达式并用其定义加以验证
13.试述运输问题中检验数的经济意义
14.何谓对偶规划，其与线性规划的关系，及其对应的数学模型。
二、应用题
1）考虑下面两个线性规划：
？
2）考虑线性规划问题
（P）
若X1,X2均为（P）的可行解，
，问：
是否是（P）的可行解？
3）某厂计划用5000万资金，购买生产同一种产品的四种型号的设备A、B、C、D，这四种型号的设备设计生产能力和价格如下表所示。
每种型号的设备应购买过少台，使总生产能力最大。
设备型号
A
B
C
D
设计生产能力Ki（吨/台）
250
280
300
320
价格Pi（万元/台）
700
750
800
850
建立该问题的动态规划模型：
列出阶段变量、状态变量、决策变量、状态转移方程、阶段指标、递推方程（不解）。
4）某工程由5道施工工序构成，其有关资料如表2所示。
1．画出工程网络图；
2．求出工程完工期及关键工序；
3．现若要求工程在正常工期基础上再提前3天完成，求使应急费用最少的应急压缩方案。
表2
工序
紧前工序
正常完成时间（天）
应急时间（天）
正常费用（元）
应急费用（元）
A
----
30
20
6000
7200
B
----
60
25
2000
2000
C
A
15
10
3000
3000
D
B、C
15
8
4000
7000
E
D
10
4
3000
4200
5）某成衣厂对一种布料的需求为每年20000件，不需要提前订货，每次订货费为25元。
该成衣每件成本为50元，年存贮费为成本的20%。
如发生供应短缺，可在下批货到时补上，但缺货损失为每件每年30元。
（1）分别求允许缺货和不允许缺货时的经济订货批量；
（2）允许缺货和不允许缺货两种情形中的哪一种相应的全年总费用更低？
6）某厂使用A、B、C三种原料生产甲、乙、丙三种产品，有关数据见下表：
ABC
生产成本（万元/吨）
销售价格（万元/吨）
甲
乙
丙
1.00.50.2
0.40.60.3
0.60.50.4
9
4
18
30
20
35
原料成本（万元/吨）
5710
原料可用数量（吨）
350460400
请写出使总销售利润最大的线性规划模型
（2）写出此问题的对偶规划模型
计算题
1.已知线性规划
MaxZ=3X1+4X2
X1+X2≤5
2X1+4X2≤12
3X1+2X2≤8
X1,X2≥0
其最优解为：
基变量
X1
X2
X3
X4
X5
X3
3/2
0
0
1
-1/8
-1/4
X2
5/2
0
1
0
3/8
-1/4
X1
1
1
0
0
-1/4
1/2
σj
0
0
0
-3/4
-1/2
1）写出该线性规划的对偶问题。
2）若C2从4变成5，最优解是否会发生改变，为什么？
3）若b2的量从12上升到15，最优解是否会发生变化，为什么？
4）如果增加一种产品X6，其P6=（2,3,1）T，C6=4该产品是否应该投产？
为什么？
解：
1）对偶问题为
Minw=5y1+12y2+8y3
y1+2y2+3y3≥3
y1+4y2+2y3≥4
y1,y2≥0
2）当C2从4变成5时，
σ4=-9/8
σ5=-1/4
由于非基变量的检验数仍然都是小于0的，所以最优解不变。
3）当若b2的量从12上升到15
X＝9/8
29/8
1/4
由于基变量的值仍然都是大于0的，所以最优解的基变量不会发生变化。
4）如果增加一种新的产品，则
P6’=（11/8,7/8，－1/4）T
σ6=3/8>0
所以对最优解有影响,该种产品应该生产
2、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。
销地
产地
B1
B2
B3
产量
A1
5
9
2
15
A2
3
1
7
11
A3
6
2
8
20
销量
18
12
16
解：
初始解为
B1
B2
B3
产量/t
A1
15
15
A2
11
11
A3
18
1
1
20
销量/t
18
12
16
计算检验数
B1
B2
B3
产量/t
A1
5
13
0
15
A2
－2
0
0
11
A3
0
0
0
20
销量/t
18
12
16
由于存在非基变量的检验数小于0，所以不是最优解，需调整
调整为：
B1
B2
B3
产量/t
A1
15
15
A2
11
11
A3
7
12
1
20
销量/t
18
12
16
重新计算检验数
B1
B2
B3
产量/t
A1
5
13
0
15
A2
0
2
2
11
A3
0
0
0
20
销量/t
18
12
16
所有的检验数都大于等于0，所以得到最优解
3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？
各承包商对工程的报价如表2所示：
项目
投标者
A
B
C
D
甲
15
18
21
24
乙
19
23
22
18
丙
26
17
16
19
丁
19
21
23
17
答最优解为：
X=0100
1000
0010
0001
总费用为50
4.考虑如下线性规划问题
Maxz=-5x1+5x2+13x3
s.t.-x1+x2+3x3≤20
12x1+4x2+10x3≤90
x1，x2，x3≥0
回答以下问题：
1）求最优解
2）求对偶问题的最优解
3）当b1由20变为45，最优解是否发生变化。
4）求新解增加一个变量x6，c6=10，a16=3，a26=5，对最优解是否有影响
5）c2有5变为6，是否影响最优解。
答：
最优解为
1）
Cj
-5
5
13
0
0
θ
CB
XB
b
X1
X2
X3
X4
X5
0
X4
20
-1
1
3
1
0
20/3
0
X5
90
12
4
10
0
1
9
Cj-Zj
-5
5
13
0
0
13
X3
20/3
-1/3
1/3
1
1/3
0
20
0
X5
70/3
46/3
22/3
0
-10/3
1
70/22
Cj-Zj
-2/3
2/3
0
-13/3
0
13
X3
185/33
-34/33
0
1
2/11
-1/22
5
X2
35/11
23/11
1
0
-5/11
3/22
-68/33
0
0
-1/11
-1/11
最优解为X1=185/33,X3=35/11
2）对偶问题最优解为
Y＝（1/22,1/11,68/33,0,0）T
3）
当b1=45时
X=45/11
-11/90
由于X2的值小于0，所以最优解将发生变化
4）P6’=（3/11,-3/4）T
σ6=217/20>0
所以对最优解有影响。
5）当C2=6
σ1=-137/33
σ4=4/11
σ5=-17/22
由于σ4大于0所以对最优解有影响
5.求如图所示的网络的最大流和最小截集（割集），每弧旁的数字是（cij,fij）。
V1
（5,0）（3,3）
（3,3）
VS（4,1）V2
（4,0）
（9,3）（8,4）
V3
Vt
（6,0）
最大流为：
14
V1
（5,3）（3,3）
（3,0）
V2
Vs（4,4）
（4,1）
（9,7）（8,8）
Vt
V3（6,6）
6.考虑如下线性规划问题
Maxz=3x1+x2+4x3
s.t.6x1+3x2+5x3≤9
3x1+4x2+5x3≤8
x1，x2，x3≥0
回答以下问题：
1）求最优解；
2）直接写出上述问题的对偶问题及其最优解；
3）若问题中x2列的系数变为（3，2）T，问最优解是否有变化；
4）c2由1变为2，是否影响最优解，如有影响，将新的解求出。
Cj
3
1
4
0
0
CB
XB
b
X1
X2
X3
X4
X5
0
X4
9
6
3
5
1
0
0
X5
8
3
4
5
0
1
Cj-Zj
3
1
4
0
0
0
X4
1
3
-1
0
1
-1
4
X3
8/5
3/5
4/5
1
0
1/5
Cj-Zj
3/5
-11/5
0
0
-4/5
3
X1
1/3
1
-1/3
0
1/3
-1/3
4
X3
7/5
0
1
1
-1/5
2/5
Cj-Zj
0
-2
0
-1/5
-3/5
最优解为X1=1/3,X3=7/5,Z=33/5
2）对偶问题为
Minw=9y1+8y2
6y1+3y2≥3
3y1+4y2≥1
5y1+5y2≥4
y1,y2≥0
对偶问题最优解为y1=1/5,y2=3/5
3）若问题中x2列的系数变为（3，2）T
则P2’=（1/3,1/5）T
σ2=-4/5＜0
所以对最优解没有影响
4）c2由1变为2
σ2=-1＜0
所以对最优解没有影响
7.求如图所示的网络的最大流和最小截集（割集），每弧旁的数字是（cij,fij）。
V1（4,4）V3
（9,5）（6,3）
VS（3,1）（3,0）（4,1）Vt
（5,3）（7,5）
V2（5,4）V4
解：
V1（4,4）V3
（9,7）（6,4）
（3,2）（4,0）
VsVt
（5,4）（7,7）
V2（5,5）V4
最大流＝11
8.某厂Ⅰ、Ⅱ、Ⅲ三种产品分别经过A、B、C三种设备加工。
已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表：
ⅠⅡⅢ
设备能力（台.h）
A
B
C
111
1045
226
100
600
300
单位产品利润（元）
1064
1）建立线性规划模型，求获利最大的产品生产计划。
2）产品Ⅲ每件的利润到多大时才值得安排生产？
如产品Ⅲ每件利润增加到50/6元，求最优计划的变化。
3）产品Ⅰ的利润在多大范围内变化时，原最优计划保持不变。
4）设备A的能力在什么范围内变化时，最优基变量不变。
5）如有一种新产品，加工一件需设备A、B、C的台时各为1、4、3h，预期每件为8元，是否值得生产。
6）如合同规定该厂至少生产10件产品Ⅲ，试确定最优计划的变化。
解：
1）建立线性规划模型为：
MaxZ=10x1+6x2+4x3
x1+x2+x3≤100
10x1+4x2+5x3≤600
2x1+2x2+6x3≤300
xj≥0,j=1,2,3
获利最大的产品生产计划为：
X*=（x1,x2,x3,x4,x5,x6）’=（100/3,200/3,0,0,0,100）’Z*=2200/3
2）产品Ⅲ每件利润到20/3才值得生产。
如果产品Ⅲ每件利润增加到50/6元，最优计划的变化为：
X*=（x1,x2,x3,x4,x5,x6）’=（175/6,275/6,25,0,0,0）’Z*=775
3）产品Ⅰ的利润在[6,15]变化时，原最优计划保持不变。
4）设备A的能力在[60,150]变化时，最优基变量不变。
5）新产品值得生产。
6）最优计划的变化为：
X*=（x1,x2,x3,x4,x5,x6）’=（190/6,350/6,10,0,0,60）’Z*=706.7
9.给出成性规划问题：
Minz=2x1+3x2+6x3
x1+2x2+x3≥2
-2x1+x2+3x3≤-3
xj≥0j=1,…，4
要求：
（1）写出其对偶问题。
（2）利用图解法求解对偶问题。
（3）利用
（2）的结果，根据对偶问题性质写出原问题最优解。
解：
1）该问题的LD为：
MaxW=2y1-3y2
y1-2y2≤2
2y1+y2≤3
y1+3y2≤6
y1≥0,y2≤0
2）用图解法求得LD的最优解为：
Y*=（y1,y2）’=（8/5,-1/5）’W*=19/5
3）由互补松弛定理：
原问题的最优解为：
X*=（x1,x2,x3）’=（8/5,1/5,0）’
10.
某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量，各销售点的销售量（单位.t）以及各工厂到各销售点的单位运价（元/t）示于下表中，要求研究产品如何调运才能使总运量最小？
B1
B2
B3
B4
产量
A1
4
12
4
11
32
A2
2
10
3
9
20
A3
8
5
11
6
44
销量
16
28
28
24
96╲96
解：
最优调运方案为：
A1-B3和B428t和4t
A2-B1和B416t和4t
A3-B2和B428t和16t
最小总运费为：
460元
11.求解下列0-1规划问题
maxz=3x1+2x2-5x3-2x4+3x5
x1+x2+x3+2x4+x5≤4
7x1+3x3-4x4+3x5≤8
11x1-6x2+3x4-3x5≥3
xj=0或1（j=1,…，5）
解：
最优解为：
x1=x2=1，其他为0，最优目标函数值为5
升级会员 