优化刘志斌练习题一和二参考标准

练习题一1、建立优化模型应试虑哪些要素?答：决策变量、目标函数和拘束条件。2、谈论优化模型最优解的存在性、迭代算法的收敛性及停止准则。minf(x)答：针对一般优化模型s..tgix0,i1,2,Lm，谈论解的可行域D，若存hjx0,jL1,,p在一点X*D，对于XD均有f(X*)f(X)则称X*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所获得的序列X(1),X(2),L,X(K)L，满足f(X(K1))f(X(K))，则迭代法收敛；收敛的停止准则有x(k1)x(k)，x(k1)x(k)，fx(k1)fx(k)fx(k1)fx(k)，fx(k)x(k)，fx(k)等等。练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R1、R2、和R3，欲出价收购（可能用于生产附加值更高的产品）。若是你是该公司的决策者，对这3种资源的收买报价是多少？（该问题称为例2.1的对偶问题）。解：确定决策变量对3种资源报价y1,y2,y3作为本问题的决策变量。确定目标函数问题的目标很清楚——“收买价最小”。确定拘束条件资源的报价最少应该高于原生产产品的利润，这样原厂家才可能卖。所以有以下线性规划问题：minw170y1100y2150y35y12y2y310s..t2y13y25y318y1,y2,y30*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。答：略。3、用单纯形法求解以下线性规划问题：minzx1x2x3minz4x2x3x1x22x32x12x2x322x1x2x33；x22x3x42（1）s.t.x34（2）s.t.x3x55x1x2x1,x2,x30xi0(i1,2,,5)解：（1）引入废弛变量x4，x5，x6minzx1x2x30*x40*x50*x6x1x22x3x4=22x1x2x3x5=3st..x3x6=4x1x1,x2,x3,x4,x5,x60cj→1-11000CB基bx1x2x3x4x5x60x421[1]-21000x532110100x64-101001cj-zj1-11000因检验数σ2<0，故确定x2为换入非基变量，以x2的系数列的正重量对应去除常数列，最小比值所行家对应的基变量x4作为换出的基变量。cj→1-11000CB基bx1x4x3x4x5x6-1x2211-21000x5110[3]-1100x64-101001cj-zj20-1100因检验数σ3<0，故确定x3为换入非基变量，以x3的系数列的正重量对应去除常数列，最小比值所行家对应的基变量x5作为换出的基变量。cj→1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因检验数σ*(0,8/3,1/3,0,0,11/3)，去除增加的j>0，表示已求得最优解：X废弛变量，原问题的最优解为：X*(0,8/3,1/3)。（2）依照题意采用x1，x4，x5，为基变量：minz4x2x3x12x2x32x22x3x42s.t.x2x3x55xi0(i1,2,,5)cj→0-11CB基bx1xx320x121-210x420[1]-20x55011cj-zj0-11

00x4x50010因检验数σ最小，故确定x2为换入非基变量，以x2的系数列的正重量对2<0应去除常数列，最小比值所行家对应的基变量x4作为换出的基变量。cj→0-1100CB基bx1xx3xx2450x1610-320-1x2201-2100x5300[3]-11cj-zj00-110因检验数σ331的系数列的正重量对<0最小，故确定x为换入非基变量，以x应去除常数列，最小比值所行家对应的基变量x5作为换出的基变量。cj→0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-zj0002/31/3因检验数σj*(9,4,1,0,0)。>0，表示已求得最优解：X4、分别用大M法、两阶段法和Matlab软件求解以下线性规划问题：minz4x1x2maxz10x15x212x33x1x2315x13x2x39（1）s.t.9x13x26；（2）s.t.5x16x215x315x12x232x1x2x35x1,x20x1,x2,x30解：（1）大M法依照题意拘束条件1和2可以合并为1，引入废弛变量x3，4，构造新问题。xminz=4x1+x2+Mx3+0*x43x1x2x33s..tx12x2x43x1,Lx40cj→41M0CB基bx1x2x3x4Mx33[3]1100x431201cj-zj4-3M1-M004x1111/31/300x420[5/3]-1/31cj-zj0-1/3M-4/304x13/5102/5-1/51x26/501-1/53/5cj-zj00M-7/51/5因检验数σjX*(3/5,6/5)。>0，表示已求得最优解：Matlab调用代码：f=[4;1];A=[-9,-3;1,2];b=[-6;3];Aeq=[3,1];beq=3;lb=[0;0];[x,fval]=linprog(f,A,b,Aeq,beq,lb)输出结果：Optimizationterminated.x=0.60001.2000fval=3.6000（2）大M法引入废弛变量x4，x5，x6，x7构造新问题。maxz10x115x212x30x40x50x6Mx75x13x2x3x495x16x215x3x515st..x2x3x6x752x1x,,x701L单纯形表计算略；当所有非基变量为负数，人工变量x7=0.5，所以原问题无可行解。请同学们自己求解。Matlab调用代码：f=[-10;-15;-12];A=[5,3,1;-5,6,15;-2,-1,-1];b=[9;15;-5];lb=[0;0;0];x=linprog(f,A,b,[],[],lb)输出结果：原题无可行解。5、用内点法和Matlab软件求解以下线性规划问题：minz2x1x2x3x12x22x36s.t.2x1x25x1,x2,x30解：用内点法的过程自己书写，参照答案：最优解X[4/37/30]；最优值5Matlab调用代码：f=[2;1;1];Aeq=[1,2,2;2,1,0];beq=[6;5];lb=[0;0;0];[x,fval]=linprog(f,[],[],Aeq,beq,lb)输出结果：Optimizationterminated.x=1.33332.33330.0000fval=5.00006、用分支定界法求解以下问题：maxz5x18x2x1x26（1）19x245；x1,x20且均为整数解：（1）调用matlab编译程序bbmethodf=[-5;-8];G=[11;59];h=[6;45][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;1],1)x=33y=-39最优解[33]；最优值392）调用matlab编译程序bbmethodf=[-7;-9];G=[-13;71];h=[6;35][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;0],1)x=50y=

