第21讲优化方法.ppt

第21讲优化方法.ppt

《第21讲优化方法.ppt》由会员分享，可在线阅读，更多相关《第21讲优化方法.ppt（50页珍藏版）》请在冰点文库上搜索。

电子信息与电气工程学院,优化方法和最优控制,OptimizationMethodsandOptimalControl,2023/5/3,第二章线性规划,四、线性规划单纯形法,五、单纯形法基本算法,本章主要内容：

一、线性规划简介,二、线性规划建模及图解法,三、线性规划问题的标准形式,2023/5/3,一、线性规划简介,线性规划（LinearProgramming）研究线性约束条件下线性目标函数的极值问题的数学理论和方法。

线性规划是运筹学的一个重要分支，它是最优化问题领域中理论成熟、方法有效、应用最广泛的方法。

线性规划问题的社会运用大量存在：

在保证具有合理精度的前提下，大量的优化问题都可抽象成线性规划问题。

解决线性规划问题的方法高效、直观：

线性规划的基本算法是单纯形法及其修正算法，当独立变量为两个时，图解法是更方便直观的方法。

线性规划最容易处理：

线性目标函数f（x）的极值只能出现在边界条件上，这样优化问题的求解就得到了极大的简化。

2023/5/3,线性规划（LP）模型,在多变量函数情况下，线性规划问题可表示为：

Minf（x）=cxSub.toAx=bx0其中x、c分别是n维的列和行矢量；b为m维列矢量；A是mn矩阵。

所有满足约束条件的解称为线性规划问题的可行解；约束方程的解中非零元素的数目不大于约束方程数m时，称之为基本解。

全体可行解构成的集合称为该线性规划问题的可行域。

由于所有约束均为线性的，可行域为多边形或多面体，所有基本可行解对应于可行域的顶点。

一、线性规划简介,2023/5/3,二、线性规划建模及图解法,例2-1，饲料配比问题：

某饲料由三种原料混合而成，每种原饲料的营养成分及单价见下表:

要求：

混合饲料中必须包含：

营养A0.04，营养B0.02，及营养C0.07。

问：

三种原饲料按什么比例混合配比，成本最低?

2023/5/3,二、线性规划建模及图解法,分析：

设x1为第一种原饲料含量比例；设x2为第二种原饲料含量比例；则第三种原饲料含量比例为1x1x2；,目标函数：

Min15x1+12x2+8（1x1x2）；约束函数：

0.06x1+0.03x2+0.04（1x1x2）0.04；0.02x1+0.04x2+0.01（1x1x2）0.02；0.09x1+0.05x2+0.03（1x1x2）0.07；1x10；1x20；1（1x1x2）0；,上述线性规划问题化简后为：

2023/5/3,二、线性规划建模及图解法,求解两变量的线性规划问题最有效的方法是图解法：

根据约束条件所包围的区域构成目标函数的解的可行域。

根据图形得到可行域的顶点分别为：

（1,0）,（1/2,1/2）,（5/8,1/8）。

目标函数:

Min8+7x1+4x2；约束函数:

2x1x20；x1+3x21；3x1+x22；1x10；1x20；1x1+x20；,1x10,1x20,2x1x20,1x1+x20,x1+3x21,3x1+x22,2023/5/3,二、线性规划建模及图解法,定理：

线性规划如果存在最优点，则它一定出现在可行域构成的凸域的顶点。

解法一：

计算可行域各顶点的函数值，比较后得出最优解。

f（1,0）=15,f（x）=8+7x1+4x2,f（1/2,1/2）=13,f（5/8,1/8）=12,显然成本最低为12，三种原饲料的配比分别为：

x1*=5/8,x2*=1/8,x3*=1/4，f*=12。

解法二：

目标函数平移法,1.作目标函数的等值线7x1+4x2=c;2.与可行域顶点相切的最小常数c所对应的等值线，即为该目标函数的最小值，对应顶点即为独立变量的最优点。

2023/5/3,二、线性规划建模及图解法,例2-2，运输问题某运输公司在各地有许多车货物需运输至其它城市，货物所在地、数量、目的地、以及每车运费如下表，问如何调度车辆使得整个运输费用最省？

运输货物任务,每车运费（百元）,2023/5/3,二、线性规划建模及图解法,42,60,36,47,51,55,2023/5/3,二、线性规划建模及图解法,根据上述定义，建立目标函数为：

约束条件为：

