最优化期末复习总结

1、第一次课后作业：老三论：控制论、信息论和系统论,新三论：突变理论、耗散结构理论和协同论美国数学家维纳的“控制论”，美国数学家申农的“信息论”，美籍奥地利理论生物学家和哲学家贝塔朗菲的“系统论”； 比利时化学家普里高津的“耗散结构理论”，德国物理学家哈肯的“协同论”， 法国数学家托姆的“突变理论”。第二次课后作业：首先标准化： Max z=-3x1-2x2-x3+x4 s.t x1-2x2+3x3-x4152x1+x2-x3+2x410 x1 ,x2,x2”,x3 ,x40添加2个松弛变量 x5 x6x1-2x2+3x2-x4+x5=152x1+x2-x3+2x4+x6=10用对偶单纯形法：Cb

2、Xbb-3-2-1100X1X2X3X4X5X6X5151-23-110X61021-1201-z0-3-2-1100X5151-2(3)-1105X61021-1201-z0-3-2-1*1000X5202-1.52.5010.551X4510.5-0.5100.5-z-5-4-2.5-0.500-0.5在最优单纯性表中，x5,x6的检验数均为负数，于是得到最优解X*=(0,0,0,5,20)T，所以可以最小值为：-5此题和上题类似： 变成标准化 Max -x1-x2-x3 s.t. x1 -x4 -2x6=5 x2+2x4-3x5+x6=3 x3+2x4-5x5+6x6=5 xj0,j=1

3、.6;CbXbb-1-1-1000X1X2X3X4X5X60X45100-10-20X530102-310X650012-56-z01110000X45100-10-2-0X530102-31-0X6500(1)2-565-z0-1-1-1*000于是得到最优解X*=(0,0,0,5,3,3)T由此得出min的值为0,。添加松弛变量 x5，x6，x7化为标准化为：max 10x1+5x2+2x3-6x4 s.t. 5x1+3x2+x39 -5x1+6x2+15x215 2x1+x2+x3-x4=13 X1 x405x1+3x2+x1+x5=9-5x1+6x2+15x3+x6=152x1+x2+

4、x3-x4+x7=13CbXbb1052-6000X1X2X3X4X5X6X70X5953101000X615-561500100X713211-1001-z0-10-5-260000X11.810.60.200.2000X624091601100X79.40-0.20.6-1-0.401-z-180-10-6-200于是得到最优解X*=(1.8,0,0,0,0,24,9.4)T于是最小值为：-18对第二个约束条件左右同时乘上-1，再添加松弛变量 x5，x6，x7。令X4=x41-2，其中x410X1-2x2+x3-x41-2+x5=15 即 X1-2x2+x3-x41+x5=172x1+x2

5、-x3+2(x41-2)+x6+x7= 10 即2x1+x2-x3+2x41+x6+x7= 14于是变为标准形为：max -3x1-2x2-x2+x41X1-2x2+x3-x41+x5=172x1+x2-x3+2x41+x6+x7= 14x410X1 x30令Z1=3x1+2x2+x3-x41则Z=3x1+2x2+x3-x41+2=Z1+2CbXbb-3-2-11000X1X2X3X41X5X6X70X5171-21-11000X61421-12011-z10321-10000X5242-1.50.5010.50.50X4710.5-0.5100.50.53.5-z1-7-4-2.5-0.5-

6、00-0.5-0.50X5242-1.50.5010.50.50X4710.5-0.5100.50.53.5-z1-7-4-2.5-0.500-0.5-0.5于是得到最优解X*=(0,0,0,7,24,0,0)T于是最小值为-5添加松弛变量 x4，x52x1+x2+2x3+x4=2;4x1+2x2+x3+x5=2CbXbb11100X1X2X3X4X50X42212100X5242101-z0111000X4221(2)1010X52421012-z0111*001X3111/211/2020X5123/20-1/211-z-101/20-1/201X3111/211/2021X212(3/2

7、)0-1/212/3-z-101/2*0-1/201X32/31/3012/3021X22/34/310-1/32/34/9-z-4/3-2/300-1/3-1/3在最优单纯性表中，x5,x6的检验数均为负数，于是得到最优解为X*=(0,2/3,2/3,0,0)T,最优化目标值为Z*=4/3。添加松弛变量 x3，x4，x5，x6Max 3x1+2x2X1-3x2+x3=62X1+4x2+x4+x5= 8-x1+3x2+x6=6CbXbb320000X1X2X3X4X5X60X461-310000X582401100X66-130001-z03200000X461-31000-0X582(4)0

8、11020X66-1300012-z032*00000X4125/2013/43/402X221/2101/41/400X60-5/200-3/43/41-z-4200-1/2-1/200X4125/2013/43/4024/52X22(1/2)101/41/4040X60-5/200-3/43/41-z-42*00-1/2-1/200X420-51-1/2-1/203X141201/21/200X610-5/2501/21/21-z-120-40-3/2-3/20在最优单纯性表中，x5,x6的检验数均为负数，于是得到最优解为X*=(4,0,0,2,0,10)T,最优化目标值为Z*=-12。第

