最优化理论与方法1(2014简版)

1、最优化理论与方法讲义（上）第一章绪论1.1学科简介最优化这一数学分支，为这些问题的解决提供了理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科。1.1.1优化的含义优化是从处理各种事物的一切可能的方案中，寻求最优的方案。（1）来源：优化一语来自英文Optimization,其本意是寻优的过程；（2）优化过程：是寻找约束空间下给定函数取极大值（以max表示）或极小（以min表示）的过程。1.2发展概况第一阶段人类智能优化第二阶段数学规划方法优化第三阶段工程优化第四阶段现代优化方法1.3研究意义研究意义：最优化在本质上是一门交叉学科，它对许多学科产生了重大影响，

2、并已成为不同领域中很多工作都不可或缺的工具。应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。总之，它是一门应用性相当广泛的学科，讨论决策的问题具有最佳选择之特性。它寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。1.4示例例1资源分配问题某工厂生产A和B两种产品，A产品单位价格为P万元，B产A品单位价格为P万元。每生产一个单位A产品需消耗煤a吨，电aBCE度,人工a个人日；每生产一个单位B产品需消耗煤b吨，电b度,LCE人工b个人日。现有可利用生产资源煤C吨，电E度，劳动力L个L人日，欲找出其最优分配方案，使产值最大。分析：（1）产值的表

3、达式；（2）优化变量确定：A产品x，B产品x；优化约束条件:AB生产资源煤约束;生产资源电约束；生产资源劳动力约束。优化蛮矍：兀生产资源电约束；生产资源劳动力约束。目标函mnxP声R+巴鼻：约東亲件；十瓦耳C十叭心匚例2指派问题设有四项任务B、B、12B、B派四个人A、A设有四项任务B、B、12341234每个人都可以承担四项任务中的任何一项，但所消耗的资金不同。设A完成B所需资金为c。如何分配任务，使总支出最少?ij分析：设变量x分析：设变量xij1指派A完成B任务,1j0,不指派A完成B任务则总支出可表示为：s=cxijiji=1j=1数学模型:minS=44cxijiji=1j=1s.t

4、.x=1,i=1,2,3,4ijj=1x=1,j=1,2,3,4iji=1x,1i,j=1,2,3,4ij1.5最优化的数学模型最优化的数学模型是描述实际优化问题目标函数、变量关系、有关约束条件和意图的数学表达式，并能反映物理现象各主要因素的内在联系，是进行最优化的基础。1.5.1基本概念1、决策变量(Decisionvariables)问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制，也称优化变量。决策变量或优化变量的全体实际上是一组变量，可用一个列向量表示。优化变量的数目称为优化问题的维数，如n个优化变量，则称为n维优化问题。优化问题的维数表征优化的自由度。优

5、化变量愈多，则问题的自由度愈大、可供选择的方案愈多，但难度亦愈大、求解亦愈复杂。通常，小型优化问题：一般含有210个优化变量；中型优化问题：1050个优化变量；大型优化问题：50个以上的优化变量。如何选定优化变量？确定优化变量时应注意以下几点：抓主要，舍次要。根据要解决问题的特殊性来选择优化变量。2、约束条件(Constraintconditions)一指决策变量取值时受到的各种资源条件的限制。约束又可按其数学表达形式分成等式约束和不等式约束两种类型：等式约束：h(x)=0不等式约束：gx)0根据约束的性质可以把它们区分成：性能约束一针对性能要求而提出的限制条件称作性能约束。边界约束一只是对设

6、计变量的取值范围加以限制的约束称作边界约束。图1-2优化问题中的约束面或约束线)(a)、二变量问题的约束线(b)三变量问题的约束面可行域：在优化问题中，满足所有约束条件的点所构成的集合。如约束条件g(X)=x2x2-16，0和gX)=2-x，0的维设计问11222题的可行域D。图约束条件规定的可行域D般情况下，可行域可表示为：Dg(xDg(x,0)u=1,2,lh(jc)=0,j=1,2,，mjf不可行域：Df可行点和不可行点：约束边界上的可行点为边界点，其余可行点为内点。f起作用的约束与不起作用的约束：满足g(X*)=0的约束为起作用约u束，否则为不起作用的约束。(等式约束一定是起作用约束)

7、3、目标函数(Objectivefunction)一它是决策变量的函数。为了对优化进行定量评价，必须构造包含优化变量的评价函数，它是优化的目标，称为目标函数，以f(x)表示。f(X)=f(x,x,x)12n在优化过程中，通过优化变量的不断向f(x)值改善的方向自动调整，最后求得f(x)值最好或最满意的X值。在构造目标函数时，目标函数的最优值可能是最大值，也可能是最小值。在优化问题中，可以只有一个目标函数，称为单目标函数。当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的最优化问题。31目标函数等值(线)面定义：在高维空间(n,3)中，使目标函数值取同一常数的点集&/f(X)=c,c为

8、常数，称为f(X)的等值线(或等值面)。(或定义：对于具有相等目标函数值的自变量构成的平面曲线或曲面称为等值线或等值面。)数学表达式f&)=cc为一系列常数，代表一族n维超曲面。对于具有相等目标函数值的自变量构成的平面曲线或曲面称为等值线或等值面。性质在通常情况下，若目标函数f(X)是连续的单值函数，则其等值线具有以下性质：不同值的等值线不相交；除极值点所在的等值线外，等值线不会中断；等值线稠密的地方，目标函数值变化较快，而稀疏的地方,目标函数值变化较慢；在极值点附近，等值线近似地呈现为同心椭球面族(椭圆族)。4、可行域(Feasibleregion)满足约束条件的决策变量的取值范围。5、最优

