青科大化工-最优化方法

PSE2009线性规划1/38第2章线性规划1、什么是线性规划？2、主要术语3、线性规划的解的重要性质4、单纯形法5、有关初始基本可行解的一些问题PSE2009线性规划2/38有约束条件问题的最优化

线性规划LP

非线性规划NLP----目标函数objectivefunction----约束条件restriction常见的有：不等式约束条件,等式约束条件若f(X)、hi(X)、gj(X)均为线性-------线性规划若f(X)、hi(X)、gj(X)中含有非线性函数-------非线性规划

其中，若f(X)为二次函数，hi(X)、gj(X)为线性函数-------二次规划有约束条件问题模型的一般表达式：PSE2009线性规划3/38处理有约束条件下优化问题的策略主要有：

1.消去约束条件，转化为无约束优化问题，如经典的拉格朗日法、罚函数法和SUMT法等。

2.不消去约束条件，但按无约束条件搜索，并随时检验是否满足约束条件，如刺绣法、复合形法、约梯度法等PSE2009线性规划4/38§2线性规划LinearProgramming（LP）

历史资料：最早研究线性规划问题的是苏联数学家和经济学家康托洛维奇。

1947年GeorgeDantzig（美）创立了求解线性规划的一般方法-----单纯形法。

2.1什么是线性规划？目标函数和约束条件对于独立变量呈线性关系。PSE2009线性规划5/38§2.线性规划LinearProgramming（LP）

单纯形法修正单纯形法对偶单纯形法线性规划可表述为：注：初始约束条件为等式的-------标准型初始模型；初始约束条件有等式的和“”的--------规范型初始模型；初始约束条件中有“”的--------一般型初始模型；----表示所有变量为非负值----表示约束方程组为线性PSE2009线性规划6/38可行解-------满足所有约束条件的解，称为~。基本解-------对如下问题，令n-m个变量等于0（n，总自变量数；m，约束方程数），联立解式(2)所得到的解，称为~。基本可行解--------同时满足式3的基本解，称为~。例1：x2约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.550246810122.2主要术语PSE2009线性规划7/38最优解-------基本可行解中使目标函数最优的那个解，称为~。基本变量--------又称基础变量，指基本可行解中的变量（必大于零），m个；非基本变量--------又称非基础变量，指除基本变量以外的其它变量，n-m个。凸-------如果在一个形体中任取两点联结成一根直线，线段上所有的点都在这个形体内部，就称这种形体为凸形的。反之，则称为非凸的。凸集合--------设在可行域内的任意两点x1、x2之间联线，若线段仍在可行域内，则称这种域为~。2.2主要术语PSE2009线性规划8/38凸函数-------对于两点x1、x2之间联线上的任意点x，若01，则有则称f(x)为凸函数。若等号去掉，则称其为严格凸函数。若第2式中不等号反向，则称f(x)为凹函数。对凸集合，凸函数f(x)的局部最小值点就是全局最小值点。对凸集合，严格凸函数f(x)有唯一的最小值点因此，若已知所处理的问题的可行域和目标函数都是凸性的，则求得的极小值点必定是最小值。PSE2009线性规划9/381.可行解的集合可表示为一个凸集合，基本可行解就是这个凸集合的顶点（又称极点）；2.极值点一定位于边界的交点上，而不会在区间内部。2.3线性规划的解的重要性质约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.55024681012PSE2009线性规划10/38例1：规范化x2x1约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.55024681012f=-1f=-2f=-3PSE2009线性规划11/38f=100f=200f=300例2：最优解：PSE2009线性规划12/382.4单纯形法x2x1约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.55024681012

基本思路：先求得基本可行解，然后在其中找到最优。从几何上，就是在凸集合的顶点之间进行变换，找到最优。单纯形法并不需要检测每一个顶点才能找到最优解，可以证明，一般计算次数在m~2m之间。m---约束方程个数。PSE2009线性规划13/38单纯形法步骤：

1.将问题标准化将约束方程组以等式形式表示，方法是加入松弛变量slackvariable（0时），或减去剩余变量surplusvariable（0时）。每个方程加入一个。为使引入的松弛变量不影响目标函数，松弛变量在目标函数中的系数应均为0。2.4单纯形法PSE2009线性规划14/38例3：同例1标准化2.4单纯形法PSE2009线性规划15/382.4单纯形法PSE2009线性规划16/382.选一组基本变量（m个），构成初始的基本可行解。一般选松弛变量或剩余变量作为基本变量最为简便。这里选x3、x4、x5为基本变量，x1、x2为非基本变量。则-------基本可行解2.4单纯形法约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.55024681012PSE2009线性规划17/383.对上述基本可行解进行检验，看是否为最优解。检验指标为：目标函数中基本变量的系数等式约束方程组中非基本变量的系数目标函数中非基本变量的系数求最小值时，若所有的j0，则为最优，否则，有一个j<0，就不是最优解。等式约束方程个数由于1<0，故上述基本可行解不是最优解。PSE2009线性规划18/384.如果不是最优解，就进行换基运算，即确定哪一个非基本变量应该进入基本变量组中（称为入基变量）。

