当前位置：问答库＞考研试题

一、简答题

1． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】Dijkstra 算法的步骤为:

（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。

（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T

，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）

（3）比较所有具有T 标号的点，把最小者改为P 标号，即:

2． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 3． 考虑两个企业的资源整合问题。如果每个单位单独组织生产，各自的效益和，往往小于把两个单位的生 产要素进行重组，然后再统筹生产带来的收益高。因此，资产重组，往往能够带来“双赢”的格局，企业自身也 希望通过合并，做大做强。问题是，每个企业可能会故意夸大其利润水平，从而希冀分得更多的合作收益。请谈谈你的设想，用以协调 其中可能出现的问题（不超过300字，可用符号表述你的想法）?

【答案】让两个企业单独汇报独立生产能获得的利润，分别记为z 1、z 2。如果z 1+z2≦z 成之，则将

，按照z 1、z 2的比例进行分配。这样的分配方式，两个企业说真话，合作后的额外收益z-（z 1+z2）

是一个均衡策略。

4． 简述常用的不确定型决策准则。

【答案】不确定性决策是指决策者对将发生结果的概率一无所知，只能凭决策者的主观倾向进行决策，适用于对 概率判断缺乏信心，对事情做出简单的估计。。不确定性决策由决策者的主观态度不同基本可分为四种准则:悲 观主义准则、乐观主义准则、等可能性准则、最小机会准则。 （l ）悲观主义决策准则:行中取min ，再取max 。

（2）乐观主义决策准则:行中取max ，再取max 。

第 2 页，共 45 页 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

（3）等可能性准则:先求各策略的收益期望值，再从中取max 。

（4）最小机会损失准则:

机会损失矩阵:每一列的值为列中最大的数分别减去其他的数（自己则变为0，其他的值全大于等

，即

于0）

（5）折衷主义决策准则

其中a （

收益值。 然后选择 ）为乐观系数，，。分别表示第i 个策略可能得到的最大收益值与最小。

二、计算题

5． 试用乘子法求解非线性规划问题（取c=2）:

【答案】设

定义拉格朗日函数 于是得到

解得，

6． 国内某电缆公司利用包括5个分销中心、8个客户区域的分销系统来销售其产品。配给每个客户区域一个专门的资源供应商，且其所有电缆产品都来自同一分销中心。为了能平衡分销中心的客户需求和雇员的工作量， 公司负责物流的副总裁特别指明一个分销中心最多负责3个客户区。如下表就是从5个分销中心到8个客户区域的供给成本（单位:1000美元）。求:

（1）使总成本最小的分销中心—客户区域的组合方式;

（2）如果有，哪一分销中心没有任务分派;

（3）若进一步规定每个分销中心最多只能负责2个区域，那么新的分配方案又是什么?

【答案】 （1）由题意知该题为指派问题，添加虚拟的人，用匈牙利解法，具体过程如下：

第 3 页，共 45 页

（2）由上一小题可知，第二2、5、6、7没有任务 （3）

表

7． 对于线性规划问题:max z=CX; AX+IXS =b，X ，Xs>=0; 设A 中存在可行基B ，其对应的基变量和非基变量X B 和X N ，C B 和C N 为它们在目标函数中的系数，试写出对应于基B 的单纯型表。

【答案】对应于基B 的单纯型表如表所示。

表 对应于基B 的单纯型表

8． 对于线性规划问题

第 4 页，共 45 页