[管理学]对偶问题.docVIP

第二章.对偶理论与灵敏度分析 已知线性规划问题： 用单纯形法求解得最终单纯形表如下表所示： 求和 求 3/2 2 1 1/2 0 1 1 0 1/2 －1 -1/2 2 -3 0 0 0 -4 答： 已知矩阵A及其逆矩阵如下： 试根据改进单纯形法中求逆矩阵的方法原理求下述矩阵B的逆矩阵，已知 答：先设 有 已知线性规划的原问题与对偶问题分别为： （P）原问题： (D)对偶问题： 若为对偶问题最优解，又原问题约束条件右端项用替换之后其最优解为，试证明有 证明：原问题右端项用替换后，新的原问题及对偶问题为： 设的最优解为，因有，有是的可行解，故有，由此 已知下表为求解某线性规划问题的最终单纯形表，表中为松弛变量，问题的约束条件为形式。 5/2 5/2 0 1 1/2 -1/2 1 0 1/2 -1/6 0 1/3 0 -4 0 -4 -2 (a)写出原线性规划问题 (b) 直接由表写出对偶问题的最优解。 答：（a）原线形规划问题如下： (b )对偶问题最优解为 已知线性规划问题： 写出其对偶问题 已知原问题用两阶段法求解时得到的最终单纯形表如下 试写出其对偶问题的最优解。 5 3 6 －6 0 0 8 5 14 －6 4 0 1 0 1 2 1 0 0 －1 0 0 1 1 0 0 0 －1 0 0 0 答： 其对偶问题为 设第（1）个约束条件的松弛变量为，第（2）个约束条件的松弛变量为，由原问题用两阶段法求得之最终单纯形表知，代入约束条件（1）~(3)有 解得： 6.已知线性规划问题： 其最优解为 （a）求k的值； （b）写出并求其对偶问题的最优解。 解：先写出其对偶问题如下： 由机互补松弛性质得 解得 7.已知线性规划问题分别说明发生下列情况时，其对偶问题的解的变化： (a)问题的第个约束条件乘上常数（）； (b)将第个约束条件乘上常数（）后加到第个约束条件乘上；(c)目标函数改变为（）； (d)模型中全部代换。 解： （a）对偶变量第个约束条件乘上常数，即的列将为变化前的，由此对偶问题变化后的解 （b）与前类似， （c）; （d）不变。 8.已知线性规划问题： 若（为其对偶问题的最优解。又若原问题约束条件的右端项变换为，这时原问题的最优解变为（，试证明 解：原问题右端项变为后，其对偶问题为： 由于约束条件不变，（必为上述问题的可行解。根据对偶理论有： 9.已知线性规划问题： 试应用对偶理论证明上述线性规划问题无最优解。 解：该问题存在可行解，如；又上述问题的对偶问题为： 由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优解。 10．已知线性规划问题： 其对偶问题最优解为试根据对偶理论求出原问题的最优解。 解：写出对偶问题并根据互补松弛性质可求得原问题最优解为 2.11 已知某实际问题的线性规划模型为： 若第i资源的影子价格为yi， （a） 若第一个约束条件两端乘以2，变为 ， 是对应这个新的约束条件的影子价格，求与的关系； （b） 令 用 替换模型中所有的，问影子价格是否变化？若x1不可能在最优基中出现，问有否可能在最优基中出现； （c） 如目标函数变为 ，问影子价格有何变化？ 解：（a） =1/2；（b） 影子价格不变，又不在最优解中出现， 也不可能在最优解中出现，（c）影子价格也增大两倍。 2.12 下述线性规划问题 已知最优解中的基变量为 且已知 要求根据上述信息确定三种资源各自的影子价格。 解：三种资源的影子价格分别为4/3，1，8/3。 2.13 若线性规划问题 约束于，具有最优解，试运用对偶性质证明下述线性规划问题不可能具有无界解，约束与是可以取任意值的向量。 解： 分别写出两个问题的对偶问题见L1，L2： 显然 的最优解是的可行解，由此 的原问题具有下界。 2.14 用对偶单纯形法求下列线性规划问题 (a) X1 X2 X3 X4 X5 -3 X2 2/5 -2 X1 11/5 0 1 1 0 -1/5 7/5 -2/5 -1/5 1/5 -2/5 Cj-zj 0 0 -9/