9、三次课后作业：固定仪器费用单人费用人数限制甲100020600乙200017800丙2500151000丁150019550公司人数 1900解： 设表示甲乙丙丁的采用(取值为1)和不采用(取值为0)。甲乙丙丁的人数，表示得到下列规划问题那么的取值要么是1要么是0，也就是共有16种情况我用015个整数来控制这16种情况K=0时d为：0 0 0 0也即将K化为二进制形式0 0 0 0 0 0 0 1 0 0 1 01 1 1 1显然当K=0时这种情况下直接进行下一种情况的处理如：K=7时，进行分枝界定法来求最优解。此时问题转化为：在各种情况求得的最小值中取最小的一个解作为本题的最后结果。4辆骑车

10、，5项运输任务，要求一辆骑车完成2项任务，其余个完成一次各车运费如下： 任务汽车ABCDE11101251431051282132197218162207387286107957841141551981282431） 求运费最少的运输方案2） 设表中为运输所得利润，利润最高方案。解：1） 引入虚拟汽车使得任务跟汽车人数一致，骑车5为所有骑车的最少运费，得系数矩阵第2，3列的最小元素为 20，29 m=4 l=4 a=14 即第一辆汽车完成任务2第二辆汽车完成任务1第三辆汽车完成任务3 5第四辆汽车完成任务4总费用为 125+132+107+78+128=5702)引入虚拟汽车使得任务跟汽车人数

11、一致，骑车5为所有骑车的最大利润，得系数矩阵2) 设上表内的数据位运输得到的利润，那么求利润最高的运算方法。解：添加虚拟车辆5，代表某一辆车完成的第二项任务，其利润为为每辆车完成任务的最大值。可列表如下：汽车任务ABCDE11101251431051282132197218162207387286107957841141551981282435132286218162243首先、减去每行每列的最大值，保证每行每列都含有至少一个0，变换可得矩阵如下：（0）-1800-15-53-21(0)-18-11-166(0)-179-153-208-96-88-45-77(0)-1210-68-86-43

12、无法满足最优解，找出其中未划线的最大值-18，继续变化矩阵，如下：（0）-36-180-33-35-21(0)0-11-148(0)-179-135-208-78-88-45-59(0)-1030-68-68-43仍无法满足最优解，找出其中未划线的最大值-45，继续变化矩阵，如下：（0）-81-180-33-35-660（0）-11-103(0)-134-90-208-33-880-14(0)-580-23-23-43仍无法满足最优解，找出其中未划线的最大值-23，继续变化矩阵，如下：（0）-104-180-33-35-89(0)0-11-80(0)-111-69-185-33-1110-14

13、(0)-3500（0）-20可得出最优解：汽车1完成任务A,汽车2完成任务C、D，汽车3完成任务B ，汽车4完成任务E ，此时的最大利润为：110+218+162+286+243=1019元第四次课后作业：1) 用图解法找出最优解(不用做)2) 写出(P)的K-T条件式，并通过求K-T点来找出最优解3) 求下列各点的下降可行方向：最优解解：2) 先把问题变为 于是得到K-T条件式 （1）由 解出 不满足条件令 解得 是K-T点，则最优解为：3) 使得 于是代入（1）得 最优解为：0 由第二步知，代入后 得小于0，故不是K-T点10用既约梯度解解：先把问题标准化，引入松弛变量x4变为则 取 ,

14、于是 ， 求解 得 ， 于是 ，求解 得 1) 用单纯行法求这个问题的满意解。2) 把目标函数改为求解，并比较于1的结果有什么不同。3）若第一个目标约束右端项改为12，求解后满意解分别有什么变化解：1） 对目标规划问题建立下列表格，其中RHS表示约束右端项RHS00-100000000000000000-100000-5-3-3-5000111-1000000801001-1000070000001-1004.5001000001-11首先处理初始基本可行解对应的各级校验数。优先级对应目标函数中含有，所以该行不是典式表示，应将第1个约束行加到这一行，使得基变量对应的校验数为0。得到（1,1,0

15、,-1,0,0,0,0,0,0;8）优先级对应的目标函数中不含，所以其校验数只需取系数负值。（0,0,0,0,0,0,0,0,0,-1;1）中含有，所以该行不为典式表示，应将第三个约束行的5倍第3个约束行的3倍加到这一行，使得基变量对应的校验数为0。得到（0,5,0,0,0,-8,0,-8,0,0;48.5）RHS110-10000008000000000-1005000-80-80048.5111-10000008801001-10000770000001-1004.5001000001-11于是得到此目标规划的初始单纯行表（a） k=1，在初始化单纯行表中基变量为（b） 因为优先级的校验数

16、均已非正，所以这个单纯行表对优先级是最优单纯行表。（c） 下面考虑，第二列的校验数数分别为1，5，此为进基变量，计算相应的比值，写在列，得到对应比值最小，于是取为转轴元进行矩阵变换，得到新的单纯行表RHS100-1-1100001000000000-100000-5-30-80013.5101-1-1100001101001-1000070000001-1004.5001000001-11（d） （d）考虑的优先级，第一列的校验数为1，此为进基变量，计算相应的比值，写在列，得到对应比值最小，于是取为转轴元进行矩阵变换，得到新的单纯行表RHS0-1-10-1100000000000000-100

