运筹学线性规划习题.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)线性规划模型具有可行域,若其有最优解,必能在上获得。
二、选择题
,自由变量可以用两个非负变量的( )代换。

( )

,且检验数为零的变量的个数大于基变量的个数时,可求得( )

( )相同。

(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

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 ④