运筹学--第二章 线性规划的对偶问题.doc

第二章 线性规划的对偶问题习题二2.1 写出下列线性规划问题的对偶问题(1) max z 10x1 x22x3 (2) max z 2x1 x23x3 x4st. x1 x22 x310 st. x1 x2 x3 x4 54x1 x2 x320 2x1 x23x3 4xj 0 （j1,2,3） x1 x3 x41x1，x30，x2，x4无约束(3) min z 3x12 x23x34x4 (4) min z 5 x16x27x3st. x12x23x34x43 st. x15x23x3 15x23x34x45 5x16x210x3 20 2x13x27x3 4x42 x1 x2 x35x10，x40，x2，x3 无约束 x10， x20，x3 无约束2.2 已知线性规划问题max zCX，AX=b，X0。分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数（0）；（2）将第k个约束条件乘上常数（0）后加到第r个约束条件上；（3）目标函数改变为max zCX（0）；（4）模型中全部x1用3代换。2.3 已知线性规划问题 min z8x16x23x36x4st. x12x2 x433x1 x2 x3 x46x3 x42 x1 x3 2xj0（j1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。2.4 已知线性规划问题 min z2x1x25x36x4 对偶变量st. 2x1 x3 x48 y12x12x2x32x412 y2xj0（j1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。2.5 考虑线性规划问题 max z2x14x23x3 st. 3x14 x22x3602x1 x22x340x13x22x380xj0 （j1,2,3）（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。2.6 已知线性规划问题 max z10x15x2st. 3x14x295x12x28xj0（j1,2）用单纯形法求得最终表如下表所示：x1x2x3x4bx201x1101sj=cj-Zj00试用灵敏度分析的方法分别判断：（1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变；（2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；（3）问题的目标函数变为max z 12x14x2时上述最优解的变化；（4）约束条件右端项由变为时上述最优解的变化。2.7 线性规划问题如下： max z5x15x213x3 st. x1x23x320 12x14x210x390 xj0 （j1,2,3）先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？（1） 约束条件的右端常数由20变为30；（2） 约束条件的右端常数由90变为70；（3） 目标函数中x3的系数由13变为8；（4） x1的系数列向量由（1，12）T变为（0，5）T；（5） 增加一个约束条件：2x13x25x350；（6） 将原约束条件改变为：10x15x210x3100。2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下：cj基变量50401060Sx1x2x3x4ac0116bd1024sj=cj-Zj00efg（1）给出a，b，c，d，e，f，g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+Da，b+Db分别代替a和b，仍然保持上表是最优单纯形表，求Da，Db满足的范围。2.9 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸千克，每打日记本用白坯纸千克，每箱练习本用白坯纸千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10 某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。产品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0销售价（元）1316（1）请构造数学模型使该厂利润最大，并求解。（2）原料A、B的影子价格各为多少。（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。（4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？2.11 某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如下表：单位产品AB可用量（千克）原料（千克）12200工时（小时）21300利润（万元）43（1） 请构造一数学模型使该厂总利