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

一、简答题

1． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?

【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。

先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐

，即可求出目标规划的满意解。 次求解k 个线性规划（k 为优先级的个数）

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

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

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

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

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

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

3． 什么是可行流?

【答案】满足下列条件的网络流f 称为可行流

（l ）容量限制条件:对每一弧（v i ，v j

）

对于起点Vs ，记

对于终点V t ，记 （2）平衡条件 对于中间点，流出量=流入量，即对每个

式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。

4． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。

【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。

（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。

（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。

（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工

工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不

使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，

行流水作业，同时消耗人、机、材等资源也合理。

二、计算题

5． 用线性规划方法求解下列矩阵对策，其中A 为

【答案】（l ）在A 中，第2列优超于第3列，故可划去第3列，得到新的赢得矩阵

可将问题化为如下两个互为对偶的线性规划问题。

，迭代过程如表所示。 利用单纯形方法求解问题（D ）

表

从上表中可得到问题（D ）的解为

由表中最终单纯形表可知，问题（P ）的解为

又因为开始就划去第3列，所以，于是

（2）在A 中，由于第l 列优超于第3列，故可划去第3列，得到新的赢得矩阵

可将问题化为如下两个互为对偶的线性规划问题。