第四章 算法

第四章 线性规划的求解法当线性规划的变量和约束条件比较多，而初始基本可行解又不知道时，是不容易用尝试的方法得到初始基本可行解的，何况有可能基本可行解根本就不存在。

在此时，大M 法可能是应付此类情况的一个行之有效的算法。

§4.1 大M 法的原理当初始基本可行解不知道时，则1.，2.两个特点不能兼得，即下列两条件不能兼得： 1. 中心部位具有单位子块； 2. 右列元素非负；这时可以先用容许的运算使由列为非负，然后在中心部位人为添加一个单位子块。

如下例所述： 例4.1123123123123min 32..323624,,0z x x x s tx x x x x x x x x =-+++-=-+-=-≥ （4.1.1）列成表格：上述第三张表中人工增加了两个变量45,x x ，称为人工变量，即把原来的约束条件改为：1234123512345..323624,,,,0s tx x x x x x x x x x x x x +-+=-++=≥ （4.1.2） 式（4.1）和（4.2）的约束方程组并不同解，但（4.1）的解和（4.2）中450x x ==的解是相对应的。

只要找到以（4.2）为约束条件，且人工变量45,x x 均为自由变量的基本可行解，也就找到了（4.1）的基本可行解，于是，要设法迫使450x x ==。

以上途径通过修改（4.1）的目标函数来实现。

具体修改为：12345min 32z x x x Mx Mx =-++++ （4.1.3）其中M 为足够大的正数，然后以（4.2）为约束条件，求（4.3）的最小值。

只要45,x x 不为零，就一定为正数，于是目标函数的值就会增加它们和的M 倍。

由于M 为足够大的正数，所以只要原问题有基本可行解，就不会在45,x x 取正值时达到最小值。

本例中把表改为：通过运算使它具备第三个特点：底行相应于单位子块位置的元素为0，然后再严格按照单纯形法的步骤求解：由于M 为足够大的正数，所以-3-4M 应视为负数，故选它。

第四章：乘法（平方）第一节、平方数基础算法一、1至9的平方:九九口诀二、11至19的平方：直接背诵或者利用十几乘以十几三、21至24的平方：记忆21 ×21 = 441 22 ×22 = 48423 ×23 = 529 24 ×24 = 576四、25～75 的两位数的平方算法：求25～75的两位数的平方，用底数减去25，得数为前积（百位数），50与底数的差的平方作为后积（个位数），满百进1，没有十位补0。

例1：37 ×3737 - 25 = 12--（50 - 37）^2 = 169 1369例2：64 ×6464 - 25 = 39-- （64 - 50）^2 = 196 4096练习：快速算出25至75的平方五、75～125的平方算法：用底数减去补数或加余数，得数为前积（百位数），补数的平方作为后积（个位数），满百进1，没有十位补0。

例1：86×8686-14=72 14×14=1967396例2：123×123123+23=146 23×23=529 15129练习：快速算出75至125的平方第二节、技巧算法1平方表 1 2 3 4 5 6 7 8 901～092 1 4 9 16 25 36 49 64 8111～192 121 144 169 196 225 256 289 324 36121～252 441 484 529 576 62526～292 676 729 784 84131～392 961 1024 1089 1156 1225 1296 1369 1444 152141～492 1681 1764 1849 1936 2025 2116 2209 2304 240126～49的平方是底数减25为前积，50减底数的差的平方为后积，满百进1,没有十位补0。

