建立优化模型专题练习题.docx
练习题一1、建立优化模型应考虑哪些要素？答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。min/(x)答：针对一般优化模型s.gj(x)0,i=l,2,m,讨论解的可行域。，若存在一点7(x)=OJ=1,pX"O,对于VXO均有/(X*)/(X)则称X"为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列X,X,，(Q,满足“(*D)(%,则迭代法收敛；收敛的停止准则制产D卜£ ,ft+-,(I)-“叫<£,m叫&等等。练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R1、R2、和R3,欲出价收购(可能用于生产附加值更高的产品)。如果你是该公司的决策者，对这3种资源的收购报价是多少？(该问题称为例2.1的对偶问题)。解：确定决策变量对3种资源报价弘,%，%作为本问题的决策变量。确定目标函数问题的目标很清楚一一“收购价最小”。确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。因此有如下线性规划问题：minw=170y1+1OOy2+150)、5>ji+2>j2÷10s.l.,2y1+3y2+5y318yvy29y30*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)。答：略。3、用单纯形法求解下列线性规划问题:min(1)s.,Z = X - 工2 + x3 Xj + X2 2与2 2x + 工2 + V 3 . 7+X34工,孙13 (2)min z = 4- X2 + 3x1 - 2x2 + X3 =2X2 2工3 += 2s.t.<X? + X3 + X5 = 5xi0 = l,2,5)解：（1）引入松弛变量X4,心，X6minz=xi-x2+x3+0*x4+0*x5+0*x6X1+X2-2工3+.V4=2s.”2x,+x2+x3+x5=3-Jd+x3+6=4xl,x2,x3,",x5,x60CL1-11OO0Cb基bXlX2X3XAXSX6OXi21I-21OOOxs3211O10OX64-101OO1Cj-Zj1-11OOO因检验数2<0,故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X4作为换出的基变量。CL1-11OO0Cb基bxX4X3X4XSX6-1Xl211-21O0OXS11O网-110OXG4-IO1OO1CJ-ZJ2O-11O0因检验数G3<0,故确定心为换入非基变量，以X3的系数列的正分量对应去除常数列，最小比值所在行对应的基变量心作为换出的基变量。Cj1-11OOOCb基bXlX2X5X4XSX6-1Xl8/35/31O1/32/301X31/31/301-1/31/3O0X611/3-4/3001/3-1/31Cj-Zj7/3032/31/30因检验数5>0,表明已求得最优解：X*=(O,83,l3,O,O,ll3),去除添加的松弛变量,原问题的最优解为：X*=(O,83,l3)o(2)根据题意选取XI,X4,minz=4-x2+Mx-2x2+工3=2%22x-+2s,t.%2+工3+工5=5xi0(i=l,2,5)X5,为基变量：Cj0-1100CB基。XlX2X3X4XS0Xi20Xi20X551-210001-21001101Q-ZjO-IlOO因检验数O2<0最小，故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X4作为换出的基变量。Cj0-1100Cb基bxX2X3XAX50Xi6I0320-1Xl201-2100XS3003.I1CJ-ZJ00-110因检验数G3<0最小，故确定了3为换入非基变量，以箝的系数列的正分量对应去除常数列，最小比值所在行对应的基变量心作为换出的基变量。CL0-1100Cb基bXlX23XlXS0Xl910011-1X240101/32/31X31001.1/31/3Cj-Zj0002/31/3因检验数5>0,表明已求得最优解：X*=(9,4J,0,0)o4、分别用大M法、两阶段法和MatIab软件求解下列线性规划问题:minz=4%+X2maxZ=IOXI+152+123x+x2=35x1+32+x39(1)l9rl+3x26.(2),5x+6-2+15x315WnC-CST<X+2%2W32x+%2+X3N5X,20X1,%2，r3解：(1)大M法根据题意约束条件1和2可以合并为1,引入松弛变量X3,X4,构造新问题。minz=4x1+x2+Mx3+0*x43x1÷x2+x3=35.f.<x1+Ix2+x4=3xvx40Cj41M0CB基bXlX2X3X4M43Ox4331101201CjF4-3MI-M004l10Xt211/31/3005/3-1/31Cj-Zj0-1/3M-4/304Xi3/51Xi6/5I02/5-1/501-1/53/5Cj-Zj00M-7/51/5因检验数5>0,表明已求得最优解：X*=(3/5,6/5).Matlab调用代码：f=4;l;A=l-9,-3U,2;b=-6;3;Aeq=3,l;beq=3;lb=O;O;x,fval=IinPrOg(f,A,b,Aeq,beq,lb)输出结果：Optimizationterminated.X=0.60001.2000fval=3.6000(2)大M法引入松弛变量X4,X6,乃构造新问题。maxZ=IOX+15x2+12x3+Ox4+Ox5+Ox6-Mx15x1+3x2+x4=9-5x1+6x2+15+x5=152xl+x2+x3-x6+x7=5x1,x70单纯形表计算略；当所有非基变量为负数，人工变量5=05所以原问题无可行解。请同学们自己求解。Matlab调用代码：f=-10;-15;-12;A=5,3,l；-5,6,15;-2,-l,-l;b=9;15;-5;lb=0;0;0;x=linrog(f,A,b,lb)输出结果：原题无可行解。5、用内点法和Matlab软件求解下列线性规划问题：minz=2x+打÷3x+2x2+2x3=6s.(2x+×2=5和孙巧之。解：用内点法的过程自己书写，参考答案：最优解X=437/30；最优值5Matlab调用代码：Aeq=1,2,221,0;beq=6;5;lb=O;O;O;x,fval=linprog(f,Aeq,beq,lb)输出结果：Optimizationterminated.x=1.33332.33330.0000fval=5.00006、用分支定界法求解下列问题：max z - 7x1 + 9x2一x ÷ 312 4 6s.tA7 Xj + x2 35X, ×2 0且X为整数maxz=5x+8x2x+X2V6(1)5./5%+9x245；Xl,%20且均为整数解：(1)调用matlab编译程序bbmelhodf=-5;-8;G=l1;59;h=6;45x,y=bbmethod(f,Gh,0;0,l;i,l)x=33y=-39最优解33；最优值39(2)调用matlab编译程序bbm&hodf=-7;-9;G=-13;7l;h=6;35x,y=bbmethod(f,G,h,0;0,l;0,l)x=50y=-35最优解50；最优值357、用隐枚举法和Matlab软件求解下列问题:(1)min Z = 4x + 3肛 + 2xS.t.'2x1 - 5x2 + 3叼-44x + X2 + 3町-3M + 43 NlXz=O或 1(/= 1,2,3)max z = 3x + 2x2 - 5与 - 2x4 + 3心Xj + X? + %3 + 214 + 15 W 47x ÷ 3叼4a?4 + 3为5 8Il X 6工2 + 314 3有之 1Xj = 0或1 CZ = 1,2,5)(1)将(0, 0, 0) (0, 0, 1) (0,解：隐枚举法:1,0)(1,0,0)(0,1,1)(1,0,1)(1,1,0)(1,1,1)分别带入到约束条件中，可以得到：原问题的最优解是(0,0,1),目标函数最优值2.(2)将(0,0,0,0,0)(0,0,0,0,1)(0,0,0,1,0)(0,0,1,0,0).(1,1,1,1,1)分别带入到约束条件中，可以得到：原问题的最优解是(1,1,0,0,0),目标函数最优值-5。Matlab软件求解：(1)调用代码:f=4;3;A=2,-5,3;-4,-1,-3:0,-1,-1;b=4;x,fval=bintprog(f,A,b,);%价值向量f%不等式约束系数矩阵A,中的分号“；”为行分隔符%不等式约束右端常数向量b%调用函数biniprog。注意两个空数组的占位作用。输出结果X=001fval=2(2)调用代码:f=-3;2523;%价值向量/A=l,1,1,2.1;7,0.3,-4,3；-lh6.0,-3,3；%不等式约束系数矩阵A,
