第二章 线性规划的对偶问题
习题
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 (1) 写出其对偶问题；
(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。
2.4 已知线性规划问题 min z＝2x1＋x2＋5x3＋6x4 对偶变量 xj≥0（j＝1,2,3,4） 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）
用单纯形法求得最终表如下表所示： x1 x2 x1 0 1 0 x2 1 0 0 x3 x4 —3 14b ?j=cj-Zj 175— 14— 1 —25 14 试用灵敏度分析的方法分别判断：
（1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变； （2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；
（3）问题的目标函数变为max z ＝12x1＋4x2时上述最优解的变化；
9??11?（4）约束条件右端项由?变为????19??时上述最优解的变化。 ?8?????2.7 线性规划问题如下： max z＝—5x1＋5x2＋13x3 st. —x1＋x2＋3x3≤20 ① 12x1＋4x2＋10x3≤90 ② xj≥0 （j＝1,2,3） 先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？ （1） 约束条件①的右端常数由20变为30； （2） 约束条件②的右端常数由90变为70； （3） 目标函数中x3的系数由13变为8；
（4） x1的系数列向量由（—1，12）T变为（0，5）T； （5） 增加一个约束条件③：2x1＋3x2＋5x3≤50；
（6） 将原约束条件②改变为：10x1＋5x2＋10x3≤100。 2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下：
50 cj 基变量 x1 a b c d 0 1 0 40 x2 1 0 0 10 x3 60 S x4 1 2 6 4 g ?j=cj-Zj e f （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两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。
产品原料 甲 乙 可用量（千克） 原料成本（元/千克） 1.0 2.0 A B 销售价（元） 2 3 13 4 2 16 160 180 （1）请构造数学模型使该厂利润最大，并求解。 （2）原料A、B的影子价格各为多少。
（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。
（4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？
2.11 某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如下表：
单位产品 A B 可用量（千克） 原料（千克） 工时（小时） 利润（万元） 1 2 4 2 1 3 200 300 （1） 请构造一数学模型使该厂总利润最大，并求解。
（2） 如果原料和工时的限制分别为300公斤和900小时，又如何安排生产？ （3） 如果生产中除原料和工时外，尚考虑水的用量，设两A，B产品的单位产品分
别需要水4吨和2吨，水的总用量限制在400吨以内，又应如何安排生产？
复习思考题