一般可根据j

的数值来决定： 当求最大值时，具有正的最大j的变量进入基本变量； 当求最小值时，具有最大绝对值的负的j的变量进入基本变量。因为此时该变量对目标函数影响最大。显然，此题中，1<0，故x1

为入基变量。PSE2009线性规划19/385.确定离基变量：哪一个基本变量应该离开基本变量组。

一般可通过变化上述入基变量，看哪一个基本变量先降为0，选使入基变量变化最小的基本变量为离基变量。入基变量的变化值可用下式表示：令基本变量x1、x2、……xm均为0，注意非基本变量中除了入基变量xj外，其余均为0。若i为负时，可不必考虑此项。i基本变量，j非基本变量PSE2009线性规划20/38对于此题：可见，应选x4为离基变量于是基本变量变为x1、x3、x5，非基本变量为x2、x4。约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.55024681012PSE2009线性规划21/386.重复步骤2~5，直至使所有的j0为止。约束条件1约束条件2约束条件3约束条件4可行解的集合00.511.522.533.544.55024681012PSE2009线性规划22/38

求最小值时，若所有的j0，则为最优，否则，有一个j<0，就不是最优解。线性规划：标准型约束条件：简要说明：PSE2009线性规划23/38经高斯消去法化为：有一基本可行解：------非基本变量-------基本变量式4代入式5得：PSE2009线性规划24/38代入式1得目标函数值：基本变量在目标函数中的系数又由式3得任一可行解：代入式1得目标函数值：PSE2009线性规划25/38PSE2009线性规划26/38

由式6可见，若所有的j=（Cj-zj）0，j=m+1,…,n，则z>z0，也就是说，任一可行解对应的目标函数值均比基本可行解对应的目标函数值大，则基本可行解为最优。否则，有一个j=（Cj-zj）<0，则有可能z<z0，基本可行解就不是最优解。同理可证，当目标函数求最大值时，若所有的j=（Cj-zj）0，j=m+1,…,n，则基本可行解为最优。否则，有一个j=（Cj-zj）>0，则基本可行解就不是最优解。PSE2009线性规划27/38例4：假设某厂有原料M1=60kg，M2=100kg，M3=60kg，可生产P1、P2两种产品。生产1kgP1需M12kg、M22kg，生产1kgP2需M11kg、M25kg、M34kg。销售1kgP1的收入为6元，销售1kgP2的收入为7元。问如何安排生产计划，可使收入最大。解：设P1的产量为x1kg，P2的产量为x2kg2.4单纯形法建模：PSE2009线性规划28/381.将问题标准化引入3个松弛变量，将上式变为标准形式：PSE2009线性规划29/38指定为x1，x2非基本变量基本解：相当于不安排生产时的情况（收入为零）2.选一组基本变量（m个），构成初始的基本可行解。一般选松弛变量或剩余变量作为基本变量最为简便。PSE2009线性规划30/38目标函数中基本变量的系数等式约束方程组中非基本变量的系数目标函数中非基本变量的系数求最大值时，若所有的j0，则为最优，否则，有一个j>0，就不是最优解。等式约束方程个数由于1

、2>0，故上述基本可行解不是最优解。3.对上述基本可行解进行检验，看是否为最优解。检验指标为：PSE2009线性规划31/384.如果不是最优解，就进行换基运算，

当求最大值时，具有正的最大j的变量进入基本变量；显然，此题中，2

最大，故x2

为入基变量。5.确定离基变量：使入基变量变化最小的基本变量为离基变量。若i为负时，可不必考虑此项。i基本变量，j非基本变量PSE2009线性规划32/38可见，应选x5为离基变量于是基本变量变为x2、x3、x4，非基本变量为x1、x5。PSE2009线性规划33/386.重复步骤2~5，直至使所有的j0为止。指定为x1，x5非基本变量基本解：PSE2009线性规划34/38最优解：即表示生产P125kg，P210kg，用完M1、M2，剩余M320kg时，可得最大收入220元。PSE2009线性规划35/38

一般总是采用松弛变量和剩余变量构成初始可行解，但有时没有松弛变量或其个数不够，此时，需引入人工变量（ArtificialVariable）以补充。

当达到最优解时，所有的人工变量应为零，否则就不满足原约束条件