最优化方法习题答案

习题一1.1利用图解法求下列线性规划问题：（1）21xxzmax0x,x5x2x2xx3.t.s212121解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A点取得最优值，最优值z=5（2）21x6xzmin0x,x7xx1xx2.t.s212121解：图中阴影部分表示可行域，由图可知原问题在点A处取得最优值，最优值z=-6.（3）21x2x3zmax0x,x4x2x1xx.t.s212121解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。（4）21x5x2zmin0x,x2xx6x2x.t.s212121解：由图可知该线性规划可行域为空，则原问题无可行解。1.2对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。（1）4321x6x3x2x5zmin0x,x,x,x3x2xxx27x4x3x2x.t.s432143214321解：易知1x的系数列向量21p1，2x的系数列向量12p2，3x的系数列向量13p3，4x的系数列向量24p4。①因为21p,p线性无关，故有43214321x2x3xx2x4x37x2x，令非基变量为0xx43，得311x31x21，所以得到一个基解)0,0,311,31(x)1(是非基可行解；②因为31p,p线性无关，可得基解)0,511,0,52(x)2(，543z2；③因为41p,p线性无关，可得基解)611,0,0,31(x)3(，是非基可行解；④因为32p,p线性无关，可得基解)0,1,2,0(x)4(，1z4；⑤因为42p,p线性相关，42x,x不能构成基变量；⑥因为43p,p线性无关，可得基解)1,1,0,0(x)6(，3z6；所以)6()4()2(x,x,x是原问题的基可行解，)6(x是最优解，最优值是3z。（2）54321xxx2xxzmax5,4,3,2,1i,0x4xx2x1xxxx.t.si5214321解：易知1x的系数列向量11p1，2x的系数列向量21p2，3x的系数列向量01p3，4x的系数列向量01p4，5x的系数列向量10p5。①因为21p,p线性无关，故有5214321x4x2xxx1xx，令非基变量为0xxx543，得35x32x21，所以得到一个基解)0,0,0,35,32(x)1(，是非基可行解；②因为31p,p线性无关，可得基解)0,0,5,0,4(x)2(，是非基可行解；③因为41p,p线性无关，可得基解)0,5,0,0,4(x)3(，是非基可行解；④因为51p,p线性无关，可得基解)5,0,0,0,1(x)4(，4z4；⑤因为32p,p线性相关，得基解)0,0.1,2,0(x)5(，是非基可行解；⑥因为42p,p线性无关，可得基解)0,1,0,2,0(x)6(，是非基可行解；⑦因为52p,p线性无关，可得基解)2,0,0,1,0(x)7(，1z7；⑧因为43p,p线性相关，43x,x不能构成基变量；⑨因为53p,p线性无关，可得基解)4,0,1,0,0(x)9(，6z9；⑩因为54p,p线性无关，可得基解)4,1,0,0,0(x)10(，3z10；所以原线性规划的基可行解是)10()9()7()4(x,x,x,x，最优解是)7(x，最优值是1z。1.3用单纯形法求解下列线性规划问题；（1）21x3x2zmax0x,x2xx5x3x.t.s212121解：引入松弛变量3x，剩余变量4x和人工变量5x，把原问题化为规范式521Mxx3x2zmax5...2,1i,0x2xxxx5xx3x.t.si5421321，其中M无限大，构造初始单纯形表并计算如下：1x2x3x4x5x2+M3+M0-M03x1310055x110-112以2x作为换入基，3x作为换成基，计算得1x2x3x4x5x1+32M0-1-3M-M02x3113100355x32031-1131以1x为换入基，5x作为换出基有1x2x3x4x5x002123M23-5.52x012121211.51x102123230.5以4x换入，2x换出有1x2x3x4x5x0-3-20M3-104x0211-131x131005根据单纯形表可知，原问题的最优解为)3,0,0,5(x*，最优值为10z*（2）321x2xxzmax0x,x,x7xx4x5xxx3.t.s321321321解：引入松弛变量4x，剩余变量5x和人工变量6x，把原问题规范化为6321Mxx2xxzmax6...2,1i,0x7xxxx4x5xxxx3.t.si6532143211x2x3x4x5x6x1+M1-4M-2+M0-M04x31-110056x1-410-117以1x作为换入基，4x作为换出基有1x2x3x4x5x6x03M1332353M43M1-M01x131-313100356x03133431-11316以3x为换入变量，6x为换出变量，得所以原问题最优解为)4,0,3(x*，最优值为5z*。（3）321xx3x2zmin0x,x,x6x2x38x2x4x.t.s32121321解：引入剩余变量4x,5x和人工变量6x,7x,利用两阶段法得到辅助线性规划76xxwmax321'xx3x2zmax7...2,1i,0x6xxx2x38xxx2x4x.t.si752164321构造初始单纯形表，并计算1x2x3x4x5x6x0M44190121454M451x165041-3133x0413141-434341x2x3x4x5x6x7x'z-2-3-10000w462-1-1006x142-101087x3200-1016以2x为换入变量，6x为换出变量，得1x2x3x4x5x6x7x'z45021430430w250-121-12302x41121-41041027x250-121-12112以1x为换入变量，7x为换出变量，得1x2x3x4x5x'z00021212x010.6-0.30.11.81x10-0.40.2-0.40.8从单纯行表中可知，原问题有无限多个最优解，其中一个为)0,8.1,8.0(x*，最优值为7z*。（4）321x12x15x10zmax3,2,1j,0x5xxx215x15x6x59xx3x5.t.sj321321321解：引入松弛变量5,4xx，剩余变量,6x，人工变量7x，将原问题化为规范式7321Mxx12x15x10zmax7,...,2,1j,0x5xxxxx215xx15x6x59xxx3x5.t.sj7632153214321构造初始单纯形表并计算得以1x为换入变量，4x为换出变量，得以1x为换入变量，4x为换出变量1x2x3x4x5x6x7xz10+2M15+M12+M00-M04x531100095x-56150100157x21100-1151x2x3x4x5x6x7x进一步计算知道，0x7，所以原问题没有可行解。1.4设目标函数极大化的线性规划问题的单纯形表如下，表中无人工变量，当待定常数21121c,c,b,a,a为何值时，表中的解：（1）为唯一最优解，（2）为多重解，（3）有无界解，（4）为退化解。解：①当0c,c,0b211，为唯一最优解；②当0c,0c0c,0c,0b21211或，为多重解；③当0c,0c,0a,0b2121，具有无界解；④0c,0a0c,0b2211或，为退化的可行解。1.5某商店要制定某种商品第二季度的计划，已知该商店仓库容纳此种商品的容量不超过600件，3月底已存货200件，以后每月初进货一次。假定各月份此种商品买进售出的单价如下，问各月进货、售货各多少件才能使利润最大？假设进货时受到仓库容量的限制，售货z05M95M3105M220-M01x10.60.20.20001.85x09161100247x0-0.20.6-0.40-111.41x2x3x4x5x6x1c02c-9000z2x1a12a-10075x-10-501036x40-21011b时受到进货量的限制，不考虑货物存放在仓库的耗损与保管费用。月份买进单价/(元/件)售出单价/(元/件)41718516.51861719解：设ix表示每个月进货量，iy表示相应月份售货量，其中3,2,1i，则有数学模型：321321x17x5.16x17y19y18y18zmax3,2,1i,0y,x200yxyxyx200yxyx200yx200600xyxyx200600xyx200600x.t.sii332211221111322112111经计算，当600y,600x,600y,500x,600y,400x332211时，即四月份进货400件，售货600件，五月份进货500件，售货600件，六月份进货600件售货600件时，最大利润为6100元。1.6设市场上可买到n种不同的食品，第j种食品的单位售价为jc，每种食品含有m种基本营养成分，第j种食品每一个单位含第i种营养成分为ija，每人每天对第i种营养成分的需要量不少于ib，试确定在保持营养成分要求条件下的最经济食谱。解：设没人每天需要第j种食品的数量为jx（j=1,2,...,n），建立数学模型为：n1jjjxczminn,...2,1j,0xm,...,2,1i,bxa.t.sjn1jijij1.7A,B两种产品都需要经过前、后两道工序加工，每一个单位产品A需要前道工序1h和后道工序2h，每一个位产品B需要前道工序2h和后道工序3h.可利用的前道工序有11h，后道工序有17h。没加工一个单位产品B的同时，会产生2个单位的副产品C，并且不需要任何费用，产品C一部分可出售盈利，其余的只能加以销毁。出售单位产品A,B,C的利润分别为3元，7元，2元，每单位产品C的销毁费为1元。预测表明，产品C最多只能出售13个单位。试建立总利润最大的生产计划数学模型。解：设21x,x分别为产品A,B的产量，3x为副产品C的销售量，4x为副产品C的销毁量，于是有243x2xx，z为总利润，则数学模型如下：4321xx2x7x3zmax0x,x,x,x13x0xxx217x3x211x2x.t.s432134322121习题二2.1写出下列线性规划问题的对偶问题：（1）321xx5x10zmin自由变量2312321321x,0x,x7x12x5x6x10x4x2xs.t.解：原问题的对偶问题为：4321y7yy2y10wmax0y,y,y,0y1y5y45yyy62y10yys.t.432121432121（2）4321x4x3x