maxz7x19x2（2）s.t.x13x267x1x235x1,x20且x1为整数-35最优解[50]；最优值357、用隐列举法和Matlab软件求解以下问题：minz4x13x22x3maxz3x12x25x32x43x52x15x23x34x1x2x32x4x544x1x23x337x13x34x43x58（1）s.t.x2x31；（2）s.t.6x23x43x5111x1xj0或1(j1,2,3)xj0或1(j1,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;2];

%价值向量

fA=[2,-5,3;-4,-1,-3;0,-1,-1];

%不等式拘束系数矩阵

A，[]中的分号“；”%为行分开符b=[4;-3;-1];

%

b[x,fval]=bintprog(f,A,b,[],[]);

%调用函数

bintprog。注意两个空数组的占位作用。输出结果x=001fval=2（2）调用代码：f=[-3;-2;5;2;3];

%价值向量

fA=[1,1,1,2,1;7,0,3,-4,3;-11,6,0,-3,3];

%不等式拘束系数矩阵

A，[]中的分号“；”%为行分开符b=[4;8;-1];

%不等式拘束右端常数向量

b[x,fval]=bintprog(f,A,b,[],[]);%调用函数bintprog。注意两个空数组的占位作用。输出结果x=11000fval=-5最优值5。8、某地区有A、B、C三个化肥厂，供应当地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试拟定一个使总运费最少的化肥调拨方案。表2-1运价/产粮(元/吨)甲乙丙丁各厂供应量/万吨区化肥厂A158737A2491078A384293各区需要量/万吨6633解：设A、B、C三个化肥厂为A1、A2、A3，甲、乙、丙、丁四个产粮区为B1、B2、B3、B4；cij为由Ai运化肥至Bj的运价，单位是元/吨；xij为由Ai运往Bj的化肥数量（i=1,2,3;j=1,2,3,4）单位是吨；z表示总运费，单位为元，依题意问题的数学模型为：34minzcijxiji1j1x11x21x316x12x22x326x13x23x333st..x14x24x343x11x12x13x147x21x22x23x248x31x32x33x347该题可以用单纯形法或matlab自带工具箱命令（linprog）求解。9、求解以下不平衡运输问题（各数据表中，方框内的数字为单位价格cij，框外右侧的一列数为各发点的供应量ai，框底下一行数是各收点的需求量bj）：（1）51710要求收点3的需求必定正好满足。6468032515752050（2）51020要求收点1的需求必定由发点4供应。32410752159601551015解答略。10、一公司经理要分配4位销售员去4个地区销售某种商品。销售员各有不同的经验和能力，所以他们在不同样地区能获得的利润不同样，其盈利估计值如表2-29所示。公司经理应怎样分配才使总利润最大？表2-2地区1234销售员135272837228342940335243233424322528解：用求极大值的“匈牙利法”求解。效率矩阵表示为：3527283751312328342940M－Cij126110行约简35243233M=40516872432252816815122109012611列约简001132807标号4

2106(0)12680*所画（）0元素(0)