9、解(Optimalsolution)一可行域中使目标函数达到最优的决策变量的值。优化问题一般数学形式设优化变量向量X，lx,x，,x112n求目标函数f(X)tmin满足约束条件:g(X0,j，1,2,mjh(X)，0,k，1,2,lk即minf(X，f(x,x，xXeRn12nS.t.g(X0,j，1,2,mjh(X)，0,k，1,2,lk建模实例建立优化问题的数学模型一般步骤：根据问题要求，应用专业范围内的现行理论和经验等，对优化对象进行分析。对诸参数进行分析，以确定问题的原始参数、优化常数和优化变量。根据问题要求，确定并构造目标函数和相应的约束条件，有时要构造多目标函数。必要时对数学模型

10、进行规范化，以消除诸组成项间由于量纲不同等原因导致的数量悬殊的影响。例混合饲料配合以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含:至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：配料每铸配料中的营养含量每務成*（元）钙蛋白质纤维石灰石大豆粉0.3800.00OJQO0.0010.090.020*0020*500.01640.1250解：设x,x,x是生产100磅混合饲料所须的石灰石、谷物、大豆粉的TOC o 1-5 h z123量（磅）。minZ=0.016

11、4x+0.0463x+0.1250 x123st.x+x+x=1001230380 x+0.001x+0.002x0.012100123，0.380 x+0.001x+0.002x0.0081001230.09x+0.50 x0.22100230.02x+0.08x012解：画出等式约束曲线x+x25x=0的图形。这是一条抛物线;122画出不等式约束区域：x+x-50和x,x0；1212画出目标函数等值线，以及等值线与可行集的切点。可见可行域为曲线段ABCD。d点是使目标函数值最小的可行点，其坐标可通过解方程组:得出:x+得出:x+x2-5x=0122x+x5=0121.6.2优化问题的基本解

12、法求解优化问题的基本解法有：解析法和数值解法。1.6.2.1解析法利用数学分析(微分、变分等)的方法，根据函数(泛函)极值的必要条件和充分条件求出其最优解析解的求解方法。局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。1.6.2.2数值解法这是一种数值近似计算方法，又称为数值迭代方法。它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点或直至达到最优点。数值解法(迭代法)是优化设计问题的基本解法。其中也可能用到解析法，如最速下降方向的选取、

13、最优步长的确定等。数值计算的迭代方法具有以下特点：是数值计算而不是数学分析方法；具有简单的逻辑结构并能反复进行同样的数值计算；最后得出的是逼近精确解的近似解。这些特点正与计算机的工作特点相一致。在数学规划中，采用Xk+1，Xk+dk进行迭代运算时，求n维函数f(X,f(x,x,x)的极k12n值点的具体算法如下图所示。一、求解步骤：数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：（1）首先初选一个尽可能靠近最小点的初始点X（0），从X（0）出发按照一定的原则寻找可行方向和初始步长，向前跨出一步

14、达到X1）点；（2）得到新点X1）后再选择一个新的使函数值迅速下降的方向及适当的步长，从XG）点出发再跨出一步，达到X（2）点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。在中间过程中每一步的迭代形式为：X(kX(k+1)X(k)+，(k)s(k)上式中：x）一第k步迭代计算所得到的点,称第k步迭代点，亦为第k步设计方案;,k）一第k步迭代计算的步长;图迭代计算机逐步逼近最优点过程示意图sCt）一第k步迭代计算的探索方向。用迭代法逐步逼近最优点的探索过程如右图所示。运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求:fx（k+i）0，都存在一个只与有关

15、而与咒无关的自然数N,使得当两自然数m,pN时,满足Xm-XPmmXP人8iii=1或（二）迭代终止准则（1）点距准则XkXk+1Xk|8或Xk+1Xk8Xk2其中8、8是事先给定的要求精度。12（2）函数值下降量准则fkfk+1fk8JJ3fk+1fk1503510130235120余料长度（cm）56235246235上述下料问题的数学模型为：minf&)=5x+6x+23x+5x+24x+6x+23x+5xTOC o 1-5 h z2345678St.2x+x+x+x=1001234x+x+3x+2x+x15023567x+x+3x+2x+3x+5x120134678x0=1,2,8i2

16、.1.2基本特点丄线性规划问题的共同特征：一组决策变量X表示一个方案，一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的，且求目标函数最大化或最小化。丄线性规划模型的一般形式：minf=exexex1122nnTOC o 1-5 h zax+axax1111221nnax+axax2112222nnax+axaxm11m22mnnx,x，x0 x,x匕力q+1n线性规划问题的标准形式(1)标准形式为一目标函数最小、约束条件等式、决策变量非负。minf=ex+ex+ex1122nnax+ax+ax+ax1111221nnax+ax+ax2112222nn(2)简写形式(3)向量形式a

17、x+a(2)简写形式(3)向量形式ax+ax+axm11m22mnnx,x,x0V12nminf(X)=工j=1工ax=b,i=1,2,mijjij=1x0,j=1,2,njminf&)=exs.t.工AX=bjjj=1x0,s.t.工AX=bjjj=1x0,j=1,2,nvj其中C（c1，X2,XnAu,a，aj1j2jtnj（4）矩阵形式st.AX=bXO其中TOC o 1-5 h zaa其中=VA,A,A)12naam1mn丄一般线性规划问题的标准化目标函数最小;maxf（X）=CX等价于（X）约束条件等式；约束条件16改为minf*=-2x一3x一0 x约束条件16改为minf*=-2

18、x一3x一0 x一0 x一0 x“2345=83+x=1x1242+x=1250 x+2x+x124x14x2x,x,x,x,x12345“”约束：减去非负剩余变量,即x可正可负k（即无约束）。x+x+x+(xx)+x=712456xx+(xx)x=2124573x+x+2(xx)=7minf=一叮一/J一叮OX0 x71245例2：minf=-x+2x一3xTOC o 1-5 h z123x+x+x7123x一x+x21233x+x+2x=7123x,x0,x无约束123其中2.2线性规划的图解法maxf=2maxf=2x+3x12x+2x8124x1614x012目标函数约束条件如上述例1

19、目标函数约束条件222图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向;平移目标函数的等值线，找出最优点，算出最优值。223线性规划问题求解的几种可能结果(A)唯一最优解;(B)无穷多最优解;(A)(B)(A)(B)(C)无界解；(D)无可行解。其可行域为空集224由图解法得到的启示可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。2.3线性规划解的性质2.3.1线性规划解的概念标准型minfCTXs.t.A

20、XbG）X，0其中AL,设ra）m，即约束方程组AXb中没有多余的方程，jmxn则应有n,m。如果用P表示矩阵A的第j列，则AXb也可记为j工xPb。jjj1基：若B=（P,P，,P）可逆，则B称为线性规划式G）的基。12mP（j1,2,m）称为基向量。有时也称向量组P,P,P为G的基，j12m而将B称为基矩阵（或称基阵）基（描述二）：若B是矩阵A中mXm阶非奇异子矩阵（囘工0，即可逆），则B可逆），则B是线性规划问题的一个基矩阵或称基阵）。不妨设：TOC o 1-5 h z(a,.,aBB(P1,.,P)a,.,am1mmP,j1,2,m基向量其中x,j1,2,m基变量x,jj+1,n-非基

21、变量j求解AXb，贝【Jr、(c、aa111r、(c、aa111mx+.+x1m,a丿m1、a丿mm(b)1(a1m+1lb丿mx-m+1(a1nw丿mm+1w丿mn基变量X(x,X,x，令Xm+1Xm+2Xn0B12m可求出：X(b,b,b,0,0,0)12mnn解为X=XB解为X=XBXN。这样AX二b变为XBXN=BX+NX=bBN特别地,若B=(P,P，P)N=(P，,P)，则A=(B,N)，相应地将X特别地,m,m,1nnnnnB-ib0AX=AX=(B,N:B-ib0nnnn右令B-ib=(x,x,x，则,0,0,0,x，x12m是上述标准型线性规划问题的一个基本解。基本解：对于基

22、b,令非基变量为零，求得满足AX=b的解，称为B对应的基本解（或称基解）。基本可行解：非负的基本解X称为基本可行解。可行基：对应基本可行解的基称为可行基。最优解：使f=CX达到最小值的可行解称为最优解。线性规划解的关系图nnnn由于A是mn矩阵，故线性规划问题的不同的基最多有Cm个。而一个基最多对应一个基本可行解，故此线性规划问题最多有Cm个n基本可行解。上述分析可知，基本可行解中非零分量的个数不会超过m，若基本可行解中非零分量的个数恰为m，称此基本可行解为非退化的基本可行解，否则称为退化的基本可行解。若一个线性规划的所有基本可行解都是非退化的，称此线性规划是非退化的。例：求基阵、基本可行解。

23、minz一2x-3x+0 x+0 x+0 xTOC o 1-5 h z12345x+2x8124x+x16，144x+x1225x,x,x,x,x01234512100A=40010，A的秩是3。、04001丿根据定义100、根据定义B=01011001丿是一个基阵，它对应的基本解为X=(0,0,8,16,12显然它是基本可行解。另根据定义200、另根据定义B=01021401丿也是一个基阵，它对应的基本解为X也是一个基阵，它对应的基本解为X=(0,4,0,16,-4它不是基本可行解。2.3.2线性规划问题的几何意义2.3.2.1基本概念一、凸集设K是n维欧式空间的一点集，对VXG),K，XG

24、),K连线上的一切点aXG+(1-a)x(2),K，0a1则k为凸集。二、顶点若k是凸集，X,K；若X不能用不同的两点XG),K，XG),K的线性组合表示为：aXG+G-a)XG),K，0a1则X为顶点。三、凸组合设XG,.,XQ是n维向量空间中的k个点，若存在卩，,卩，且1k0卩1,i=1,k，工P=1，使ii=1X二卩XG+PXc)+卩X(k)12k则X为XG),X(k)的凸组合。2322基本定理定理1：若线性规划问题存在可行域，则其可行域：D二&/AX二b,X，0是凸集。证明：设XGwD，XG）wD，XGhXG），则有AXG=b,XG,0，AXG）=b,XG,0令X为XG）和xG）连线上

25、的任意一点贝lj:X二aXG+（1-a）xG（0a1）（只要验证X在D中即可!）显然，X,0，将X代入约束条件，有AX=A（aX（1）+（1-a）X）=aAX（1）+（1a）AX（2）=ab+（1a）b=b因此，XeD，D是凸集。引理1：可行解X为基本可行解X的正分量（非零分量）在A中所对应的列向量线性无关。定理2：线性规划问题的基本可行解X对应于可行域D的顶点。定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。2.3.2.3几点结论线性规划问题的可行域D=x/AX=b，X,0是凸集。基本可行解与可行域的顶点一一对应。若线性规划有最优解，则必在其可行域的顶点处取得

26、。528可彳亍城为凸集528可彳亍城为凸集貝标禹数不同时等值线的斜率不同最优解在顶点产生4七0如果已知一个可行基B是一个m阶单位矩阵，不妨设B刚好位于矩阵A的前m列。这是，约束方程axb的形式为：x+axaxb1l,m+lm+11nn10,(i1,2,m)。此时，与B相对应的基本可行解是iX0(b，,b,0,0。1m设A(I,N)，I(P,P,P)为单位矩阵，N(P,P,P)TOC o 1-5 h z12mm+1m+2nX(x,x，,xI12mX(x,x,x)TNm+1m+2nC(c,c,c)TI12mC(c,c,c)TNm+1m+2n则有CCICN于是，线性规划问题可记为minf(X)=Ct

27、X+CtXIINN0,X0IN显然，X0二是此线性规划的一个基本可行解。显然，X0二数值为f(X0)=(CtCt)b由IX由IX+NX=b可得,INX二b-NXINf(X)=Ct(b-NX)+CtXf(X)=Ct(b-NX)+CtXINNNINN由于X0，故当CtNCtfOo)NIN即此时fQ0)是线性规划的最优值。定理1(最优解判别准则):对于上述线性规划问题，当CtN-CT0IN时，X时，X0二此线性规划的最优解。用分量的形式来表示，令=Ct=CtPcIjj(j=m+1,n)则当0时，x0=0,是其最优解。又当j=I,.,m时，若令=CtPcjIjj则因P=(0,0,1,0,.,0，1是第

28、j个分量，所以=c-c=0jjjj因此称(j=1,n)为P或x的判别数，由以上讨论可知，基向量或基jjj变量的判别数必定为零。可见，定理1又可叙述为:定理I：若线性规划各判别数03（j，J.,4）j解：1-2解：1-20151001为基，即1001为基，即x,x13为基变量，则X0，（4,0,5,0）T是与I对应的基本Ct，Ct，G,2,3,-2），Ct，（1,3）。贝【J判别数为0（j，1,-,4）j可行解。又可见，因此，X0，（4,0,5,0是其最优解。定理2：若线性规划的某个判别数0，而相应的列向量P0,X0BN由B可逆，则可得X，B-ib-B-1NXBN于是Ct-ib-B-iNX)+C

29、tXBNNNBN)T-CTB-iNXNBN，CtB-ib-BN)T-CTB-iNXNBNBBNNN，CtB-ib+B若B-1b0，则B-ib是一个基本可行解。如果进一步，CT如果进一步，CT-CTB-iN0NB或CtB-iN-CtCtB-ibBB-ib为式(*)的最优解。综上，可将CtB-iN-Ct非正作为式(*)的最优解的判别条件。BN又由于CTB-iA-CTB，CtB-iB,N)-(C,C，CtB-iB,CtB-iN)-(C,C，Ct,CtCTB-iA-CTBBB)BN，QCtB-iN-Ct丿BN所以，CtB一1NCt0与CtB-1A-Ct0是完全等价的。BNB令CtB-iPc(j1,n)

30、(*)jBjj仍称为P或x的判别数。jjj显然，前面定义的判别数是式(*)中B=I时的一种特殊情形。2、换基运算所谓换基运算就是从一个基本可行解迭代出一个新的基本可行解的方法。由于只考虑基本可行解之间的迭代问题，暂不涉及目标函数，这里先考虑以下这一组特殊的约束。xaxaxb11,m1m+11nn1VxVx0jmnnmj1,n)用矩阵表示，即A=G,N)，b(b,b，,b12m于是X=(b,b，,b,0,012m是一个基本可行解。现在从X出发，寻找新的基本可行解。对于矩阵1a，a，ab1,m11l1n1(Ab)=1a，abklknk1a，a，ab1m,m0，则X、就是一个基本可行解。而X0就是b

31、0。于是,ibb-,b0kakkl可知，必有akl0时，为使b0，应有ilb0ibb()aailkl故当a符合条件klmin丄/a0(探)aki逶ma江此时，可取a为主元对(Ab)进行换基运算，得到新基:ilI=(P，,P,P,P，,P)1k-1lk+1m及新的基本可行解：X=(b0bb、00b00)1k，1k+1mk换基运算的步骤：(1)在进基列P中按式(探探)选取主元a；lkl按式径)按式径)计算b、kb，得到上述所示的新的基本可行解。i举例：给定约束条件x+3x一x+3x=21456x+2x一2x+x=12456x一2x一x+2x=33/450 x0j=1,6丿j显然，X0=(2,l,3

32、,0,0,0是一个初始基本可行解。显然，如果要将P引入基中41003-132（Ab）=0102-211001-2-123则主元a应满足k4TOC o 1-5 h zbb/0.211b匚=min/a“0=min,=-aIai4I13212ak4i424于是（Ab）中的元a=2就是主元。按照式（探）作换基运算，得到24新的基本可行解是新的基本可行解是11-TX1=2,0,4,2,0,0”130023丄一2220101一1112220110一334同理可将P引入基中，则主元a应满足TOC o 1-5 h z6k6bb/0212baIai6I131J3ak6i616则a=3为主元。以a为主元对（Ab）

33、按照式（探）作换基运算，得到16161313一1-3一2-3001-11-33521010-3301-4-10533新的基本可行解为应当注意：并不是A的任何一列都可以引入基中。如上例中p就5不能入基，因为P0导致b二伫0，故在确定进基列的时候，应保证该列至少有一个正分量。3、进基列的选择以上换基运算分析可知，对进基列的要求是至少有一个正分量。然而满足这个条件的列向量可能很多。那么，挑选哪一个作为进基列更好呢？这需要与目标函数联系起来。如果在上例的约束条件上加上一个目标函数：f(X)=x一2x3x一4xx于是12346于是CT二U,-则在X则在X0、X1和X2处相应的目标函数值为fGo)=CtX