求262是 26-25＝01，50-26＝24，242是576，576的5加1＝676;求342是 34-25＝09，50-34＝16， 162是256，256的2加9＝1156求472是47-25＝22，50-47＝03，32＝09，结果是2209求11~192是一个数加另一个数的个数连上个位平方182=18+8连64=324求21~292是任选232=460+69=529 262=520+156=676 272=810-81=729求31~392是自身减不足50的差再折半连上差的平方372=12连169=1369求41~492是自身减个位补数后折半连上补数平方49=24连01=2401求51~592是首数平方加尾数连尾数平方562=25+6连36=3136求61~692的平方是自身加超50的差,再折半连上差的平方672=(67+17)折半连289=4489求71~792的平方是自身减自身的补数连上补数平方732=73-27连729=5329求81~892的平方是自身减自身的补数连上补数平方822=82-18连324=6724求91~992的平方是自身减尾数的补数连上尾数平方942=94-6连36=8836例如:672前部是42后部是289则把289的2加到42的2上=4489;732前部是46后部是729则把729的7加到46的6上=5329822前部是64后部是324则把324的3加到64的4上=67241、任意两位数平方，首积连尾积加上首尾之积的2倍57×57=2549+50×7×2=324946×46=1636+480=211639×39=981+540=1521第二节、技巧算法22、首位数是1的两位数平方，一个数加上另一个数的个位，扩大十倍，再加上个位平方19×19=280+9×9=36118×18=32417×17=28916×16=25615×15=22514×14=19613×13=16912×12=14411×11=1213、首位数是3的两位数平方，减去不足50的差后的一半，填俩0，连加上差的平方38×38=（38-12）÷2连12×12 =144434×34=（34-16）÷2连16×16 =11564、首位数是4的两位数平方，减去个位补数后的一半，填俩0，加上补数的平方46×46=（46-4）÷2连4×4 =2116 43×43=184947×47=220948×48=230449×49=2401实际就是46×46=（46+4）×（46-4）+4×4=50×42+16=21165、首位数是5的两位数平方，首位自乘加上一个个位数，再连上个位平方59×59=5×5+9连9×9=348158×58=336457×57=324956×56=313655×55=302554×54=291653×53=280952×52=270451×51=26016、首位数是6的两位数平方，自身加上超过50的差后的一半，填俩0，加上差的平方69×69=（69+19）÷2+19×19=4400+361=476168×68=4300+324=4624 67×67=4200+289=448966×66=4100+256=435664×64=3900+196=40967、首位数是8的两位数平方，自身减去补数后填俩0，再加上补数平方89×89=7800+121=792188×88=7600+144=774487×87=7400+169=756986×86=7200+196=739684×84=6800+256=7056 83×83=6600+289=688982×82=6400+324=672481×81=6200+361=65618、首位数是9的两位数平方，自身减补数，连上补数平方99×99=99-01连1×1=9801 98×98=960497×97=940996×96=921695×95=902594×94=883693×93=864992×92=846491×91=8281第二节、技巧算法3两位数平方（续）个位是5的平方已介绍过省略1、个位数是1两位数平方，十位相乘的积，加上十位相加的和，再加191×91=8100+180+1=828181×81=656171×71=5041 6 1×61=3721 51×51=260141×41=168131×31= 96121×21= 44111×11=1212、个位数是9两位数平方，先把底数变成平数或齐数的乘积，减去平或齐数2倍，再加199×99=100×100-100×2+1=9801或8181+1620=980189×89=8100-180+1=7921 79×79=624169×69=476159×59=348149×49=240139×39=152129×29= 84119×19= 3613、个位数是2两位数平方，首积连尾积加上个位的和乘十位数92×92=8104+90×4=846482×82=6404+320=672472×72=4904+280=518462×62=3844 52×52=2704 42×42=176432×32=102422×22= 48412×12= 1444、个位数是3两位数平方，首积连尾积加上个位的和乘十位数93×93=8109+90×6=864983×83=6409+480=688973×73=4909+420=532963×63=396953×53=280943×43=184933×33=108923×23=52913×13= 169 5、个位数是4两位数平方，首积连尾积加上个位的和乘十位数94×94=8116+720=883684×84=7056 83×83=688973×73=5329依此类推6、个位数是6两位数平方，首积连尾积加上个位的和乘十位数96×96=8136+1080=921686×86=6436+960=739676×76=4936+840=5776依此类推7、个位数是7两位数平方，首积连尾积加上个位的和乘十位数97×97=8149+1260=940987×87=6449+1120=756977×77=4949+980=5929依此类推8、个位数是8两位数平方，首积连尾积加上个位的和乘十位数98×98=8164+1440=9604依此类推，或用自身减补数再连上补数平方的方法计算综上归纳起来就是看两个尾数之和是多少,有三种情况,一不足10,二正好10,或超10,三接近20.不受应试教育鹦鹉学舌的束缚,怎样方便就怎样算.例如一.632=3609+360=3969或4209-240=3969二.852=6425+800=7225或72连25=7225三.782=4964+1120=6084或5664+420=6084或6364-280=6084注:两位乘两位的积应是四位数,连上的数是三位时,应把百位加在前部的个位上.(补到脑算实例连载11的最前面)两位数的平方差：大数加小数乘大数减小数。

