- 230.00 KB
- 2022-08-10 发布
- 1、本文档由用户上传，淘文库整理发布，可阅读全部内容。
- 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，请立即联系网站客服。
- 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细阅读内容确认后进行付费下载。
- 网站客服QQ：403074932
第二章.对偶理论与灵敏度分析1.已知线性规划问题：maxz=c1x1+c2x2+c3x3a\\a2\st.0用单纯形法求解得最终单纯形表如下表所示:(a)求，°22，°23和勺上2(b)求56疋32.已知矩阵A及其逆矩阵如下:「210_「1/2-1/40_A=020A-1=01/20401-211试根据改进单纯形法中求逆矩阵的方法原理求下述矩阵B的逆矩阵,己知5-14'250__5__11/4_0-10A'1•-1=-1/2441••■4-7C答：先设_111/20__l/25/2O'C'1=0-20•A"1=0—■100-1412-61~25rT_ll/2_=0-12C1■2=-2441有1-13•••B\n「1011/26-■-9/26-1/2611/26-B'{=01-2/13•C_,=8/26-2/26-4/26_00-1/13__4/2612/26-2/26_3.已知线性规划的原问题与对偶问题分别为：(P)原问题：maxz=CX(D)对偶问题：minwH”[AXCst.{st{[x>o[y>o若y*为对偶问题最优解，又原问题约束条件右端项用产替换之后其最优解为乂，试证明有CXo__设D的最优解为0,因有CZ=Yhf有厂是D的可行解，故有Yh0(b)对偶问题最优解为厂=(4,2)5.已知线性规划问题:\nmaxz=5x{+3x2+6x3x{+2x2+x3<182x{+x2+3x3=16stAx{+x2+x3=10XpX2>0,花无约束(a)写出其对偶问题'(b)已知原问题用两阶段法求解时得到的最终单纯形表如下试写出其对偶问题的最优解。536-60西兀2屯’為"兀40x48010015X\1412000-6叮401-110CJ一ZJ0-1000答：(a)其对偶问题为minw=18开+16y2+10%必+2力+北》5(1)stV2必+j2+>3(2)s・必+3旳+%=6(3)X>0,y29y3无约束(b)设第(i)个约束条件的松弛变量为九，第(2)个约束条件的松弛变量为儿2,由原问题用两阶段法求得之最终单纯形表知儿1二°，几2=1，H=°,代入约束条件(1)〜⑶有”必+2%+%=5<2y+y2+y3-l=3必+3力+为=6解得：(必』2』3)=(°，1，3)6•己知线性规划问题:minz=2坷+£+2x3\nst.<-Xj+x2-<6X,0,兀3无约束其最优解为州=一5宀=0，®=-1(a)求k的值；(b)写出并求其对偶问题的最优解。解：先写出其对偶问题如下:maxw=4y}+6场_X_旳二2X+)‘2§_1X_灯2=2X无约束,旳50由/=『机互补松弛性质得[-X-『2=2〔4必+6儿=12解得X=0,y2=-2,代入求得k=1.7•己知线性规划问题maxz=CX,AX=b,X>0,分别说明发生下列情况时，其对偶问题的解的变化:(a)问题的第仝个约朿条件乘上常数免(2工0)；(b)将第k个约束条件乘上常数久(久H0)后加到第7个约束条件乘上;(C)目标函数改变为maxz=ACX(2工0)；(d)模型中全部州用％；代换。解：(a)•・・对偶变量y-cBB-\^k个约束条件乘上常数2,即旷的R列\n丄将为变化前的刁，由此对偶问题变化后的解（*，必，…y；，…必）=（卩，）2…+九，…）q）;亠亠乂二人儿,y；=必（心厂）；（b）与前类似，（C）%=切（，=1,…，加）；（d）x（‘=1，…，加）不变。8•已知线性规划问题：nmax=》CjXj;=1工嗨Xj0(;=1,...,/?)若（y：，/，•••*：）为其对偶问题的最优解。又若原问题约束条件的右端项勺变换为以,这时原问题的最优解变为（球用，…，几）,试证ny明闫Cjfj<*y：/=!\n解：原问题右端项变为b；后，其对偶问题为：minz=》bj%Z=1mX^c.（j=1,...,/?）stAz=i）：＞0（/=由于约束条件不变，（X,/,•••」;）必为上述问题的可行解。根据对偶理论有:nZ./=!Cjfj<£b；y：/=!9•已知线性规划问题:maxz=X]+兀?\n-Xj+x2+x3<2stA一2xl+x2-x3<1x^x2,x3>0试应用对偶理论证明上述线性规划问题无最优解。解：该问题存在可行解，如X=(0,0,0)；又上述问题的对偶问题为:minw=2x+旳-x-2旳st.=1X.>0((z=1,2....h)若第i资源的影子价格为yi，工(2a、j)Xj=2bj-(a)若第一个约束条件两端乘以2,变为,X是对应这个新的约束条件的影子价格，求X与H的关系；(b)令盯=3若用(和/3)替换模型中所有的西，问影子价格X是否变化？若X】不可能在最优基屮出现，问兀「有否对能在最优基中岀现；\nmaxz二工2C/X,(a)如目标函数变为>=«'，问影子价格有何变化？解：(a)^=1/2>1；(b)影子价格必不变，又舛不在最优解中岀现，为‘也不可能在最优解中出现，(c)影子价格X也增大两倍。2.12下述线性规划问题maxz=8召+4x2+6x3+3x4+9x5%,+2x2+3x3+3兀4+3x5<180(资源1)x,+2x2+3兀3+3x4+3x5<270(资源2)st」£+3兀2+2兀3+x4+3x5<180(资源3)xj>0(j=1.2...5)己知最优解中的基变量为兀3X]-兀5且己知13、-1<11-311241=69-3272\13丿(2-310耍求根据上述信息确定三种资源各口的影子价格。解:三种资源的影子价格分别为4/3,1,8/3o2.13若线性规划问题minz=cX约束于AX=b,x>Qf具有最优解，试运用对偶性质证明下述线性规划问题不可能具有无界解，minz=fX约束与AX=b,x>0是可以取任意值的向量。解：分别写出两个问题的对偶问题见L1,L2：L、:maxw=YhL2:maxw=Yd[YA>C[YA>CSt:o[r>o显然厶的最优解是厶的可行解，由此厶的原问题具有下界。2.14用对偶单纯形法求下列线性规划问题(a)minz=+3x2+4x3£+2x2+x3>3<2xj-x2+3x3>4m»0XiX。X3X4X5-3X22/5-2X|11/50110-1/57/5-2/5-1/51/5-2/5Cj・Zj00-9/5-8/5-1/5\nminz=4兀］+12x2+18x3x}+3兀3A3<2x2+2兀3>5(b)J-3-°Xix2X3X4x5-18X311/301-1/30-12X23/2-1/3101/3-1/2Cj・Zj■200・2・62.15证明当用对偶单纯形法求解线性规划问题时，若有br<0而^-0则对偶问题具有无界解。解：设用⑷迭代前对偶问题的目标函数值，用母替换兀后，新解的目标函数值为有w'=w+0br=(一bj0=minj—~/a”<0|因ali-0,故&可任意大不受限制，又(一$)>°,故就可无限减小。2.16已知线性规划问题2西+4兀51600(1)6%.4-2x2<1800(2)x2<350(3)xex2>0用单纯形法求解吋得到的最终的单纯形表如下：XiX：X,X.>X5Xi100101/20・2X450000-3110\nX235001001Cj-Zj00-3/20・2其中约束条件(3)变为兀2^50°,试分析最优解的变化。解：变化后直接反映到表中如下所示：XiX2X3x4X5X]-100101/20・2X4200000-311050001001PfZj00-3/20・2再用对偶单纯形迭代最优解为X二(0,400,0,1000,100),maxz=3200o2・17某厂生厂甲、乙、丙三种产品，已知有关数据如下表，试回答下面的问题:消耗、产品定额甲乙丙原料拥有量A63545B34530单件利润415(a)建立线性规划模型，求使得该厂获利最大的生产计划？(b)若产品乙、丙的单件利润不变，则产品的利润在什么范圉变动时，上述最优解是不变的；(c)若有一种新产品丁，其原料消耗定额，A为3单位,B为2单位，单件利润为2.5单位。问该种产品是否值得安排生产，并求新的最优计划？(d)若原材料A市场紧缺，除拥有量外一时无法购进，而原料B如数量不足可以去市场购买，单价为0.5,问该厂是否购买？购买多少为宜？(e)由于某种原因，该厂决定暂停甲产品的生产，试从新确定新的生产计划.解：(a)以％兀2,兀分别代代表甲、乙、丙产品产量，则有X=(5,0,3)最大盈利Z*=35；(b)产品甲的利润变化范围是［3,6］；(c)安排生产丁有利，最优化计划为了安排生产产品丁15件，而xf=x2=x3=O;\n(b)购进原材料B15单位最为合适；(c)最新计划为X*=(0,0,6),Z*=30.2.18某厂生产I、II、III三种产品，分别经过A、B、C三种设备加工，已知生产单位各种产品所需要的设备台吋，设备的现有加工能力以及每件产品的预期的利润如下表：(a)求获利最大的产品计划？(b)产品III每件的利润增加到多大时才值得安排生产？如果产品III的每件利润增加到50/6元，求最优计划的变化？(c)产品I的利润在多大范围变化吋，原最优计划保持不变？(d)设备A的能力如为100+100，确定保持最优基不变的&的变化范围？(e)如有一种新产品，加工一件设备A、B、C的台时为1、4、3小时，预期每件的利润为8元，是否值得安排生产？(f)如合同规定该厂至少生产10件产品III,试确定最优的变化？IIIIII设备能力(台时)A111100B1045600C226300Cj・zj1064解：西无內分别代代表I、II、III三种产品的产量，则有：(X*=(100/3,200/3,0).(b)X=(175/6,275/6,25).(c)6We］<15.(d)~4W&55；(e)该新产殆值得安排生产。(f)x*=(95/3,175/3,10)2.19某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品.该厂现有工人100人，每月白坯纸的供应量为30000千克.已知工人的劳动生产率为:每人每月可生产原稿纸30捆,或生产日记本30打，咸练习本30箱.已知原材料的消耗为:每捆原稿纸用白坯纸10/3千克,每打日记本用白坯纸40/3千克，每练习本用白坯纸70/3千克.又知道每生产一捆原稿纸可以获利2元住产一打日记本获利3元,生产一箱练习本获利1元.试确定：(1)现有生产条件下的获利最大的方案.(2)如白坯纸的供应量不变，当工人数不足可以招收临时工，临时工的工资支出为每人每月40天，则该厂要不要招收临时工，招多少最为合适？解：(1)分别用西02."代表原稿纸，日记本和练习本的每月生产量。建立线性规划模型并求解得最终的单纯形表如下：\nXiX2X3x4X5X22000017/31/10-10X]100010-4/3-1/1040Cj・Zj00-10/3-1/10-50(2)临吋工影子价格高于市场价格，故应招工。用参数规划计算确定招200人最为合适。2.20某厂准备生产A,B,C三种产品，它们都消耗劳动力和材料，有关数据见表所示:(a)所确定获利最大的产品生产计划：(b)产品A的利润在什么变动时，上述最优计划不变；(c)如设计一种新的产品D,单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？(d)如劳动力数量不变，材料不足时可以从市场上购买，每单位0.4元，问该厂要不要购进材料扩大生产，购多少为宜？消耗^产品资源ABC拥有量63545劳动力材料34530单位产品利润314解：(a)建立线性规划模型，模型中西兀2,心代表a、B、C的生产量。用单纯形法求解得最优计划的单纯形表如下：XiX2x3X4x5X)51-1/301/3-1/3X33011-1/52/5Cj-zj0-20-1/5-3/5(b)产品A的利润在L55」范围内变化时，最优计划不变。(a)安排生产新产品D时合算的。(⑴材料市场价格低于影子价格，故购进是合理的。用参数规划计算时确定购15单位最为合适。
微信/支付宝扫码支付下载