第二章
线性规划的对偶理论与灵敏度分析

1 写出下列线性规划问题的对偶问题，并以对偶问题为原问题，再写出对偶的对偶问题。

（1）

（2）

（3）

解： （1）对偶问题：

对偶的对偶问题：

（2）对偶问题：

对偶的对偶问题：

（3）对偶问题：

对偶的对偶问题：

2 判断下列说法是否正确，并说明为什么。

（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；

（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；

（3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；

（4）任何线性规划问题具有唯一的对偶问题。

解： （1）错误。如果原问题是无界解，则对偶问题无可行解。

（2）错误。如果对偶问题无可行解，也可能是因为原问题是无界解。

（3）错误。如果原问题是求极小，则结论相反。

（4）正确。

3 对本章第三节影子价格的6点叙述试分别举例说明其实际应用。

解： 关于叙述1：

例子：工厂在计划期内生产甲乙两种产品，已知生产单位甲乙产品所需的设备台时分别1台和2台；生产单位甲产品消耗A、B两种原材料分别4kg和0kg，生产单位乙产品消耗A、B两种原材料分别0kg和4kg；该工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元。目前，工厂设备台时数为8，原材料A有16kg，原材料B有12kg，如何安排生产计划才能使该工厂获利达到最多？

设x ₁ 、x ₂ 分别表示在计划期内产品甲和乙的产量，通过分析得出数学模型为：

由单纯形法求解可同时给出两个信息：一个是线性规划问题的最优解，另一个是其对偶问题的最优解，即各种资源的影子价格。

可求得线性规划问题的最优解：X ^* ＝（4，2） ^T 即该工厂在计划内的最优生产方案是：生产甲产品4件，生产乙产品2件，获得最大利润为14元。

其对偶问题的最优解：W ^* ＝（1.5，0.125，0）即三种资源——设备、原材料A、原材料B的影子价格分别为1.5，0.125，0。也就是这三种资源每单位对利润的贡献。

关于叙述2：

同样可用上面这道例题说明，在资源得到最优利用的生产条件下，影子价格1.5表示设备每增加一个单位时目标函数z会增加1.5。

关于叙述3：

在完全市场经济下，如果市场价格高于原材料A的成本加上影子价格0.125时，可以卖出这种资源，同时随着卖出材料A，A的影子价格也会发生变化。

关于叙述4：

由互补松弛性知，原材料B的影子价格为0，说明该材料未得到充分利用，在原分配方案中有剩余。

关于叙述5：

在求解单纯形表时，检验数＞0，说明生产这项产品有利，否则应生产别的产品。

关于叙述6：

企业需减（增）某些资源的投量时，若目标函数z为总利润，应首先考虑减少（增加）影子价格低（高）的资源。部门之间调配资源时，应将资源由影子价格较低的部门调向较高的部门。从上面的分析得出：采用本方法，系统决策者可以对系统内各部门的资源利用情况进行评价，对现有的资源分配方案进行调整，从而达到最优化。这样，既能使有限的人、财物资源，从利润低的部门流向利润高的部门，从而提高整体经济效益，又能促使部门自身降低资源消耗，提高劳动生产率，使自己现有资源得到最大利用，从而获得最大的经济效益，获得最大的利润。

4 下列两个线性规划问题

（LP1）

（LP2）

已知对（LP1）有最优解X ^* ＝（50，500），z ^* ＝550，求（LP2）的最优解。

解： 已知线性规划问题max z＝CX，AX＝b，X≥0，如X ^* 是该问题的最优解，又λ＞0为某一常数，当AX＝b变为AX＝λb，z＝CX变为z＝CX/λ时，最优解由X ^* 变为λX ^* ，最优值不变。

则此题中，λ＝1/100，则最优解X´ ^* ＝（1/2，5），最优值z´ ^* ＝550。

5 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-2-1所示，求表中各括号内未知数（a）～（l）的值。

解： l＝1，k＝0，h＝－1/2，a＝2，c＝3，b＝10，e＝5/4，f＝－1/2，d＝1/4，g＝－3/4，i＝－1/4，j＝－1/4。

6 给出线性规划问题

（1）写出其对偶问题；

（2）用图解法求解对偶问题；

