第四章单纯形法的灵敏度分析与对偶.doc

第三章 单纯形法的灵敏度分析与对偶 1、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 （ ） A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零 2、关于线性规划的原问题和对偶问题，下列说法正确的是 （ ） A．若原问题为元界解，则对偶问题也为无界解 B．若原问题无可行解，其对偶问题具有无界解或无可行解 c．若原问题存在可行解，其对偶问题必存在可行解 D．若原问题存在可行解，其对偶问题无可行解 3、下面哪些不是线性规划问题的标准形式所具备的（ ） A 所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式 C 添加新变量时，可以不考虑变量的正负性 D 求目标函数的最小值 4、已知线性规划问题 Max Z=4X1+7X2+2X3 X1+2X2+X3 ≤10 S.t 2X1+3X2+3X3≤10 X1，X2，X3 ≥0 应用对偶理论证明该问题最优解的目标函数值不大于25 5、已知线性规划问题max Z=3x1+4x2+x3 -x1+2x2+3x3≤6 S.t -3x1+x2-4x3≤7 x1,x2,x3 ≥0 利用对偶理论证明其目标函数值无界 6、写出下列线性规划问题的对偶问题 7、已知线性规划 的最优解为，试利用互补松弛定理，求对偶问题的最优解。 8、已知线性规划问题 其对偶问题的最优解为、，试用对偶理论求解原问题的最优解。 9、用对偶单纯形法求解 10、有线性规划如下： 先用单纯形法求出最优解，再分析以下各种条件下，最优解分别有什么变化： （1）约束条件①的右端常数由20变为30； （2）约束条件②的右端常数由90变为85； （3）目标函数中的系数由13变为8； （4）的系数列向量由[-1, 12]T变为[0, 5]T； （5）和的系数列向量由[-1, 12]T 、[1, 4]T变为[0, 5]T 、[2, 1]T； （6）增加一个约束条件③； （7）将约束条件②改变为。 11、试分析当参数变化时，的变化，其中是下述线性规划的最优目标函数值。 12、某个求最大值的线性规划问题的最优单纯形表如下，其中、为松弛变量。 2 0 －1 1 3 1 4 1 －1 0 －1 0 0 －3 0 －3 －1 （1）写出该问题的最优解； （2）当为何值时，其对偶问题无解？ 13、已知线性规划 的最优单纯形表为 2 5 0 1 0 1/2 1/2 1 3 1 0 0 0 1 0 3 0 0 1 －1/2 3/2 0 0 0 －1 －2 （1）写出最优基矩阵及其逆矩阵 （2）写出其对偶问题； （3）给出对偶问题的最优解； 14、已知线性规划 的最优单纯形表为 6 2 12 0 0 12 8 4/3 1/3 1 1/3 0 0 6 －2 5 0 －1 1 －10 －2 0 －4 0 其中，、分别为第1、2个约束的松弛变量。 （1）求出最优基不变的变化范围； （2）求出最优解不变的变化范围； （3）在原问题中增加约束条件，求最优解。 15、化下列线性规划为标准形 max z=2x1+2x2－4x3 x1 + 3x2－3x3 ≥30 x1 + 2x2－4x3 ≤80 x1、x2≥0，x3无限制 16、将下述线性规划问题化成标准形式。 17、用单纯形法求解 max z=50x1+100x2 x1 + x2 ≤300 2x1 + x2≤400 x2≤250 x1、x2≥0 18、用单纯形法求解 max Z=2x1+x2 －x1 + x2≤5 2x1－5x2≤10 x1、x2≥0 19、用单纯形法（大M法）求解下列线性规划 max z =3x1－2x2－x3 x1 －2x2 + x3 ≤ 11 －4x1 + x2 + 2x3 ≥ 3 －2x1 + x3 = 1 x1、x2、x3≥0 20、用单纯形法（大M法）求解下列线性规划 max z=3x1+2x2 2x1+ x2 ≤ 2 3x1 +4x2 ≥12 x1、x2≥0 21、用单纯形法求解下述LP问题。 22、用单纯形法求解下述LP问题。 23、用单纯形法求解下述LP问题。 24、用单纯形法求解下述线性规划 25、用单纯形法求解下述LP问题。 26、用大M法求解下述LP问题 27、求解下述LP问题 28、写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 +