34、0二1“2(-2“13“3二9f&1)=CtX1=1“1+3“4+C4“1=21222f(X2丿=CtX2=C2)x1+3x5+1“-=5333同Xo相比，X1处目标函数值上升，X2处目标函数值下降，则此时应该选取P作进基列。然而，对于一般的线性规划来说，选择什么样的6列作进基列可以使目标函数值下降呢？定理3：设线性规划minf（X）=CtX+CtXs.t.BX+NX=bX0,X0满足以下条件：(1)基本可行解X(1)基本可行解X0=B-ib0非退化；P的判断数0；(3)p的分量中至少有一个为正。则用p作进基列将得到使目标函数值下降的基本可行解。定理3的证明详见傅英定等主编最优化理论与方法P6

35、0-P61)。但一般的线性规划符合进基列条件的列通常不止一个，那么，选取哪一列作进基列最好呢？由于由于所以，当最大时，目标函数值下降最快。可见与进基列的选择有关。如果对每一个可供选择的进基列p都计算一次，再比较各个jjjl的大小，则当可供选择的进基列数目较大时，相应的计算量也较大。所以，通常情况下，若有多个列满足进基列的条件，则选取判别数最大的那一列作进基列，这时目标函数值获得较大的下降。举例：对于线性规划mins.t.fX)=-2x-x12x+x+x123-x+x+x1246x+2x+x=5=1=210(j=1,5)111005(Ab)=-1101016200121=(P1,P2,P3,P4

36、,P5,取I=(P,P,P)为基，贝U345=CtP一c=0一c=20I111=CtP一c=0一c=10I222由于P、P均有正分量，故P、P都可作进基列但,故选取P为1212121将使目标函数值得到较大下降。2.4.3单纯形算法1、初始单纯形表的建立对于线性规划minf(X)=CtX+CtXBBNNs.tBX+NX=bBNX0,X0BN其中B是可逆矩阵，可作为这个线性规划的基，并建立以下矩阵:B-1AB-1bCtB-1A-CCtB-1bBB由上述讨论可知：x0=B-1b是线性规划的一个基本可行解。0CtB-1A-C的各分量就是判别数。BCtB-1b=f(X0)是对应于基本可行解X0的目标函数

37、值。B因此，矩阵式()记录着我们所关心的关于线性规划的全部信息。我们将这个矩阵称为线性规划的初始单纯形表。特别地，若基BI是单位矩阵，则初始单纯形表变为()CtA-CCTbII如果将A用(in)来表示，则基向量的判断数为零，且将目标函数值CTbI用f来表示，则式()又可记为0_INb_0tatfN0其中OT(0,0)aT(a,a)N(m+l、nlmffX0CTbX0(b,b,0,lm此时，线性规划对应的初始单纯形表的一般形式即为下表所示。P1PkPmPm+1plpnb1aaab1,m11l1n11aaabk,m1klknk1aaabm,m1k,m1k,nm000aaafm1ln0初始单纯形表记

38、录着以下信息：(l)等式约束AX=b的有关数据；各列向量的判别数a(j1,n)；初始基本可行解X0，(b，,b,0,0；1m对应于X0的目标函数值f。0对于基B=I的线性规划，建立初始单纯形表需要计算非基变量的判别数c,，以及相应的目标函数值f。m1n02、换基运算后的新单纯形表在初始单纯形表上对线性规划作换基运算。首先确定主元a，然klaGaGkjcjjalkl注意，此时c，ckic，0)llalklbf二f亠c0alkl于是，初始单纯形表变为新单纯形表如下图所示P1PkPmPm1P/Pnb1aa0ab.1k1,m+1:1n1aa1abkkk,m+1knka1a0abmkm,m+1mnm0c

39、0c0cfkm+1n上表中：(1)c是新单纯形表中P判别数；jj(2)f是新基本可行解Xi所对应的目标函数值。其中Xi=1b0bb00b00)1k1k1mk在新单纯形表中，(1)若c0j=1,6丿j解：取I=P,p,p）为初始基。则146Xo二（7,0,0,12,0,10）t为初始基本可行集。Ct二（0,0,0）I由q=CtPc计算出：=-1,二3，a=2jIjj235a、a、a为基变量所对应的判别数，必有a=q=q=0146146f=CTb=00I因此，初始单纯形表如下所示。P1P2P3P4P5P6b13-102070-2Q100120-43081100-130-200在非零判别数中，只有a

40、=30，且P有正分量，故应将P引入基底。TOC o 1-5 h z333由性=罰仝/a。=殳巴!=12，可知，应选a=4为主元作换基a1i6a13JI43J423k3il运算得到如下新单纯形表。P1P2P3P4P5P6b12/501/420100-1/211/40030-5/20-3/481101/20-3/4-20-9上表中只有,=120，且P有正分量，故应以a=25为主元作换基222125运算得到如下新单纯形表。PPPPPPb1234562/5101/104/5041/5013/102/505100-1/210111-1/500-4/5-12/50-11上表中各判别数,0j，1,2,n,n

41、+1,n+mj求解上述线性规划问题就是从最小化角度迫使人工变量取零，以达到求原问题最优解的目的。此时X(o)=(O,O,b，b可作为一个基本可1m行解，对上述线性规划问题可以用单纯形方法求解。容易理解，若X*，C,x*)为辅助线性规划问题的最优解，当1n+m*n+1-，x*，0日寸，n+mX*，C,x*)即为原问题的最优解；否则，原问1n题无可行解。举例：求解线性规划问题f一31+x2+x3x一2x+x3st0123解：(1)加入松弛变量和剩余变量进行标准化,加入人工变量构造初始可行基。x一2x+x+x，111234一4x+x+2xx+x，312356一2x+x+x，113x0(j，1,2,7

42、)7minf，-3x+x+x+0 x+0 x+Mx+Mx1234567j(2)用单纯形法求解300-M-MbXiX2x3兀1耘耘X-g11311-21-412亠11o0-100001001113/21f03-6MM-13M-10-M00表初始单纯形表)其最优解为x4,x1,x9，目标函数值f-2。123(3)求解结果出现检验数非正若基变量中含非零的人工变量，则无可行解；否则，有最优解。41两阶段法由于在大M法中引入一个很大的正数，可能产生较大的舍入误差，且在计算机上处理困难，故在实际问题中常用两阶段法。所谓两阶段法，就是将线性规划问题的求解过程分成两阶段，即先求初始基，再求解。两阶段法与大M法

