北航最优化方法最新最全答案2015版

1流量工程问题重述定一个有向网 G=(N,E) ，此中 N 是点集， E 是弧集。

令 A 是网 G 的点弧关矩，即 N×E 矩，且第 l 列与弧里 (I,j) ，第 i 行元素 1 ，第 j 行元素 -1 ，其他元素 0。

再令b m=(b m1 ,⋯,b mN )T，f m =(f m1,⋯ ,f mE )T，可将等式束表示成：Af m=b m本算例一典 TE 算例。

算例网有 7 个点和 13 条弧，每条弧的容量是 5 个位。

别的有四个需求量均 4 个位的源一目的，详细的源点、目的点信息如所示。

里了，省区了未用到的弧。

别的，弧上的数字表示弧的号。

此，c=((5,5 ⋯,5) 1 )T，×13依据上述四个束条件，分求得四个状况下的最决议量x=((x 12 ,x13,⋯ ,x75)1×13 )。

1 网拓扑和流量需求7 节点算例求解算例1（b1=[4;-4;0;0;0;0;0]T）转变为线性规划问题：Minimize c T x1Subject to Ax1=b1x1>=0 利用 Matlab 编写对偶纯真形法程序，可求得:最优解为 x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0] T对应的最优值 c T x1=201.2.2 算例 2（b2=[4;0;-4;0;0;0;0] T）Minimize c T x2Subject to Ax2=b2X2>=0 利用 Matlab 编写对偶纯真形法程序，可求得:最优解为 x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T对应的最优值 c T x2=201.2.3 算例 3（b3=[0;-4;4;0;0;0;0] T）MinimizeTc x3Subject to Ax3=b3X3>=0 利用 Matlab 编写对偶纯真形法程序，可求得:最优解为 x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0] T对应的最优值 c T x3=40算例4（b4=[4;0;0;0;0;0;-4]T ）Minimize c T x4Subject to Ax4=b4X4>=0利用 Matlab 编写对偶纯真形法程序，可求得:最优解为 x4*=[4 0 0 4 0 0 0 0 0 4 0 0 0] T对应的最优值 c T x4=601.3 计算结果及结果说明算例1（b1=[4;-4;0;0;0;0;0]T）算例 1 中，由 b1 可知，节点 2 为需求节点，节点 1 为供应节点，由节点 1 将信息传输至节点 2 的最短路径为弧 1。

1 2( ( ⎨最优化方法部分课后习题解答1.一直优化问题的数学模型为：习题一min f (x ) = (x − 3)2 + (x − 4)2⎧g (x ) = x − x − 5 ≥ 0 ⎪ 11 2 2 ⎪试用图解法求出：s .t . ⎨g 2 (x ) = −x 1 − x 2 + 5 ≥ 0 ⎪g (x ) = x ≥ 0 ⎪ 3 1 ⎪⎩g 4 (x ) = x 2 ≥ 0（1） 无约束最优点，并求出最优值。

（2） 约束最优点，并求出其最优值。

（3） 如果加一个等式约束 h (x ) = x 1 −x 2 = 0 ，其约束最优解是什么？ *解 ：（1）在无约束条件下， f (x ) 的可行域在整个 x 1 0x 2 平面上，不难看出，当 x =（3，4） 时， f (x ) 取最小值，即，最优点为 x * =（3，4）：且最优值为： f (x * ) =0（2）在约束条件下， f (x ) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是在约束集合即可行域中找一点 (x 1 ,x 2 ) ，使其落在半径最小的同心圆上，显然，从图示中可以看出，当 x *=15 , 5 ) 时， f (x ) 所在的圆的半径最小。

4 4⎧g (x ) = x −x − 5 = 0⎧ 15 ⎪x 1 = 其中：点为 g 1 (x) 和 g 2 (x ) 的交点，令 ⎪ 1 1 2 ⎨2 求解得到： ⎨ 45即最优点为 x *= ⎪⎩g 2 (x ) = −x 1 −x 2 + 5 = 015 , 5 ) ：最优值为： f(x * ) = 65 ⎪x =⎪⎩ 2 44 48（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。

2.一个矩形无盖油箱的外部总面积限定为 S ，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题. 解：列出这个优化问题的数学模型为：max f (x ) = x 1x 2 x 3⎧x 1x 2 + 2x 2 x 3 + 2x 1x 3 ≤ S ⎪ s .t . ⎪x 1 > 0⎪x 2 > 0 ⎪⎩x 3 > 0该优化问题属于三维的优化问题。

