线性规划的对偶问题

第二章 线性规划的对偶问题

第二章 线性规划的对偶问题

习题

2.1 写出下列线性规划问题的对偶问题

(1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4 st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4 ≤5

4x1＋ x2＋ x3≤20 2x1－ x2＋3x3 ＝－4 xj ≥0 （j＝1,2,3） x1 － x3＋ x4≥1

x1，x3≥0，x2，x4无约束

(3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15

x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20

2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5 x1≥0，x4≤0，x2，，x3 无约束 x1≤0， x2≥0，x3 无约束

2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：

（1）问题的第k个约束条件乘上常数λ（λ≠0）；

（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； （4）模型中全部x1用3x'1代换。

2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4

st. x1＋2x2 ＋ x4≥3

3x1＋ x2＋ x3＋ x4≥6

x3 ＋ x4＝2

x1 ＋ x3 ≥2

xj≥0（j＝1,2,3,4）

(1) 写出其对偶问题；

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

2.4 已知线性规划问题 min z＝2x1＋x2＋5x3＋6x4 对偶变量

st. 2x1 ＋x3＋ x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2

xj≥0（j＝1,2,3,4）

其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。

４７

第二章 线性规划的对偶问题

2.5 考虑线性规划问题 max z＝2x1＋4x2＋3x3

st. 3x1＋4 x2＋2x3≤60

2x1＋ x2＋2x3≤40 x1＋3x2＋2x3≤80 xj≥0 （j＝1,2,3）

（1）写出其对偶问题

（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；

（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；

（4）比较（2）和（3）计算结果。

2.6 已知线性规划问题 max z＝10x1＋5x2

st. 3x1＋4x2≤9

5x1＋2x2≤8 xj≥0（j＝1,2）

用单纯形法求得最终表如下表所示：

x2 x1 x1 0 1 0 x2 1 0 0 x3 x4 b ?j=cj-Zj 5 141— 75— 143 142 725— 14—3 21 试用灵敏度分析的方法分别判断： （1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变；

（2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；

（3）问题的目标函数变为max z ＝12x1＋4x2时上述最优解的变化；

（4）约束条件右端项由????时上述最优解的变化。 ???变为?2.7 线性规划问题如下： max z＝—5x1＋5x2＋13x3 st. —x1＋x2＋3x3≤20 ①

12x1＋4x2＋10x3≤90 ②

?9??8??11??19?xj≥0 （j＝1,2,3） 先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？ （1） 约束条件①的右端常数由20变为30；

４８

第二章 线性规划的对偶问题

（2） （3） （4） （5）

约束条件②的右端常数由90变为70； 目标函数中x3的系数由13变为8；

TT

x1的系数列向量由（—1，12）变为（0，5）； 增加一个约束条件③：2x1＋3x2＋5x3≤50；

（6） 将原约束条件②改变为：10x1＋5x2＋10x3≤100。 2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下：

cj a b 基变量 c d ?j=cj-Zj 50 x1 0 1 0 40 x2 1 0 0 10 x3 60 x4 1 2 f S 6 4 g 1 21 4e （1）给出a，b，c，d，e，f，g的值或表达式；

（2）指出原问题是求目标函数的最大值还是最小值；

（3）用a+?a，b+?b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。

2.9 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸坯纸

1040千克，每打日记本用白坯纸千克，每箱练习本用白3380千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生3产一箱练习本获利1元。试确定：

（1）现有生产条件下获利最大的方案；

（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？

2.10 某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。 产品原料 A B 销售价（元） 甲 2 3 13 乙 4 2 16 可用量（千克） 原料成本（元/千克） 160 180 1.0 2.0 （1）请构造数学模型使该厂利润最大，并求解。

４９

第二章 线性规划的对偶问题

（2）原料A、B的影子价格各为多少。

（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。

（4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？

2.11 某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如下表：

单位产品 原料（千克） 工时（小时） 利润（万元） A 1 2 4 B 2 1 3 可用量（千克） 200 300 （1） 请构造一数学模型使该厂总利润最大，并求解。

（2） 如果原料和工时的限制分别为300公斤和900小时，又如何安排生产？ （3） 如果生产中除原料和工时外，尚考虑水的用量，设两A，B产品的单位产品

分别需要水4吨和2吨，水的总用量限制在400吨以内，又应如何安排生产？

复习思考题

2.12 试从经济上解释对偶问题及对偶变量的含义。

2.13 根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。

2.14 什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。

2.15 试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。

2.16 将aij，b，c的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。 2.17 判断下列说法是否正确

(a)任何线性规划问题存在并具有唯一的对偶问题； (b)对偶问题的对偶问题一定是原问题；

(c)根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；

(d)若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；

(e)应用对偶单纯形法计算时，若单纯形表中某一基变量xi<0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；

(f)若线性规划问题中的bi，c,值同时发生变化，反映到最终单纯形表中，不会出

５０

第二章 线性规划的对偶问题

现原问题与对偶问题均为非可行解的情况；

(g)在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。

５１