43、的不同之处在于其辅助问题中的目标函数仅为各人工变量之和，即辅助问题minfminfxLKxn+ii=1工ax+x=bi=1,2,ms.t.jjn+ij=1x0j=1,2,n,n+1,n+mij当辅助线性规划问题的最优解f=0时，若X*=(*,X*)为其最优TOC o 1-5 h z1n+m解，则当X*=X*=0时，X*=C*,X*）必为原问题的最优解；否n+1n+m1n第一阶段：构造如下的线性规划问题=b1第一阶段：构造如下的线性规划问题=b1=b2何棚函數仅含人齐#晟忧解的tI标阳敕伯平为叽IU中杏f步的人丄甸问虺兀可订懈“Minf=x+x+.+xn+1n+2n+max+ax+ax+x111

44、1221nnn+1ax+ax+ax+x2112222nnn+2s.t.+x=bn+mmax+x=bn+mmm11m22mnnx,x，,x,x.,x012nn+1,n+m用单纯形法求解上述问题，若f=0，进入第二阶段；否则，原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表,然后利用单纯形法求解即可(下面举例说明，仍用大M法的例)。举例：求解线性规划问题x一2x+x0123解：(1)构造第一阶段问题并求解。x一2xx一2x+x+x=111234一4x+x+2x一x+x=312356一2x+x+x=11/3x0j=12.,7)7j利用单纯形法求解G00U0-1二1bxiXj