最优化方法部分课后习题解答习题一1.一直优化问题的数学模型为：22121122123142min ()(3)(4)5()02()50..()0()0f x x xg x x x g x x x s t g x x g x x =−+−⎧=−−≥⎪⎪⎪=−−+≥⎨⎪=≥⎪=≥⎪⎩试用图解法求出：（1）无约束最优点，并求出最优值。

（2）约束最优点，并求出其最优值。

（3）如果加一个等式约束，其约束最优解是什么？12()0h x x x =−=解：（1）在无约束条件下，的可行域在整个平面上，不难看出，当=（3，4）()f x 120x x *x 时，取最小值，即，最优点为=（3，4）：且最优值为：=0()f x *x *()f x （2）在约束条件下，的可行域为图中阴影部分所示，此时，求该问题的最优点就是()f x 在约束集合即可行域中找一点，使其落在半径最小的同心圆上，显然，从图示中可12(,)x x 以看出，当时，所在的圆的半径最小。

*155(,)44x =()f x 其中：点为和的交点，令求解得到：1()g x 2()g x 1122125()02()50g x x x g x x x ⎧=−−=⎪⎨⎪=−−+=⎩1215454x x ⎧=⎪⎪⎨⎪=⎪⎩即最优点为：最优值为：=*155(,)44x =*()f x 658（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。

2.一个矩形无盖油箱的外部总面积限定为S，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：该优化问题属于三维的优化问题。

123122313123max ()220..00f x x x x x x x x x x S x s t x x =++≤⎧⎪>⎪⎨>⎪⎪>⎩32123sx y z v⎛⎞=====⎜⎟⎝⎠习题二3.计算一般二次函数的梯度。

北航2015年考研991科目的答案一、单项选择题1．C 2．A 3．D 4．B 5．C 6．B 7．D 8．A 9．C 10．D 二、填空题1．顺序2．O(m) 3．log2k+1 4．235 5．2(n-1) 6．该有向图中不存在回路7．2.9 8．m-1 9．插入排序法10．9三、综合题1．答：（1）多个堆栈共享一个连续的存储空间，可以充分利用存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个堆栈溢出时需要向左、右栈查询有无空闲单元。

若有，则需要移动相应元素和修改相关的栈底和栈顶指针的位置。

当各个堆栈接近溢出时，查询空闲单元、移动元素和修改栈底栈顶指针位置的操作频繁，计算复杂，并且耗费时间。

（2）每个堆栈仅用一个顺序存储空间时，操作简便。

但难以确定初始分配存储空间的大小，空间分配少了，容易产生溢出，空间分配多了，容易造成空间浪费；并且各个堆栈不能共享空间。

（3）一般情况下，分别建立多个链接堆栈不考虑堆栈的溢出（仅受用户内存空间限制），缺点是堆栈中各元素要通过指针链接，比顺序存储结构多占用存储空间。

2．(T->lchild==NULL && T->rchild==NULL) T->lchild T->rchild3．（由于图表显示限制，此题答案见指定教材(《数据结构教程第二版》(2012年4月第7次印刷)) 第418页8-16题）4．(1)．根据α=散列表中存入的元素数/散列表的长度，得到表的长度为18，因此，合适的散列函数应该为H(k)=k MOD 17。

(2)．（由于图表显示限制，此题答案见指定教材(《数据结构教程第二版》(2012年4月第7次印刷)) 第428页9-15题）四、算法设计题SORT(int A[ ], int n){ int ,i, j, min, max, temp; i=1;while(i<=n/2){ min=i; max=i;for(j=i+1;j<n-i+1;j++){ if(A[j]<A[min])min=j; if(A[j]>A[max]) max=j;} /* 确定某趟排序的最小值元素和最大值元素*/ if(min!=i){temp=A[min]; A[min]=A[i]; A[i]=temp; } /* 交换A[min]与A[i]的位置*/ if(max!=n-i+1) if(max==i){temp=A[min]; A[min]=A[n-i+1]; A[n-i+1]=temp; } /* 交换A[min]与A[n-i+1]的位置*/ else{temp=A[max]; A[max]=A[n-i+1]; A[n-i+1]=temp; /* 交换A[max]与A[n-i+1]的位置*/ } i++; } }五、填空题1．break a/q 2．a[n-1]>=a[n-2] FUNC2(a, n-1) 3．(*(a+i)+i) (*(a+i)+N-i-1) 4．i!=0 n%10+′0′5．ch-=30 ch-=266．*(s+i) t++ 7．strlen(p)-1 p<q 8．ch & 24 9．4 &number 10．argv[1],“rb”argv[2], “wb”六、简答题1．答：通常有下列三种方式：(1)参数传递方式：函数调用时根据实参传递给形参内容的不同又分为值传递与地址传递两种。