（3）利用（2）的结果及根据对偶问题性质写出原问题最优解。

解： （1）对偶问题：

（2）图解法求解（见图2-2-1）：

最优解是：y ₁ ＝8/5，y ₂ ＝－1/5，目标函数值19/5。

（3）由于y ₁ ＝8/5，y ₂ ＝－1/5都不等于零，原问题中的约束取等号。又上面第4个约束不等号成立，故x ₄ ＝0，令x ₃ ＝0就可以得到最优解：x ₁ ＝8/5，x ₂ ＝1/5。

7 给出线性规划问题

其最优解为：X＝（400/3，0，0，20/3），z ^* ＝2800/3

（1）写出其对偶问题；

（2）利用互补松弛性质找出对偶问题的最优解。

解： （1）其对偶问题为：

（2）由互补松弛性可知，原问题最优解中x ₁ ，x ₄ 非零，则对应对偶问题约束条件中第一个式子和第四个式子取等号，再由最优值相等可列出以下方程：

解方程得到对偶问题最优解为：Y＝（22/15，2/15，0） ^T 。

8 已知线性规划问题

试根据对偶问题性质证明上述线性规划问题目标函数值无界。

解： x ₁ ＝2，x ₂ ＝x ₃ ＝0是原问题的一个可行解，原问题的对偶问题为：

由于（1）和（4）是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。

9 给出线性规划问题

要求：

（1）写出其对偶问题；

（2）已知原问题最优解为X ^* ＝（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。

解： （1）对偶问题：

（2）已知原问题最优解为X ^* ＝（2，2，4，0），带入原问题，第4个约束不等式成立，故y ₄ ＝0。有由于x ₁ ，x ₂ ，x ₃ ＞0，上面对偶问题前3个约束取等号，故得到最优解：y ₁ ＝4/5，y ₂ ＝3/5，y ₃ ＝1，y ₄ ＝0。

10 已知线性规划问题A和B如下：

试分别写出 同y _i （i＝1，2，3）间的关系式。

解：

得 。

11 用对偶单纯形法求解下列线性规划问题。

（1）

（2）

解： （1）先将问题改写为：

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如表2-2-2所示。

由上表可得原问题最优解：x ₁ ＝0，x ₂ ＝3/2，x ₃ ＝1，目标函数z＝36。

（2）先将问题改写为：

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如表2-2-3所示。

由上表可得原问题最优解：x ₁ ＝2/3，x ₂ ＝2，x ₃ ＝0，目标函数得z＝22/3。

12 考虑如下线性规划问题：

要求：

（1）写出其对偶问题；

（2）用对偶单纯形法求解原问题；

（3）用单纯形法求解其对偶问题；

（4）对比（2）与（3）中每步计算得到的结果。

解： （1）对偶问题：

（2）先将问题改写为

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如表2-2-4所示。

由上表可得原问题最优解：x ₁ ＝5/6，x ₂ ＝2/3，x ₃ ＝0，代入目标函数得z＝230/3。

（3）用单纯形法求解其对偶问题，如表2-2-5所示。

由上表可得对偶问题最优解：x ₁ ＝0，x ₂ ＝20/3，x ₃ ＝50/3，代入目标函数得w＝230/3。

（4）由于对偶单纯形法选择min{b _i }对应的x _i 为换出基的变量，而原问题则选择max{σ _j }对应的x _j 为换入基变量，由于互为对偶问题，则每次选择的min{b _i }＝－max{σ _j }（下标不同，但数值相等）。同理，最小比值的数值绝对值也相等，通过每步单纯形表对比可以验证，且每次计算结果原问题和对偶问题目标函数值相等。

13 已知线性规划问题：

先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。

（1）目标函数变为max z＝2x ₁ ＋3x ₂ ＋x ₃ ；

（2）约束右端项由 变为 ；

（3）增添一个新的约束条件－x ₁ ＋2x ₃ ≥2。

解： 先用单纯形法计算如表2-2-6所示。

由上表可得最优解为x ₁ ＝6，x ₂ ＝x ₃ ＝0，z ^* ＝12。

（1）当目标函数变为max z＝2x ₁ ＋3x ₂ ＋x ₃ ，反映到最终单纯形表上如表2-2-7所示。