45、1123111-4-2-2101ft00-100100ni113/21厂4-610-100表100000-1-1XBbXiXj召愍x7x4121x211x3/I30-2010001100-2-10210-5-2I4fo00000-1-1衣头最终单纯形表表3中不含人工变量且f0,转入第二阶段。表4：去掉人工变量后的初始单纯形表表5：最终单纯形表单纯形法计算中的几个问题：1、目标函数极小化时解的最优性判断只需用检验数,0作为最优性的标志。j2、无可行解的判断当求解结果出现所有,0时，如基变量仍含有非零的人工变量j（两阶段法求解时第一阶段目标函数值不等于0）,则原线性规划问题无可行解。单纯形法有三种

46、形式：方程组形式；表格形式；矩阵形式。一、方程组形式的单纯形法1、思路由一个基本可行解转化为另一个基本可行解。例:minf-3x-5x12s.t.x+x=813minf-3x-5x12s.t.x+x=8132x+x=120V1234512f+3x+5x=012x+x=8132x+x=120v12345Y1=30F2=5aof+1V1+Sr2+0-v3+0.t4血o81236-一華曲tl）当前基：in冷排列阵目标方程中:切戛至呈的系議F尸Df囲|M寸jJHF.sijgprihi-IjfJ十F一HJa-初始基本可厅解样列臨毎行每列有且仅有一于元素*1-其余元麦全为。的方眸Xft(0?0.8,12,

47、36)tz0-0当前解Xo非忧匚LbXfl转化沖另-个某本呵令解X1亠思路匕LDh中的一个韭基变量进基去替换原来的一个基菠量（离基o-00-s-Ml=12+x5-36进览最大检验数规则）:庭正检藝赴申选择養丸的进基匕皿瑞/j|/j：0-rk瓦进Mmax3,5-5-rj也进卑蛊基葢小比值规則）:屯菟min,122,36.4-6耳=iniii12.2,364-6闷仍为非皐变帘，具怕为九由（D有12斗为韶基愛吕X1=(0,6,&0,12)T2、单纯形法的几何意义3、单纯形法的计算步骤5*5*确鬼主元5*5*确鬼主元maxZjIZj0=yk确运进基变量耳和主列去：.再按最小比值规则minI站ikA0=

