运筹学试题及答案分享

运筹学试卷A》参考答案

一、对线性规划问题

在第1个约束中引入人工变量,第2个约束中引入松弛变量,采用大M法利用单纯形表求解得到了最优解,单纯形表完整的迭代过程见下表:

4 5 0
1 [2] 1 1 0
0 18 3 2 0 1
0 0
4 5 0
5 [1/2] 1 1/2 1/2 0
0 3 0 1/2 -3/2 1
3/2 0 0
4 5 0
4 1 2 1 1 0
0 8 0 1 3/2 -1 1
0 -3 -2 0

 

(1)试根据上述求解过程单纯形表,确定参数,和的值,以及该问题的最优解;

(2)以上述线性规划问题为原问题,写出其对偶问题;

(3)利用对偶性质,求出对偶问题的最优解。(本题共25分,第1小题15分,第2、3小题各5分)

解:

(1)由最终单纯形表的判别数,得到;

由中间单纯形表右端项的初等行变换规则:,得到;

由中间单纯形表到最终单纯形表的变换规则:,得到;

该问题的最优解:,,

(2)对偶问题:

(3)依据互补松弛定理。在最优解处,原问题第2个约束为严格不等式,故。

由于,故对偶问题第1个约束为等式,,得到。

故对偶问题的最优解为,。

二、用分支定界法求解如下整数规划问题

LP

先解其松弛问题LP,得最优解,,不满足整数要求。显然,为问题IP的一个可行解。

(1)依据以上信息,给出问题IP最优目标函数值的初始上下界;

(2)写出针对的分支子问题;

(3)基于上述分支子问题,完成问题IP的求解(提示:可用图解法),给出最优解并更新最优目标函数值的上下界。(本题共10分,第1小题2分,第2小题3分,第3小题5分)

解:

(1)将松弛问题最优解代入目标函数,;

,为IP的一个可行解,对应的;

故最优目标函数值:

(2)分支子问题

 

(3)用图解法(略)求得:

松弛问题最优解,恰好满足整数要求,不必再探测,对应目标值;更新最优目标函数值上下界:

松弛问题最优解,不满足整数要求。

对应目标值,不大于已知的的下界,故不可能找到更好的解,不必再探测。

所有子问题探测完毕,得到最优解:

三、已知约束非线性优化问题

(1)判断该问题是否为凸规划;

(2)写出该问题的Kuhn-Tucker条件;

(3)利用Kuhn-Tucker条件,求出该问题的K-T点和最优解。(本题共15分,每小题5分)

解:

(1)易证不等式约束函数为凹函数,满足的点的集合不是凸集,故该问题不是凸规划。

(2)重写原问题,以便套用K-T条件:

K-T条件:

(梯度条件)

(互补松弛条件)

(不等式约束乘子非负条件)

(可行性条件,可不写)

(3)讨论:

Þ  和

根据梯度条件可求出配套的Lagrange乘子: 和

这两个点均为K-T点。

Þ

检查可行性:=,不满足不等式约束,故不可能是K-T点。

因此,该问题有两个K-T点: 和 。

它们具有相同的目标函数值,故都是该问题最优解,最优目标值为5。

四、已知A点到E点单行线交通网络如下图所示,箭线旁的数字表示该线路的距离。

 

(1)用动态规划的逆推解法求出从A点到E点的最短路,要求列出计算过程。

(2)用图论中求最短路的Dijkstra算法求A点到E点的最短路,在算法执行过程中得到如下结果(P代表永久标号,T代表临时标号,l代表回溯指针):

 

指出下一步迭代应将哪个点的临时标号T修改为永久标号P,列出算法终止时各点的标号值及指针(l)值(不要求列出计算过程)。(本题共20分,每小题10分)

解:

(1)分3个阶段,最优指标值为各点到E点的最短距离。

初始状态,状态转移方程

当时:

当时:

当时:

故A到E的最短距离为10,最短路为:。

(2)下一步迭代应将点的临时标号T修改为永久标号P。

算法终止时各点的标号值及指针(l)值如下:

;,,;,,;

;,,;,,;

五、某杂货店设置了一个小型停车场,有3个车位。杂货店不营业时停车场关闭。在营业时间,当停车场未满时,车辆可进入停车场使用停车位,平均每小时有两个停车位被占用;若停车场已满,则到达的车辆会离开且不再回来。据统计,0,1,2,3个停车位被占用的概率分别为:

,,,

(1)将停车场看作一个排队系统,说明该排队系统中顾客是什么?服务台又是什么?有多少个服务台?系统容量有多大?

(2)确定该系统的基本性能指标:期望队长,期望排队长,顾客平均等待时间,顾客平均逗留时间。

(3)该杂货店对驾车购物顾客的损失率是多少?(本题共10分,第1小题2分,第2小题6分,第3小题2分)

解:

(1)该排队系统中顾客是车辆,服务台是停车位,有3个服务台,系统容量为3。

(2)期望队长

期望排队长=0

顾客等待时间

顾客平均逗留时间(小时)

(3)该杂货店对驾车购物顾客的损失率就是停车场满员的概率0.2。

六、设矩阵对策中,局中人I策略集为,局中人II策略集为,局中人I的赢得矩阵。

(1)用图解法求解该矩阵对策,给出局中人II的最优策略及矩阵对策的值;

(2)根据(1)的结果,确定局中人I的最优策略。(本题共10分,每小题5分)

解:

(1)令局中人II的混合策略为,图解法(略)得到。

局中人II的最优策略为,对策的值。

(2)设局中人I的混合策略为当局中人I采取策略,期望赢得为(严格不等式),故=0。(或由图直接得出此结论亦可)

由于局中人II的最优策略,,故有,在加上概率归一条件,解得

故局中人I的最优策略为(通过其它思路求出亦可)

七、已知决策收益表如下:

状态 状态1 状态2 状态3
概率 0.3 0.5 0.2
方案1 20 12 8
方案2 16 a b
方案3 12 12 12

为两个待定参数,,。已知此问题的完全情报价值为1.6,拥有完全情报时的期望收益为16.4。若按最大期望收益准则决策,其结果为选择方案2。试求ab之值。(本题共10分)

解:

如果拥有完全情报,则对应状态1、状态2、状态3时,所获得的收益分别为:

max(20,16,12)=20,max(12,a,12)=a,max(8, b,12)=max(b,12)。

则完全情报下的期望收益为:EVWPI=0.3×20+0.5×a+0.2×max(b,12)

只拥有原始情报时,方案2为最优方案,则期望收益为:

EVWOI=0.3×16+0.5a+0.2b

完全情报价值EVPI=1.6,拥有完全情报时的期望收益EVWPI=16.4,因此:

EVWPI=0.3×20+0.5×a+0.2×max(b,12)=16.4

EVPI=EVWPI- EVWOI=16.4-(0.3×16+0.5a+0.2b)=1.6

上述两式化简为:

0.5a+0.2×max(b,12)=10.4

0.5a+0.2b=10

分情况讨论:

(1)b>12,则有:0.5a+0.2b=10.4 且 0.5a+0.2b=10,不可能成立,舍去。

(2)b≤12,则有:0.5a +0.2×12=10.4 且 0.5a+0.2b=10,得到a=16and b=10。

综上,a=16,b=10。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: