运筹学习题集.doc

该【运筹学习题集 】是由【雨林书屋】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【运筹学习题集 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。判断题判断正误,如果错误请更正第二章 线形规划的对偶理论原问题第i个约束是<=约束,则对偶变量yi>=,或则同时都有最优解,,,原问题无可行解,,,Y分别为{minZ=CX|AX>=b,X>=0}和{maxw=Yb|YA<=C,Y>=0}的可行解,则有(1)CX<=Yb;(2)CX是w的上界;当X,Y为最优解,CX=Yb;当CX=Yb时,有YXs+YsX=0;(5)X为最优解且 B是最优基时,则Y=CBB-1是最优解;松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解,则X=-,,,Y是原问题与对偶问题的最优解 .则X=,,,,, 目标值不会比原来变差 .减少一个非基变量,(j=1,2,3,,n)在允许的最大范围内同时变化时,最优解不变。选择题在下列各题中,从 4个备选答案中选出一个或从 5个备选答案中选出 2~5个正确答案。第二章 线性规划的对偶理论1. 如果决策变量数列相等的两个线规划的最优解相同,则两个线性规划 A约束条件相同B目标函数相同 C最优目标函数值相同 ,则最优解相同B原问题无可行解,则对偶问题也无可行解C对偶问题无可行解,原问题可能无可行解D一个问题无界,则另一个问题无可行解E一个问题无可行解,(max)的最优表中的检验数为(λ1,λ2,λn),松弛变量的检验数为(λn+1,λn+2,λn+m),则对偶问题的最优解为A—(λ1,λ2,n)B(λ1,λ2,λn)C—(λn+1,λn+2,λn+m)D(λn+1,λn+2,n+m)5. 原问题与对偶问题都有可行解,则 A原问题有最优解,对偶问题可能没有最优解 B原问题与对偶问题可能都没有最优解 C可能一个问题有最优解, 另一个问题具有无界解 D原问题与对偶问题都有最优解计算题线性规划问题和对偶问题对于如下的线性规划问题minz=3x1+2x2++x2+x32x1-x2+x3-x1+2x2+2x3x1x2x315 (1)(2)(3)、写出题目中线性规划问题的对偶问题;2、分别求出原始问题和对偶问题的最优解(求解的次序和方法不限);解答:1、写出题目中线性规划问题的对偶问题;解:maxw=15y1+9y2++2y2-y33(1)y1-y2+2y32(2)y1+y2+2y31(3)y10、y20、y302、分别求出原始问题和对偶问题的最优解(求解的次序和方法不限);解:先将原问题化成以下形式,则有minz=3x1+2x2++x2+x3+x4=15(1)-2x1+x2-x3+x5=-9(2)-x1+2x2+2x3+x6=8(3)Xx1x2x3x4x5x6X0XXXX右端123456z-3-2-1000X411110015X5-21[-1]010-9X-12200186XXXXXX右端123456z-1-300-109X4-1201106X32-110-109X[-5]40021-106X1X2X3X4X5X6右端z0-19/500-7/5-1/511X406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52原始问题的最优解为(XX2XX4XX)=(2,0,5,8,0,0),minz=111356对偶问题的最优解为(y1y2y3y4y5y6)=(0,7/5,-1/5,0,19/5,0),maxw=11对于以下线性规划问题maxz=-x1-2x2.-2x1+3x212(1)-3x1+x26(2)x1+3x23(3)x10,x201、写出标准化的线性规划问题;2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值;3、写出这个(极大化)线性规划问题的对偶问题;4、求出对偶问题的最优解和最优解的目标函数值;5、第(2)个约束右端常数 b2=6在什么范围内变化,最优解保持不变。解答:1、写出标准化的线性规划问题*=-x1:令x1maxz=x*-2x21. 2x3x-xx*+3x2+x=12(1)131*+x2+x4=6(2)1*+3x2-x5=3(3)1*x2x3x4x502、(6分)用单纯形表求出这个线性规划问题的最优解和最优的目标函数值x1*X2X3X4X5R右端Z’1-M3M-200-M03MX323100012X43101006R-1[3]00-113x1*XXXXR右端2345Z’1/3000-2/32/3-M2X330101-19X[10/3]0011/3-1/354-1/3100-1/31/31X2x1*X2X3X4X5R右端Z’000-1/10-7/1021/30-M3/2X001-9/109/23X1*1003/101/10-1/103/2X20101/103/2此时最优解为(X1、X2、X3、X4X5)=(-3/2,3/2,9/2,0,0)maxz=-3/23、写出这个(极大化)线性规划问题的对偶问题;minw=12y1+6y2+3y3.-2y1-3y2+y3-1(1)3y1+y2+3y3-2(2)y10、y20、y304、求出对偶问题的最优解和最优解的目标函数值;此时最优解为(y1、y2、y3、y4y5)=(0,1/10,-7/10,0,0)minw=-3/25、则有1 b2 11,最优解不变。已知LP问题:maxz=x1+2x2+3x3++2x2+2x3+3x420(1)2x1+x2+3x3+2x420(2)x1、x2、x3、x40的最优解为(0,0,4,4)T,最优值为Z=28。请用互补松弛定理计算其对偶问题的最优解。解答:首先写出此 LP问题的对偶问题为:minw=20y1++2y21(1)2y1+y22(2)2y1+3y23(3)3y1+2y24(4)y1、y2、0将上述对偶问题的化成标准型,取松弛变量分别为v1、v2、、v3、v4,则有minw=20y1++2y2-v1=1(5)2y1+y2-v2=2(6)2y1+3y2-v3=3(7)3y1+2y2-v4=4(8)y1、y2、0利用互补松弛定理可知:x3=4>0,又有x3v3=0,所以有v3=0代入(7)式x4=4>0,又有x4v4=0,所以有v4=0代入(8)式,则有2y1+3y2=3(9)3y1+2y2=4(10)从中可计算出y1=6/5、y2=1/5,则w*=28一个工厂用四种原料生产三种产品,生产每种产品要消耗的各种原料数量(表中“—”表示相应的产品不需要这种原料)、各种产品的利润以及各种原料的限量如下表所示。1、写出原料限制条件下利润最大化的线性规划模型;2、写出以上问题的对偶问题;3、已知利润最大的线性规划问题的最优解是产品A生产120件,产品B不生产,产品C生产52件,用互补松弛关系求四种原料的影子价格。原料消耗产品产品产品原料限量(吨/件)ABC(吨)原料甲128102400原料乙610151500原料丙1518——1800原料丁——20222000产品利润120180210(万元/件)解答:一个工厂用四种原料生产三种产品,生产每种产品要消耗的各种原料数量(表中“—”表示相应的产品不需要这种原料)、各种产品的利润以及各种原料的限量如下表所示。写出原料限制条件下利润最大化的线性规划模型;maxz=120x1+180x2++8x2+10x32400(1)6x1+10x2+15x31500(2)15x1+18x21800(3)20x2+22x32000(4)x10,;minw=2400y1+1500y2+1800y3++6y2+15y3120(1)8y1+10y2+18y3+20y4180(2)10y1+15y2+22y4210(3)y10,,产品B不生产,产品C生产52件,用互补松弛关系求四种原料的影子价格。maxz=120x1+180x2++8x2+10x3+x4=2400(1)6x1+10x2+15x3+x5=1500(2)15x1+18x2+x6=1800(3)20x2+22x3+x7=2000(4)x10,x20x30x40x50x60x70x4=440x5=0x6=0x7=856minw=2400y1+1500y2+1800y3++6y2+15y3-y5=120(1)8y1+10y2+18y3+20y4-y6=180(2)10y1+15y2+22y4-y7=210(3)y10,y20y30y40y50y60y70由互补松弛关系可知,x1x3x4x70,得到y5=y7=y1=y4=06y2+15y3=12010y2+18y3-y6=18015yy=2y==210解得y=14236原材料甲的影子价格为:0万元/吨原材料乙的影子价格为:14万元/吨原材料丙的影子价格为:万元/吨原材料丁的影子价格为:0万元/吨