第二章 线性规划的对偶问题
习题
2.1 写出下列线性规划问题的对偶问题
⑴ max z = 10x i + X 2 + 2x 3
st.
x i + X 2 + 2 X 3W 10 4x i + X 2 + X 3 W 20
X > 0
(j = 1,2,3)
(3) min z = 3x i + 2 X 2 — 3x 3 + 4x 4 st.
x i －2x 2+ 3x 3+ 4x 4W 3
X 2 + 3X 3 + 4X 4》一5
2x i — 3x 2 — 7x 3 — 4x 4= 2 =
x i >0, X 4W 0, X 2，, X 3 无约束
(2) max z = 2x i + x 2+ 3x 3+ x 4
st. x i + x 2+ x 3 + x 4 W 5
2x i
－ x
2+
3x 3
=－ 4 X i
— X 3 + X 4> i
X i , X 3 > 0, X 2, X 4 无约束 (4) min z =— 5 x i — 6x 2— 7x 3 st.
— X i + 5X 2— 3X 3 > i5 — 5X
i — 6X
2+ i0X
3 W 20
X i — X 2 — X 3=— 5
X i W 0, X 2>0 , X 3 无约束
2.2已知线性规划问题 max z = CX , AX=b , X >0。
分别说明发生下列情况时，其对偶问题的解的 变化： (1 )问题的第k 个约束条件乘上常数 入(炉0);
(2)
将第k 个约束条件乘上常数 入(苗0)后加到第r 个约束条件上；
(3) 目标函数改变为 max z = 2CX (入工0)； 4)模型中全部 X i 用 3 X'i 代换。
2.3 已知线性规划问题 min z = 8X i + 6X 2+ 3X 3+ 6X 4
st. x i + 2X 2
+ X 4》3
3x i + X 2 + X 3+ X 4 A 6 X 3 + X 4= 2
X i
+ X 3 A 2 X j A 0(j =i,2,3,4)
(1) 写出其对偶问题；
(2) 已知原问题最优解为 X*=(i ，i ，2，0) ，试根据对偶理论，直接求出对偶问题的最优解。
2.4 已知线性规划问题 min z = 2X i + X 2+ 5X 3+ 6X 4
对偶变量
st. 2X i
+ X 3+ X 4W 8
y i
2X i + 2X 2+ X 3+ 2X 4W i2
y 2
X j A 0(j =i,2,3,4)
其对偶问题的最优解 y i *=4； y 2*=i ，试根据对偶问题的性质，求出原问题的最优解。
2.5 考虑线性规划问题 maX z = 2X i + 4X 2+
3X 3
st. 3X i +4 X 2+ 2X 3W 60
2X i + X 2+ 2X 3W 40
X i + 3X 2+ 2X 3W 80 X j A 0
(j = i,2,3)
( i )写出其对偶问题
( 2)用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；
( 3)用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶 问题的解； ( 4)比较( 2)和( 3)计算结果。
2.6已知线性规划问题
max z = 10x i + 5x 2
st. 3x i+4x2< 9
5x i + 2x2 W 8
X > 0(j = 1,2)
试用灵敏度分析的方法分别判断：
(1)目标函数系数C i或C2分别在什么范围内变动，上述最优解不变；
(2)约束条件右端项b i，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；
(3)问题的目标函数变为max z = 12x i+4x2时上述最优解的变化；
(4)约束条件右端项由8)变为'ii时上述最优解的变化。
I8丿加
2.7线性规划问题如下：max z = —5x i + 5x2 + i3x3
st. —x i + x2 + 3x3^ 20①
i2x i+ 4X2+ i0x3W 90 ②
X j > 0 (j = i,2,3 )
先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？
(1)约束条件①的右端常数由20变为30;
(2)约束条件②的右端常数由90变为70;
(3)目标函数中X3的系数由i3变为8;
(4)x i的系数列向量由(一i，i2) T变为(0, 5) T;
(5)增加一个约束条件③：2x i + 3x2 + 5X3 < 50;
(6)将原约束条件②改变为：i0x i + 5X2+ 10X3W i00。
2.8用单纯形法求解某线性规划问题得到最终单纯形表如下:
(1)给岀a，b，c，d，e，f，g的值或表达式；
(2)指岀原问题是求目标函数的最大值还是最小值；
(3)用a+ a，b+ b分别代替a和b，仍然保持上表是最优单纯形表，求：a，:b满足的范围。
2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。
该厂现有工人100人，每月白坯纸供应量为30000千克。
已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本
10 40
30打，或练习本30箱。
已知原材料消耗为：每捆原稿纸用白坯纸千克，每打日记本用白坯纸千
3 3
80
克，每箱练习本用白坯纸千克。
又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生
3
产一箱练习本获利1元。
试确定：
(1)现有生产条件下获利最大的方案；
(2)如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支岀为每人每月40 元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？
2.10某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表(表中的消耗系数
为千克/件)。
(1)请构造数学模型使该厂利润最大，并求解。
(2)原料A、B的影子价格各为多少。
(3)现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。
(4)工厂可在市场上买到原料A。
工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？
2.11某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如下表：
(1)请构造一数学模型使该厂总利润最大，并求解。
(2)如果原料和工时的限制分别为300公斤和900小时，又如何安排生产？
(3)如果生产中除原料和工时外，尚考虑水的用量，设两A，B产品的单位产品分别需要水4吨和
2吨，水的总用量限制在400吨以内，又应如何安排生产？
复习思考题
2.12试从经济上解释对偶问题及对偶变量的含义。
2.13根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检
验数之间的对应关系。
2.14什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。
2.15试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。
2.16将a j，b，c的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的
解各自将会出现什么变化，有多少种不同情况以及如何去处理。
2.17判断下列说法是否正确
(a) 任何线性规划问题存在并具有唯一的对偶问题；
(b) 对偶问题的对偶问题一定是原问题；
(c) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶
问题无可行解时，其原问题具有无界解；
(d) 若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k;
(e) 应用对偶单纯形法计算时，若单纯形表中某一基变量X i<0,又X i所在行的元素全部大于
或等于零，则可以判断其对偶问题具有无界解；
(f) 若线性规划问题中的bi，c,值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；
(g) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数C j或在各约束中的相应系数a ij,反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。