运筹学第二章线性规划的对偶理论复习题

第二章线性规划的对偶理论习题1、某厂生产A、B、C三种产品，每种产品要经过Ⅰ、Ⅱ、Ⅲ三道工序加工，设每件产品在每道工序上加工所消耗的工时，每道工序可供利用的工时上限，以及每件产品的利润如表2-1所示.表2-1消工序耗产品ⅠⅡⅢ单件利润（元）ABC342212133200300250可用工时604020试列出使总利润昀大的线性规划模型，并写出它的对偶问题，同时，就这个对偶问题作出经济上的解释.解：设123xxx，，分别表示A、B、C各产品的数量，Z表示总产值则：12123123123max200300250.42602403320(1,2,3)0izxxstxxxxxxxxxxi=++++≤++≤++≤=≥　3　　　2　　　　　　3xy３min604020.230023250wyystyyyyyyyyyyyy=++++≥++≥++≥≥≥≥１２１２３１２３１２３１２３原问题的对偶问题为　　3200　　　４3　　　2　　　0，0，0经济解释：y1，y2，y3分别表示给别人代工时所得收入，对厂方而言，w越大越好，但定价不能太高，要对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理，厂方不会吃亏，对方也容易接受。2、写出下列线性规划问题的对偶问题：(1)321210maxxxxz++=s.t.102321≤++xxx20321≤++xxx1)3,2,1(0=≥jxjmin1020.1012wystyyyyyyyy=++≥+≥+≥≥≥１２１２１２１２１２解：　　　　　2　　0，0y(2)321422minxxxz++=s.t.2532321≥++xxx373321≤++xxx564321≤++xxx)3,2,1(0=≥jxjmax235.32427640wyyystyyyyyyyyyyyy=++++≤++≤++≤≥≤≤１２１２３１２３１２３１２３解：　2　　3　　5　　0，0，３(3)321365maxxxxz++=s.t.522321=++xxx35321≥−+−xxx8374321≤++xxx1x无约束，，02≥x03≤xmin538.45576330wyyystyyyyyyyyyyyy=++−+=++≥−+≤≤≥１２３１２３１２３１２３１２３解：　　　2　　2　　自由，0，(4)43214323minxxxxz+−+=s.t.34324321≤+−−xxxx2543432−≥++xxx247324321=−−−xxxx无约束3241,,0,0xxxx≤≥解：max3.2353374440wyyystyyyyyyyyyyyyyy=−++≤+−+−+−≥≤≥≤１２３１２１２３１２３１２３１２３52　　　-2＝2　　-3＝-3　　4　　0，0，3、应用对偶理论证明线性规划问题.21maxxxz+=s.t.2321≤++−xxx12321≤−+−xxx0,,321≥xxx有可行解，但无昀优解.证明：是线性问题的可行解，即该问题存在可行解；000x⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠又∵其对偶问题为：min2.2110,0201wyystyyyyyyyyyyyy=+−≥+≥−≥≥≥≥−≤１２１２１２１２１２１２１２　-　　　　　　0，0-这与约束条件（）不符该对偶问题无可行解原问题无昀优解。∵∴∴∴4、应用弱对偶定理，证明线性规划问题33212maxxxxz++=s.t.2321≤−+xxx1321=+−xxx22321≥++xxx无约束321,0,0xxx≤≥的昀大值不超过1.证明：该线性问题的对偶问题为：00min22.2121001001(2,1,2)10maxTwyyystyyyyyyyyyyyyYcxybz=++++≥−+≤++=≥≤=⎛⎞⎜⎟≤==⎜⎟⎜⎟⎝⎠≤１２３１２３１２３１２３１２３　　　　　-　　0，自由，易知（，，）是对偶问题的一个可行解，由对偶问题的对偶定理可得：即昀大值不超过1∴15、应用对偶理论，证明线性规划问题2123maxxxz+=s.t.4221≤+−xx142321≤+xx321≤−xx0,21≥xx有昀优解，并证明其对偶问题也有昀优解.证明：对偶问题4min4143.3324023wyyystyyyyyyyyy=++++≥+−≥≥≥≥−１２３１２３１２３１２３TT　-　　2　　0，0，由题易知X=（3，0）是原问题的一个可行解，Y=（0，1，0）是对偶问题的一个可行解由对偶问题的推论可得它们都有昀优解。即得证。26、已知标准线性规划问题cxz=maxs.t.Ax=bx≥0具有昀优解，假设将右端向量b改为另一向量d，如果改变后的问题是可行的，试证该问题一定有昀优解.7、考虑下列原始线性规划32132maxxxxz++=s.t.52321≤++xxx12432321=++xxx)3,2,1(0=≥jxj(1)写出其对偶问题；(2)已知（3,2,0）是上述原始问题的昀优解，根据互补松弛定理，求出对偶问题的昀优解；(3)如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格.解：（1）对偶问题：min512.223143wyystyyyyyyyy=++≥+≥+≥≥１２１２１２１２１２　　　　　2　　0，无符号限制（2）由题知原问题的昀优解为*(320)Tx=，，；5由互补松弛定理得：在对偶问题中对应第一，二个约束为紧，第三个约束条件为松，即，**12*1**12*2**12224311243yyyyyyyy⎧+=⎧=⎪⎪+=⇒⎨⎨=⎪⎪⎩+≥⎩∴对偶规划问题的昀优解*141y=（，）（3）影子价格为y1=4：8、已知线性规划问题4321432maxxxxxz+++=s.t.203234321≤+++xxxx202324321≤+++xxxx)4,,1(0L=≥jxj其对偶问题的昀优解为，试根据对偶理论求出原问题的昀优解.2.0,2.1*2*1==yy解：先写出其对偶问题。min2020.21283324wystyyyyyyyyy=++≥+≥≥+≥≥≥１２１２１２２１２１２　　　3　　　　　　　0，0yy+１22y1+3y2∴对偶规划问题的昀优解**1**12**121.20.200yyxxyy====Q２，，代入约束条件，知第1，2约束条件成立严格不等式，由互补松弛定理，原规划昀优解中相应变量又，不为，则在原问题规划中对应的约束条件为紧，得*334*3444232032204xxxxxx⎧=⎧+=⎪⎪⇒⎨⎨+==⎪⎪⎩⎩∴原对偶规划问题的昀优解*0,0,4,4x=（）69、已知某线性规划问题的昀优单纯形表如表2-2所示，表中为松弛变量，问题的约束为≤形式54,xx(1)写出原线性规划问题；(2)写出原问题的对偶问题；(3)直接由表2-2写出对偶问题的昀优解.解：111221221/210011/61/21/2xxNBxx⎛⎞⎛⎞⎜⎟⎜⎟−⎝⎠⎝⎠⎛⎞⎛⎞==⎜⎟⎜⎟−⎝⎠⎝⎠-1-1　0（1）由表知B；　Ｉ=1/3　　B令则　　表2-23x5xBx1x2x4x111221221/2010201/61/301131/21/2011/21/61/31xxBBxxaNNb⎛⎞⎛⎞⎛⎞⎛==⇒⎜⎟⎜⎟⎜⎟⎜−⎝⎠⎝⎠⎝⎝⎠⎛⎞⎛⎞⎛⎞⎛⎞==⇒=⎜⎟⎜⎟⎜⎟⎜⎟−−−⎝⎠⎝⎠⎝⎠⎝⎠-1-1B　　B　　　⎞=⎟⎠b⎛⎞=⎜⎟⎝⎠1313220125/253115/21061/2042101/61/3442AbCCCCCC⎛⎞⎛⎞==⇒⎜⎟⎜⎟−⎝⎠⎝⎠=⎧⎛⎞−=−−⎨⎜⎟⇒=−⎝⎠⎩⎛⎞+−=−⇒=−⎜⎟⎝⎠-1　　　　　∴；B　　　　　　　（，）（，）1　　　（，-2）-112323123max.10(1,2,3)0izxxxstxxxxxxi=−++≤−+≤=≥　　　　原线性问题为：　　6210　　　　2　　　5　　　　3　　　　　　∴2min510.36210wyystyyyyyyy=+≥−≥−+≥≥≥１２２１２１２１２（）　　　　　2　　0，0b3x01/211/205/21x1-1/20-1/61/35/20-40-4-27**4535*3(5/205/2)40;0034224TxZxxyyyyyyyyyyyY=======⎧⎧⎪⎪−−−⇒=⎨⎨⎪⎪+=⎩⎩=2１１２４２１２4T*（），，；　　　　　　　　　＝6　　即＝2　=10　　　（4，2）w=40；10、某厂拟生产甲、乙、丙三种产品，都需要在A、B两种设备上加工，有关数据如表2-3所示.(1)如何充分发挥设备能力，使产品总产值昀大？(2)若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？解：（1）设123xxx，，分别表示甲、乙、丙各产品的数量，Z表示总产值则：123123123max32.22500(1,2,3)0izxxxstxxxxxxxi=++++≤++≤=≥　　　　　2　　　400化为标准形：12312341235max32.24002500(1,2,345)0izxxxstxxxxxxxxxi=++++=++==≥　　　+　　　2+　　　　，，C32100CBXBX1X2X3X4X5b0X4121104000X521201500检验数321000X403/201-1/2150表2-3单耗（台时/件）产品设备甲乙丙设备有效台时（每月）A121400B212500产值(千元/件)32183X111/2101/2250检验数01/2-20-3/22502X20102/3-1/31003X1101-1/32/3200检验数00-2-1/3-4/3-800**(200,100)800;TxZ==；　2min400500.23221wyystyyyyyyyy=++≥+≥+≥≥≥１２１２１２１２１２（）原问题的对偶问题为　　　　　2　　　　　　0，0此时，y1，y2分别表示出租A，B设备所得利润，由（1）中的昀优表得=1/3，即如出租A设备可获得1000/3元，而1000/3350*1y所以不合算。11、已知某实际问题的线性规划模型为∑==njjjxcz1maxs.t.∑==≤njijijmibxa1),,2,1(L),,2,1(0njxjL=≥若第i项资源的影子价格为),,2,1(miyiL=(1)若第一个约束条件两端乘以2，变为，∑=≤njijijbxa12)2(1ˆy是对应于这个新约束条件的影子价格，求与的关系；1ˆy1y9(2)令，用替换模型中所有的，问影子价格是否变化？若不可能在昀优基中出现，问是否可能在昀优基中出现；113'xx=3/'1x1xiy1x1'x(3)如果目标函数变为∑==njjjxcz12max问影子价格有何改变？(4)如果模型中约束条件变为∑===njijijmibxa1,,2,1L问(1)、(2)、(3)中的结论是变化?解：（1）由影子价格的定义可得：'111'1111212ZZyybbbyy∂∂===∂∂=，而；∧∧∴1b（2）由（1）可知y1只与bi的值有关∴当x1的系数由3变为x’的系数1/3时，yi的值并不发生变化；∵x1不可能在昀优基中出现，∴x’也不可能在昀优基中出现（3）∵11112nnJjiijjnnJjJjjjjzCXbywzCXzCXC=========∑∑∑∑i当目标函数由变为时，增大了两倍影子价格y也增大了两倍。∵∴（4）分别相同。12、用对偶单纯形法求解下列线性规划问题：(1)3214510minxxxz++=s.t.3323321≥−+xxx10102431≥+xx0,,321≥xxx解：先将问题化为标准式'1234123413max105400.23321(1,2,3,4,5)0izxxxxxstxxxxxxxxi=−−−++−++=−−+=−=≥55　　-3　　　-4　　　　　　0取初始正则基B=（p4p5）=I则原问题已化为关于基B的典式，C23100CBXBX1X2X3X4X5B0X4-3-2310-30X5-40-201-10检验数-10-5-40000X4-9-2013/2-18-4X32010-1/25检验数-2-500-220-10X112/9