第二章 线性规划在电力系统中应用 2011

2020/5/27,SoutheastUniversity,1,第二章线性优化在电力系统中应用,Dr.TANGYitangyi,本章框架,2020/5/27,SoutheastUniversity,2,1939年苏联数学家L.V.坎托罗维奇;从40年代到50年代中期，美国由于军事和生产的需要迅速地发展了这一分支;1947年美国空军数学顾问G.B.丹齐克首次提出线性规划的概念，并且提出求解线性规划的单纯形法；,2020/5/27,SoutheastUniversity,3,2.1什么是线性规划,2.1.1线性规划的初步认识在生产和管理经营活动中，经常遇到这样的两类问题：（1）如何合理地使用有限的劳动力、设备、资金等资源，以得到最大的效益（如生产经营利润）；（2）为了达到一定的目标（生产指标或其他指标），应如何组织生产，或合理安排工艺流程，或调整产品的成分，以使消耗资源（人力、设备台数、资金、原材料等）为最少。,2020/5/27,SoutheastUniversity,4,(1)配载问题：某种交通工具（车、船、飞机等）的容积和载重量一定，运输几种物资，这些物资有不同的体积和重量，如何装载可以使这种运输工具所装运的物资最多？(2)下料问题：某厂使用某种圆钢下料，制造直径相同而长度不等的三种机轴，采用什么样的下料方案可以使余料为最少？(3)物资调运：某种产品有几个产地和销地，物资部门应太如何合理组织调运，从而既满足销地需要，又不使某个产地物资过分积压，同时还使运输费用最省？(4)营养问题：各种食品所含营养成分各不相同，价格也不相等，食堂应该如何安排伙食才能既满足人体对各种营养成分得需要，同时又使消费者得经济负担最少？此外，在地质勘探、环境保护等方面也都有与上述情况类似的问题。,2020/5/27,SoutheastUniversity,5,例2.1.1生产安排问题,某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量分别为30Kg，20Kg，所占设备时间分别为5台班，1台班，该厂每周所能得到的维生素量为160kg，每周设备最多能开15个台班。且根据市场需求，甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？,2020/5/27,SoutheastUniversity,6,解：设该厂每周安排生产甲、乙两种药品的产量分别为x1,x2吨，则有：,2020/5/27,SoutheastUniversity,7,例2.1.2喜糖问题,设市场上有甲级糖和乙级糖，单价分别为20元/斤，10元/斤。现在要筹办一桩婚事，筹备小组计划怎样花费不超过200元，使糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定采购方案，使糖的总斤数最大。,2020/5/27,SoutheastUniversity,8,解：设采购甲、乙两种糖各x1,x2斤:,2020/5/27,SoutheastUniversity,9,2.1.2线性规划问题的数学模型,（1）每一个问题都有一组变量称为决策变量，一般记为x1，x2，xn。对决策变量的每一组值：代表了一种决策方案。通常要求决策变量取值非负，即。（2）每个问题中都有决策变量需满足的一组约束条件线性的等式或不等式。（3）都有一个关于决策变量的线性函数称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。,2020/5/27,SoutheastUniversity,10,将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。线性规划的一般数学模型为：,2020/5/27,SoutheastUniversity,11,2.1.3两个变量问题的图解法,对于只有两个决策变量的线性规划问题，可以用图解法来求解。应用图解法求解线性规划问题可能出现的结果：(1)有唯一最优解；(2)有无穷多个最优解；(3)无最优解；(4)无可行解。,2020/5/27,SoutheastUniversity,12,2.1.4线性规划数学模型的标准形式,一般线性规划问题可写成下列标准形式：,2020/5/27,SoutheastUniversity,13,2020/5/27,SoutheastUniversity,14,A是m*n矩阵，c是n维行向量，b是m维列向量,2.1.4将非标准形式化为标准形式,如何从实际问题得到的线性规划非标准形式的数学模型转化为标准形式的数学模型：1）目标函数为求最大化；2）约束条件是小于等于型；3）约束条件是大与等于型；4）有个约束方程右端项；5）决策变量无非负要求。,2020/5/27,SoutheastUniversity,15,例：将下列线性规划模型化为标准形式：,2020/5/27,SoutheastUniversity,16,标准形式：,2020/5/27,SoutheastUniversity,17,线性优化法,简而言之，目标函数和约束条件均为线性的，即为线性优化。线性优化可简单分为两类：单纯形法与内点法。两类方法均可解决数千变量和约束的线性优化问题。单纯形法虽然计算效率很高，但是随着问题规模的扩大其迭代次数会呈指数型增长，而内点法在这一点上具有优势，因此电力系统中很多线性优化问题都采用内点法。,2020/5/27,SoutheastUniversity,18,2.2单纯形法,2.2.1单纯形迭代原理求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。,2020/5/27,SoutheastUniversity,19,单纯形法的一般解题步骤可归纳如下：,把线性规划问题的约束方程组表达成标准型方程组，找出基本可行解作为初始基本可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。,2020/5/27,SoutheastUniversity,20,例1.2.1求解下列线性规划问题的最优解,2020/5/27,SoutheastUniversity,21,解：化为标准形式,2020/5/27,SoutheastUniversity,22,第一步：确定一个初始基本可行解；基本可行解就是满足非负条件的基本解，因此要在约束矩阵A中找出一个可逆的基矩阵。,这里m=3，3阶可逆方阵，可以看出x3,x4,x5的系数列向量是线性独立的，这些向量构成一个基,2020/5/27,SoutheastUniversity,23,对应的基变量为x3,x4,x5，x1,x2为非基变量。,将基变量用非基变量表示,x3=160-30 x1-20 x2x4=15-5x1-x2（3）x5=4-x1,2020/5/27,SoutheastUniversity,24,将(3)代入目标函数得Z=5x1+2x2+0,令非基变量x1=x2=0,代入,x3=160-30 x1-20 x2x4=15-5x1-x2（3）x5=4-x1,得到一个基可行解X(0),X(0)=(0,0,160,15,4),第二步：从当前基可行解转换为更好的基可行解,从数学角度看，x1,x2的增加将会增加目标函数值，从目标函数值中x1,x2前的系数看，x1前的系数大于x2前的系数，所以让x1从非基变量转为基变量，称为进基变量，怎样确定离基变量：,2020/5/27,SoutheastUniversity,25,因为x2仍为非基变量，故x2=0则(3)式变为x3=160-30 x1160/30=16/3x4=15-5x115/5=3x5=4-x14/1=4min=3，所以当x1=3时，x4第一个减少到0，所以x4出基则X(1)=(3,0,70,0,1)Z(1)=15,2020/5/27,SoutheastUniversity,26,此时非基变量为x2,x4,用非基变量表示基变量，代入(3)x3=70-14x2+6x4x1=3-1/5x2-1/5x4x5=1+1/5x2+1/5x4将(4)代入目标函数得Z=15+x2-x4,2020/5/27,SoutheastUniversity,27,第三步：继续迭代x2进基，x4仍为非基变量，令x4=0，则(4)式表示为x3=70-14x270/145x1=3-1/5x23/(1/5)15x5=1+1/5x2min=5，所以当x2=5时，x3首先减少到0，所以x3出基则X(2)=(2,5,0,0,2)Z(2)=20,2020/5/27,SoutheastUniversity,28,此时非基变量为x3,x4,用非基变量表示基变量，代入(4)x2=5-1/14x3+3/7x4x1=2+1/70 x3-2/7x4x5=2-1/70 x3+2/7x4将(5)代入目标函数得Z=20-1/14x3-4/7x4此时若非基变量x3,x4的值增加，只能使Z值下降所以X(2)为最优解，Z*=20,X*=(2,5,0,0,2),2020/5/27,SoutheastUniversity,29,单纯形法的基本步骤：,第一步：构造一个初始基本可行解。对已经标准化的线性模型，设法在约束矩阵中构造出一个m阶单位阵作为初始可行基，相应就有一个初始可行基，相应就有一个初始基本可行解。,2020/5/27,SoutheastUniversity,30,第2步：判断当前基本可行解是否为最优解。求出用非基变量表示基变量及目标函数的表达式，称之为线性规划问题的典式（或称为规范式）。在目标函数的典式中，若至少有一个非基变量前的系数为正数，则当前解就不是最优解；若所有的非基变量前的系数均为非正数，则当前解就是最优解（指最大化问题）。将目标函数的典式中非基变量前的系数称为检验数。故对最大化问题，当所有的检验数0时，当前解即为最优解。,2020/5/27,SoutheastUniversity,31,第3步：若当前解不是最优解，则要进行基变换迭代到下一个基本可行解。首先从当前解的非基变量中选一个作进基变量。选择的原则一般是：目标函数的典式中，最大的正检验数所属的非基变量作进基变量。再从当前解的基变量中选一个作离基变量。选择的方法是：在用非基变量表示基变量的典式中，除了可进基变量外，让其余非基变量取值为零，再按最小比值准则确定离基变量。这样就得到了一组新的基变量和非基变量，即已从上一个基本可行解迭代到下一个基本可行解。然后求出关于新基矩阵的线性规划问题的典式，这就完成了基变换的全过程。在新的典式中可求出新基本可行解的取值及目标函数的取值。,2020/5/27,SoutheastUniversity,32,再回到第2步判断当前新基本可行解是否已达到最优。若已达到最优，停止迭代。若没有达到最优，再进行第3步作新的基变换，再次进行迭代。如此往复，直到求得最优解或判断无（有界）最优解时停止。,2020/5/27,SoutheastUniversity,33,2.2修正单纯形法,算法原理在单纯形算法中，每步都需要计算矩阵B的逆。修正单纯形法通过对旧的矩阵B的逆做行变换，来得到新的矩阵B的逆，从而只需要在迭代的初始需要计算矩阵B的逆，缩短了求解时间。,2020/5/27,SoutheastUniversity,34,2.3大M法,算法原理大M法的求解线性规划的过程和单纯形法一样，不同的是对线性规划的一般形式的处理方法，大M法将线性规划:,2020/5/27,SoutheastUniversity,35,转化为,2.4对偶理论,随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随着与之配对的、两者有密切联系的另一个线性规划问题。将其中一个称为原问题，另一个称为对偶问题。,2020/5/27,SoutheastUniversity,36,2.4.2三种形式的对偶关系,原问题与其对偶问题之间通常有3种不同的关系形式。以下将原问题记作LP问题，对偶问题记作DP问题。1对称形式的对偶关系2非对称形式的对偶关系3混合形式的对偶关系,2020/5/27,SoutheastUniversity,37,表2.1对偶关系相互对照表,2020/5/27,SoutheastUniversity,38,1对称形式的对偶关系2非对称形式的对偶关系3混合形式的对偶关系,2020/5/27,SoutheastUniversity,39,2.4.3对偶解（影子价格）的经济解释,如果把原问题的约束条件看成是广义资源约束，则右端项的值表示每种资源的可用量。对偶解的经济含义就是资源的单位改变量引起目标函数值的增加量。在经济学中，通常用价值量来衡量目标函数值。因此对偶解也具有了价值内涵，通常称对偶解为影子价格。影子价格是对偶解的一个十分形象的名称，它既表明了对偶解是对系统内部资源的一种客观估价，又表明它是一种虚拟的价格，而不是真实的价格。,2020/5/27,SoutheastUniversity,40,2.4.4灵敏度分析,以上讨论线性规划时，把等均看成是常数。但实际上这些数据有的是统计数据，有的是测量值，有的是专家评估得到的数据，并非是绝对精确的，且也不是绝对不变的。因此有必要来分析一下当这些数据发生波动时，对目前的最优解与最优值会产生什么样的影响？这就是所谓的灵敏度分析。灵敏度分析通常有两类问题：一是当中某一部分数据发生给定的变化时，讨论最优解与最优值怎么变？二是研究中数据在多大范围内波动时，使原有最优解仍为最优解，同时讨论此时最优值如何变动？,2020/5/27,SoutheastUniversity,41,2.4用MATLAB解决线性规划中的优化问题,2.4.1软件包解决线性规划问题1951年,国际水平只能求解约束条件为10个方程的线性规划问题；1963年,能求解100010000个方程的线性规划问题；1984年,美国贝尔实验室的数学家卡玛卡把射影几何原理用于大规模线性规划问题的求解；MATLAB是一个通用数学软件包,除了可以用其中的优化工具箱来求解线性规划外,还有许多其他的强大功能。,2020/5/27,SoutheastUniversity,42,2.4.2MATLAB求解步骤,线性规划的算法主要是迭代算法,它从初始的基本可行解开始,通过多次迭代过程选出最优解，它的迭代过程一般可描述为：,2020/5/27,SoutheastUniversity,43,求线性规划问题数学模型如下：,A不等式约束的系数矩阵Aeq等式约束的系数矩阵b不等式约束的常向量beq等式约束的常向量lb,ub自变量的上下范围,线性规划问题又分大型问题与中型问题,解决方法有些不同,大型问题的算法的第一步需对涉及到的约束条件进行预处理。,2020/5/27,SoutheastUniversity,44,函数linprog的用法(1)：,x=linprog(f,A,b):线性规划只存在不等式约束；x=linprog(f,A,b,Aeq,beq):线性规划存在不等式和等式约束；x=linprog(f,A,b,Aeq,beq,lb,ub):一般格式的线性规划；x=linprog(f,A,b,Aeq,beq,lb,ub,x0):设定初始值x0，这个初始值只适应于中型问题；x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options):通过options选项指定优化参数；x=linprog(problem):线性规划问题通过构造problem来指定。,2020/5/27,SoutheastUniversity,45,problem结构字段含义,2020/5/27,SoutheastUniversity,46,函数linprog的用法(2)：,x,fval=linprog():不但求出最优解，而且返回目标函数的最优值；x,fval,exitflag=linprog():exitflag参数表示求解的结果;x,fval,exitflag,output=linprog():output参数包含优化过程中的各种输出信息；x,fval,exitflag,output,lambda=linprog():lambda参数是一个结构体，包含最优解处的拉格朗日乘子。,2020/5/27,SoutheastUniversity,47,具体求解时,首先是给矩阵f,A,b，Aeq，beq