第2章对偶问题

第2章对偶问题判断下列说法是否正确：对偶问题的对偶问题一定是原问题；根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；已知为线性规划的对偶问题的最优解，若>0，说明在最优生产计划中的i种资源已完yy**ii全耗尽；已知为线性规划的对偶问题的最优解，若＝0，说明在最优生产计划中第i种资源一yy**ii定有剩余；若某种资源的影子价格等于k，在其它条件不变的情况下，当改种资源增加5个单位时，相应的目标函数值将增大5k；在线性规划问题的最优解中，如某一变量x为非基变量，则在原来问题中，无论改变它在j目标函数中的系数c或在各约束中的相应系数a，反映到最终单纯形表中，除该列数jij字有变化外，将不会引起其它列数字的变化。简答题、试述对偶单纯形法的优点及其应用的上局限性。、试述对偶单纯形法的步骤。、试解释对偶解的经济含义和影子价格在市场决策中的作用。间有何区别？以及研究影子价格的意义是什、什么是资源的影子价格？同相应的市场价格之么？:判断下列说法是否正确，为什么？（a）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；也一定无可行解；管原问题是求极大或极小，原问题可行（b）如果线性规划的对偶问题存在可行解，则其原问题（c）在互为对偶的一对原问题和对偶问题中，不解的目标函数都一定不超过其对偶问题可行解的目标函数。k，在其5k吗？若某种资源的影子价格等于他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数最大值将增加已知y*为某线性规划问题的对偶问题最优解中的第i分量，若y*＝0，能否肯定在最优生产ii计划种第i种资源一定有剩余？写出对偶问题写出下列线性规划问题的对偶问题maxZ10x2xx312