17、000-5-30-80013.5101-1-1100001101001-1000070000001-1004.5001000001-11(e) 当前的单纯行表格各优先级的校验数满足上述条件，故为最有单纯行表得最优解=1 =72）约束条件该了后变为对目标规划问题建立下列表格，其中RHS表示约束右端项RHS00-1000000000000-5-3-3-5000000000000-10111-1000000801001-1000070000001-1004.5001000001-11首先处理初始基本可行解对应的各级校验数。优先级对应目标函数中含有，所以该行不是典式表示，应将第1个约束行加到这一行，使

18、得基变量对应的校验数为0。得到（1,1,0,-1,0,0,0,0,0,0;8）优先级对应的目标函数中不含，所以其校验数只需取系数负值。（0,0,0,0,0,0,0,0,0,-1;1）中含有，所以该行不为典式表示，应将第三个约束行的5倍第3个约束行的3倍加到这一行，使得基变量对应的校验数为0。得到RHS110-1000000805000-80-80048.5000000000-10111-10000008801001-10000770000001-1004.5001000001-11于是得到此目标规划的初始单纯行表（e） k=1，在初始化单纯行表中基变量为（f） 因为优先级的校验数均已非正，所以

19、这个单纯行表对优先级是最优单纯行表。（g） 下面考虑，第二列的校验数数分别为1，5，此为进基变量，计算相应的比值，写在列，得到对应比值最小，于是取为转轴元进行矩阵变换，得到新的单纯行表RHS100-1-11000010000-5-30-80013.5000000000-10101-1-1100001101001-1000070000001-1004.5001000001-11（h） （d）考虑的优先级，第一列的校验数为1，此为进基变量，计算相应的比值，写在列，得到对应比值最小，于是取为转轴元进行矩阵变换，得到新的单纯行表RHS0-1-10-11000000000-5-30-80013.5000

20、000000-10101-1-1100001101001-1000070000001-1004.5001000001-11(e) 当前的单纯行表格各优先级的校验数满足上述条件，故为最有单纯行表得最优解=1 =73) 得表格RHS00-100000000000000000-100000-5-3-3-5000111-10000001201001-1000070000001-1004.5001000001-11首先处理初始基本可行解对应的各级校验数。优先级对应目标函数中含有，所以该行不是典式表示，应将第1个约束行加到这一行，使得基变量对应的校验数为0。得到（1,1,0,-1,0,0,0,0,0,0;

21、12）优先级对应的目标函数中不含，所以其校验数只需取系数负值。（0,0,0,0,0,0,0,0,0,-1;1）中含有，所以该行不为典式表示，应将第三个约束行的5倍第3个约束行的3倍加到这一行，使得基变量对应的校验数为0。得到（0,5,0,0,0,-8,0,-8,0,0;48.5）RHS110-100000012000000000-1005000-80-80048.5111-1000000121201001-10000770000001-1004.5001000001-11于是得到此目标规划的初始单纯行表（i） k=1，在初始化单纯行表中基变量为（j） 因为优先级的校验数均已非正，所以这个单纯行

22、表对优先级是最优单纯行表。（k） 下面考虑，第二列的校验数数分别为1，5，此为进基变量，计算相应的比值，写在列，得到对应比值最小，于是取为转轴元进行矩阵变换，得到新的单纯行表RHS100-1-1100005000000000-100000-5-30-80013.5101-1-1100005501001-1000070000001-1004.5001000001-11（l） （d）考虑的优先级，第一列的校验数为1，此为进基变量，计算相应的比值，写在列，得到对应比值最小，于是取为转轴元进行矩阵变换，得到新的单纯行表RHS0-1-10-1100000000000000-100000-5-30-800

23、13.5101-1-1100005501001-1000070000001-1004.5001000001-11(e) 当前的单纯行表格各优先级的校验数满足上述条件，故为最有单纯行表得最优解=5 =7某工厂可以生产4种产品，这4种产品都需要一种原料，这种原料总数有5袋。设各种产品使用这种原料的袋数与获得的效益见下表：原料产品号01234510358121320257911303691112404691014如何分配，使得总效益最大？产品号1用4袋原料产品号2用0袋原料产品号3用0袋原料产品号4用1袋原料获得的最大效益=16K=5 f5(x5)=0K=4 0<=d4<=x4 x5=x

24、4-d4X4D4(x4)X5V4(x4,d4)V4(x4,d4)+f5(x5)F4(x4)D4*00000+0=00010100+0=0411044+0=4*20200+0=0621144+0=42066+0=6*30300+0=0931244+0=42166+0=63099+0=9*40400+0=01041344+0=42266+0=63199+0=9401010+0=10*50500+0=01451444+0=42366+0=63299+0=9411010+0=10501414+0=14*K=3 0<=d3<=x3 x4=x3-d3X3D3(x3)X4V3(x3,d3)V3(x3