北航最优化方法 答案 版

数学规划基础部分习题参考解答刘红英编北京航空航天大学数学与系统科学学院2015年5月内容简介本 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 是《数学规划基础》(刘红英，夏勇，周水生，北京航空航天大学出版社，2012.10)的配套教学辅导材料，较详细地给出了该教材各章后部分习题的参考解答.前言本习题解答自2008年春季开始编写，当时由硕士研究生阎凤玉提供部分习题解答，经讨论和确认后，由作者首次录入排版.后来陆续参加习题解答修订的硕士研究生包括王浩、欧林鑫、朱丽媛、易彩霞和杨茜，其中的数值结果由欧林鑫提供.作者在此向他们的辛勤劳动表示衷心的感谢.本解答得到了？项目的资助，在此表示感谢.由于这些参考解答尚未经过特别严格的校对，仅供参考.任何意见、建议或其它反馈都可以发送至liuhongying@buaa.edu.cn，在此深表感谢.刘红英2015.5于北京目录第一章引言1第二章线性规划:基本理论与方法3第三章线性规划：应用及扩展23第四章无约束优化：基础27第六章无约束优化：线搜索法31第六章无约束优化：信赖域法375第一章引言1.2(该练习的目的是提高你的建模技巧，同时熟悉利用计算机求解线性优化问题)一个原油精练场有8百万桶原油A和5百万桶原油B用以安排下个月的生产.可用这些资源来生产售价为38元/桶的汽油，或者生产售价为33元/桶的民用燃料油.有三种生产过程可供选择，各自的生产参数如下：过程1过程2过程3输入原油A315输入原油B513输出汽油413输出燃料油314成本(单位：元)511140除成本外，所有的量均以桶为单位.例如，对于第一个过程而言，利用3桶原油A和5桶原油B可以生产4桶汽油和3桶民用燃料油，成本为51元.表格中的成本指总的成本(即原油成本和生产过程的成本).将此问题建模成线性规划，其能使管理者极大化下个月的净利润.请利用Lingo,Cplex或Matlab在计算机上求解此问题.解:设下个月利用第一个过程生产x次,第二个过程生产y次,第三个过程生产z次.则利润为f(x;y;z)=(38�4+33�3�51)x+(38+33�11)y+(38�3+33�4�40)z=200x+60y+206z其数学模型为maximize200x+60y+206zsubjectto3x+y+5z�80000005x+y+3z�5000000x;y;z�0;且x;y;z是整数:忽略掉整性要求后，调用Matlab中的linprog.m函数求解，得最优解x=0;y=500000;z=1500000，自动满足整性要求.1.3利用图解法和优化软件两种方法求解下列问题minimize(x1�2)2+(x2�1)2subjecttox21�x2�0;x1+x2�2:1.4确定下列n元函数的梯度向量和Hessian阵：(a)aTx:a是常向量；(b)xTAx:A是非对称的常矩阵；(c)12xTAx�bTx:A是对称的常矩阵，b是常向量；(d)r(x)Tr(x):r(x)=(r1(x);���;rm(x))T是依赖于x的m维向量，记rrT为AT，它一般不是常量.12第一章引言解:(a)rf(x)=a;r2f(x)=0n�n;(b)rf(x)=(A+AT)x;r2f(x)=A+AT;(c)rf(x)=Ax�b;r2f(x)=A;(d)f(x)=Pmi=1r2i(x);rf(x)=2Pmi=1ri(x)rri(x)=2A(x)Tr(x);r2f(x)=2Pmi=1ri(x)r2ri(x)+2Pni=1rri(x)(rri(x))T=2Pmi=1ri(x)r2ri(x)+2A(x)TA(x):1.6考虑向量值函数f(x):Rn!Rm，设f的每个分量函数fi(x)在x0都可微.写出f在x0的Taylor展式，请用A(x)T表示rf(x)T(=[rf1(x);���;rfm(x)]).解:为了具体，考虑m=2;n=3给出，再表示成一般形式.此时f(x)=f1(x)f2(x)!=f1(x1;x2;x3)f2(x1;x2;x3)!:因为函数f1(x)和f2(x)可微，则由多元函数的Taylor展式，有fi(x)=fi(x0)+rfi(x0)T(x�x0)+o(kx�x0k);i=1;2:写成向量形式，即f(x)=f(x0)+A(x0)(x�x0)+o(kx�x0k);(1.1)这里o(kx�x0k)表示limx!x0f(x)�f(x0)�A(x0)(x�x0)kx�x0k=0:这里的式(1.1)即为f在x0的Taylor展式，其中的矩阵A(x)称为雅可比(Jacob)矩阵，它的第i行为fi(x)在x处的梯度向量的转置.1.7假设在点x0有g06=0，证明在所有单位向量pTp=1中，函数沿方向向量p=g0=kg0k2的斜率最大.称该方向是函数的最速上升(steepestascent)方向.证：记g0=rf(x0).因为函数可微，由方向导数与梯度的关系知函数沿方向p的方向导数，即斜率为pTg0.设�为方向向量p与梯度向量g0的夹角，则由向量夹角的定义和kpk2=1，有pTg0=kpTk2kg0k2cos��kpTk2kg0k2=kg0k2;其中等式成立当且仅当�=0，即p与梯度向量g0同方向.又因为p为单位向量，所以当p=g0=kg0k2时，函数沿该方向的斜率(也即方向导数)最大.第二章线性规划:基本理论与方法习题 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 说明：1.化 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形练习：习题2.1-习题2.3，其中习题2.2和习题2.3是最优化中常用的两种重新表述技巧，这两种技巧的应用和进一步说明分别见习题2.27和习题7.19.2.基本解、基本可行解、退化基本可行解的练习：习题2.4,习题2.5，习题2.6，习题2.7，教材第25页的例2.2.3.3.习题2.8,习题2.9、习题2.12(b)是为了理解使用单纯形法时，如何根据单纯形表的数据判断线性规划何时有惟一解，何时有多解.如果有多解时，如何得到多个解.结论是：最优解不惟一时，某基本可行解的非基变量的相对费用系数非负，并且至少有一个非基变量的相对费用系数是零.此外，习题2.30说明，当原始问题的最优解是对偶非退化的(即非基变量的既约费用系数严格大于零)，对偶问题有惟一解；否则，对偶问题有多个极点解，进而有无穷多个解(这些极点解的凸组合都是原始问题的解).4.单纯形法的练习：习题2.10，习题2.11，习题2.12，习题2.13，习题2.20(说明单纯形法的效率的一般性例子中，自变量为三个时所得问题)，习题2.21(说明单纯形法采用最小相对费用系数进基原则确定进基变量时，如果所求解问题是退化的，则单纯形法会出现循环！)，习题2.31.5.两阶段法的练习：习题2.14-习题2.16；大M法的练习：习题2.18.6.修正单纯形法的练习：习题2.17，习题；单纯形法的矩阵表示：2.19.7.习题2.11，习题2.12(c)，2.32是关于灵敏度分析的练习，这也可以看成是单纯形法的应用，是难点.8.关于对偶性的练习：习题2.22－习题2.36.2.1将下面的线性规划问题化成标准形，并求解第3个问题(c)：(c)minimizex1+4x2+x3subjecttox1�2x2+x3=4x1�x3=1x2�0;x3�0:解:(c)由于变量x1无限制，可利用约束x1=x3+1对其消去.因此，得其标准形minimize4x2+2x3subjectto�2x2+2x3=3x2�0;x3�0:再把约束2x3=3+2x2代入目标函数，得6x2+4;又因为x2�0，所以其最小值为4，最优解为x1=2:5;x2=0;x3=1:5.34第二章线性规划:基本理论与方法2.2将下面的问题化成线性规划minimizejxj+jyj+jzjsubjecttox+y�12x+z=3:方法1:令x=u1�v1;jxj=u1+v1;u1�0;v1�0,类似地表示y和z，则可将原问题重新编述为minimizeu1+u2+u3+v1+v2+v3subjecttou1�v1+u2�v2+s=1;2u1�2v1+u3�v3=3;ui;vi;s�0;i=1;2;3:方法2:引入非负变量t1;t2;t3，将原问题转化成等价问题minimizet1+t2+t3subjecttox+y�1;2x+z=3;jxj=t1;jyj=t2;jzj=t3:该问题的最优值与minimizet1+t2+t3subjecttox+y�1;2x+z=3;jxj�t1;jyj�t2;jzj�t3:的最优值相同，将这个问题的最优解投影到(x;y;z)所在的空间可以得到原问题的解.这个问题可以写成线性规划问题：minimizet1+t2+t3subjecttox+y�1;2x+z=3;�t1�x�t1;�t2�y�t2;�t3�z�t3:2.3一类逐段线性函数f(x)=maxfcT1x+d1;cT2x+d2;���;cTpx+dpg，其中ci2Rn;di2R;i=1;���;p.针对这样的函数，考虑问题minimizex2Rnf(x)subjecttoAx=bx�0:将此问题化成线性规划.5解:引入变量t，所给问题等价于minimizetsubjecttof(x)=t;Ax=b;x�0:考虑问题minimizetsubjecttof(x)�t;Ax=b;x�0;因为该问题关于t最小化，故将最优解代入第一个不等式，必有等号成立，即问题的最优解和最优值与上一个问题的相同.从而所给问题等价于线性规划问题minimizetsubjecttocTix+di�t;i=1;���;p;Ax=b;x�0:2.5考虑问题minimizec1x1+c2x2+c3x3subjecttox1+x2+x3�4x1�2x3�33x2+x3�6x1;x2;x3�0:注意系数c1;c2;c3尚未确定.表示成标准形Ax=b;x�0后,其中A=266666411110001000100001001003100013777775;x=0BBBBBBBBBBBBB@x1x2x3x4x5x6x71CCCCCCCCCCCCCA;b=0BBBBB@42361CCCCCA;记A的第i列为ai.(a)画出所给问题的可行域(三维空间中).(b)点(0;1;3;0;2;0;0)T是基本可行解吗？(c)点(0;1;3;0;2;0;0)T是退化基本可行解吗？如果是的话，找出可能的与其对应的基.6第二章线性规划:基本理论与方法解:(a)略.(b)是基本可行解，因为满足约束条件，且非零元素对应列a2;a3;a5线性无关.(c)是退化的基本可行解，因为非零元素个数是3，小于系数矩阵A的秩4；共有四个基与该基本可行解对应，他们是B=[a2a3a5aj]，其中j=1;4;6;7.2.8如果与每个非基变量xj对应的既约费用系数rj>0，证明与其对应的基本可行解是唯一的最优解.证明:不妨设满足条件的基本可行解x�对应的基B为系数矩阵A的前m列，即x�=(x�1;:::;x�m;0;0;:::0)T，且rj>0;j=m+1;���;n.则对所有可行的x，有cTx�cTx�=nXj=m+1rjxj�0:设�x是另一个最优解，则必有cT�x�cTx�=0.由于诸rj>0，而�xj�0，由上式，对j=m+1;:::;n有�xj=0；此外，因为�x满足Pnj=1aj�xj=b，将�xj=0;j=m+1;:::;n代入，得Pmj=1aj�xj=b.再由x�的可行性，也有Pmj=1ajx�j=b.而a1;���;am线性无关，从而有�xj=x�j;j=1;���;m.综上，问题的任一最优解均和所给解x�相同，从而满足条件的基本可行解是问题的惟一最优解.2.9举例说明退化基本可行解不用满足所有rj�0也可以是最优的.解:考虑问题minimizex2R3�x1�x2subjecttox1+x2+x3=0x1�0;x2�0;x3�0:显然可行解只有x=(0;0;0)T，这也是最优解。但若用单纯形法来求解，例如选取x3为基变量,则表格为a1a2a3b1110rT�1�100此时非基变量所对应的相对费用系数都是负的，但可见这已经达到最优.2.10将下面的问题转化成标准形，用单纯形法求解，然后画出问题在x1;x2空间的可行域，并标明单纯形法的迭代路径.(b)maximizex1+x2subjectto�2x1+x2�1x1�x2�1x1�0;x2�0:7解:(b)引入松驰变量x3;x4，化为标准形minimize�x1�x2subjectto�2x1+x2+x3=1;x1�x2+x4=1;xi�0;i=1;2;3;4:写出初始表，其已是第一张单纯形表x1x2x3x4xBx3�21101x41�1011cT(rT)�1�1001!x1x2x3x4xBx30�1123x11�1011rT0�2012因为x2对应列无正元素,所以原问题是无界的.2.11(a)利用单纯形法求解maximize2x1+4x2+x3+x4subjecttox1+3x2+x4�42x1+x2�3x2+4x3+x4�3xi�0;i=1;2;3;4:利用(a)中的求解结果回答以下问题：(b)为使最优基保持不变，给出b=(4;3;3)T中第一个元素的可变范围(其它的保持不变)；(c)为使最优基保持不变，给出c=(2;4;1;1)T中第一个元素的可变范围(其它的保持不变)；第四个的？(d)对于b微小的改变，最优解将发生怎样的改变？(e)对于c微小的改变，最优值将发生怎样的改变？解:将原问题化为标准形，得初始表，并依次演算，得x1x2x3x4x5x6x7xBx513011004x621000103x701410013cT(rT)�2�4�1�10000!x1x2x3x4x5x6x7xBx405/2011�1=205=2x111=20001=203=2x601410013rT0�3�1�101038第二章线性规划:基本理论与方法!x1x2x3x4x5x6x7xBx20102=52=5�1=501x1100�1=5�1=53=501x60043=5�2=51=512rT00�11=56=52=506!x1x2x3x4x5x6x7xBx20102=52=5�1=501x1100�1=5�1=53=501x30013=20�1=101=201=41=2rT0007=2011=109=201=413=2至此，所有rj�0,得到最优解x�=(1;1;1=2;0)T.最优基B=[a2a1a3].因为初始单纯形表的最后三列是单位矩阵，故B�1=26642=5�1=50�1=53=50�1=101=201=43775:(a)设b的改变量为�b=(�b1;�b2;�b3)T.要使最优基不变,此时相对费用系数保持不变，故仅需要B�1(b+�b)=xB+B�1�b�0,即266411123775+26642=5�1=50�1=53=50�1=101=201=437752664�b1�b2�b33775�0:(2:1)当b的第一个分量发生变化时，�b2=�b3=0.将此代入(2.1)，可得第一个分量的变化范围为�b12[�5=2;5],相应的，分量b1的取值范围为b12[3=2;9].(b)设c的改变量为�c=(�c1;�c2;�c3;�c4)T.要使最优基不变,基变量的取值不变，仅需要(�cN��cN)T�(�cB��cB)TB�1N�0(请注意该问题是max).而(�cN��cN)T+(cB+�cB)TB�1N=(�cTN+cTBB�1N)��cTN+�cTBB�1N=rTN��cTN+�cTBB�1N:将所需条件写成分量形式，再由yj=B�1aj，得rj��cj+�cTByj�0;j=4;5;6;7:(2:2)由(a)中的最优单纯形表读出rj;yj;j=4;5;6;7，代入不等式组(2.2).当c只有一个分量改变时,令其他分量的改变量为零，解不等式组(2.2)，可得各分量的变化范围.具体地，对第一和第四个分量分别有�c12[�3=4;7=4];�c42(�1;7=20]c12[5=4;15=4];c42(�1;27=20]::9(c)当b改变时，新的基本解是B�1(b+�b)=B�1b+B�1�b，因为B�1b>0，故当b变化不大时，新的基本解仍然是可行的，从而也是最优的.这时，最优解的改变量B�1�b=�25�b1�15�b2;�15�b1+35�b2;�110�b1+120�b2+14�b3�T:(d)当c改变时，新的相对费用系数见(2.2).因为rj>0;j=4;5;6;7，故当c的改变量不大时，相对费用系数仍然是非负的，从而原来的最优解也是最优的.此时，新的最优值是(�cB��cB)TB�1b，最优值的改变量��cTBB�1b=��cTBx�B=��c1��c2�12�c3:2.12考虑问题minimizex1�3x2�0:4x3subjectto3x1�x2+2x3�7�2x1+4x2�12�4x1+3x2+3x3�14x1�0;x2�0;x3�0:(a)找出一个最优解.(b)存在多少个最优基本可行解？(c)证明：如果c4+15a14+45a24�0，则以费用系数c4和系数向量(a14;a24;a34)T引入另一个变量x4后，最优解仍保持不变.解:(a)引入松驰变量x4;x5;x6化为标准形后，得初始表，其也是第一张单纯形表，然后依次演算，x1x2x3x4x5x6xBx43�121007x5�24001012x6�43300114cT(rT)1�3�0:40000!x1x2x3x4x5x6xBx45/20211=4010x2�1=21001=403x6�5=4030�3=415rT�1=20�0:403=409!x1x2x3x4x5x6xBx1104=52=51=1004x2012=51=53=1005x60051�1=2115rT0001=54=501110第二章线性规划:基本理论与方法因为rj�0,得到一个最优解(4;5;0)T,且最优值f�=�11.(b)在(a)的最后一张单纯形表中，因为r3=0，令x3进基,由最小正比率法则，知x6出基,即以5为转轴元转轴后，得x1x2x3x4x5x6xBx11006=259=50�4=258=5x20103=258=25�2=2519=5x30011=5�1=101=53rT0001=54=5011因为rj�0,所以又得到一个最优基本可行解(8=5;19=5;3)T,且目标值仍为f�=�11.(c)将c4和(a14;a24;a34)代入单纯形表，得最后的单纯形表a1a2a3a4a5a6a7B�1b104=5(2=5)a14+(1=10)a242=51=1004012=5(1=5)a14+(3=10)a241=53=1005005a14+a34�(1=2)a241�1=2115rT000(1=5)a14+(4=5)a24+c41=54=5011如c4+(1=5)a14+(4=5)a24�0,则上表达到最优,且最优解保持不变.也可以由(a)中的最后一张表读出最优基B的逆，然后由y4=B�1a4和r4=c4�cTBy4算出单纯形表中与x4对应的数据，然后得出结论.2.16在两阶段法的第I阶段，假定给系统Ax=b;x�0的辅助问题应用单纯形法后，所得表格(忽略费用行)形如x1xkxk+1���xny1���ykyk+1���ym10���0b01...R1S1.........10���0b0k0���010......R2S2......0���010即基变量中有m�k个人工变量，它们取零值.(a)证明R2中的任何非零元素都可作为转轴元以消去人工基变量，这样将产生一个类似的表格，但k会增加1.(b)重复(a)中的过程，直到R2=0.证明原始系统是冗余的，并说明可以删除底端的这些行，然后继续第II阶段.11(c)利用上面的方法(即两阶段法)求解线性规划minimize2x1+6x2+x3+x4subjecttox1+2x2+x4=6x1+2x2+x3+x4=7x1+3x2�x3+2x4=7x1+x2+x3=5xi�0;i=1;2;3;4:解：(c)第I阶段：引入人工变量y1;y2;y3;y4，构造辅助问题minimizey1+y2+y3+y4subjecttox1+2x2+x4+y1=6;x1+2x2+x3+x4+y2=7;x1+3x2�x3+2x4+y3=7;x1+x2+x3+y4=5;xi�0;yi�0;i=1;2;3;4:辅助问题的初始表为x1x2x3x4y1y2y3y4xBy1120110006y2121101007y313�1200107y4111000015cT000011110将最后一行与基变量对应的系数化为零，得第一张单纯形表后，因此进行转轴运算，得x1x2x3x4y1y2y3y4xBy1120110006y2121101007y313�1200107y4111000015rT�4�8�1�40000�25!x1x2x3x4y1y2y3y4xBy11=302=3�1=310�2=304=3y21=305/3�1=301�2=307=3x21=31�1=32=3001=307=3y42=304=3�2=300�1=318=3rT�4=30�11=34=3008=30�19=312第二章线性规划:基本理论与方法!x1x2x3x4y1y2y3y4xBy11/500�1=51�2=5�2=502=5x31=501�1=503=5�2=507=5x22=5103=501=51=5014=5y42=500�2=50�4=51=514=5rT�3=5003=5011=56=50�6=5!x1x2x3x4y1y2y3y4xBx1100�15�2�202x30010�11001x20101�21102y40000�20110rT000031000因为该单纯形表第4行与原问题数据对应的数全为零，从而不能再次转轴将人工变量y4赶出基；此时，第4个约束为冗余的,将其删除后，得基本可行解(2;2;1;0)T.第II阶段：以上述基本可行解作为初始基本可行解，利用单纯形法求解原问题.首先得到如下初始表x1x2x3x4xBx1100�12x300101x201012cT26110将最后一行与基变量对应的系数化为零后，得第一张单纯形表后，因此进行转轴运算，得x1x2x3x4xBx1100�12x300101x201012rT000�3�17!x1x2x3x4xBx111004x300101x401012rT0300�11因为rj�0,所以得最优解x�=(4;0;1;2)T,f�=11.132.17利用修正单纯形法找出下列系统的一个基本可行解x1+2x2�x3+x4=32x1+4x2+x3+2x4=12x1+4x2+2x3+x4=9xi�0;i=1;2;3;4:解：引入人工变量x5;x6;x7，构造辅助问题.得辅助问题的如下表格B�1xBx51003x601012x70019由此表格得�T=(1;1;1);rTN=cN��TN=(�4;�10;�2:4).让x2进基，计算y2=B�1a2=(2;4;4)T，得首张修正单纯形表，并转轴，得B�1xBy2x510032x6010124x700194�T1112410!B�1xBx21=2003=2x6�2106x7�2013�T�4119计算相对费用系数，得r1=1;r3=�7;r4=1;r5=5.选取x3进基，计算y3=B�1a3=(�1=2;3;4)T.故有B�1xBy3x21=2003=2�1=2x6�21063x7�20134�T�41197!B�1xBx21=401=815=8x6�1=21�3=415=4x3�1=201=43=4�T�1=21�3=415=4计算相对费用系数，得r1=�3=4;r4=�3=4;r5=3=2;r7=7=4.选取x1进基，计算y1=B�1a1=(3=8;3=4;�1=4)T.故有B�1xBy1x21=401=815=83=8x6�1=21�3=415=43/4x3�1=201=43=4�1=4�T�1=21�3=415=43=4!B�1xBx21=2�1=21=20x1�2=34=3�15x3�2=31=302�T0000计算相对费用系数，得r4=0;r5=r6=r7=1.至此得到辅助问题的最优基本可行解.因为基变量不含人工变量，所以得原问题的基本可行解x=(5;0;2;0)T.2.20利用单纯形法求解问题(2.2.14)，其中初始点x(0)=(0;0;0)T，要求每次迭代选既约费用系数最负的变量进基.14第二章线性规划:基本理论与方法解：将原始问题化为标准形,利用单纯形法求解，因此得如下单纯形表格x1x2x3x4x5x6xBx41001001x5410010100x684100110000rT-4-2-10000�!x1x2x3x4x5x6xBx11001001x5010-41096x6041-8019992rT0-2-14004�!x1x2x3x4x5x6xBx11001001x2010-41096x60018-419608rT00-1-420196�!x1x2x3x4x5x6xBx41001001x2410010100x6-8010-419600rT40-1020200�!x1x2x3x4x5x6xBx41001001x5410010100x6-8010-419600rT-4000-219800�!x1x2x3x4x5x6xBx11001001x2010-41096x30018-419608rT0004-21980415�!x1x2x3x4x5x6xBx11001001x5010-41096x3041-8019992rT020-4019996�!x1x2x3x4x5x6xBx41001001x5410010100x384100110000rT42000110000整个迭代遍历了原问题在三维空间中的超立方体可行域的全部8个顶点.得最优解x�=(0;0;10000)T;对应的目标函数值是10000.2.24构造一个原始问题和对偶问题都没有可行解的例子.解：构造原问题如下minimize�x1�x2subjecttox1�1;�x2�1;x1�0;x2�0:其对偶问题为maximize�1+�2subjectto�1��1;��2��1;�1�0;�2�0:易见二者均无可行解.2.25设A是m�n矩阵,b是n维向量.证明Ax�0蕴含着cTx�0当且仅当存在��0使得c+AT�=0.给出该结论的一个几何解释.证：充分性.假设存在��0，使得cT+�TA=0成立，则对任意的x2Rn，有cTx=��T(Ax)成立.如果x使得Ax�0，则由��0必有cTx�0成立.必要性.构造如下线性规划问题，即minimizecTxsubjecttoAx�0:它的对偶问题为maximize0subjectto�TA=cT��0:16第二章线性规划:基本理论与方法易见x=0是原始问题的一个可行解，且由Ax�0蕴含着cTx�0可知，原始问题的目标函数有下界.根据弱对偶性，对偶问题也有可行解，即存在�0�0且满足(�0)TA=cT.令�=��0，易见�即为满足条件的向量.注：这个结论即著名的Farkas引理，详见课本163页的引理7.3.4.关于该结论的证明常见的有两种，一种即该作业的基于线性规划对偶理论的证明，还有一种就是课本上给出的基于点与闭凸锥的分离定理(引理7.3.5)的证明.课本上给出的证明是构造性的，即给出了具体的满足要求的向量�.将该结论用在非线性规划的最优性条件的推导中，这个结论中的向量�就是著名的Lagrange乘子.此外，如果要用对偶性构造出所需的向量�，需要用线性规划强对偶定理的证明，即37页的定理2.3.2，那里也用了凸集分离定理.几何解释：定义集合C=fcjc=AT�;��0g，此即A的行向量生成的锥集合(行向量的所有非负线性组合形成的集合)，以及C�=fxjAx�0g，此集合由与C中每个向量所夹角均不是锐角的向量组成，也称为C的极锥(polarcone).Farkas引理表明：如果向量c与C�中的每个向量的夹角为锐角或者直角，即满足cTx�0;8x2C�;那么�c必属于C，反之亦成立.令A="1113#，Farkas引理的几何解释见图2.1.2a1aC$C图2.1:习题2.25Farkas引理的几何解释Farkas引理的另一种描述：系统I：Ax�0;cTx<0与系统II：��0;cT+�TA=0有且只能有一个有解.系统I有解等价于存在向量x，它与A的每个行向量的夹角至少为90�，且它与向量�c的夹角小于90�；系统II有解等价于向量�c在由A的行向量生成的凸锥中.基于此描述，Farkas引理的几何解释如下：给定一个由A的行向量生成的凸锥C和向量�c，要么向量�c属于锥，要么存在一个超平面H:=fy2Rn:yTx�=0g;其中x�为系统I的解17分离该凸锥和这个向量(即C在这个超平面的非正半空间，向量�c在这个超平面确定的正半空间)，且二者不会同时成立.2.26通常在优化理论和自由竞争之间有很强的联系，这可通过经营实体选址的理想模型进行说明.假设存在n种经营实体(各种工厂、公司、商场等)，准备将它们单独地设在n块不同的土地上.如果将实体i设在第j块上，能够产生sij单位(元)的价值.如果给实体指派土地的工作由专家来作，一种作法是使生产价值最大来作出决定.换句话说，确定的指派方式要极大化PiPjsijxij，其中xij=(1;如果将实体i指派到土地j0;否则.更明确地说，该方法需要求解优化问题maximizePiPjsijxijsubjecttoPjxij=1;i=1;2;���;nPixij=1;j=1;2;���;nxij�0;xij2f0;1g;i;j=1;2;���;n:实际上，能够证明：通过约束定义的集合的任一极点是自动满足最终的要求(xij=0或1)的，所以通过线性规划的单纯形法能够找到最优指派.如果一个人从自由竞争的观点来考虑问题，假定不是由专家来确定指派，而是建立价格机制，由各个实体对土地进行投标.(a)证明：存在实体的价格pi;i=1;���;n和土地价格qj;j=1;���;n使得pi+qj�sij;i=1;���;n;j=1;���;n:进一步，如果一个最优解指派实体i到土地j，在这组价格使上述不等式中的等号成立.(b)证明(a)蕴含着：如果最优解指派实体i到土地j，且如果j0是任一其他的土地，有sij�qj�sij0�qj0:给出该结论的一个经济解释，并以此为背景解释自由竞争和最优性之间的关系.(c)假定每一个sij是正的，请证明(a)中存在的价格是非负的.解：(a)令c=(s11���s1ns21���s2n���sn1���snn)T;y=(x11���x1nx21���x2n���xn1���xnn)T.A=0BBBBBBBBBBBBBBBB@11���111���1...11���110���010���0���10���001���001���0���01���0......���...00���100���1���00���11CCCCCCCCCCCCCCCCA=A1A2!b=0BBBBBBBBBBBBBBBB@11...111...11CCCCCCCCCCCCCCCCA=b1b2!则所给的优化问题可写为maximizecTysubjecttoAy=by�0;y2f0;1gn2(2.1)18第二章线性规划:基本理论与方法这个问题的松弛问题(去掉整性约束)为maximizecTysubjecttoAy=by�0(2.2)用单纯形法求解这个具有标准形的线性规划问题.因为该问题有可行解，且目标函数在可行域上有上界，所以能得到基本可行(极点)解x�，x�会自动满足整性要求.所以这个松弛问题和原始问题(2.1)的最优值相等.考虑松弛问题(2.2)的对偶问题，即minimize�TbsubjecttoAT��c具体地，即minimizePiui+Pjvjsubjecttoui+vj�sij;i;j=1;2;���;n:(2.3)因为原始问题(2.2)有最优解，由强对偶定理，对偶问题(2.3)有最优解.设��=(p1p2���pnq1q2���qn)T是一个最优解，这里qj是为第j块土地定出的价格.则由可行性有pi+qj�sij.如果最优解指派实体i到土地j，即x�ij=1>0，则由互补性有pi+qj=sij.(b)sij�qj表示当实体i投标土地j时所能获得的净利润.如果最优解指派实体i到土地j，(a)中最后的结论表明pi+qj=sij(互补性).若实体i未投标土地j0，则由可行性有pi+qj0�sij0.联立这两个式子，得到sij�qj�sij0�qj0;这表明按照题目中所给的问题的最优解配置时，既能使整个收益最大化，也能使每个实体i获得最大利润.即专家按照总体收益最大化进行配置与自由竞争下各实体追求各自的利润最大化得到的结果相一致.从而，专家可以通过对土地进行合理定价(求解问题(2.3))，所得价格可以诱导各实体在自由竞争的情况下追求各自利润最大的同时使得总体收益最大.(c)考虑问题maximizecTysubjecttoAy�by�0;y2f0;1gn2(2.4)maximizecTysubjecttoAy�by�0(2.5)如果问题(2.4)的最优解使得不等式约束Ay�b取等号，那么其松弛问题(2.5)的对偶问题与问题2.3相比，会增加非负约束.利用与(a)和(b)中完全类似的分析，可以得到(a)和(b)中的结果.19下面说明问题(2.4)的最优解使得不等式约束中的等号成立.假设x�是最优解，且对应的向量是y�.则Ay��b.若这2n个不等式中至少有一个严格成立，不妨设是前n个不等式中的第1个不等式严格成立.再由整性约束，必有Pnj=1x�ij=0，从而x�1j=0;j=1;2;���;n.进一步，由A的特殊性，后n个不等式中至少有一个是严格成立的，设为n.同前，得x�in=0;i=1;2;���;n.令x^1n=1;x^ij=x�ij;i6=1;j6=n;易见x^是(2.4)的可行解，且其对应的目标值比最优值大s1n，又因为s1n是正的，这与x�的最优性矛盾.综上，总可以假定价格是非负的.2.32(a)利用单纯形法求解minimize2x1+3x2+2x3+2x4subjecttox1+2x2+x3+2x4=3x1+1x2+2x3+4x4=5xi�0;i=1;2;3;4:(b)利用(a)中所作工作和对偶单纯形法求解相同的问题,除了方程组的右端向量变成(18)T.解:(a)因为该问题没有显然的基本可行解，利用两阶段法求解该问题.第I阶段：首先引入人工变量x5;x6，构造辅助问题minimizex5+x6subjecttox1+2x2+x3+2x4+x5=3;x1+x2+2x3+4x4+x6=5;xi�0;i=1;2;3;4;5;6:利用单纯形法求解辅助问题.首先得初始表x1x2x3x4x5x6xBx51212103x61124015cT0000110将基变量x5;x6对应的最后一行的系数化为零，得第一张单纯形表x1x2x3x4x5x6xBx51212103x61124015rT�2�3�3�600�820第二章线性规划:基本理论与方法以4为转轴元，即x4进基，x6出基，得x1x2x3x4x5x6xBx51=23/2001�1=21=2x41=41=41=2101=45=4rT�1=2�3=20003=2�1=2再次转轴之后，得x1x2x3x4x5x6xBx21=31002=3�1=31=3x41=601=21�1=61=37=6rT0000110因为辅助问题的最优值为0，所以原始问题有可行解.因为基变量不含人工变量，故x=(0;1=3;0;7=6)T是一个基本可行解.第II阶段：在第I阶段的最后一个单纯形表中删去人工变量所对应列和最后一行，可得原始问题的一张初始表x1x2x3x4xBx21=31001=3x41=601=217=6cT23220将基变量x2和x4下面的系数化为零，得第一张单纯形表x1x2x3x4xBx21=31001=3x41=601=217=6rT2=3010�10=3因为相对费用系数向量非负，故得最优解x�=(0;1=3;0;7=6)T，最优值z�=10=3.(b)由(a)可知B=(a2;a4)，所以B�1="2=3�1=3�1=61=3#.右端项改为(18)T后，只需将上表的最后一列改为B�1"18#="�2156#.这时，得新问题的单纯形表x1x2x3x4xBx21=3100�2x41=601=21156rT2=30101此时，由对偶单纯形法，x2出基，但是第一行没有负元素.由单纯形表第一行的数据知，问题的第一个约束等价于13x1+x2=�2.而变量非负，故修改右端项后所得新问题没有可行解.212.33对于问题minimize5x1�3x2subjectto2x1�x2+4x3�4x1+x2+2x3�52x1�x2+x3�1x1�0;x2�0;x3�0;(a)以1为转轴元,仅转轴一次找到一个可行解；(b)利用单纯形法求解问题；(c)对偶问题是什么?(d)对偶问题的解怎么样?解:(a)引入松驰变量x4;x5和盈余变量x6后，得标准形问题minimize5x1�3x2subjectto2x1�x2+4x3+x4=4;x1+x2+2x3+x5=5;2x1�x2+x3�x6=1;x1;x2;x3;x4;x5;x6�0:得与等式约束对应的表格如下x1x2x3x4x5x6b2�14100411201052�1100�11以1为转轴元转轴(即从第三个方程解出x3，代入第一个和第二个方程消去x3)后，得x1x2x3x4x5x6xB�6301040�33001232�1100�11该表对应着原始问题的一个基本可行解.(b)下面利用单纯形法求解原始问题.首先得初始表为x1x2x3x4x5x6xBx4�6301040x5�3300123x32�1100�11cT(rT)5�30000022第二章线性规划:基本理论与方法因为最后一行与基变量对应的系数已经为零，故上面的初始表即为第一张单纯形表.以3为转轴元进行转轴后，得x1x2x3x4x5x6xBx2�2101=304=30x5300�11�23x30011=301=31rT�1001040再以3为转轴元转轴后，得x1x2x3x4x5x6xBx2010�1=32=302x1100�1=31=3�2=31x30011=301=31rT0002=31=310=31因为相对费用系数向量非负，故得原始问题最优解x�=(1;2;1)T,最优值z�=�1.(c)原始问题的对偶问题为maximize4w1+5w2+w3subjectto2w1+w2+2w3�5;�w1+w2�w3��3;4w1+2w2+w3�0;w1�0;w2�0;w3�0:(d)易于看到原始问题引入松驰变量x4;x5和盈余变量x6后，所得标准形问题的对偶问题也是该问题.从而标准形问题的最优乘子(��)T=cTBB�1即为对偶问题的最优解，其中B为最优解对应的基.而hr4r5r6i=hc4c5c6i�cTBB�1ha4a5a6i=h000i�h��1��2��3i266410001000�13775=h���1���2��3i所以由(b)中的最优单纯形表，得��=(�2=3;�1=3;10=3)T.计算易得最优值为�1.第三章线性规划：应用及扩展习题设计说明：1.习题3.1用以熟悉网络单纯形法中各个量的计算方式；习题3.4用以熟悉网络单纯形法求解运输问题时，其中各个量的存储和计算方式.2.习题3.2和习题3.3是关于网络流问题的理论性质的练习.3.习题3.5，习题3.6和习题3.7介绍典型的可以建模为整数规划的运筹问题，其中背包问题和车辆路由问题都可建模为0-1线性规划、二次指派是0-1二次规划，利用线性化技术也可表示成0-1线性规划问题.并以背包问题为例，说明求解该问题的分枝定界法的计算复杂度是指数级的.4.习题3.8是用以体会对偶单纯形法在求解整数线性规划的分支限界法中的特殊应用，体会根据问题性质和应用场景选取算法的重要性！5.习题3.9用以熟悉分枝定界法，如剪枝、定界、分支等.3.1.考虑图3.1.1所示的网络流问题，令T=f(b;c);(c;a);(d;c);(e;b)g，即如下生成树.abedc请以e为根节点,完成以下工作:(a)求每个树弧上的原始流量；(b)求与每个节点对应的单纯形乘子；(c)求与每个非树弧对应的既约费用系数.解:(a)原始流量为xca=2,xdc=5,xbc=1,xeb=1.(b)以e为根节点，则单纯形乘子依次为yb=�11,yc=�13,yd=12,ya=�27.(c)非树弧的既约费用系数依次为rab=28;rce=23;rda=�29;rde=�2:3.4考虑表3.2.1所给的运输问题.(a)表3.2.2给出的树解原始可行吗？对偶可行吗？(b)求解该运输问题.解:(a)树解非负，故为原始可行，相对费用系数含负数，故不是最优解.2324第三章线性规划:应用及扩展(b)首先假设S=f1;2;3;4g;D=f5;6;7g.表3.2.1费用信息SnD102715756*1184318*9*16*36表3.2.2运输问题的树解yinyj-5-1-4075*338-48*18*2*115因为只有r27=�4为负，所以选x27为入弧，这样弧x26;x27;x46;x47形成一个圈.与x27异向的弧有x26;x47，选取流量最小的弧x26为出弧；更新圈上弧的流量为x26=0;x27=8;x46=9;x47=7:然后分别计算子树3,6的单纯形乘子和非树弧x16;x26的相对费用系数y3=12;y6=3;(入弧指向不含根节点的子树，单纯形乘子均减少-4)；r16=9;r26=4:(非树弧均与入弧同向，相对费用系数都减少-4)最后得到更新后的树解：yinyj-530079*334812*18*6*97因为相对费用系数都非负，所以当前树解是最优的；最小运输费f�=314:3.7二次指派问题(quadraticassignmentproblem).令F是n个工厂的集合,C是n个城市的集合.要求在每一城市中设置且只设置一个工厂,并要使工厂两两之间总的通讯费用最小.每对工厂(i;k)之间一定时间内通讯的次数为tik,每对城市(j;l)之间的距离为djl.通讯费用cijkl=tikdjl.(a)试为该问题建立目标函数为二次函数的整数规划模型.(b)将上述模型中的非线性目标函数线性化.解:(a)建模：设xij=1表示在城市j建工厂i，xij=0表示不在城市j建工厂i，则i2F,j2C.这样，cijkl（即tikdjl）表示在城市j的工厂i到在城市l的工厂k之间的通讯费.这样得到二次的目标函数，即Xi;k2FXj;l2Ccijklxijxkl:显然有0,1约束：xij2f0;1g.由于每一个城市中有且只有一个工厂，故得到约束PFxij=1;8j2C:而每一个工厂也只能在一个城市中，故得到约束PCxij=1;8i2F:习题325综上，二次指派问题的优化模型为minimizePi;k2FPj;l2CcijklxijxklsubjecttoPi2Fxij=1;8j2C;Pj2Cxij=1;8i2F;xij2f0;1g;8i2F;j2C:(b)线性化目标函数：由于诸cijkl�0，故可以利用新变量yijkl来替换xijxkl，其中yijkl满足yijkl�xij+xkl�1;yijkl�0:这样，二次指派问题就转化为具有线性目标函数的0-1线性规划问题，即minimizePi;k2F;j;l2CcijklyijklsubjecttoPi2Fxij=1;8j2C;Pj2Cxij=1;8i2F;yijkl�xij+xkl�1;yijkl�0;8i;k2F;j;l2Cxij2f0;1g;8i2F;j2C:3.8考虑例3.4.4的枚举树上节点2的线性规划松弛问题P2.请从P0的最优单纯形表开始,利用对偶单纯形法求解P2.解:首先写出P0的最优单纯形表x1x2x3B�1b10:5�0:251:25rT01:50:25�1:25给P0添加约束x1�2就得到P2，再对该约束引进一个松弛变量x4，继而写出表格x1x2x3x4B�1b10:5�0:2501:25�1001�2rT01:50:250�1:25将第一行加到第二行后，得到单纯形表x1x2x3x4B�1b10:5�0:2501:2500:5-0.251�0:75rT01:50:250�1:25此时得到的P2的基本解是对偶可行的，所以利用对偶单纯形法求解.以-0.25为转轴元转轴后，得到x1x2x3x4B�1b100�120�21�43rT0201�226第三章线性规划:应用及扩展此为最优表，得最优解x�=(2;0)T.3.9对线性规划minimize�x1�2x2subjectto�2x1+2x2�32x1+2x2�9;分(i)无整数限制,(ii)x1为整数,(iii)x1;x2均为整数三种情况，用图解法求解相应的问题.并给出用分枝定界法求解(iii)的过程,画出枚举树.解:根据题意，由图3.1(a)可知，三种情况的最优解分别是x�=(1:5;3)T;(ii)x0=(2;2:5)T;(iii)x00=(2;2)T.1x2x12229xx!12223xx"!(0)x122xx""(3)x(7)x(5)x(8)x(1)x(2)x(a)整数规划的图解.016-7.5-7.5-7-7-¥11x£12x³223x³22x£422x£23x³-63-657812x£13x³-6.5-6.5(b)分枝定界法的枚举树(采用的是深度优先的枚举策略).图3.1:习题3.9图解图3.1(b)表示用分枝定界法求解(iii)的枚举树，其中枚举策略是深度优先.方法依次求解问题的详细信息见下表，其中Pi表示子问题编号，L表示为子问题确定的下界，x�和f�分别表示松弛子问题后所得线性规划问题的最优解和最优值，x^和f^分别表示当前最好解和最好值.(Pi;L)x�Tf�采取措施x^Tf^(P0;�1)(1:5;3)�7:5分枝，得(P1;�7:5)&(P2;�7:5)[]+1(P1;�7:5)(1;2:5)�6分枝，得(P3;�6)&(P4;�6)(P3;�6)(1;2)�5得可行解，更新x^，剪枝(1;2)�5(P4;�6)[]+1子问题不可行，剪枝(P2;�7:5)(2;2:5)�7分枝，得(P5;�7)&(P6;�7)(P5;�7)(2:5;2)�6:5分枝，得(P7;�6:5)&(P8;�6:5)(P7;�6:5)(2;2)�6得可行解，更新x^，剪枝(2;2)�6(P8;�6:5)(3;1:5)�6f��L;剪枝(P6;�7)[]+1子问题不可行，剪枝第四章无约束优化：基础习题设计说明：1.最优性条件：习题4.1-习题4.5.2.凸函数：习题4.6.收敛速度：习题4.7.3.一维搜索：4.8-4.13.4.2考虑问题minx2RnkAx�bk2,其中A是m�n矩阵,b是m维向量，m>n.(a)给出问题的几何解释.(b)写出最优性的必要条件.它也是一个充分条件吗？(c)最优解唯一吗？理由是什么？(d)你能给出最优解的一种闭合形式(解析式)吗？在满足题目所给信息下，允许规定任何你所需的假设.(e)求解该问题,其中A=26666641�100210101013777775;b=0BBBBB@21101CCCCCA:解:(a)几何解释：问题在求向量b到A的值空间R(A)(即由A的列生成的子空间)的最小距离.设b在R(A)上的投影为c，则满足Ax=c的解x�即为最优解.具体例子见(e)，这时有三个未知数，四个方程，所给方程没有普通意义的解，称这里求出的x�是方程组的最小二乘解.(b)令f(x)=kAx�bk2=xTATAx�2bTAx+bTb;rf(x)