线性规划的对偶问题0001

《线性规划的对偶问题0001》由会员分享，可在线阅读，更多相关《线性规划的对偶问题0001（7页珍藏版）》请在装配图网上搜索。

1、第二章线性规划的对偶问题习题2.1写出下列线性规划问题的对偶问题(1) max z =10X+ x2+2x3st.x + x +2 x W101234x + x + xW20123% N0 (j = 1,2,3)(3) min z =3x +2 x 3x +4x1234st. x2x+3x+4xW31234x +3x +4x N52342x 3x 7x 4x =21234=x N0, x W0, x , x 无约束142,3(2) max z =2x + x +3x + x1234st. x+ x + x + x W5123421x x2+3x3=4x x3+ x41x , x N0, x ,

2、 x无约束1324(4) min z =5 x16x27x3st. x1+5x23x3 N155x16x2 + 10x3 W20x x x =5123xW0, x20, x3 无约束2.2已知线性规划问题maxz=CX, AX=b, XN0。分别说明发生下列情况时，其对偶问题的解的变化:(1) 问题的第k个约束条件乘上常数入(入#0)；(2) 将第k个约束条件乘上常数入(入#0)后加到第r个约束条件上;(3) 目标函数改变为max z=XCX (入#0)；(4) 模型中全部用3 x1代换。2.3已知线性规划问题min z=8x +6x +3x +6x1234st. x1+2x2+ x433x

3、+ x + x + x N61234x3 + x4=2x1+ x3N2%N0 (j = 1,2,3,4)(1) 写出其对偶问题；(2) 已知原问题最优解为x*=(1, 1, 2, 0),试根据对偶理论，直接求出对 偶问题的最优解。2.4已知线性规划问题min z=2x+x+5x+6x对偶变量1234st. 2x +x + x W8y13412x +2x +x +2x W12y12342*0 (j = 1,2,3,4)其对偶问题的最优解y*=4； y*=1,试根据对偶问题的性质，求出原问题的最优 12解。2.5考虑线性规划问题max z=2x1+4x2+3x3st. 3x+4 x+2x W601

4、232x + x +2x W40123x +3x +2x W80123卒0 (j = 1,2,3)(1) 写出其对偶问题(2) 用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的 对偶问题的解；(3) 用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题 解及与其互补的对偶问题的解；(4) 比较(2)和(3)计算结果。2.6已知线性规划问题 max z=10x1+5x2st.3%+4x2W95x1+2x2W8%N0 (j = 1,2)用单纯形法求得最终表如下表所示:x1x2x3xbx201-134x110一 71b 二c-Z.00一 154_2514试用灵敏度分析的方法分

5、别判断:(1) 目标函数系数匕或匕分别在什么范围内变动，上述最优解不变；(2) 约束条件右端项bi, b2,当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；(3) 问题的目标函数变为max z =12xi+4x2时上述最优解的变化;(4) 约束条件右端项由f 9变为时上述最优解的变化。* 8 )1?2.7线性规划问题如下：max z=一5xi+5x2+13x3st.x +x +3x W2012312x+4x+10x W90123卒0 (j = 1,2,3)先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化?(1) 约束条件的右端常数由20变为30；(2) 约束条件的右

6、端常数由90变为70；(3) 目标函数中x3的系数由13变为8；(4) 乂的系数列向量由(一1，12) t变为(0，5) t；(5) 增加一个约束条件：2x +3x +5x 50；123(6) 将原约束条件改变为：10x+5x+10x W100。 1232.8用单纯形法求解某线性规划问题得到最终单纯形表如下:Cj基变量50401060SXX2X3X4ac0116bd102400efg(1) 给出a, b, c, d, e, f, g的值或表达式；(2) 指出原问题是求目标函数的最大值还是最小值；(3) 用a+Aa, b+Ab分别代替a和b,仍然保持上表是最优单纯形表，求Aa, b满足的范围。2

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

8、10某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表 (表中的消耗系数为千克/件)。产品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0销售价（元）1316（1）请构造数学模型使该厂利润最大，并求解。（2）原料A、B的影子价格各为多少。（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售 价格至少为多少时才值得投产。（4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保 持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？2.11某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如 下表：单位

9、产品AB可用量（千克）原料（千克）12200工时（小时）21300利润（万元）43（1）请构造一数学模型使该厂总利润最大，并求解。（2）如果原料和工时的限制分别为300公斤和900小时，乂如何安排生产？（3）如果生产中除原料和工时外，尚考虑水的用量，设两A，B产品的单位产品分另蠕要水4吨和2吨，水的总用量限制在400吨以内，乂应如何安排生产？复习思考题2.12试从经济上解释对偶问题及对偶变量的含义。2.13根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。2.14什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。2.15试述对偶

10、单纯形法的计算步骤，它的优点及应用上的局限性。2.16将ab，c的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题 的解各自将会出现什么变化，有多少种不同情况以及如何去处理。2.17判断下列说法是否正确(a) 任何线性规划问题存在并具有唯一的对偶问题；(b) 对偶问题的对偶问题一定是原问题；(c) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(d) 若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；(e) 应用对偶单纯形法计算时，若单纯形表中某一基变量0，乂所在行的元素 全部大于或等于零，则可以判断其对偶问题具有无界解；(f) 若线性规划问题中的bi，c，值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(g) 在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无 论改变它在目标函数中的系数cj或在各约束中的相应系数a反映到最终单纯形表 中，除该列数字有变化外，将不会引起其它列数字的变化。