运筹学线性规划习题

一、需要掌握的主要内容

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 S.t

=

3x1 x1 -x1 2x1 x1

+ + + + ，

2x2 x2 2x2 3x2 x2

≤ ≥ ≥ ≥

4 2 6 0

（1） （2） （3）

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

x2 4 B A G H -2 -1 0 1 2 3 4 3 C 2 E D O F x1 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）经过初等变换后的某个线性规划问题的约束系数矩阵为：

x1?4??2?x210x331x40? ?1??则基变量为X2和X4。

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

minf?x1?4x2?3x3?2x1?3x2?5x3?2??3x1?x2?6x3?1??x1?x2?x3?4 ?x?0,x?0,x无约束23?1

五、某一最大化线性规划问题最终单纯形表如下所示：

基 变 CB 量 X3 X1 X2 0 2 1 2 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 5/4 1/4 -1/4 -1/4 0 -15/2 -1/2 3/2 -1/2 15/2 7/2 3/2 X1 X2 X3 X4 X5 b Cj－Zj 原问题约束条件为5X2≤15， 6X1+2X2≤24，? X1+X2≤5，X1，X2≥0 请根据表中数据回答下列问题：

（1）变量X2的系数在什么范围内变化，此问题最优解不变？

（2）约束条件3的常数项b在什么范围内变化时，其对偶价格不改变？

六、某一最大化线性规划问题最终单纯形表如下所示：

基 变 量 X3 X1 X2 0 70 120 Zj Cj－Zj

原问题约束条件为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，）下对应的单纯形表为：

基变量 X3 X4 X5 3 1 4 CB X1 X2 X3 X4 X5 -1 2 3 1 4 -1 1 1 0 0 -2 -2 0 1 0 E 3 0 0 1 H -9 0 0 0 b 4 1 D F CB 70 0 1 0 70 0 120 0 0 1 120 0 0 1 0 0 0 0 0 -3.12 0.4 -0.12 13.6 -13.6 0 1.16 -0.2 0.16 5.2 -5.2 84 20 24 X1 X2 X3 X4 X5 b σj

试根据上述资料，回答问题： （1）H和F应该怎样计算。 （2）D为何值时，B为可行基。 （3）D和E为何值时，B为最优基。

（4）D和E分别为何值时，该问题有唯一最优解，若干个最优解，无最优解，无可行解。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学线性规划习题在线全文阅读。