因变量x ₂ 的检验数大于零，故需继续用单纯形法迭代计算得表2-2-8。

由上表可得最优解变为：x ₁ ＝8/3，x ₂ ＝10/3，x ₃ ＝0，z ^* ＝46/3。

（2）约束右端项由 变为 ，因有 ， 。将其反映到最终单纯形表中如表2-2-9所示。

由表可得最优解为：x ₁ ＝3，x ₂ ＝0，x ₃ ＝0，z ^* ＝6。

（3）增添一个新的约束条件－x ₁ ＋2x ₃ ≥2

先将原问题的最优解x ₁ ＝6，x ₂ ＝0，x ₃ ＝0代入新增约束条件－x ₁ ＋2x ₃ ≥2中，因－6＋2×0＝－6≤2，故原问题最优解发生变化。

给新增约束条件中加入松弛变量并规范化得：x ₁ －2x ₃ ＋x ₆ ≤－2

以x ₆ 为基变量，将上式反映到最终单纯形表中得表2-2-10。

因上表中x ₁ 列不是单位向量，故需进行变换，得表2-2-11。

因上表中对偶问题为可行解，原问题为非可行解，故用对偶单纯形法迭代计算得表2-2-12。

由上表可得最优解为x ₁ ＝10/3，x ₂ ＝0，x ₃ ＝8/3，z ^* ＝28/3。

14 给出线性规划问题

要求：

（1）以x ₁ ，x ₂ 为基变量列出单纯形表（当λ＝0时）；

（2）若x ₁ ，x ₂ 为最优基，确定问题最优解不变时c ₃ ，c ₄ 的变化范围；

（3）保持最优基不变时的λ的变化范围；

（4）增加一个新变量，其系数为（c _k ，2，3） ^T ，试求问题最优解不变时c _k 的取值范围。

解： （1）初始单纯形表如表2-2-13所示。

经过变换得到以x ₁ ，x ₂ 为基变量的单纯形表如表2-2-14所示。

（2）x ₁ ，x ₂ 为最优基，则最优解不变需满足c ₃ －5≤0且c ₄ －8≤0，即c ₃ ≤5且c ₄ ≤8。

（3）含λ时以x ₁ ，x ₂ 为基变量的单纯形表如表2-2-15所示。

则λ应该满足5－λ/5≥0且5＋λ/10≥0，即－50≤λ≤25。

（4）增加一个新变量后以x ₁ ，x ₂ 为基变量的单纯形表如表2-2-16所示。

则应满足c _k －16≤0，则c _k ≤16。

15 分析下列线性规划问题中，当λ变化时（λ≥0）最优解的变化，并画出z（λ）对λ的变化关系图。

（1）

（2）

（3）

（4）

解： （1）先令λ＝0求得最优解，并将λC ^* 反映到最终单纯形表中，得表2-2-17。

上表中，当0≤λ≤1/2时，表中解为最优，且X ^* ＝（0，5，2，0）T，z ^* （λ）＝5－2λ；

当λ＞1/2时，变量x ₁ 的检验数＞0，用单纯形法迭代计算得表2-2-18。

上表中，当1/2≤λ≤1时，表中解为最优，且X ^* ＝（2，1，0，0）T，z ^* （λ）＝3；

当λ＞1时，变量x ₃ 的检验数＞0，用单纯形法迭代计算得表2-2-19。

上表中，当λ≥1时，表中解为最优，且X ^* ＝（0，2，0，1）T，z ^* （λ）＝2＋2λ；

图2-2-2表明了目标函数值z（λ）随λ值变化的情况：

（2）先令λ＝0求得最优解，并将λC*反映到最终单纯形表中，得表2-2-20。

上表中，当0≤λ≤2时，表中解为最优，且X ^* ＝（0，5）T，z ^* （λ）＝120－10λ；

当λ＞2时，变量x ₁ 的检验数＞0，用单纯形法迭代计算得表2-2-21。

上表中，当2≤λ≤8时，表中解为最优，且X ^* ＝（10/3，10/3）T，z ^* （λ）＝（320－10λ）/3；

当λ＞8时，变量x ₃ 的检验数＞0，用单纯形法迭代计算得表2-2-22。

