线性规划的对偶问题

第二章线性规划的对偶问题习题(1)maxz=10x1+x2+2x3st.x1+x2+2X3WIO4x1+x2+x3^20x.NO(j=1,2,3)(3)minz=3x1+2x2_(1)maxz=10x1+x2+2x3st.x1+x2+2X3WIO4x1+x2+x3^20x.NO(j=1,2,3)(3)minz=3x1+2x2_3x3+4x4st.x~2x+3x+4xW31234x2+3x3+4x4N—52x1~3x2~7x3—4x4=2=x1N0,x4W0,x2,x3无约束2.2已知线性规划问题maxz=CX,x1,x3N0,x2,x4无约束(4)minz=—5x1—6x2—7x3st.—x1+5x2—3x3N15—5x1—6x2+10x3W20x1—x2—x3=—5x1W0,x2N0,x3无约束AX=b,XN0。分别说明发生下列情况时，其对偶问题的解的变化：问题的第k个约束条件乘上常数久。乏0)；将第k个约束条件乘上常数久。乏0)后加到第r个约束条件上;目标函数改变为maxz=XCX(A^0);(4)模型中全部x1用3x'i代换。2.3已知线性规划问题minz=8x1+6x2+3x3+6x4st.x1+2x2+x4N33x+x+x+xN61234x3+x4=2TOC\o"1-5"\h\zx1+x3N2x.N0(j=1,2,3,4)写出其对偶问题；7已知原问题最优解为x*=(1,1,2,0)，试根据对偶理论，直接求出对偶问题的最优解。2.4已知线性规划问题minz=2x1+x2+5x3+6x4对偶变量st.2x1+x3+x4W8y12x1+2x2+x3+2x4^12y^x.N0(j=1,2,3,4)其对偶问题的最优解y1*=4；y；=1，试根据对偶问题的性质，求出原问题的最优解。2.5考虑线性规划问题maxz=2x1+4x2+3x3st.3x1+4x2+2x3W602x1+x2+2x3^40x+3x+2xW80123x.N0(j=1,2,3)写出其对偶问题用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；比较(2)和(3)计算结果。

2.6已知线性规划问题maxz=10x1^5x2s3jc+4^5x,~h2xnW812x.^0(j，=1,2)用单纯形法求得最终表如下表所示：x1x2x3x4bx201-14x110-712*00-寻2514试用灵敏度分析的方法分别判断:目标函数系数C1或c2分别在什么范围内变动，上述最优解不变；约束条件右端项b,b2,当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；问题的目标函数变为maxz=12x1^4x2时上述最优解的变化；(4)约束条件右端项由变为(4)约束条件右端项由变为f11］时上述最优解的变化。2.7线性规划问题如下：maxz=—5x1+5x2+13x3S~x1+x2+3x^20①12x1+4x2+10x3^90②先用单纯形法求解，然后分析下列各种条件下，’最优解分别有什么变化?约束条件①的右端常数由20变为30；约束条件②的右端常数由90变为70；目标函数中x3的系数由13变为8；x的系数列向量由(一1，12)t变为(0，5)t；增加一个约束条件③：2x+3x+5x<50；将原约束条件②改变为：10x+5x+10x<100。一……1232.8用单纯形法求解某线性规划问题得到最终单纯形表如下：cj基变量50401060Sx1x2xxAac0116bd102400efg给出a，b，c，d，e，f，g的值或表达式；指出原问题是求目标函数的最大值还是最小值；用a+?a，b+2b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本104030打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸y千克，每打日记本用白坯纸耳千80一一克，每箱练习本用白坯纸亏千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。产品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0销售价（元）1316（1）请构造数学模型使该厂利润最大，并求解。（2）原料A、B的影子价格各为多少。（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。（4）工厂可在市场上买到原料AoX厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？2.11某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如下表：单位产品AB可用量（千克）原料（千克）12200工时（小时）21300利润（万元）43（1）请构造一数学模型使该厂总利润最大，并求解。（2）如果原料和工时的限制分别为300公斤和900小时，又如何安排生产？（3）如果生产中除原料和工时外，尚考虑水的用量，设两A，B产品的单位产品分别需要水4吨和2吨，水的总用量限制在400吨以内，又应如何安排生产？复习思考题2.12试从经济上解释对偶问题及对偶变量的含义。2.13根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。2.14什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。2.15试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。2.16将气.，b，c的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。2.17判断下列说法是否正确（a）任何线性规划问题存在并具有唯一的对偶问题；（b）对偶问题的对偶问题一定是原问题；（c）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；（d）若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；（e）应用对偶单纯形法计算时，若单纯形表中某一基变量x.<0，又x.所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；11（f）若线性规划问题中