期未试卷2 离散优化

诚信应考考出水平考出风格。

浙江大学城市学院。

2008—2009 学年第一学期期末考试试卷。

离散优化》

开课单位：信计分院；考试形式：开卷；考试时间：_2008_年_1_月_5__日；

所需时间： 120 分钟。

一．__问答题___本大题共__2__题，每题__10__分，共_20_分。)

1．怎样的问题是p问题？举出3个p问题的例子，并分别说明它们各有什么算法

2．一个问题是np难的，它的特殊情况下的子问题是否有可能为p问题，请举例加以说明。

二．__问答题___本大题共__2_题，每题__5__分，共__10__分。)

注：须说明理由，未说明理由只给一半分数）

1．叙述层次分析法建模的一般步骤。层次结构图应当包含哪些层次？

2．风险型决策问题的特点是什么，通常是怎样求解的？

三．（本题15分）

对右图中的网络求一个由s到t的最大流，边上的数字是该边的容量。试根据最小切割最大流定理说明为什么你求得的流是最大流。如果想增大流量，网络中哪些边的容量必须增大？

（注：必须有中间步骤，否则将视情况扣分）

四。（本题15分）求右面的最小覆盖： **菜单。

五．（本题10分）写出右面线性规划问题的对偶规划： min

六。（本题10分）证明下面的数学规划为凸规划，即求解凸集上凸函数的极小问题：

min 七。（本题10分）要用40块方形瓷砖铺如图所示形状的地面，但市场上只有长方形瓷砖，每块大小等于方形的两块。一人买了20块长方形的瓷砖，试着铺地面，结果弄来弄去始终铺不好。

问是这人功夫不到家还是这个问题根本就无解？请说明理由。

八。（本题10分）海盗是一帮桀骜不驯的亡命之徒，船上平时一切事都投票解决。船上的唯一惩罚，就是被丢到海里去喂鱼。

若现在船上有10个海盗，要分抢来的 100枚金币。投票的规则如下：先由最凶猛的海盗来提出分配方案，如果有 50%或以上的海盗同意这个方案，那么就以此方案分配；如果少于 50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。

那么海盗将会怎样给出他的方案？

解答此问题的思想如下：如果只剩两名海盗，记他们为p1和p2，其中p2比较凶猛。p2的最佳方案当然是：他自己得100枚金币，p1得0枚。投票时他自己的一票就足够50%了。

现在增加一个更凶猛的海盗 p3。p1知道（p3也知道他知道）如果p3的方案被否决了，游戏就会只由p1和p2来继续，而 p1就一枚金币也得不到。所以 p3知道，只要给p1一点点甜头， p1就会同意他的方案（当然，如果不给 p1一点甜头，反正什么也得不到，p1宁可投票让 p3去喂鱼）。

所以p3的最佳方案是：p1得 1枚，p2什么也得不到，p3得 99枚。依次增加一个更凶猛的海盗……试给出如此解答这个问题所必须的假设条件（至少写出3点）。

并给出 p1,p2,p3再加上更凶猛的海盗 p4，则p4的最佳方案是什么？