上表中，当λ≥8时，表中解为最优，且X ^* ＝（5，0）T，z ^* （λ）＝40＋5λ；

图2-2-3表明了目标函数值z（λ）随λ值变化的情况：

（3）令λ＝0求解得最终单纯形表，又因有

将其反映到最终单纯形表中，得表2-2-23。

上表中，当0≤λ≤10/3时，解为最优解，且X ^* ＝（0，5－λ，30＋λ）T，z ^* （λ）＝160＋3λ；

当λ＞10/3时，表中基变量x ₆ 将小于0，这时用对偶单纯形法继续求解得表2-2-24。

表中，当10/3≤λ≤30/7时为最优解，且X ^* ＝（0，15/2－7λ/4，30＋λ）T，z ^* （λ）＝165＋3λ/2；

当λ＞70/3时，原问题无可行解。

图2-2-4表明了目标函数值z（λ）随λ值变化的情况：

（4）令λ＝0求解得最终单纯形表，又因有

将其反映到最终单纯形表中，得表2-2-25。

上表中，当0≤λ≤1时，解为最优解，且X ^* ＝（10＋2λ，10＋2λ）T，z ^* （λ）＝30＋6λ；

当λ＞1时，表中基变量x ₄ 将小于0，这时用对偶单纯形法继续求解得表2-2-26。

表中，当1≤λ≤5时为最优解，且X ^* ＝（10＋2λ，15－3λ） ^T ，z ^* （λ）＝35＋λ；

当λ＞5时，表中基变量x ₂ 将小于0，这时用对偶单纯形法继续求解得表2-2-27。

表中，当5≤λ≤25时为最优解，且X ^* ＝（25－λ，0） ^T ，z ^* （λ）＝50－2λ。

图2-2-5表明了目标函数值z（λ）随λ值变化的情况：

16 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见表2-2-28。要求：（1）确定获利最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述最优计划不变；（3）如果设计一种新产品D，单件劳动力消耗为8h，材料消耗为2kg，每件可获利3元，问该种产品是否值得生产？（4）如果原材料数量不增，劳动力不足时可从市场购买，为1.8元/h。问：该厂要不要招收劳动力扩大生产，以购多少为宜？

解： （1）用x ₁ ，x ₂ ，x ₃ 分别表示该厂生产的三种产品A、B、C的数量，则对该问题建模如下：

解得最优生产计划为：x ₁ ＝50，x ₂ ＝0，x ₃ ＝30，Z＝2700；

（2）设产品A的利润为（30＋λ）元，反映到最终单纯形表上如表2-2-30。

为使上表中的解仍为最优解，应有

λ/3－20≤0，－λ/3－2≤0，λ/3－6≤0

解得

－6≤λ≤18

即产品A的利润在[24，48]内变动时，生产计划不变。

（3）设该公司生产x ₆ 件产品D，有c ₆ ＝30，P ₆ ＝（8，2） ^T 。

将其反映到最终单纯形表中得表2-2-31。

因σ ₆ ＞0，故用单纯形法继续迭代计算得表2-2-32。

由上表可知产品D值得投入生产，最优解为x ₁ ＝0，x ₂ ＝0，x ₃ ＝50，x ₆ ＝25，z ^* ＝2750。

（4）由（1）可知劳动力的价格是2元，大于市场价格。故应该招收劳动力扩大生产。

当招收劳动力为150h时，利润达到最大值3600元。

17 已知线性规划问题：

当t ₁ ＝t ₂ ＝0时求解得最终单纯形表见表2-2-33。

（1）确定c ₁ ，c ₂ ，c ₃ ，a ₁₁ ，a ₁₂ ，a ₁₃ ，a ₂₁ ，a ₂₂ ，a ₂₃ 和b ₁ ，b ₂ 的值；

（2）当t ₂ ＝0时，t ₁ 在什么范围内变化上述最优解不变；

（3）当t ₁ ＝0时，t ₂ 在什么范围内变化上述最优基不变。

解： （1）由题给可得：

即

解之得

又由最终单纯形表得

解之得

（2）将目标函数的系数变化直接反映到最终单纯形表中，得表2-3-34。

为使上表中的解仍为最优解，应有