第四章1算法策略迭代算法迭代算法是一种通过重复应用一些过程或步骤来逐步逼近解的策略。

在计算机科学中，迭代算法是解决问题的一种常见方法，尤其在计算复杂度比较高的情况下，迭代算法可以提供一种有效的解决方案。

迭代算法的核心思想是将问题分解成一系列小的子问题，并通过重复执行一些步骤来逐渐逼近解。

每次迭代时，算法会根据上一次迭代的结果来更新当前的状态，然后继续下一次迭代。

这样的迭代过程会持续进行，直到达到一些停止条件为止。

迭代算法可以应用在各个领域的问题中，比如数值计算、优化问题、问题等。

下面将介绍一些常见的迭代算法。

1.迭代加深：这是一种在问题中应用的常见迭代算法。

它通过逐渐增加的深度来逼近解。

首先进行深度为1的，如果没有找到解，则增加深度，再次进行。

通过不断增加深度，直到找到解为止。

2.迭代法解线性方程组：线性方程组的解可以通过迭代算法逐步求得。

一种常见的迭代算法是雅可比迭代法，它通过不断迭代解方程组的近似解，直到满足特定的收敛准则为止。

3.迭代法求函数零点：对于给定的函数，通过迭代算法可以逐步逼近函数的零点。

其中，牛顿迭代法是一种常见的迭代算法，它通过使用函数的导数和当前函数值来逐步逼近零点。

除了上述几种常见的迭代算法，还有其他很多迭代算法方法，如迭代法解非线性方程组、最小二乘法、迭代法求特征值等。

迭代算法的优点是它可以解决很多复杂的问题，并且可以提供一种近似解。

此外，迭代算法通常比较灵活，可以根据实际情况进行调整。

迭代算法的缺点是它可能需要进行大量的迭代次数才能得到满意的结果，并且在一些情况下可能无法收敛到解。

总之，迭代算法是一种常见的算法策略，可以应用于很多领域的问题。

通过不断迭代，算法可以逐步逼近最优解或者满足特定的目标。

虽然迭代算法可能需要较长时间才能得到完美的解，但它是解决复杂问题的一种有效方法。

第四章蚁群算法习题与答案1.填空题（1）蚁群算法的缩写是，它模拟了自然界中过程而提出，可以解决问题。

（2）蚁群算法需要一个记忆空间，称为，表示已经过的路径。

判断选择城市的主要依据有和，前者代表愿望，后者代表愿望，反映了问题求解过程中经验的积累。

解释：本题考查蚁群算法的基础知识。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：（1）ACO，蚂蚁觅食，组合优化（2）禁忌列表，能见度，虚拟信息素，启发式，获知式2.考虑如下情形：分头沿着两条长度不同的路径去食物源，当到达食物源时哪条路径会以较高的概率被其选择？论证你的答案。

解释：本题考查蚁群算法中信息素的特点与作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：路径长度短的会以较高的概率被选择。

具体论证如下：单位时间内通过路径短的蚂蚁数量大于通过路径长的蚂蚁数量，这意味着短路径上遗留的信息素浓度比较髙，由于蚂蚁倾向于朝着信息素浓度高的方向移动，所以到后期选择短路径的蚂蚁会越来越多。

于是，蚁群的集体行为表现出一种信息正反馈现象，即最短路径上走过的蚂蚁越多，信息素浓度也就越高，后来的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流寻找食物和蚁穴之间最短路径的。

3. 探讨在信息素释放公式中遗忘因子的重要性。

解释：本题考查蚁群算法中信息素挥发因子的作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：参数ρ表示信息素挥发因子，ρ的大小从另一个侧面反映了蚂蚁群体中个体间相互影响的强弱，它直接关系到蚁群算法的全局搜索能力及收敛速度；参数1ρ-表示信息素残留因子，反映了蚂蚁个体之间相互影响的强弱。

信息素残留因子的大小对蚁群算法的收敛性能影响非常大，一般取值在0.1～0.99范围内，并且1ρ-与进化迭代次数近似成正比。

若1ρ-很大，导致残留信息素增多，进而信息的正反馈作用增强，使路径上的残留信息占主导地位，算法容易陷入一个范围窄小的搜索空间，从而使得算法搜索的随机性减弱，此时虽然算法收敛速度加快，但搜索质量不高。

第四章 共轭梯度法§4.1 共轭方向法共轭方向法是无约束最优化问题的一类重要算法。

它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。