练习题一1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。

2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。

答：针对一般优化模型()()min ()..0,1,2, 0,1,,i j f x s t g x i m h x j p≥===，讨论解的可行域D ，若存在一点*X D ∈，对于X D ∀∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列(1)(2)(),,,K X X X ，满足(1)()()()K K f X f X +≤，则迭代法收敛；收敛的停止准则有(1)()k k x x ε+-<，(1)()()k k k x x x ε+-<，()()(1)()k k f x f x ε+-<，()()()(1)()()k k k f x f x f x ε+-<，()()k f x ε∇<等等。

练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。

如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。

解：确定决策变量 对3种资源报价123,,y y y 作为本问题的决策变量。

确定目标函数 问题的目标很清楚——“收购价最小”。

确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。

因此有如下线性规划问题：123min 170100150w y y y =++1231231235210..23518,,0y y y s t y y y y y y ++≥⎧⎪++≥⎨⎪≥⎩ *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。

答：略。

3、用单纯形法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤+-≤++≤-++-=0,,43222..min32131321321321x x x x x x x x x x x t s x x x z ； （2）⎪⎪⎩⎪⎪⎨⎧=≥=++=+-=+-+-=)5,,2,1(052222..4min53243232132 i x x x x x x x x x x t s x x z i解：（1）引入松弛变量x 4，x 5，x 6123456min 0*0*0*z x x x x x x =-++++12341232 =22 5 =3..13 6=41,2,3,4,5,60x x x x x x x x s t x x x x x x x x x +-+⎧⎪+++⎪⎨-++⎪⎪≥⎩因检验数σ2<0，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。

习题一1.1利用图解法求下列线性规划问题： （1）21x x z max +=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 5x 2x 2x x 3.t .s 212121 解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A 点取得最优值，最优值z=5（2）21x 6x z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+0x ,x 7x x 1x x 2.t .s 212121 解：图中阴影部分表示可行域，由图可知原问题在点A 处取得最优值，最优值z=-6.（3）21x 2x 3z max +=⎪⎪⎩⎪⎪⎨⎧≥-≥-≤+-0x ,x 4x 2x 1x x .t .s 212121 解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。

（4）21x 5x 2z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 2x x 6x 2x .t .s 212121 解：由图可知该线性规划可行域为空，则原问题无可行解。

1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。

（1）4321x 6x 3x 2x 5z min -+-=⎪⎪⎩⎪⎪⎨⎧≥=+++=+++0x ,x ,x ,x 3x 2x x x 27x 4x 3x 2x .t .s 432143214321 解：易知1x 的系数列向量⎪⎪⎭⎫ ⎝⎛=21p 1，2x 的系数列向量⎪⎪⎭⎫ ⎝⎛=12p 2，3x 的系数列向量⎪⎪⎭⎫⎝⎛=13p 3，4x 的系数列向量⎪⎪⎭⎫⎝⎛=24p 4。

①因为21p ,p 线性无关，故有⎪⎩⎪⎨⎧--=+--=+43214321x 2x 3x x 2x 4x 37x 2x ，令非基变量为0x x 43==，得⎪⎪⎩⎪⎪⎨⎧=-=311x 31x 21，所以得到一个基解)0,0,311,31(x )1(-=是非基可行解； ②因为31p ,p 线性无关，可得基解)0,511,0,52(x)2(=，543z 2=；③因为41p ,p 线性无关，可得基解611,0,0,31(x )3(-=，是非基可行解；④因为32p ,p 线性无关，可得基解)0,1,2,0(x )4(=，1z 4-=；⑤因为42p ,p 线性相关，42x ,x 不能构成基变量； ⑥因为43p ,p 线性无关，可得基解)1,1,0,0(x )6(=，3z 6-=；所以)6()4()2(x ,x ,x是原问题的基可行解，)6(x 是最优解，最优值是3z -=。

习题一1.1利用图解法求下列线性规划问题： （1）21x x z max +=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 5x 2x 2x x 3.t .s 212121 解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A 点取得最优值，最优值z=5（2）21x 6x z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+0x ,x 7x x 1x x 2.t .s 212121 解：图中阴影部分表示可行域，由图可知原问题在点A 处取得最优值，最优值z=-6.（3）21x 2x 3z max +=⎪⎪⎩⎪⎪⎨⎧≥-≥-≤+-0x ,x 4x 2x 1x x .t .s 212121 解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。

（4）21x 5x 2z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 2x x 6x 2x .t .s 212121 解：由图可知该线性规划可行域为空，则原问题无可行解。

1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。

（1）4321x 6x 3x 2x 5z min -+-=⎪⎪⎩⎪⎪⎨⎧≥=+++=+++0x ,x ,x ,x 3x 2x x x 27x 4x 3x 2x .t .s 432143214321 解：易知1x 的系数列向量⎪⎪⎭⎫ ⎝⎛=21p 1，2x 的系数列向量⎪⎪⎭⎫ ⎝⎛=12p 2，3x 的系数列向量⎪⎪⎭⎫⎝⎛=13p 3，4x 的系数列向量⎪⎪⎭⎫⎝⎛=24p 4。

①因为21p ,p 线性无关，故有⎪⎩⎪⎨⎧--=+--=+43214321x 2x 3x x 2x 4x 37x 2x ，令非基变量为0x x 43==，得⎪⎪⎩⎪⎪⎨⎧=-=311x 31x 21，所以得到一个基解)0,0,311,31(x )1(-=是非基可行解； ②因为31p ,p 线性无关，可得基解)0,511,0,52(x)2(=，543z 2=；③因为41p ,p 线性无关，可得基解611,0,0,31(x )3(-=，是非基可行解；④因为32p ,p 线性无关，可得基解)0,1,2,0(x )4(=，1z 4-=；⑤因为42p ,p 线性相关，42x ,x 不能构成基变量； ⑥因为43p ,p 线性无关，可得基解)1,1,0,0(x )6(=，3z 6-=；所以)6()4()2(x ,x ,x是原问题的基可行解，)6(x 是最优解，最优值是3z -=。

习题二包括题目： P36页 5〔1〕〔4〕 5〔4〕习题三包括题目：P61页 1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下 5,6题14题解如下14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T-处的牛顿方向。

解： (1)(4,6)T x=-，由题意得∴(1)1344()56g f x -⎛⎫=∇=⎪⎝⎭21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------⎛⎫∇= ⎪+--------+--⎝⎭∴(1)2(1)1656()()564G x f x --⎛⎫=∇=⎪-⎝⎭∴(1)(1)11141/100()574/100d G x g -⎛⎫=-=⎪-⎝⎭15〔1〕解如下15. 用DFP 方法求以下问题的极小点〔1〕22121212min 353x x x x x x ++++解：取 (0)(1,1)T x=，0H I =时，DFP 法的第一步与最速下降法一样2112352()156x x f x x x ++⎛⎫∇= ⎪++⎝⎭， (0)(1,1)T x =，(0)10()12f x ⎛⎫∇= ⎪⎝⎭(1)0.07800.2936x -⎛⎫= ⎪-⎝⎭， (1)1.3760() 1.1516f x ⎛⎫∇= ⎪-⎝⎭以下作第二次迭代(1)(0)1 1.07801.2936x x δ-⎛⎫=-= ⎪-⎝⎭， (1)(0)18.6240()()13.1516f x f x γ-⎛⎫=∇-∇= ⎪-⎝⎭其中，111011126.3096,247.3380T T TH δγγγγγ===11 1.1621 1.39451.3945 1.6734T δδ⎛⎫= ⎪⎝⎭ ， 01101174.3734113.4194113.4194172.9646T TH H γγγγ⎛⎫== ⎪⎝⎭所以 令 (2)(1)(1)1xx d α=+ ， 利用 (1)(1)()0df x d d αα+=，求得 10.5727α=-所以 (2)(1)(1)0.77540.57270.8535x x d ⎛⎫=-= ⎪-⎝⎭ ， (2)0.2833()0.244f x ⎛⎫∇= ⎪-⎝⎭以下作第三次迭代(2)(1)20.85340.5599x x δ⎛⎫=-= ⎪-⎝⎭ ， (2)(1)2 1.0927()()0.9076f x f x γ-⎛⎫=∇-∇= ⎪⎝⎭22 1.4407T δγ=- ， 212 1.9922T H γγ=所以 令 (3)(2)(2)2xxdα=+ ， 利用(2)(2)()0df x d d αα+=，求得 21α= 所以 (3)(2)(2)11x x d ⎛⎫=+=⎪-⎝⎭， 因为 (3)()0f x ∇=，于是停顿 (3)(1,1)T x =-即为最优解。