48、确定主元叭上刖时也就确定第丁行的基变就芯离基.6以紬“为主元对当前表格送行-次换基运算.得到一牛新单纯形表，返3，送代步陳二、单纯形表从上述单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。按定义，化为当前基对应的典式。fcxcxcxcx011mmm+1m+1nnx+ax+axb11m+1m+11nn1，x+ax+axb22m+1m+12nn2x+ax+axbmmm+1m+1mnnm例2：用单纯形表求解LP问题解：化标准型maxf2x+x125x1526x+2x2412x+x0V12minf-2x-x+0 x+0 x+0 x123455x+x15236x+2x+x

49、240表1：列初始单纯形表（单位矩阵对应的变量为基变量）XbXX500X45100500I6正检验数中最大者对应的列为主列XbXX500X45100500I6正检验数中最大者对应的列为主列主元化为1主列单位向量尤.换出X换入表2：换基（初等行变换，主列化为单位向量，主元为1）表3：换基（初等行变换，主列化为单位向量，主元为1）步骤：1、初始基可行解的确定观察法：直接观察得到初始可行基。丄W约束条件：加入松弛变量即形成可行基。上约束条件：加入非负人工变量。2、最优性检验与解的判别最优解判别定理：若x(o)，C,b,b,0,0,0)为基可行解，且全部12m0,j，m+1,n，则X(0)为最优解。i

