最优化刘志斌练习试题一及二参考答案解析

1、WORD格式整理.练习题一1、建立优化模型应考虑哪些要素？答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则min f(x)答:针对一般优化模型s.t gi (x)K0,i =1,2,川m，讨论解的可行域D，若存hj x =0, j =1,| p在一点X： D，对于-X D均有f (X ) _ f (X)则称X*为优化模型最优解，最 优解存在；迭代算法的收敛性是指迭代所得到的序列 xx(2),|i(,x(K)|i(，满 足f (X(K A) f (X(K)，则迭代法收敛；收敛的停止准则有 x(kx(k)；，卜宀x(k)|IIx(k)|等等o(k 1)(

2、k)f(X )- f(X J Jf x(k 1) -f x(k)f x(k).专业知识分享练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R、巳、和欲出价收购(可能用于生产附加值更高的产品)。如果你是该公司的决策者，对这 3种资解：确定决策变量确定目标函数确定约束条件 可能卖。源的收购报价是多少？(该问题称为例 2.1的对偶问题)对3种资源报价y1,y2,出作为本问题的决策变量。问题的目标很清楚一一“收购价最小”。资源的报价至少应该高于原生产产品的利润，这样原厂家才因此有如下线性规划问题：min 170y1 100y2 150y35y2y2 y3 -10s.t+ 3y2 +5y3 兰18

3、71, 丫2,丫3 -0*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)3、用单纯形法求解下列线性规划问题:minz = X - x2 x3乂 +x2 -2x3 兰22X +X2 +X3 兰3 ；s.t.-XiX3 乞 4Xi,X2,X3_0(2)min z = 4 - X2X3X - 2X2 + X3=2s.t.X22x3X4=2X2 X3X5 =5xi - 0 (i 二 1,2,5)解：（1）引入松弛变量X4, X5, X6min z =论x2 x3 0* x4 0* x5 0* x6乂 +x2 2x3 +&=22为 +x2 +x3+x5 =3s.t彳x1

4、 + x3+ x6=4x1,x2, x3,x4,x5,x6 _ 0Cj T1-11000CB基bX1X2X3X4X5X60X4211-21000X532110100X64-101001Cj-Zj1-11000因检验数（T 20,故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量 X4作为换出的基变量Cj T1-11000CB基bX1X4X3X4X5X6-1X2211-21000X51103-1100X64-101001Cj-Zj20-1100因检验数T 30,表明已求得最优解：X* =(0,8/3,1/3,0,0,11/ 3)，去除添加 的松弛变量，原问

5、题的最优解为： X* =(0,8/3,1/3)。(2)根据题意选取xi，X4，X5，为基变量：min z = 4 - X2 X3X -2x2 +X3=2X2 - 2x3 X4 2st. 234X2 +X3+ X5 =5Xi _0 (i =1,2，,5)C T0-1100O基bX1X2X3X4X50X121-21000X4201-2100X5501101Cj-Zj0-1100因检验数(T 20最小，故确定X2为换入非基变量，以X2的系数列的正分量对 应去除常数列，最小比值所在行对应的基变量 X4作为换出的基变量。C T0-1100CB基bX1X2X3X4X50x1610-320-1X2201-2

6、100x53003-11Cj-Zj00-110因检验数T 30,表明已求得最优解：X* =（9,4,1,0,0）4、分别用大M法、两阶段法和Matlab软件求解下列线性规划问题:min z =4X x2max z =10X15x212x33x1 x25x1 3x2 X3 _ 9（1）st9X +3x2 兰 6x1 2x2 - 3xx2 一0(2)一 5x1 + 6x2 十 15x3 乞 15 s.t.2X + x2 + x3 X 5X1,X2,X3 K0解：（1）大M法根据题意约束条件1和2可以合并为1,引入松弛变量X3, X4，构造新问题min z=4x1 +x2+Mx 3+0*x 43X|

7、 X2 x3=3s.t 0,表明已求得最优解：X* =（3/ 5,6/5）Matlab调用代码：f=4；1；A=-9,-3;1,2;b=-6;3;Aeq=3,1;beq=3;lb=0;0;x,fval = lin prog(f,A,b,Aeq,beq,lb)输出结果：Optimization terminated.x =0.60001.2000fval =3.6000(2)大M法引入松弛变量X4, X5, X6, X7构造新问题max z =10x1 15x2 12x3 0x4 0x5 0x6 - Mx7s.t *5片十 3x2 + x3 + x4一5为 +6x2 +15x3 +x5 2为 +

8、x2 +x3Xi|,x0=15-X6X7 =5单纯形表计算略；当所有非基变量为负数，人工变量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 = lin prog(f,A,b,lb)输出结果：原题无可行解。5、用内点法和Matlab软件求解下列线性规划问题：min z =2Xx2 x3|x1 - 2x2 2x3 =6s.t. 2x1x2= 5x1 ,x2,x3 -0解：用内点法的过程自己书写，参考答案：最优解 X =4/3 7/3 0;最优值5Matl

9、ab调用代码：f=2;1;1;Aeq=1,2,2;2,1,0;beq=6;5;lb=0;0;0;x,fval = lin prog(f,Aeq,beq,lb)输出结果：Optimization terminated.1.3333WORD格式整理.2.3333 0.0000fval =5.00006、用分支定界法求解下列问题：max z- 7xi 9x?-x1 3x2 _ 6(2)s.t.1 xj =0或1(j -1,2,3)s.t.2x3_4_3 ； (2)max z = 3X 2x? -5x32x4 3x5X + X2 + X3 + 2x4 + X5 兰 43x3 - 4x4 3x5 _ 8

10、-6x23x4 - 3x5 亠 1=0或 1 (j =1,2,5)s.t.7x111x1Xj解:隐枚举法:(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),目标函数最优值-5M

11、atlab软件求解：(1)调用代码:f=4; 3;2;A=2,-5,3;-4,-1,-3;0,-1,-1;b=4; -3;-1;x, fval=bintprog(f. A, b,%价值向量f%不等式约束系数矩阵 A,中的分号“；” %为行分隔符%不等式约束右端常数向量b%调用函数bintprog。注意两个空数组的占位作用。,);输出结果x=001fval=.专业知识分享2(2)调用代码:f=-3； -2;5;2;3;A=1,1,1,2,1; 7,0,3,-4,3;-11,6,0,-3, 3;b=4; 8;-1;x, fval=bintprog(f. A, b,);%价值向量f%不等式约束系数矩

12、阵 A 中的分号“；” %为行分隔 符%不等式约束右端常数向量b%调用函数bintprog。注意两个空数组的占位作用。输出结果x=11000fval=-5最优值58、某地区有A B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。运价/ 产粮化肥厂甲乙丙丁各厂供应量/万吨A158737A491078A84293各区需要量/万吨6633解：设A、B、C三个化肥厂为A、A A，甲、乙、丙、丁四个产粮区为 Bi、B、B、B4； Cj为由A运化肥至B的运价，单位是元

13、/吨；xj为由A运往B的化肥数量(i=1,2,3;j=1,2,3,4)单位是吨；z表示总运费，单位为元，依题意问题的数学模型为:34mi nz八 CMi 4 j丄Xu +x21 +x31 = 6X12 + X22 + X32 = 6X13 + X23 + x3 = 3S.t X14 +X24 +X34 = 3X11 * X12 + $ + X14 = 7X21 + X22 * X23 * X24 = 81X31+ X32 + X33 + X34 = 7该题可以用单纯形法或 matlab自带工具箱命令(linprog )求解。*9、求解下列不平衡运输问题(各数据表中，方框内的数字为单位价格q，框

14、外右侧的一列数为各发点的供应量ai，框底下一行数是各收点的需求量bj):要求收点3的需求必须正好满足75 20 50要求收点1的需求必须由发点4供应WORD格式整理.5 10 15解答略。10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表2-29所示。公司经理应怎样分派才使总利润最大？表2- 2地区推销员1234135272837228342940335243233424322528解：用求极大值的“匈牙利法”求解。勺5272837283429403524323324322528 21090126110011321 8074效率矩阵表示为:列约简5 = 4),少于M C jM =40 51251612标号(0)8136168121181530712行约简1011(0)未得到最优解，需要继续