运筹学线性规划习题.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 AXb X0有一可行基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 AXb YACX0 Y0现用单纯形表解（P）求得最优解，则在最优单纯形表中，同时也可得到（D）的最优解，它应等于：（a）表中松弛变量的检验数 （b）表中松弛变量的检验数的负值（c）表中非基变量的检验数 （d）表中非基变量的检验数的负值6. 线形规划问题maxz=3x1+2x2S.tx1+x24（1）-x1+2x22（2）2x1+3x26（3）x1，x20的约束条件（1），（2），（3）相应的松弛变量分别为x3、x4、x5，相应的约束直线如图所示，选择一个或多个正确答案填在相应的括号内。CFDEx24321-2 -1 0 1 2 3 4x1B AOG H1）以上线形规划的可行域是（ ）。ADO ODEG CDE BCEF EFGH GHI 2）图中（ ）是基本解，（ ）是基本可行解，（ ）是最优解。A B C D E F G H I G3）图中A点对应的基变量是（ ），非基变量是（ ）；图中E点对应的基变量是（ ），非基变量是（ ）。x1 x2 x3 x4 x5 4）图中满足x1，x2，x3，x4 0，x5 0的区域是（ ）；满足x1，x2，x30，x4，x50的区域是（ ）。ADO ODEG CDE BCEF EFGH GHI5）从点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。( )四、写出下列线性规划问题的对偶问题五、某一最大化线性规划问题最终单纯形表如下所示：基变量CBX1X2X3X4X5b21000X300015/4-15/215/2X121001/4-1/27/2X21010-1/43/23/2CjZj000-1/4-1/2原问题约束条件为5X215， 6X1+2X224， X1+X25，X1，X20请根据表中数据回答下列问题：（1）变量X2的系数在什么范围内变化，此问题最优解不变？（2）约束条件3的常数项b在什么范围内变化时，其对偶价格不改变？六、某一最大化线性规划问题最终单纯形表如下所示：基变量CBX1X2X3X4X5b70120000X30001-3.121.1684X1701000.4-0.220X2120010-0.120.1624Zj70120013.65.2CjZj000-13.6-5.2原问题约束条件为9X1+4X2360， 4X1+5X2200， 3X1+10X2300请根据表中数据回答下列问题：（1）变量X2的系数在什么范围内变化，此问题最优解不变？（2）约束条件2的常数项b在什么范围内变化时，其对偶价格不改变（3）如果X1，X2表示的是产品、的数量。现在企业试制一个新产品。已知生产每件产品需要资源1的数量为6单位，资源2的数量为5单位，资源3的数量为7单位，获利为100单位。问该厂是否应调整生产计划？该如何调整？七、某求最大化线性规划问题，在基B=（A3，A4，A5，）下对应的单纯形表为：基变量CB X1 X2 X3 X4 X5b -1 2 3 1 4 X3X4X5314-1 1 1 0 0-2