最优化方法练习题答案

练习题一1、建立优化模型应考虑哪些要素答决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。答针对一般优化模型，讨论解的可行域，若存在一MIN0,12,IJFXSTGIMHJPD点，对于均有则称为优化模型最优解，最优解存在；XDXFFX迭代算法的收敛性是指迭代所得到的序列，满足12,K，则迭代法收敛；收敛的停止准则有，1KKFF1KKX，等等。KKX1KKFXF1KFXFKFX练习题二1、某公司看中了例21中厂家所拥有的3种资源R1、R2、和R3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少（该问题称为例21的对偶问题）。解确定决策变量对3种资源报价作为本问题的决策变量。123,Y确定目标函数问题的目标很清楚“收购价最小”。确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。因此有如下线性规划问题123MIN7050WYY31258,0STY2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。答略。3、用单纯形法求解下列线性规划问题（1）0,4322MIN11XXXTSZ；（2）5,2104MIN324132IXXXTSZI解（1）引入松弛变量X4，X5，X6123MINZX4123256,0XSTXCJ111000CB基BX1X2X3X4X5X60X421121000X532110100X64101001CJZJ111000因检验数20，表明已求得最优解，去除添加的松弛,8/1,/3X变量，原问题的最优解为。0,8/31X（2）根据题意选取X1，X4，X5，为基变量5,2104MIN324132IXXXTSZICJ01100CB基BX1X2X3X4X50X12121000X42012100X5501101CJZJ01100因检验数20，表明已求得最优解。9,4X4、分别用大M法、两阶段法和MATLAB软件求解下列线性规划问题（1）0,326934MIN112XXTSZ；（2）0,5216593210MAX313XXTSZ解（1）大M法根据题意约束条件1和2可以合并为1，引入松弛变量X3，X4，构造新问题。1234MINZ4X0X12443,0STXCJ41M0CB基BX1X2X3X4MX3331100X431201CJZJ43M1M004X1111/31/300X4205/31/31CJZJ01/3M4/304X13/5102/51/51X26/5011/53/5CJZJ00M7/51/5因检验数J0，表明已求得最优解。3/5,6XMATLAB调用代码F41A9,31,2B63AEQ3,1BEQ3LB00X,FVALLINPROGF,A,B,AEQ,BEQ,LB输出结果OPTIMIZATIONTERMINATEDX0600012000FVAL36000（2）大M法引入松弛变量X4，X5，X6，X7构造新问题。1234567MA00ZXM234156775961,0XXSTX单纯形表计算略；当所有非基变量为负数，人工变量05，所以原问题无可行解。7X请同学们自己求解。MATLAB调用代码F101512A5,3,15,6,152,1,1B9155LB000XLINPROGF,A,B,LB输出结果原题无可行解。5、用内点法和MATLAB软件求解下列线性规划问题0,526MIN31321XTSXZ解用内点法的过程自己书写，参考答案最优解；最优值54/370XMATLAB调用代码F211AEQ1,2,22,1,0BEQ65LB000X,FVALLINPROGF,AEQ,BEQ,LB输出结果OPTIMIZATIONTERMINATEDX133332333300000FVAL500006、用分支定界法求解下列问题（1）且0,459568MAX2121XTSXZ；（2）且121210,35769MAXXXTSXZ解（1）调用MATLAB编译程序BBMETHODF58G1159H645X,YBBMETHODF,G,H,00,11,1X33Y39最优解33；最优值39（2）调用MATLAB编译程序BBMETHODF79G1371H635X,YBBMETHODF,G,H,00,10,1X50Y35最优解50；最优值357、用隐枚举法和MATLAB软件求解下列问题（1）3,210445223MIN1JXXXTSXZJ且；（2）5,21036184374235MAX2531JXXXTSXZJ且解隐枚举法（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）调用代码F432价值向量FA2,5,34,1,30,1,1不等式约束系数矩阵A，中的分号“；”为行分隔符B431不等式约束右端常数向量BX,FVALBINTPROGF,A,B,调用函数BINTPROG。注意两个空数组的占位作用。输出结果X001FVAL2（2）调用代码F32523价值向量FA1,1,1,2,17,0,3,4,311,6,0,3,3不等式约束系数矩阵A，中的分号“；”为行分隔符B481不等式约束右端常数向量BX,FVALBINTPROGF,A,B,调用函数BINTPROG。注意两个空数组的占位作用。输出结果X11000FVAL5最优值5。8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表228所示。试制定一个使总运费最少的化肥调拨方案。表21运价/产粮元/吨区化肥厂甲乙丙丁各厂供应量/万吨A158737A2491078A384293各区需要量/万吨6633解设A、B、C三个化肥厂为A1、A2、A3，甲、乙、丙、丁四个产粮区为B1、B2、B3、B4；CIJ为由AI运化肥至BJ的运价，单位是元/吨；XIJ为由AI运往BJ的化肥数量（I1,2,3J1,2,3,4）单位是吨；Z表示总运费，单位为元，依题意问题的数学模型为341MINIJIZCX1233142341231234678XSTXX该题可以用单纯形法或MATLAB自带工具箱命令（LINPROG）求解。9、求解下列不平衡运输问题（各数据表中，方框内的数字为单位价格IJC，框外右侧的一列数为各发点的供应量IA，框底下一行数是各收点的需求量JB）（1）51710要求收点3的需求必须正好满足。6468032515752050（2）51020要求收点1的需求必须由发点4供应。32410752159601551015解答略。10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表229所示。公司经理应怎样分派才使总利润最大表22地区推销员1234135272837228342940335243233424322528解用求极大值的“匈牙利法”求解。效率矩阵表示为2853243409877125816750233所画（）0元素少于4708231629408218620N（N4），未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）4082108620未被直线覆盖的最小元素为CIJ2，在未被直线覆盖处减去2，在直线交叉处加上2。640810640810）（）（得最优解010使总利润为最大的分配任务方案为11，24，33，42此时总利润W35403232139标号列约简MCIJM40行约简标号练习题三1、用0618法求解问题12MIN30TTT的近似最优解，已知的单谷区间为，要求最后区间精度。T,05答T08115；最小值00886（调用GOLDSM函数）2、求无约束非线性规划问题MIN,321XF123214X的最优解解一由极值存在的必要条件求出稳定点，则由0FX得，12FX28FX3FX120X3再用充分条件进行检验，21FX2F23FX21FX213FX23FX即为正定矩阵得极小点为，最优值为1。2082FT,0解二目标函数改写成MIN,321XF221341X易知最优解为（1,0,0），最优值为1。3、用最速下降法求解无约束非线性规划问题。2121MINXXXF其中，给定初始点。TXX,21T0,解一目标函数的梯度FX11224FXXF令搜索方向再从出发，沿方向作一维寻01FX101DFX0X1D优，令步长变量为，最优步长为，则有1011XD故01221FXXD令可得求出点之后，121101D1X与上类似地，进行第二次迭代令1FX21F令步长变量为，最优步长为，则有21211XD故1222211151FX令可得20252208XD此时所达到的精度2FX208F本题最优解，151,5FX解二利用MATLAB程序求解首先建立目标函数及其梯度函数的M文件FUNCTIONFFUNXFX1X22X1X12X1X2X2X2FUNCTIONGGFUNXG14X12X2,12X12X2调用GRADM文件X00,0X,VAL,KGRADFUN,GFUN,X0结果X10000,15000VAL12500K33即迭代33次的到最优解X10000,15000；最优值VAL12500。4、试用NEWTON法求解第3题。解一计算目标函数的梯度和HESSE阵目标函数的梯度FX11224FXXF，其逆矩阵为242FXG1051010,1,5TTTF计算。1FX本题最优解，51,25FX解二除了第3题建立两个M文件外，还需建立HESSE矩阵的M文件利用MATLAB程序求解首先建立目标函数及其梯度函数的M文件FUNCTIONFFUNXFX1X22X1X12X1X2X2X2FUNCTIONGGFUNXG14X12X2,12X12X2FUNCTIONHHESSXG4222调用NEWTONM文件X00,0X,VAL,KNEWTONFUN,GFUN,HESS,X0结果X10000,15000VAL12500K15、用FLETCHERREEVES法求解问题215MINXXF其中，要求选取初始点。TXX,21600,2T解一，1122,05XFX05G12,50TRFXX第一次迭代令，4,TPR0,1012504,5TRG即，10019,TXP第二次迭代，1384,TR210|30RT103846,015PR184,22363846,015015TRPG217,TX第三次迭代（建议同学们自己做下去，注意判别KR）2046,3TR解二利用MATLAB程序求解首先建立目标函数及其梯度函数的M文件FUNCTIONFFUNXFX1225X2X2FUNCTIONGGFUNXG2X1,50X2调用FRCGM文件X02,2EPSILON1E6X,VAL,KFRCGFUN,GFUN,X0,EPSILON结果X10E00602651,00088VAL72182E014K616、试用外点法（二次罚函数方法）求解非线性规划问题012MINXXGTSXF其中21,RXX解设计罚函数,2PMF采用MATLAB编程计算，结果X10；最优结果为1。（调用WAIDIANFAM）7、用内点法（内点障碍罚函数法）求解非线性规划问题3122MIN0XST解容易看出此问题最优解为X10；最优值为8给出罚函数为31212,/PXRXRX令；21211,30PXR22,0P从而当时，0R1/3RXRX（建议同学自己编程序计算）8、用乘子法求解下列问题211MIN0FXXH解建立乘子法的增广目标函数211212,XXX令1121,02121,XX解上述关于X的二元一次方程组得到稳定点2X当乘子取2时，或发参数趋于无穷时，得到即最优解。1X（建议同学自己编程序计算）练习题四1、石油输送管道铺设最优方案的选择问题考察网络图46，设A为出发地，F为目的地，B，C，D，E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小图41解第五阶段E1F4；E2F3；第四阶段D1E1F7；D2E2F5；D3E1F5；第三阶段C1D1E1F12；C2D2E2F10；C3D2E2F8；C4D3E1F9；第二阶段B1C2D2E2F13；B2C3D2E2F15；第一阶段AB1C2D2E2F17；最优解AB1C2D2E2F最优值172、用动态规划方法求解非线性规划123123MAX7,0FX解，最优值为9。1239,9XX3、用动态规划方法求解非线性规划22121MAX765039,ZXST解用顺序算法阶段分成两个阶段，且阶段1、2分别对应。12,X决策变量12,X状态变量分别为第J阶段第一、第二约束条件可供分配的右段数值。IVW122211110,MA76IN76,XVFVW11IN,X2212205222AX,3MIN76,7363FVWFVXVXWXX由于，221,9V2222205AXIN39760,83961FWFXX可解的，最优值为70292。126,X4、设四个城市之间的公路网如图47。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路线及相应的最短距离。214358674图42城市公路网解城市1到城市4路线134距离10；城市2到城市4路线24距离8；城市3到城市4路线34距离4。5、某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表419所示。试问在各地区如何设置销售点可使每月总利润最大。表41地区销售点0123412306120517402163217地区地区销售点销售点解将问题分为3个阶段，K1，2，3；决策变量XK表示分配给第K个地区的销售点数；状态变量为SK表示分配给第K个至第3个地区的销售点总数；状态转移方程SK1SKXK，其中S14；允许决策集合DK（SK）XK|0XKSK阶段指标函数GK（XK）表示XK个销售点分配给第K个地区所获得的利润；最优指标函数FK（SK）表示将数量为SK的销售点分配给第K个至第3个地区所得到的最大利润，动态规划基本方程为104MAX3,21KKKKSFGFXK3时，333XSF417174316163214142110101000043210X3F3S3G3（X3）（）K2时，222320MAXSFGFSX2,33120211017141216017422721017101214016312170121001421121200101000043210X2F2S2G2X2F3S2X2K1时，10MAXSFGFSX1204MAXFSGFX最优解为X12，X21，X31，F1447，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。6、设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解四个季度为四个阶段，采用阶段编号与季度顺序一致。设SK为第K季初的库存量，则边界条件为S1S50设XK为第K季的生产量，设YK为第K季的订货量；SK，XK，YK都取实数，状态转移方程为SK1SKXKYK仍采用反向递推，但注意阶段编号是正向的目标函数为12342,1MIN05IIXFXS第一步第四季度总效果F4S4,X40005X42S4由边界条件有S5S4X4Y40，解得X41200S4将X4代入F4S4,X4得F4S400051200S42S4720011S40005S42第二步第三、四季度总效果F3S3,X30005X32S3F4S4将S4S3X3500代入F3S3,X3得23232233333323,05701501619,01085,7FXSXSFSSFSXFS解得代入得第三步第二、三、四季度总效果F2S2,X20005X22S2F3S3将S3S2X2700代入F2S2,X2得22222222,057070,15703,6FSFSXSFXFSS解得代入得第四步第一、二、三、四季度总效果F1S1,X10005X12S1F2S2将S2S1X1600X1600代入F1S1,X1得212111112,050603,4860,FXFSXFSFS解得代入得由此回溯得最优生产库存方案X1600，S20；X2700，S30；X3800，S4300；X4900。7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为G8U1，其中U1为投入生产的机器数量，年完好率A07；在低负荷下生产的产量函数为H5Y，其中Y为投入生产的机器数量，年完好率为B09。假定开始生产时完好机器的数量S11000。试问每年如何安排机器在高、低负荷下的生产，使在5年内生产的产品总产量最高。解构造这个问题的动态规划模型设阶段序数K表示年度。状态变量SK为第K年度初拥有的完好机器数量，同时也是第K1年度末时的完好机器数量。决策变量UK为第K年度中分配高负荷下生产的机器数量，于是SKUK为该年度中分配在低负荷下生产的机器数量。这里SK和UK均取连续变量，它们的非整数值可以这样理解，如SK06，就表示一台机器在K年度中正常工作时间只占6/10；UK03，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。状态转移方程为1079,1,25KKKKKSAUBSSUK段允许决策集合为DU设为第K年度的产量，则,KVSU85KKVS故指标函数为15,KKVVSU令最优值函数FKSK表示由资源量SK出发，从第K年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式610MAX850791,234KKKKKKUDSFSUFUS从第5年度开始，向前逆推计算。当K5时，有5555655050AX8079M3USUSFUFSU因F5是U5的线性单调增函数，故得最大解U5，相应的有8FS当K4时，有44445440440MAX807981362AXUSUSFUFSUS故得最大解，U4S4，相应的有44136FS依此类推，可求得33322211175008UFSF,相应的相应的,相应的因S11000，故137FS计算结果表明最优策略为123450,UUSUS即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知S11000台，于是可得2113222433354446555079098760790SUSSSSU台台台台台8、有一辆最大货运量为10T的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表420所示。应如何装载可使总价值最大表42货物编号I123单位重量（T）345单位价值CI456解123,X建模设三种物品各装件123MA64500,JJXI利用动态规划的逆序解法求此问题。111,|SCDXS2222|0SX3333,|SXS状态转移方程为1,1KKKTSX该题是三阶段决策过程，故可假想存在第四个阶段，而40X，于是动态规划的基本方程为14MAX,32,10KKKKKDSFSFS3,K330,1/5MAX6SFS2K222230,142,AX54SSFSFSX,K1120,231,MAX43FSFSX计算最终结果为，最大价值为13。123,0X9、设有A，B，C三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器A，B，C产生次品的概率分别为PA30,PB40,PC20,而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款5万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案方案1不拨款，机器保持原状；方案2加装监视设备，每部机器需款1万元；方案3加装设备，每部机器需款2万元；方案4同时加装监视及控制设备，每部机器需款3万元；采用各方案后，各部机器的次品率如表421。表43ABC不拨款304020拨款1万元203010拨款2万元102010拨款3万元5106问如何配置拨款才能使串联系统的可靠性最大解为三台机器分配改造拨款，设拨款顺序为A,B,C，阶段序号反向编号为K，即第一阶段计算给机器C拨款的效果。设SK为第K阶段剩余款，则边界条件为S35；设XK为第K阶段的拨款额；状态转移方程为SK1SKXK；目标函数为MAXR1PA1PB1PC仍采用反向递推第一阶段对机器C拨款的效果R1S1,X1D1S1,X1R0S0,X0D1S1,X1X1S10123X1R1S1,X10080081080910920809091,209308090909430944080909094309450809090943094第二阶段对机器B,C拨款的效果由于机器A最多只需3万元，故S22递推公式R2S2,X2D2S2,X2R1S1,X1例R23,2D23,2R11,110209072得第二阶段最优决策表X1S1X1R1S1,X10008110921,209330944309453094X2S20123X2R2S2,X220540630642064305640630720722,3072405640658072081308150564065807520813081第三阶段对机器A,B,C拨款的效果边界条件S35递推公式R3S3,X3D3S3,X3R2S2,X2例R35,3D35,3R22,210050640608得第三阶段最优决策表X2S2X2R2S2,X22206432,30724308153081S3X30123X3R3S3,X3505670648064806081,20648回溯有多组最优解。IX31,X23,X11,R30809090648IIX32,X22,X11,R30908090648IIIX32,X23,X10,R30909080648练习题五1、考察多目标规划问题其中212,1,XXFXF，试画出个目标函数的图形，并求出12,ABPWR，这里IR是24MNIXF的最优解集。解2、用线性加权法中的法求解下述多目标规划问题1122121MIN46AX3,0FXST。解最优解为；112MIN46FXTX最优解为；212MAX3FX2T3利用法得线性方程组12045解得唯一加权系数03846,15T原多目标规划加权后12MINFXFXFX解得加权后的最优解为，最优值为12312T403、用线性加权求和法求解下述多目标规划问题，取1206,4。1221212MIN3,36,0TVFXXSTX解将问题转化为一个新的单目标规划问题。1212MIN0634VFX约束条件同上，该问题转化为线性规划问题，可用单纯形法求解，也可用MATLAB命令求解（求解过程略）。解得加权后的最优解为，最优值为14。TX014、用平方和加权法求解多目标规划问题12MIN,TXDVFX其中1122,FXF，21248,0X，12,3。解不难看出两个目标函数下界均为0，得平方和加权法后的新目标规划问题21MIN3FX121248,0XD利用MATLAB程序求解首先建立目标函数及其梯度函数的M文件FUNCTIONFFUNXF1/3X122/3X2X2X,FVALFMINCONF,00,1111,48,00解得最优解为，最优值为0。TX05、用极小极大法和MATLAB软件求解下述多目标规划问题1222112MIN3,TVFXSTX。解取评价函数为，再求22211MA3,IVX221INN,DIFXXMATLAB软件求解编制M文件FUNCTIONFMNMAXXF1X132X22F2X12X222设初值X000调用函数X,FVALFMINIMAXMNMAX,X0,11,2结果X1300007000FVAL33