ai0，bi0，xi0，共有mn个变量，分别表示从某城市到另一城市运货的车数。

同时，从m个城市发出的车辆总数应等于n个城市接收到的车辆的总数。

故有：

运输问题的一般模型描述为：

出发地m处，目的地n处。

设ai=出发地i拥有的车辆，i1，2，m；,bj=目的地j所需的车辆，j1，2，n；,cij=由出发地i到目的地j每车货物的运费；,xij=由出发地i到目的地j车辆运货数目。

2023/5/3,二、线性规划建模及图解法,为将运输问题转换为线性规划的一般描述形式，设：

约束方程系数为：

A为（m+n）（mn）维矩阵；,HnT=1111为n维矢量,矩阵A中n维矢量HnT共m个,0nT=0000为n维矢量,2023/5/3,二、线性规划建模及图解法,In为（nn）单位矩阵，共有m个。

由上述分析可知，运输问题的建模十分庞大，需结合实际的运输情况具体分析，进一步简化模型。

2023/5/3,二、线性规划建模及图解法,运输问题建模：

设由A城运往C的车辆数为x11、运往D的车辆数为x12、运往E的车辆数为50x11x12；,设由B城运往C的车辆数为20x11、运往D的车辆数为36x12、运往E城的车辆数为34（50x11x12）或40（20x11）（36x12）。

2023/5/3,二、线性规划建模及图解法,f（x）=42x11+55x12+60（50x11x12）+36（20x11）+47（36x12）+51（x11+x1216）,=3x11x12+4596,目标函数：

以总运费为目标函数，经简化，得,约束函数:

x110；x120；20x11036x12050x11x12016+x11+x120,解法一：

图解法，根据约束函数，得出可行域及其顶点的坐标，计算可行域各顶点的函数值。

从实际情况出发，每处调度的车辆或接收的车辆数目不可能为负数，因而增加非负约束：

2023/5/3,二、线性规划建模及图解法,20,0,0,36,f（20,0）=4536,f（x）=3x11x12+4596,f（16,0）=4548,f（0,16）=4580,f（0,36）=4560,f（14,36）=4518,f（20,30）=4506,由计算结果知最低运输费用为：

f*=Minf=f（20,30）=4506,解法二：

目标函数平移法,1.作代表目标函数变化的等值线族3x11x12=c;2.减小c，则等值线平行上移，和可行域最后相交于顶点（20，30），得到同样的结果。

2023/5/3,二、线性规划建模及图解法,运输问题的最优调度方案,根据上述解法的过程，可以直观地总结出线性规划的特性:

满足约束条件的解一般有无穷多组，称为可行解，其集合为可行域，线性规划的可行域一般为凸域，可行解的集合为凸集合。

约束方程组的解x中，非零元素数目不超过约束方程数m时，称为基本解。

符合实际约束x0的基本解称为基本可行解。

如果线性规划有最优解，则一定存在一个基本可行解是最优解。

即线性规划的最优解可以在基本可行解的集合中寻找，也就是在可行域的顶点处。

2023/5/3,三、线性规划问题的标准形式,线性规划问题的标准形式为：

Minf（x）=cxSub.toAx=bx0其中x为独立变量（n元素列矢量）；c为价格系数（n元素行矢量）；A为约束方程组系数矩阵（mn）；b为约束方程组等式中m维列矢量；x0要求所有元素均为非负。

具体线性规划问题的模型如果不符合标准形式为，则需通过各种方法将其转换成为标准形式，再作讨论。

将非标准形式转换成标准形式的方法如果极大化目标函数，Maxf（x）则可转换成为极小化负函数Minf（x）形式。

引入松弛变量，将不大于不等式约束条件转换为等式约束条件。

2023/5/3,三、线性规划问题的标准形式,若线性规划问题的模型为：

Minf（x）=cxSub.toAxbx0,则将约束条件转换为：

转换成标准形式之后，变量数由n个增加至n+m个，标准形式的约束方程系数矩阵变为：

同时，x1,x2,xn0，并且松弛变量xn+1,xn+2,xn+m0,2023/5/3,三、线性规划问题的标准形式,其中，A是原约束方程系数矩阵（mn）；而I是单位矩阵（mm）,转换后的约束方程可表示为：

其中，xs为由松弛变量组成的矢量。

2023/5/3,三、线性规划问题的标准形式,3.引入剩余变量，将不小于不等式约束条件转换为等式约束条件。

若线性规划问题的模型为：

