《运筹学研究生辅导课件》胡运权习题.doc

习题 1.1用图解法求解下列线性规划问题，并指出问题具有唯一最优解，无穷多最优解、无界解还是无可行解。  1.2将下述线性规划问题化成标准形式。 1.8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到的表1-19，试求括弧中未知数a～ 表1-19 项目 X1 X2 X2 X4 x X4 X5 6 1 (b) -1 (c) 3 (d) (e) 1 0 0 1 Cj-zj (a) -1 2 0 0 X1 X5 (f) 4 (g) (h) 2 (i) -1 1 1/2 1/2 0 1 Cj-zj 0 -7 (j) (k) (l) 1.9 若均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。 习题 写出下列线性规划问题的对偶问题。 （1）min z=2x+2x+4x (2)max z=5x+6x+3x 判断下列说法是否正确，为什么？ 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 如果线性规划的对偶问题无可行解，则原问题也一定无可行解 在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过对偶问题可行解的目标函数值； 任何线性规划围绕具有唯一的对偶问题。 2.7给出线性规划问题 max z=2x1+4x2+x3+x4 要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。 2.10 考虑如下线性规划问题： min z=60x1+40x2+80x3 要求：（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；（3）用单纯形法求解其对偶问题；（4）比（2）与（3）中每步计算的结果。 2.12给出线性规划问题 max z=2x1+3x2+x3 用单纯形法求解得最终单纯形表见表2-33。 表2-33 cj 2 3 1 0 0 CB 基 b x1 x2 x3 x4 x5 2 x1 1 3 x2 2 1 0 -1 4 -1 0 1 2 -1 1 cj-zj 0 0 -3 -5 -1 试分析下列各种条件下最优解（基）的变化； 目标函数中变量x3的系数变为6； 分别确定目标函数中变量x1和x2的系数在什么范围内变动时最优解不变； 约束条件右端项由 变为； (4)增加一个新的变量x6, ,c6=7； (5)增加一个新的约束x1+2x2+x3≤4 2.15已知线性规划问题： max z=（c1+t1）x1+c2x2+c3x3+0x4+0x5 当t1=t2=0时求解得最终单纯形表见表2-35。 表 2-35 项 目 x1 x2 x3 x4 x5 x3 5/2 x1 5/2 0 1 1/2 - 1/2 1 0 1/2 - 1/6 0 1/3 cj 0 -4 0 -4 -2 （1）确定c1，c2，c3，a11，a12，a13，a21，a22，a23，和b1，b2的值； （2）当t2=0时，t1在什么范围内变化上述最优解不变； （3）当t1=0时，t2在什么范围内变化上述最优基不变。 习题 写出下列线性规划问题的对偶问题： maxZ=2x1+x2+3x3+x4 s.t. (2) minZ=3x1+2x2-3x3+4x4 s.t. (3) minZ=-5x1-6x2-7x3 s.t. 2. 已知原问题： maxZ=x1+2x2 s.t. （1）写出对偶问题； （2）利用对偶定理证明原问题无界。 3. 已知线性规划问题： minZ=3x1+4x2+2x3+5x4+9x5 s.t. （1）求原问题的最优解； （2）利用互补松弛定理求对偶问题的最优解。 4．已知原问题： maxZ=x1+4x2+3x3 s.t. 最优解X