50、唯一最优解判别定理：若所有丫0，并且对应的m+km+k非基变量的系数a0,i，1,2,m，则具有无界解。i,m+k令x，,x为基变量，x,x为非基变量，则X(0)，(0,0,b,b)是n+1n+m1n1m一初始基可行解。5、对偶线性规划5.1问题提出假设某工厂有m种设备：B、B、B，一年内各设备的生产能力TOC o 1-5 h z12m(有效台时数)为b、b、b。利用这些设备可以加工n种产品：12mA、A、A，单位产品的利润分别为c、c、c。第j种产品需要在第i12n12n种设备上加工的台时数为a。问在设备能力允许的条件下怎样安排生产计划，使全年总收入最多？设x,x,x为各产品的计划年产量，s

51、为全年总收入，则该问题12n的数学模型为maxS=工cxjjj=1s.t.工ax，bi=1,2,，m(P)ijjij=1x0j=1,2,nj换个角度(从经济问题角度)：假设工厂将所有的设备用于出租，需要给各种设备制定出租价格。定价原则有两条：一是出租后得到的单位利润不得少于直接生产时的收入；二是出租价格尽量的低，以利于市场竞争。设第i种设备B的单位台时的出租价格为y，全年总收入为,ii则得到另一个线性规划问题的数学模型为min=byiii=1s.t.aycj=1,2,n(D)ijiji=1y0i=1,2,mi如果将式(P)的线性规划问题称作原问题，则式(D)为其对偶问题。5.2对称形式的对偶线