Minf（x）=cxSub.toAxbx0,则将约束条件转换为：

2023/5/3,三、线性规划问题的标准形式,转换后的约束方程可表示为：

其中，xs为由剩余变量组成的矢量。

4.如果x为自由变量，没有非负约束，将该问题转换为标准形式。

将自由变量表示为两个非负约束的变量之差，如：

xi=uiviui0,vi0,这样，xi可以为正，也可以为负，即为自由变量。

该线性规划问题的模型为：

Minf（x）=cxSub.toAx=b,2023/5/3,单纯形法（SimplexAlgorithm）是美国数学家G.B.Dantzig于1947年提出，1953年，他又提出改进单纯形法，其运算效率高，占用的存储容量小，现今几乎所有的商品化的实用线性规划软件都采用改进单纯形法。

1.满足线性约束的可行域定理一：

线性约束的集合是凸集。

定理二：

线性规划问题的所有可行解的集合是凸集。

定理三：

线性规划问题的目标函数f（x）只要有最优解，则一定能在约束集合的某一极点处达到最优。

即最优函数f（x*）值只需搜索可行域多面体的顶点。

单纯形法算法依据：

线性规划问题的一些基本性质。

四、线性规划单纯形法,2023/5/3,2.线性约束方程组的基本解,线性约束的标准形式是：

Ax=b其中x为n维矢量；b为m维矢量；A为mn维矩阵，通常mn。

矩阵A的秩为m，从n个列矢量中选取一组m个线性无关的独立列矢量，组成基矩阵B，得到：

BxB=b其中xB为m维矢量；则x=xB,0是约束方程组Ax=b的一组解。

定义：

已知n个未知变量组成m个联立方程式Ax=b，而矩阵B是由矩阵A的任意列矢量所组成的mm非奇异子矩阵。

若在矢量x中，将所有和矩阵B不相关的nm个变量元素都设为零，这样所形成的方程组的解（矢量x），被称为Ax=b对应于矩阵B的基本解。

B为具有m个线性独立的列矢量的基，可把它看作是m维线性空间Em的基。

矢量x中与矩阵B的列矢量有关的元素成为基本变量。

四、线性规划单纯形法,2023/5/3,四、线性规划单纯形法,若一组基本解中有一个或多个基本变量为零，则称为退化基本解。

若一组基本解不仅满足约束Ax=b，且满足x0，则称之为基本可行解。

线性规划的基本定理：

已知线性规划问题为标准形式，则：

若该线性规划有可行解，则一定有基本可行解。

若该线性规划有最优解，则一定有最优基本可行解。

该定理把求解线性规划问题的任务简化在基本可行解范围内进行搜索。

一个具有n个变量和m个约束的问题，其基本解相当于从n个变量中选出m个变量组成，变量的组合数也就是基本解的个数。

不超过Cnm=n!

/m!

（n-m）!

2023/5/3,标准形式的线性规划问题，采用单纯形法求解，是在约束方程组的各组基本可行解之间进行一次次转换，不断减小目标函数，直至达到最小值。

单纯形法算法原理:

标准形式的线性规划问题模型：

Minf（x）=cxSub.toAx=bx0其中x、c分别是n维的列和行矢量；b为m维列矢量；A是mn矩阵。

（1）换元运算.即从一个基本可行解转换到另一个基本可行解。

将约束方程组Ax=b变换为如下的典型形式。

四、线性规划单纯形法,2023/5/3,这样，可得到一组基本解，其中基本变量,而所有非基本变量xm+1=xm+2=xn=0,即基本可行解为xB=（b1,b2,bm,0,0）。

四、线性规划单纯形法,2023/5/3,将约束方程的系数用表格的形式来表示，aj表示第j列矢量。

换元运算就是用非基本变量xk替换基本变量xp，其中1pm,m+1kn，同时，进行换元运算的先决条件是apk0。

四、线性规划单纯形法,2023/5/3,

（2）入基（k=?

）选择主元列k进入基，使换元后的目标函数值有所降低。

每次基本解的转换都力求使目标函数值有所降低，这是单纯形法的核心思想，从而使单纯形法的寻优搜索效率大大优于其它寻优算法的搜索效率。

目标函数：

f（x）=c1x1+c2x2+cnxn,对应基本解，目标函数为f0（xB）=cBxB,如果xm+1,xm+2,xn,被赋予任意值而不再为零，则由约束方程的典型形式得到：

