线性规划的对偶问题

1、文档编码 : CX2Y10J2C8A10 HC5V6T1U4S5 ZP10D3T3O3V6其次章 线性规划的对偶问题习题2.1 写出以下线性规划问题的对偶问题1 max z 10 x1 x 22x3 2 max z 2x1 x 23x3 x 4st. x 1 x 22 x 310 st. x 1 x 2 x 3 x 4 5 4x1 x 2 x 320 2x 1 x 23x34 xj 0 （j 1,2,3 ） x 1 x 3 x 41 x1,x30,x2,x4 无约束3 min z 3x12 x 23x34x4 4 min z 5 x 16x27x3st. x 12x23x34x43 st. x

2、15x23x3 15 x23x34x45 5x16x210 x3 20 2x13x27x3 4x42 x1 x 2 x 3 5 x10,x40,x2,x3 无约束 x10, x 20,x3 无约束2.2 已知线性规划问题 max zCX,AX=b,X0；分别说明发生以下情形时,其对偶问题的解的变化：（1）问题的第 k 个约束条件乘上常数 （ 0）；（2）将第 k 个约束条件乘上常数 （ 0）后加到第 r 个约束条件上；（3）目标函数转变为 max z CX（ 0）；（4）模型中全部 x1用 3 1x 代换；2.3 已知线性规划问题min z 8x16x23x36x4st. x12x2 x 43

3、 3x1 x 2 x 3 x 46 x3 x 42 x1 x 3 2 xj 0（j 1,2,3,4 ）1 写出其对偶问题；2 已知原问题最优解为 偶问题的最优解；x*（1,1,2,0）,试依据对偶理论,直接求出对2.4 已知线性规划问题 min z 2x1x25x36x4 对偶变量st. 2x 1 x3 x 48 y 12x12x2x32x412 y 2xj 0（j 1,2,3,4 ）其对偶问题的最优解y1*=4；y2 *=1,试依据对偶问题的性质,求出原问题的最优解；2.5 考虑线性规划问题（1）写出其对偶问题max z2x14x23x3 st. 3x 14 x 22x360 2x1 x 2

4、2x340 x13x22x380 xj0 （j 1,2,3 ）（2）用单纯形法求解原问题,列出每步迭代运算得到的原问题的解与互补的 对偶问题的解；（3）用对偶单纯形法求解其对偶问题,并列出每步迭代运算得到的对偶问题 解及与其互补的对偶问题的解；（4）比较（ 2）和（ 3）运算结果；2.6 已知线性规划问题 max z10 x15x2 14x29 st. 3x5x12x28 xj 0（j 1,2 ）用单纯形法求得最终表如下表所示：x2x1x2x3x4b 3 140 1 x11 0 1 71 25 145 14j=cj-Z j0 0 试用灵敏度分析的方法分别判定：（1）目标函数系数c1或 c2 分

5、别在什么范畴内变动,上述最优解不变；（2）约束条件右端项 b1,b2,当一个保持不变时,另一个在什么范畴内变化,上述最优基保持不变；（3）问题的目标函数变为max z 12x14x2时上述最优解的变化；（4）约束条件右端项由9 变为 811 时上述最优解的变化；192.7 线性规划问题如下： max z 5x15x213x3st. x1x23x320 12x14x210 x390 xj0 （j 1,2,3 ）先用单纯形法求解,然后分析以下各种条件下,最优解分别有什么变化？（1） 约束条件的右端常数由 20 变为 30；（2） 约束条件的右端常数由 90 变为 70；（3） 目标函数中 x 3

6、的系数由 13 变为 8；（4） x1 的系数列向量由（1,12）T变为（ 0,5）T；（5） 增加一个约束条件：2x13x25x350；（6） 将原约束条件转变为：10 x15x210 x3100；2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下：cj基变量50 40 10 60 S x1x2x3x4a c 0 1 e 1 6 b d 1 0 2 4 j=cj-Zj0 0 f g （1）给出 a,b,c,d,e,f ,g 的值或表达式；（2）指出原问题是求目标函数的最大值仍是最小值；（3）用 a+ a,b+ b 分别代替 a 和 b,仍然保持上表是最优单纯形表,求 a,b 中意的范畴

7、；2.9 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品；该厂现有工人 100 人,每月白坯纸供应量为30000 千克；已知工人的劳动生产率为：每人每月可生产原稿纸 30 捆,或日记本 30 打,或练习本 30 箱；已知原材料消耗为：每捆原稿纸用白坯纸 10 千克,每打日记本用白坯纸 40 千克,每箱练习本用白3 3坯纸 80 千克；又知每生产一捆原稿纸可获利 2 元,生产一打日记本获利 3 元,生产3一箱练习本获利 1 元；试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变,当工人数不足时可招收临时工,临时工工资支出为每人每月40 元,就该厂要不要招收临时

8、工？如要的话,招多少临时工最合适？2.10 某厂生产甲、乙两种产品,需要（表中的消耗系数为千克 / 件）；A、 B两种原料,生产消耗等参数如下表产品原料甲乙可用量（千原料成本（元 / 千A 2 4 克）克）160 1.0 B 3 2 180 2.0 销售价13 16 （元）（1）请构造数学模型使该厂利润最大,并求解；（2）原料 A、B 的影子价格各为多少；（3）现有新产品丙,每件消耗 价格至少为多少时才值得投产；（4）工厂可在市场上买到原料3 千克原料 A 和 4 千克原料 B,问该产品的销售A；工厂是否应当购买该原料以扩大生产？在保持原问题最优基的不变的情形下,最多应购入多少？可增加多少利润

9、？2.11 某厂生产 A、B 两种产品需要同种原料,所需原料、工时和利润等参数如下表：单位产品A B 可用量（千克）原料（千克）1 2 200 工时（小时）2 1 300 利润（万元）4 3 （1） 请构造一数学模型使该厂总利润最大,并求解；（2） 假如原料和工时的限制分别为300 公斤和 900 小时,又如何支配生产？（3） 假如生产中除原料和工时外,尚考虑水的用量,设两 A,B 产品的单位产品分别需要水 4 吨和 2 吨,水的总用量限制在400 吨以内,又应如何支配生产？复习摸索题2.12 试从经济上说明对偶问题及对偶变量的含义；2.13 依据原问题同对偶问题之间的对应关系,分别找出两个问

10、题变量之间、解以 及检验数之间的对应关系；2.14 什么是资源的影子价格,同相应的市场价格之间有何区分,以及争论影子价 格的意义；2.15 试述对偶单纯形法的运算步骤,它的优点及应用上的局限性；2.16 将 aij, b, c 的变化分别直接反映到最终单纯形表中,表中原问题和对偶问题 的解各自将会显现什么变化,有多少种不同情形以及如何去处理；2.17 判定以下说法是否正确 a 任何线性规划问题存在并具有唯独的对偶问题；b 对偶问题的对偶问题确定是原问题；c 依据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之,当 对偶问题无可行解时,其原问题具有无界解；5 个 d 如某种资源的影子价格等于 k,在其它条件不变的情形下,当该种资源增加 单位时,相应的目标函数值将增大 5k；e 应用对偶单纯形法运算时,如单纯形表中某一基变量 xi0,又 xi 所在行的元素 全部大于或等于零,就可以判定其对偶问题具有无界解；