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

一、简答题

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

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;

第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

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

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

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。

2． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。

【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。

（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。

二、计算题

3． 已知LP 问题为

要求:（1）设其对偶变量为y 1, y 2, y 3, y 4，写出其对偶问题; （2）已知原问题最优解【答案】（l ）对偶问题为:

, 试根据对偶性质直接求出对偶问题的最优解。

（2）将原问题的最优解代入原问题的约束条件，得原问题中的第四个约束条件为严格不等式，由互补松弛性得y 4*=0。因为x 1，x 2，x 3≥0，所以对偶问题的前三个约束条件应取等式。

即因此

4． 一个建筑工地现场，如图所示，其中A 、…、G 表示的是需要混凝土的施工点，路径则是允许 运送混凝土的路线，线旁的数字表明相应路径的距离。

图

请在A~G这7个点中，选择一个搅拌混凝土的地方，使得该点到达基他各需要混凝土施工点的总运送距离 之和最短

【答案】首先采用矩阵算法，计算任意两个点的最短距离。 设

为图中相邻两点的距离，得到初始矩阵如下:

经过迭代3次，得到网络图中从的最短距离，可得矩阵D ，如下:

3

因此，可以确定分别从A ，B ，C ，…，G 出发，到达所有点的最短距离和分别为:

故应将混凝土搅拌地选在F 点。

5． 试用SUMT 外点法求解

【答案】原非线性规划问题可改写为:

构造惩罚函数

令

，得

的解为

，为最优解。

6． 案例分析:需要多少个服务人员?

某商科技公司的MIS 中心处理本公司信息系统的维护服务。公司其他部门职员打电话到信息中心进行咨询 和服务请求，不过如果恰巧所有服务人员都在忙的时候，该职员就必须等待。该中心每小时平均接受到40个服 务请求，服务请求的到达服从泊松分布。每个请求的平均服务时间是3分钟，且服从负指数分布。