其中cB=c1,c2,cm；xxB,0,四、线性规划单纯形法,2023/5/3,代入到目标函数式中，得到：

f（x）=cx=f0+（cm+1fm+1）xm+1+（cm+2fm+2）xm+2+（cnfn）xn,f0=c1b1+c2b2+cmbm,fj=a1jc1+a2jc2+amjcm,m+1jn,由此可见，约束方程Ax=b取任何解时，均可将目标函数表示为xm+1,xn的函数。

因此，可判断将某一非基本变量引入基本解将对目标函数产生影响。

四、线性规划单纯形法,2023/5/3,对应某一个j，其对应的系数（cjfj）0，若xj由零增大至一正值，总的目标函数将减小，从而使得新的解比原来的解的目标函数有所改进。

其中，系数rj=cjfj称为检验数。

定理：

最优检验条件若一组基本可行解中所有j对应的cjfj都非负（0），则这组解为最优解。

四、线性规划单纯形法,2023/5/3,用非基本变量xk替换基本变量xp，进行换元时，对所有系数作如下运算：

其中，apk为主元，位于p行k列。

连续换元的过程都是以非退化假定为前提。

即假定每个基本可行解都是非退化基本可行解（或基本可行解中每个元素都大于零）。

四、线性规划单纯形法,2023/5/3,在所有的非负比值bi/aik中，选取最小者以确定p，即主元行。

这样，以主元行换行的结果是：

1）.第ak列变为0,0,1,0,0T;2）.第ap列变为非零向量T;3）.其它基向量保持不变。

出基（p=?

）（确定哪一个列矢量p离开基运算）,假定约束条件等式右侧的量bi均为非负，所以相应的基本解是可行解。

已经确定矢量ak将进入基，km，,若k列中任选一个元素i作为“主元”，即xi目前为基本变量，但它即将退出基本变量：

四、线性规划单纯形法,2023/5/3,上述确定主元行的选择原则的依据是：

变换后，所有的bi都应大于零。

i=1,2,m。

所以，必须有：

而且必须保证变换后：

所以，选择bi/aik比值中最小、而且非负者为主元p，确保变换后的基本解仍然是可行解。

四、线性规划单纯形法,2023/5/3,综上所述，单纯形法算法的基本原理如下：

用基本可行解改进目标函数的理论来选ak为主元列；决定离开基的列p，即在第k列中选取第p个元素apk为主元；换元，以非基本变量xk取代基本变量xp；迭代终止判据，即所有检验数rj=cjfj都非负，而且在矢量b中所有的元素都非负，得出一组最优基本可行解。

四、线性规划单纯形法,2023/5/3,五、单纯形法基本算法,

（一）、列表法,对于下列形式的线性规划问题,Minf（x）=cxSub.toAxbx0其中x、c分别是n维的列和行矢量；b为m维列矢量；A是mn矩阵。

将非标准形式的线性规划问题，通过在约束方程中加入松弛变量xi，i=1,2,m。

使其成为标准形式的线性规划问题，同时得到一组初始基本可行解x1,x2,xm,0,0。

2023/5/3,五、单纯形法基本算法,2023/5/3,列表中i表示基变量下标；ci为基变量的价格系数；xB为基变量集合；aij为约束方程系数；b为约束方程等式右边的常数矢量；rj=cjfj；检验数或相对价格系数；i=bi/aik，k为选定的主元列。

列表法的迭代计算步骤：

由检验数rj=cjfj行中找出最小值（负数中绝对值最大）对应的主元列k；计算所有的i=bi/aik，i=1,2,m,其中aik为主元列中的各个系数；在所有的i中找出最小的正i，此行为主元行p；主元列k和主元行p的交点即为主元apk；主元apk被自身除得1；将主元列中除apk外全部变为零；主元行中所有的apj（cB和i除外）都除以主元apk；,五、单纯形法基本算法,2023/5/3,将主元行中原基本变量用主元列中新进入的基本变量代替，并将目标函数中有关新基本变量的价格系数放在cj列中；表中的其余元素作相应变换，新元素aij=原元素aijapjaik/apk,其中apj为主元行p中对应于原元素所在列j位置上的系数；aik为主元列k中对应于原元素所在行i位置上的系数。

回至步骤，顺序进行计算、迭代，直到所有的检验系数都非负，则达到最优解。

列表法的迭代计算步骤：

五、单纯形法基本算法,2023/5/3,例2-1：

Maxf（x）=40x1+60x2Sub.to2x1+x270x1+x240x1+3x290x10,x20,解：

