天大历年试题分类

一、线性规划 二、运输问题 三、多目标规划 四、动态规划 五、图论

六、网络计划技术 七、决策论 八、存储论 九、排队论 十、对策论 十一、模拟技术

一、线性规划

（一）选择填空题 （二）线性规划建模 （三）互补松弛应用 （四）灵敏度分析 （五）证明题

（一）选择填空题

1．下面给出某线性规划问题的单纯形初表和终表（Min型）： CB XB B-1b 0 x1 7 0 x4 12 0 x6 10 σ CB XB B-1b x2 x6 σj j 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x6 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 x1 x2 x3 x4 x5 x6 2/5 0 1/10 0 1/5 1 3/10 0 1 0 -1/2 1

(1)初表的出基变量为 ，进基变量为 。

(2)最优基逆B*?1???

(3)填完终表。

(4)最优解X*?

(5)对偶问题最优解y*?

(6)若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变小） 。（2007）

解：1．(1)出基变量为x4；进基变量为x3。

?2?5?1*?1 (2)B???5??1??(3) CB XB B-1b 1?0?10?30?。 ?10?1?1??2?x1 x2 x3 x4 x5 x6 1 x2 4 2/5 1 0 1/10 4/5 0 -3 x3 5 1/5 0 1 3/10 2/5 0 0 x6 11 1 0 0 -1/2 10 1 σj 1/5 0 0 4/5 12/5 0

(4) X*?(4(5) Y?((6) 变小

*511)T

450)

151．用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。

A．可行域（约束集合）有界，无有限最优解（或称无解界） B．可行域（约束集合）无界，有唯一最优解

C．可行域（约束集合）是空集，无可行解

D．可行域（约束集合）有界，有多重最优解 （2006）

解：1． A

2．根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润。 A． 小于 B． 等于 C． 大于 D． 大于等于 （2006）

解：2． B

1．用大M法求解Max型线形规划时，人工变量在目标函数中的系数均为____________，若最优解的_______________中含有人工变量，则原问题无解。（2005）

解：1、-M 基变量

*1. 设线性规划问题maxcxAx?bx?0有最优解x和影子价格y,则线性规划问题

??*max?2cxAx?bx?0?的最优解= ，影子价格= 。

（2004）

解：1. x* 2y*

3. 某工程公司拟从1、2、3、4四个项目中选择若干项目。若令

?1，第i个项目被选中xi??，i?1，??4

?0，第i个项目未选中请用xi的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中： （2）只有项目1被选中，项目3才能被选中： 。（2004）

解：3. x2?x4?1,x1?x3?0

一、简答（18%）

（1）请简述影子价格的定义。

（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？ （3）写出影子价格的数学表达式并用其定义加以验证 （4）试述运输问题中检验数的经济意义（2003）

解：一、简答

⑴当各资源增加一单位时引起的总收入的增量，影子价格大于零的资源一定没有剩余，有剩余一定为零。

⑵松弛变量检验数的负值，对偶问题的最优解。 ⑶CBB-1

B是原问题{maxz=CX∣AX≤b,X≥0}最优基 **Z= CBB-1b=Yb ****

Z=y1b1+y2b2?ymbm

?z*=y3* ?b⑷表明增加一个单位的运量会引起总运输费用的变化

1． 线性规划原问题中约束的个数与其对偶问题中的 变量 个数相等。若原问题第j个约束

为等式，则对偶问题第j个 变量 自由。（2002） 解：

2． 设线性规划问题max:{cx|Ax≤bx≥0}有最优解，且最优解值z>0；如果c和b分别被v>1

所乘，则改变后的问题 也有 （也有、不一定有）最优解；若有最优解，其最优解 大于 (大于、小于、等于)z。（2002）

1．下列数学模型中 a 是线性规划模型。(2001)

(a)maxZ?4x1?2x2?3x3

?7x1?3x2?6x3?150?s.t.?4x1?4x2?5x3?120 ?x,x,x?0?123 解：

?7x?6x2?8x35x1?9x2?2x3?(b)maxZ?min?1?

43???5x1?5x2?3x3?300?s.t.?6x1?9x2?8x3?500 ?x,x,x?0?123

2．下列图形（阴影部分）中 b 是凸集。(2001)

（a） （b） （c） 解：

3．标准形式的线性规划问题，其可行解 b 是基本可行解，最优解 a 是可行解，最优解 a 能在可行域的某顶点达到。(2001)

（a）一定 （b）不一定 （c）一定不 解：

4．目标函数取极小（min Z）的线性规划问题可以转化为目标函数取极大 b 的线性规划问题求解，原问题的目标函数值等于 c 。(2001)

（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z （a）最小元素法 （b）比回路法 1. 线性规划单纯形算法的基本步骤是：（1） （2） (3) 每次迭代保持解的 ，改善解值的 。对偶单纯形法每次迭代保持解的 ，改善解值的 。（2000）

解：确定一个初始基可行解；检验一个基可行解是否为最优解；寻找一个更好基可行解；可行性；最优性。

2. 设有线性规划问题?min?f?CX,X?R??X|AX?b,X?0?，有一可行基B（为A中的前m列），记相应基变量为X?，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X= ；用非基变量来表示基变量的表达式为XB= ；用非基变量表示目标函数的表达式为f= ，B为最优基的条件是 。（2000）

?B?1b??1?1?1?1?1解：??,Bb?BNXN,CBBb?(CN?CBBN)XN,CN?CBBN?0

?0?

3. 线性规划（Min型）问题有多重最优解时，其最优单纯形表上的特征为： （2000）

解：所有检验数?j?0,而某一个非基变量xk检验数?j?0. 6. 某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。令

?1第i号上场 xi??1，2，3，4，5?0第i号不上场，i＝请用xi的线性表达式表示下列要求：（1）从1，2，3中至多选2名： （2）如果

2号和3号都上场，则5号不上场： （3）只有4号上场,1号才上场：(2000) 解：x1?x2?x3?2,x4?x5?0,x1?x4?1.

1．某工程公司拟从四个项目中选择若干项目，若令

?1,第i个项目被选中xi??i?1,2,3,4.

?0,第i个项目末被选中请用xi的线性表达式表示下列要求：

（1）从1，2，3项目中至少选择一个： ，

（2）只有项目2被选中，项目4才能被选中 。（1999）

解：1、x1+x2+x3≥1

x2≥x4

2．考虑线形规划问题

maxZ?5x1?12x2?4x3?x1?2x2?x3?5?s..t?2x1?x2?3x3?2?x,x,x?0?123

用单纯型法求解，得其终表如下： Cj 5 12 4 0 -M CB XB B-1b x1 x2 x3 x4 x5 12 x2 8/5 0 1 -1/5 2/5 -1/5 5 x1 9/5 1 0 7/5 1/5 2/5 2?j 0 0 -3/5 -29/5 -M+ 5其中x4位松弛变量，x5为人工变量。 （1）上述模型的对偶模型为 ， （2）对偶模型的最优解为 ，

（3）当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ，

?（4）最优基的逆矩阵B?1????? ?（5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？（1999）

解：2．（1）

本文来源：https://www.bwwdw.com/article/kivv.html