xx2x101234xxx20123x,x,x0123写出下列线性规划问题的对偶问题maxZ2xx3xx4123x2xxx512342xx3x4123xxx1134x,x0,x,x无约束1324写出下列线性规划问题的对偶问题minZ3x2x3x4x4123x2x3x4x31234x3x4x522x3x7x4x2341234x0,x0,x,x无约束1423写出下列线性规划问题的对偶问题minZ5x6x7x312x5x3x151235x6x10x20123xxx5123x0,x0,x无约束123写出下列线性规划问题的对偶问题maxZ2xx5x3122x3x5x21233xx7x31x6x52313x,x,x0123写出下列线性规划问题的对偶问题maxZxxx3122xx5x12123x2x7x6123x6x413x,x,x0123写出下列线性规划问题的对偶问题minZ4x2x3x1232xx5x6123x2x7x4123xx213x无约束,x0,x0123写出下列线性规划问题的对偶问题：MinZ2x2x4x1232x3x5x21233xx7x3s.t.123x4x6x5123x,x,x0123写出下列线性规划问题的对偶问题：MinZx2x3x1232xx3x11233xx2x51xx3x4x1,x,0,x无限制s.t.2312323写出下列线性规划问题的对偶问题：MaxZ2xx4x1232x3xx11233xxx4s.t.123xx413x10,x0,x无限制23写出下列线性规划问题的对偶问题：MaxZ2x7x5xx3x12345x5x4x6x2x512345s.t.2x3xx2x6x912345x0,x无限制51~4写出下面线性规划问题的对偶问题maxz5x2x12xx3122x3x51x,x0212写出下面线性规划问题的对偶问题maxz5x6x12x2x512x5x312x无限制,x012设有原始问题maxz3x2x5x312x2xx5601233x2x420约束条件：13x4x40012x,x,x0123写出以上原始问题的对偶问题。写出下面线性规划问题的对偶问题minzmncxijiji1j1i1,m,nxaijij1j1,n,mxbijji1x0i1,,m;j1,,nij如下线性规划模型：minZxxxxxx12345xx416xx812xx1023xx7约束条件：34xx1245xx456x,x,x,x,x,x0123456写出以上原始问题的对偶问题，在通过对偶问题求出原始问题的最优解。对偶单纯形法试用对偶单纯形法求解下列线性规划问题。minZxx122xx412x7x713x,x012试用对偶单纯形法求解下列线性规划问题。minZ8x16x12x123x4x2122x4x313x,x,x0123试用对偶单纯形法求解下列线性规划问题。minZ50x40x123x2x35125x6x60132x3x3012x,x012试用对偶单纯形法求解下列线性规划问题。minZx2x3x312xxx4123xx2x8123xx223x,x,x0123试用对偶单纯形法求解下列线性规划问题。minZ2x2x12x4xx8123x2x2x6123x,x,x0123试用对偶单纯形法求解下列线性规划问题。minZ3x2xx4x41232x4x5xx012343xx7x2x212345x2xx6x151234x,x,x,x01234用对偶单纯形法求解：minZxxxxxx123456xx416xx812xx1023xx7约束条件：34xx1245xx456x,x,x,x,x,x0123456用对偶单纯形法求解：minz2x3x122x3x3012x2x1012xx012x5,x012用对偶单纯形法求解minz4x12x18x312x3x3132x3x5约束条件：23x,x,x0123．考虑线性规划问题：MaxZ5x2x3x3x5x2x3012123s.t.x5x6x40123x,x,x0123（1）写出对偶问题；（2）求解对偶问题通过对偶问题求下面问题的最有解minz5x6x3x3125x5x3x50123xxx201237x6x9x301235x5x5x351232x4x15x1012312x10x9012x10x2023x,x,x0123用单纯形法求解下面的线性规划问题：(2)MinZ3x2xx4x4(1)MinZ5x2xx1232x4x5xx01235x2xx41xx23x2447x323123s.t.6x3x5x10..st125x2xx6x151x,x,x0231234x,x,x,x01231234．用对偶单纯形法证明下面的线性规划问题无解：MinZ3x2xx123xxx6123xx4s.t.13xx32x,x,x03123设有线性规划问题minz2x3x122x3x3012x2x1012xx012x5,x012（1）用图解法解以上问题(2)写出它的对偶问题用大M方法解下面的问题，再从最优表格中求对偶解。maxz5x2x3x312x5x2x30123约束条件：x5x6x40123x,x,x0123已知线性规划问题x3xx81242xx612约束条件：xxx6234xxx9123x,x,x,x01234要求：（1）写出其对偶问题；（2）已知原问题最优解为X*2,2,4,0，试根据对偶理T论，直接求出对偶问题的最优解。考虑问题maxz8x6x12xx3/512xx2约束条件：12x,x012用图解法证明原始问题和对偶问题都没有可行域。因此。当一个问题不可行时，它的对偶问题不一定无界。灵敏度分析已知线性规划问题maxZ5x5x13x312xx3x2012312x4x10x90123x,x,x0123先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1）第一个约束条件的右端项常数由20变为30；（2）第二个约束条件的右端项常数由90变为70；（3）目标函数中3x的系数由13变为8；10（4）x的系数列向量由变为；12512x3x5x50；（5）增加一个约束条件12310x5x10x100（6）将原第二个约束条件改变为123、某厂准备生产三种产品A、B、C，需消耗劳动力和原料两种资源，其有关数据如下表：单位消耗产品资源ABC资源限量劳动力63415554530原料单位利润33（1）用单纯形法总利润最的大生产计划。（2）分别求出料的影子价格。若原料不够，可到市场上购买，市场价格为0.8元/单位。问是否要购进，最多可购进多少？总利润增加多少？（3）当产品A、C的单位利润在何范围变化时，最优生产计划不变？确定劳动力和原（4）劳动力可减少多少二不改变最优计划？2xx3x10（5）现需增加电力的限制条件，试求出最优的生产方案。123、已知线性规划问题maxZ2xxx123xxx6123x2x412x,x,x0123用单纯形法求解的最优表如下：cj2－1100x50bCB2XBX1X5x110x21x31x4160311110z=500－3－1－20j试说明分别发生下列变化时，最优解分别有什么变化？（1）目标函数变为maxZ2x3xx；12363变为；44x2x2（2）约束条件的右端项由（3）增加一个约束条件。12．一个最大化的线性规划问题有四个非负变量，三个“”型约束条件，其最优表为：Xx1xxxxx6B2345bx7012/312/3014/3x4x6x02-1001-1/3410/31111/301/301/3024/304/301/3j（1）列出此问题的对偶问题；（2）写出对偶问题的最优解。全部约束条件都是“”的最大化问题，它的最优表如下：．有一Xxxxxx12345bB011/2-1/202x210-1/83/803/2x1x5001-214001/41/40j其中x，x是决策变量，1x，x，x是松弛变量。3452（1）在保持最优解基不变的情况下，若要把一个约束条件的右端项扩大，用扩大哪一个？为什么？最大扩大多少？求出新的目标函数值；c,c是目标函数中x和x的系数，求使最优基变量（x,x,x）保持最优（2）设1212152c/c的范围。性的比值12．一个工厂利用三种原料能生产五种产品，其有关数据如下表：可利用材料数量（千万件材料所用材料数（千克）克）原材料ABCDE甲乙丙0.510.500.550.500.51.51120.5111110.5万件产品利润41051010.5（万元）（1）确定一种最优生产计划；c,c做灵敏度分析；（2）对目标函数的系数14b,b做灵敏度分析；（3）对约束条件中的12（4）如果引进新产品F要用原料甲、乙、丙分别为0.5，1，0.5（千克）。而每单位F可得利润10万元，（5）如果又增加煤耗不允许超过20吨的限制，而生产每单位A，B，C，D，E产品分别需要煤3，2，1，2，1（吨），问是否需要改变原来的最优方案？问：产品是否有利于投产？它的利润多少时才有利于投产？已知线性规划问题maxz2xxx312xxx6123约束条件：x2x412x,x,x0123先用单纯形法求解，在分析在下列条件单独出现的情况下最优解的变化。（a）目标函数变为maxz2x3xx12363（b）约束右端项由变为44（c）增加一个新的约束条件x2x213已知线性规划问题maxz3x2x12x2x6122xx812xx112x22x,x012已知用单纯形法求的最有解的单纯形表如下表所示。试分析在下列各种条件单独出现的情况下，最优解将如何变化。x1x2xx4x5x630112/3-1/3-1-1/32/31002300x4/310/