首先将上述线性规划问题转换为标准形式。

Minf（x）=40x160x2Sub.to2x1+x2+s1=70x1+x2+s2=40x1+3x2+s3=90x1,x2,s1,s2,s30初始基本可行解x=x1,x2,s1,s2,s3=0,0,70,40,90,五、单纯形法基本算法,2023/5/3,五、单纯形法基本算法,2023/5/3,五、单纯形法基本算法,2023/5/3,这样，经过两次换元，三次迭代后，检验数rj非负，目标函数达到最优。

最优解为x1*=15，x2*=25，f（x*）=2100。

五、单纯形法基本算法,2023/5/3,对于用单纯形列表法求解线性规划问题，计算的初始条件是约束方程系数矩阵中存在mm单位矩阵，即已知初始基本可行解（可行域的一个顶点）。

一般情况下，线性规划建模并化为标准形式后，系数矩阵中未必存在单位矩阵。

通常采用下列两种处理方法。

1）.两阶段法第一阶段，在等式约束方程组的系数矩阵中，再加入人工变量组成mm单位矩阵。

目标函数修改为极小化各人工变量之和,

（二）、列表法初始基本可行解建立方法,Minw（x）=xn+1+xn+2+xn+mSub.toa11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1,x2,xn,xn+1,xn+m0,五、单纯形法基本算法,2023/5/3,对于上述修正后的线性规划问题，用单纯形法求解，如果w（x）=0，说明所有的人工变量都是零，这样就得到原线性规划问题的一个基本可行解。

第二阶段以第一阶段得到的基本可行解为起点，目标函数换成原问题的目标函数，继续用单纯形法求得最优解。

如果第一阶段最优计算结果为w（x）0，表示原问题无可行解，则终止计算。

2）.大M法（罚系数法）在线性规划问题的约束条件中，加入人工变量，组成第一个基本可行解，同时，在目标函数中也加入人工变量，且人工变量的价格系数取一个很大的正系数M，其目的是在迭代过程中使人工变量尽早退出基本变量，不影响最优解，加速迭代过程。

五、单纯形法基本算法,2023/5/3,例2-2：

Minf（x）=3x1+x2+x3Sub.tox12x2+x3114x1+x2+2x332x1x3=1x1,x2,x30,解：

首先将其转换为线性规划标准形式Minf（x）=3x1+x2+x3Sub.tox12x2+x3+x4=114x1+x2+2x3x5=32x1+x3=1x1,x2,x3,x4,x50其中，松弛变量x4是基本变量，而其它两个方程中没有基本变量，故加入非负人工变量x6和x7构成初始基本可行解，使系统变为：

五、单纯形法基本算法,2023/5/3,Minf（x）=3x1+x2+x3Sub.tox12x2+x3+x4=114x1+x2+2x3x5+x6=32x1+x3+x7=1x1,x2,x3,x4,x5,x6,x70,这样，系统的初始基本可行解为：

x=0,0,0,11,0,3,1T,若采用两阶段法，则第一阶段的目标函数改为：

Min.w（x）=x6+x7,初始单纯形表中的基变量为x4,x6,x7，第一阶段的结果是w（x）=0，最优解变量x=0,1,1,12,0,0,0T。

由于x6=x7=0，原线性规划问题的初始基本可行解为x=0,1,1,12,0T。

取消第一阶段最终计算表中的人工变量x6,x7，将目标函数换回原来的目标函数，继续用单纯形列表法求解得x*=4,1,9,0,0T,目标函数达极小值为f（x*）=2。

五、单纯形法基本算法,2023/5/3,若采用大M法，则原线性规划转换为：

Minf（x）=3x1+x2+x3+Mx6+Mx7Sub.tox12x2+x3+x4=114x1+x2+2x3x5+x6=32x1+x3+x7=1x1,x2,x3,x4,x5,x6,x70,直接用单纯形法计算，M和其它系数一样参加迭代，同样得到最优解x*=4,1,9,0,0T，目标函数达极小值为f（x*）=2。

大M法算法评价：

优点：

相比两阶段法，大M法可以一次完成优化；缺点：

容易出现除零，计算机求解线性规划时很少采用此法。

五、单纯形法基本算法,2023/5/3,本章小结,四、线性规划单纯形法,五、单纯形法基本算法,一、线性规划简介,二、线性规划建模及图解法,三、线性规划问题的标准形式,2023/5/3,第二章线性规划,