一、共轭方向定义4.1 设G 是n n ⨯对称正定矩阵，1d ，2d 是n 维非零向量，若120T d Gd = （4.1）则称1d ，2d 是G －共轭的。

类似地，设1,,m d d L 是n R 中一组非零向量。

若0T i j d Gd =()i j ≠ （4.2）则称向量组1,,m d d L 是G －共轭的。

注：(1) 当G I =时，共轭性就变为正交性，故共轭是正交概念的推广。

(2) 若1,,m d d L G －共轭，则它们必线性无关。

二、共轭方向法共轭方向法就是按照一组彼此共轭方向依次搜索。

模式算法：1）给出初始点0x ，计算00()g g x =，计算0d ，使000Td g <，:0k = （初始共轭方向）；2）计算k α和1k x +，使得0()min ()k k k k k f x d f x d ααα≥+=+，令1k k k k x x d α+=+；3）计算1k d +，使10Tk j d Gd +=，0,1,,j k =L ，令:1k k =+，转2）。

三、共轭方向法的基本定理共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。

定理4.2 对于正定二次函数，共轭方向法至多经过n 步精确搜索终止；且对每个1i x +，都是()f x 在线性流形00,i j j j j x x x d αα=⎧⎫⎪⎪=+∀⎨⎬⎪⎪⎩⎭∑中的极小点。

证明：首先证明对所有的1i n ≤-，都有10T i j g d +=，0,1,,j i =L （即每个迭代点处的梯度与以前的搜索方向均正交）事实上，由于目标函数是二次函数，因而有()11k k k k k k g g G x x Gd α++-=-=1）当j i <时， ()1111iTT T i j j j k k j k j g d gd g g d +++=+=+-∑110iT T j j kkj k j gd dGd α+=+=+=∑2）当j i =时，由精确搜索性质知：10T i j g d +=综上所述，有 10Ti j g d += (0,1,,)j i =L 。

1、BFGS算法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];function alpha=wolfe(x0,d0)% Wolfe-Powell stepalpha=1;pho=1/2;sigma=0.251;sigma1=0.4;itermax=100;d=d0;% Forward.for i=1:itermaxx1=x0+alpha*d;f1=fun_obj(x1);f0=fun_obj(x0);df=fun_grad(x0)'*d;if f1-f0>sigma*alpha*dfalpha=pho*alpha;elsebreakendend% Backward.for i=0:itermaxx1=x0+alpha*d;df1=fun_grad(x1)'*d;if df1<sigma1*dfbeta=alpha/pho;che=1;for j=1:itermaxx1=x0+alpha*d;f1=fun_obj(x1);f0=fun_obj(x0);if f1-f0>sigma*alpha*dfche=che*pho;alpha=alpha+che*(beta-alpha);elsebreakendendelsebreak;endendfunction [minx,minf,k]=BFGSmain(x0)EPS=1e-6; % 精度n=length(x0); % 计算输入的x0的维数B0=eye(n); % 令B0的初始值为单位矩阵k=1;Bk=B0; % 初值xk=x0; % 将x(0)的值存储到xk中if norm(fun_grad(xk))<=EPS % 判断初始点是否为最优解minx=xk;endwhile norm(fun_grad(xk))>EPS % 迭代停止的条件dk=fun_grad(xk); % x(k)处的梯度%% 用BFGS法求xk处的下降方向d=Bk\(-dk)'; % 求解Bk*d+fun_grad(xk)=0%% Wolfe_Powell法求步长rminr=wolfe(xk,d'); % 步长r%% 更新迭代minx=xk+minr*d'; % x(k+1)的值sk=minx-xk; %s(k)=x(k+1)-x(k);yk=fun_grad(minx)-dk; %y(k)=fun_grad(x(k+1))-fun_grad(x (k));if yk*sk'>0Dk=Bk*sk'; %BFGS公式中的B(k)*s(k),为列向量Bk=Bk-(Dk*Dk')/(Dk'*sk')+(yk'*yk)/(yk*sk'); %B(k+1)=B(k)-( B(k)*s(k)*s(k)'*B(k))/(s(k)'*B(k)*s(k))+(y(k)*y(k)')/(y(k)'*s(k)); elseBk=Bk;endk=k+1;xk=minx;endminf=fun_obj(minx); % 计算最优解处的函数值x0=[11,22];[xk,fk,k]=BFGSmain_HK(x0);。