－4＋t ₁ /2≤0，－4＋t ₁ /6≤0，－2－t ₁ /3≤0

解得

－6≤t ₁ ≤8

（3）因有

将其反映到最终单纯形表中，其b列数字为

当b≥0时问题的最优基不变，解得－5/3≤t ₂ ≤15。

18 某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸的供应量为30000kg。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸 每打日记本用白坯纸 每箱练习本用白坯纸 。已知生产各种产品的赢利为：每捆原稿纸1元，每打日记本2元，每箱练习本3元。试决定：

（1）在现有生产条件下使该厂赢利最大的方案；

（2）如白坯纸供应量不变，而工人数量不足时可从市场上招收临时工，临时工费用为每人每天40元。

问：该厂应否招临时工及招收多少人为宜？

解： （1）设该厂每天生产x ₁ 捆原稿纸，x ₂ 打日记本，x ₃ 箱练习本，则对该问题建模如下：

用单纯形表法计算如表2-3-35所示。

解得最优生产计划为：x ₁ ＝1000，x ₂ ＝2000，x ₃ ＝0，z ^* ＝5000。

（2）设应招收临时工λ人，因有

将其反映到最终单纯形表中，其b列数字为

当b≥0时问题的最优基不变，解得0≤λ≤200

故该厂应从市场招收临时工200人/天，新计划只生产原稿纸9000捆。

19 某厂生产 Ⅰ 、 Ⅱ 、 Ⅲ 三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润表见表2-2-37。

要求：

（1）求获利最大的生产计划；

（2）产品 Ⅲ 每件的利润增加到多大时才值得安排生产？如产品 Ⅲ 每件利润增加到50/6元，求最优计划的变化；

（3）产品 Ⅰ 的利润在多大范围内变化时，原最优计划保持不变；

（4）设备A的能力为100＋λ，求保持最优基不变时的λ的变化范围；

（5）如有一种新产品，加工一件需设备A、B、C的台时分别为1、4、3h，预计每件的利润为8元，是否值得安排生产；

（6）如合同规定该厂至少生产10件产品 Ⅲ ，试重新确定最优生产计划。

解： （1）根据题意设分别生产 Ⅰ 、 Ⅱ 、 Ⅲ 三种产品x ₁ ，x ₂ ，x ₃ ，建立线性规划模型得：

求得最优单纯形表为表2-2-38。

即获利最大生产X ^* ＝（100/3，200/3，0） ^T ，最大利润为Z ^* ＝2200/3。

（2）设产品 Ⅲ 每件利润变为（4＋λ），则上述最优单纯形表变为表2-2-39。

要安排产品 Ⅲ 生产，则λ－8/3≥0，即λ≥8/3。

当产品 Ⅲ 利润为50/6时，即λ＝13/3，则最优单纯形表变为表2-2-40。

生产最优解为X ^* ＝（175/6，275/6，25） ^T ，最大利润为Z ^* ＝775。

（3）设产品 Ⅰ 的利润为（10＋m），则（1）中最优单纯形表变为表2-2-41。

要保持原计划不变，则应该满足以下条件：

解得－4≤m≤5，即产品 Ⅰ 的利润范围为[6，15]时，最优计划不变。

（4）因有

将其反映到（1）中的最优单纯形表，得到表2-2-42。

最优基不变，则应满足b _i ≥0，得到λ取值范围为：－40≤λ≤50。

（5）设生产x ₇ 件新产品，则c ₇ ＝8，P ₇ ＝（1，4，3） ^T 。

则（1）中最优单纯形表为表2-2-43。

所有检验数均≤0，最优计划不变，新产品不值得安排生产。

（6）增加一个x ₃ ≥10的约束条件，加入剩余变量x ₇ 和人工变量x ₈ 改为等式得：

x ₃ －x ₇ ＋x ₈ ＝10，c ₇ ＝0，c ₈ ＝－M，反映到（1）中的最优单纯形表中得到表2-2-44。

把基变量检验数化为0，并进行迭代得表2-2-45。

则最优解X ^* ＝（95/3，175/3，10） ^T ，最大利润Z ^* ＝2120/3。 FHi/w7XJpndeIVsIcKp4lFMX15/gz0+HyHfY3tp9zdEaRMOvweio2ftirRuCE758