运筹学线性规划习题.doc

一、需要掌握的主要内容
1、单纯形法的计算过程
（1）确定初始基本可行解
（2）最优性检验；
（3）基变换。
2、单纯形法的灵敏度分析
（1）最终单纯形表中，变量系数的灵敏度分析 针对最优解不变时，判断其变化范围；
（2）约束条件常数项b的灵敏度分析 针对最优解不变时，判断其变化范围；
（3）增加一个变量的灵敏度分析
首先，确定增加变量在初始单纯形表中的系数列Pj；然后，求出其对应在最终单纯形表中的系数列Pj ；最后求出σj=Cj-CBB-1Pj。
若σj ≤0，则最优解不变；σj ≥0，则继续进行基变换，直到求出最优解。
二、需要基本掌握的内容
1、解、基本解、可行解、基本可行解等基本概念；
2、利用单纯形法求解如何判断无可行解、无界解和无穷最优解等基本理论；
3、如何写出一个线性规划的对偶问题；
4、对偶单纯形法的基本思路和过程。
一、填空题
（1）线性规划模型中，松弛变量的经济意义是 ，它在目标函数中的系数是 。
（2）设有线性规划问题：max z=CX
AX≤b
X≥0
有一可行基B，记相应基变量为XB,非基变量为XN，则可行解的定义为 ，基本可行解的定义为 ，B为最优基的条件是 。
（3）线性规划模型具有可行域，若其有最优解，必能在 上获得。
二、选择题
1．线性规划一般模型中，自由变量可以用两个非负变量的 （ ）代换。
A．和 B．差 C．积 D．商
2．满足线性规划问题全部约束条件的解称为 （ ）
A．最优解 B．基本解 C．可行解 D．多重解
3．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得 （ ）
A．多重解 B．无解 C．无界解 D．退化解
4．原问题与对偶问题的（ ）相同。
A．最优解 B．最优目标值 C.解结构 D．解的分量个数
5.记线性规划原问题（p）max z=CX， 对偶问题（D） min w=Yb
AX≤b YA≥C
X≥0 Y≥0
现用单纯形表解（P）求得最优解，则在最优单纯形表中，同时也可得到（D）的最优解，它应等于：
（a）表中松弛变量的检验数 （b）表中松弛变量的检验数的负值
（c）表中非基变量的检验数 （d）表中非基变量的检验数的负值
6. 线形规划问题
max
z
=
3x1
+
2x2

S.t

x1
+
x2
≤
4
（1）

-x1
+
2x2
≥
2
（2）

2x1
+
3x2
≥
6
（3）

x1
，
x2
≥
0

的约束条件（1），（2），（3）相应的松弛变量分别为x3、x4、x5，相应的约束直线如图所示，选择一个或多个正确答案填在相应的括号内。
C
F
D
E
x2
4
3
2
1
-2 -1 0 1 2 3 4
x1
B

A
O
G H

1）以上线形规划的可行域是（ ）。
①ADO ②ODEG ③CDE ④BCEF ⑤EFGH ⑥GHI
2）图中（ ）是基本解，（ ）是基本可行解，（ ）是最优解。
①A ②B ③C ④D ⑤E ⑥F ⑦G ⑧H ⑨I ⑩G
3）图中A点对应的基变量是（ ），非基变量是（ ）；
图中E点对应的基变量是（ ），非基变量是（ ）。
①x1 ②x2 ③x3 ④x4 ⑤x5
4）图中满足{x1，x2，x3，x4 ≥0，x5 ≤0}的区域是（ ）；
满足{x1，x2，x3≥0，x4，x5≥0}的区域是（ ）。
①ADO ②ODEG ③CDE ④BCEF ⑤EFGH ⑥GHI
5）从点O到点G的单纯型变换中，入基变量是（ ），出基变量是 （ ）；
从E点到F的单纯型变换中，入基变量是（ ），出基变量是 （ ）。
①x1 ②x2 ③x3 ④x4 ⑤x5
6）在G点对应的松弛变量中，大于、等于、小于0的分别是（ ）、（ ）、（ ）。
①x3 ②x4 ③x5
三、判断下列问题的对或错，并适当说说你的理由
（1）图解法与单纯形法虽然求解形式不同，但从几何意义上理解，两者是一致的。（ ）
（2）线性规划问题的每一个基本解都对应着可行域中的一个角点。（ ）
（3）增加一个新的约束，如果原问题的最优解满足新的约束条件，则最优解仍然是最优解。（ ）
（4）对于一个线性规划问题，如果它有可行解，则必有基本解。（ ）
（5）当所有的检验数都为非正数时，表明已经取得了线性规划的最优解。
（6）对于一般形式的线性规划问题，如果要把其中的小于等于约束方程变成等号，需要引进或添加基变量。（ ）
（7）若某种资源的对偶解等于零，则表明应该买入这种资料。（ ）
（8）在一个线性规划问题中，非基变量的检验数总是为正数。（ ）
（9）经过初等变换后的某个线性规划问题的约束系数矩阵为：

则基变量为X2和X4。
（10）若某种资源的对偶价格等于,在其他条件不变的情况下,当该种资源增加5时，相应的目标函数值将增大5。( )
四、写出下列线性规划问题的对偶问题

五、某一最大化线性规划问题最终单纯形表如下所示：
基
变
量
CB
X1
X2
X3
X4
X5
b
2
1
0
0
0
X3
0
0
0
1
5/4
-15/2
15/2
X1
2
1
0
0
1/4
-1/2
7/2
X2
1
0
1
0
-1/4
3/2
3/2
Cj－Zj
0
0
0
-1/4
-1/2

原问题约束条件为5X2≤15， 6X1+2X2≤24， X1+X2≤5，X1，X2≥0
请根据表中数据回答下列问题：
（1）变量X2的系数在什么范围内变化，此问题最优解不变？
（2）约束条件3的常数项b在什么范围内变化时，其对偶价格不改变？
六、某一最大化线性规划问题最终单纯形表如下所示：

基
变
量
CB
X1
X2
X3
X4
X5
b
70
120
0
0
0
X3
0
0
0
1
-3.12
1.16
84
X1
70
1
0
0
0.4
-0.2
20
X2
120
0
1
0
-0.12
0.16
24
Zj
70
120
0
13.6
5.2

Cj－Zj
0
0
0
-13.6
-5.2

原问题约束条件为9X1+4X2≤360，
4X1+5X2≤200，
3X1+10X2≤300
请根据表中数据回答下列问题：
（1）变量X2的系数在什么范围内变化，此问题最优解不变？
（2）约束条件2的常数项b在什么范围内变化时，其对偶价格不改变
（3）如果X1，X2表示的是产品Ⅰ、Ⅱ的数量。现在企业试制一个新产品Ⅲ。已知生产每件产品Ⅲ需要资源1的数量为6单位，资源2的数量为5单位，资源3的数量为7单位，获利为100单位。问该厂是否应调整生产计划？该如何调整？

七、某求最大化线性规划问题，在基B=（A3，A4，A5，）下对应的单纯形表为：

基变量
CB
X1 X2 X3 X4 X5
b
-1 2 3 1 4
X3
X4
X5
3
1
4
-1 1 1 0 0
-2 -2 0 1 0
E 3 0 0 1
4
1
D
σj
H -9 0 0 0
F

试根据上述资料，回答问题：
（1）H和F应该怎样计算。
（2）D为何值时，B为可行基。
（3）D和E为何值时，B为最优基。
（4）D和E分别为何值时，该问题有唯一最优解，若干个最优解，无最优解，无可行解。