52、性规划定义(从数学问题角度)：线性规划问题(P)maxS=工cxjjj=1s.t工ax，bi=1,2,mijjij=1x0j=1,2,nj为对称形式的线性规划问题，其对偶规划(D)定义为minW=,byiii=1s.t.,aycj=1,2,，njiji=1y0i=1,2,mi原始线性规划atnixs=/可以看出，原2、艺切丸切，f=J,2,-,w/=:始规划与对偶规划是同一组数据叫工0,7=1,231243x+x+x+x61234x+x234x+x2x0j=1,4）ij_120138311166b=C=001123101026A=令W=(y1，与与y4)T，则其对偶线性规划为maxbrWs.t

53、.AtWCmaxg（W）2y1y+3y122y+ys.ts.t.+y33.0i由对称形式的线性规划问题构造其对偶问题的一般规则是:原规划问题是求目标函数最大，其约束条件统一是“W”则其对偶问题是目标函数最小，其约束条件统一为“上”原规划问题中与b相应的每个约束条件，对应着对偶问题的一i个决策变量y；i原规划问题的一个决策变量x，对应着对偶问题的一个约束条j件ay+ayHFayc1j12j2mjmj5.3非对称形式的对偶线性规划在讨论线性规划的标准形式时，需将不等式约束都转化为等式约束，而得到下面形式的线性规划minCTXAXb(P)s.t.,X0然而线性规划(P)的对偶规划应该是什么形式呢？主

54、要思想：将非对称形式的线性规划问题转化为对称形式的线性规划问题，再写出其对偶问题，也可由其对应关系表直接写出。分析思路：线性规划AXb等价于AXbAXb则线性规划(P)可变为_A-X_A-X-b-A-bminCTXs.t.(P)因此式(P”)的对偶规划为_b-TW1_-bW2maxA-ATW1W2W1_W20C(P)令W*=A-ATW1W2W1_W20C(P)令W*=W1-W2,则式(P)变为bTW*(D)s.t.AtW*C由W*的表达式可知，这里不能再要求W*0。这就是式(P)的对偶规划。举例：写出下面线性规划的对偶规划mins.t.f(X)=12x+8x+16x+12x12342x+x+x

55、=21232x+2x+4x=31x0j解：-2140-2A=b=22043Ct=(12,8,16,12)令W=(y,y12，则得到原规划的对偶规划为maxs.t.g)=2y+3y122y+2y1212y+2y8,124y1614y122通常，非对称形式的线性规划问题转化为对称形式的线性规划问题的步骤如下：第1步目标函数：对最大化问题转化为最小化问题，即;maxz=maxz=excx11nnmin一z=-exex11nn第2步约束条件：对“”不等式方程两边同乘以“-1”；对“=”等式方程ax+axax=bi11i22inn可写成两个“”式，即axax+axbi11i22inn-ax-axax一b

56、i11i22inn第3步决策变量：若x0，可令x=-x，使x0；若x无约束,jjjjj令x=x-x，使x,x0。jjjjj举例：试求下述线性规划问题的对偶问题minZ=2x3x-5xxTOC o 1-5 h z1234xx-3xx51234s.t.2x2x-xs.t.134xxx=6234x0；x,x0；x无约束1234解：设对应于三个约束条件的对偶变量分别为W=(y,y,y，按照原123问题与对偶问题的对应关系，则其对偶问题为maxW=5y4y6y123y2y212yy313-3y2yy-5123yy+y=1123y0；y0；y无约束1235.4对偶定理上节着重讨论了怎样从一个已知的线性规划

57、写出其对偶规划。原规划与对偶规划的最优解之间，很自然地有着密切的关系。本节将主要讨论对称形式的对偶定理。设线性规划min(LP)min(LP),s.t.AXbX0其可行集为R=x/AXb,Xo，以及其对偶规划PmaxbTW(DP(DP),s.t.AtWCW0及其可行集为R二W/AtWC,WO。D定理1VXeR,WeR，必有PDCTXbTW证明：由于VXeR,WeR，贝UDCtXAtW)XWT0,Y0匕，0t1YminX0,Y0设x0为上式的一个最优基本可行解，B是X0所对应的最优基，X0是BXo中基变量所组成的向量，贝U由最优解判别准则可知令W0，(CtB-1(A,-1Qt,0t)BCtB-J

58、，则由上式可知BWo)(A,-1)Ct,0t)即AtW0c,W00故W0是(DP)的可行解。由因为bTWo由因为bTWo，bTB，CtB-ib，CtXo，CtXoBBB因此由定理2的推论可知，W0是(DP)的最优解。此时，CtX0与bTW0分别是(LP)与(DP)的最优值，即minCtminCtXo，maxbTW证毕两个互为对偶的线性规划的解之间关系：两个规划都有可行解(或都有可行解)两个规划都没有最优解(或都没有可行解)；一个有可行解，但目标函数在可行集上无界，则另一个没有可行解。从上述证明还可以看出，如果B是(LP)的最优基，则CtB一1)就是B(DP)的最优解。这样一来就可以直接从(LP)的最终单纯形表中求得(DP)的最优解。下面以对称形式为例，讨论如何直接地从原规划的最终单纯形表求其对偶规划的最优解的问题。定理4设X与W分别为对称形式的原规划(LP)与对偶规划(DP)的可行解，则X与W同时也分别是(LP)与(