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

1、Dr. TANG Y2022-3-7Southeast University1本章框架1. 线性优化概念2. 单纯形法3. Matlab工具箱应用4. 电力系统中的应用2022-3-7Southeast University21939年苏联数学家L.V.坎托罗维奇;从40年代到50年代中期，美国由于军事和生产的需要迅速地发展了这一分支;1947年美国空军数学顾问G.B.丹齐克首次提出线性规划的概念，并且提出求解线性规划的单纯形法；2022-3-7Southeast University32.1 什么是线性规划2.1.1 线性规划的初步认识在生产和管理经营活动中，经常遇到这样的两类问题：（1）如

2、何合理地使用有限的劳动力、设备、资金等资源，以得到最大的效益（如生产经营利润）；（2）为了达到一定的目标（生产指标或其他指标），应如何组织生产，或合理安排工艺流程，或调整产品的成分，以使消耗资源（人力、设备台数、资金、原材料等）为最少。2022-3-7Southeast University4(1)配载问题配载问题：某种交通工具（车、船、飞机等）的容积和载重量一定，运输几种物资，这些物资有不同的体积和重量，如何装载可以使这种运输工具所装运的物资最多？(2)下料问题下料问题：某厂使用某种圆钢下料，制造直径相同而长度不等的三种机轴，采用什么样的下料方案可以使余料为最少？(3)物资调运物资调运：某种

3、产品有几个产地和销地，物资部门应太如何合理组织调运，从而既满足销地需要，又不使某个产地物资过分积压，同时还使运输费用最省？(4)营养问题营养问题：各种食品所含营养成分各不相同，价格也不相等，食堂应该如何安排伙食才能既满足人体对各种营养成分得需要，同时又使消费者得经济负担最少？此外，在地质勘探、环境保护等方面也都有与上述情况类似的问题。2022-3-7Southeast University5例2.1.1 生产安排问题某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量分别为30Kg，20Kg，所占设备时间分别为5台班，1台班，该厂每周所能得到的维生素量为16

4、0kg，每周设备最多能开15个台班。且根据市场需求，甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？每吨产品的消耗每周资源总量甲乙维生素 /kg3020160设备/台班51152022-3-7Southeast University6解：设该厂每周安排生产甲、乙两种药品的产量分别为x1,x2吨，则有：004155162325max211212121xxxxxxxxxz2022-3-7Southeast University7例2.1.2 喜糖问题设市场上有甲级糖和乙级糖，单价分别为20元/斤，10元

5、/斤。现在要筹办一桩婚事，筹备小组计划怎样花费不超过200元，使糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定采购方案，使糖的总斤数最大。2022-3-7Southeast University8解：设采购甲、乙两种糖各x1,x2斤:00502001020max211212121xxxxxxxxxz2022-3-7Southeast University92.1.2 线性规划问题的数学模型（1）每一个问题都有一组变量称为决策变量，一般记为 x1， x2 ， xn 。对决策变量的每一组值： 代表了一种决策方案。通常要求决策变量取值非负，即 。（2）每个问题中都有决策变量需满足的一组约束条件

6、线性的等式或不等式。（3）都有一个关于决策变量的线性函数称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。 001Txxx02n，012,jxjn ，,2022-3-7Southeast University10将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划线性规划。线性规划的一般数学模型为：1 122max minnnzc xc xc x11 11221121 1222221 12212,.;,0.nnnnmmmnnmna xaxa xba xa xa xbsta xaxaxbx xx2022-3-7Southeast University112.1.3 两

7、个变量问题的图解法对于只有两个决策变量的线性规划问题，可以用图解法来求解。应用图解法求解线性规划问题可能出现的结果：(1) 有唯一最优解；(2) 有无穷多个最优解；(3) 无最优解；(4) 无可行解。2022-3-7Southeast University122.1.4 线性规划数学模型的标准形式一般线性规划问题可写成下列标准形式：2022-3-7Southeast University1311min. .,1,0,1,njjjnijjijjc xstxb imxjn2022-3-7Southeast University14min. .,0cxstAxbxA是m*n矩阵，c是n维行向量，b是

8、m维列向量2.1.4 将非标准形式化为标准形式如何从实际问题得到的线性规划非标准形式的数学模型转化为标准形式的数学模型：1）目标函数为求最大化；2）约束条件是小于等于型；3）约束条件是大与等于型；4）有个约束方程右端项 ；5）决策变量无非负要求。0ib 2022-3-7Southeast University15例： 将下列线性规划模型化为标准形式：32132minxxxz., 0, 523, 2, 7.321321321321无约束xxxxxxxxxxxxts2022-3-7Southeast University16标准形式：7654210032maxxxxxxxz. 0, 5223, 2

9、, 7.76542154217542165421xxxxxxxxxxxxxxxxxxxxts2022-3-7Southeast University17线性优化法简而言之，目标函数和约束条件均为线性的，即为线性优化。线性优化可简单分为两类：单纯形法与内点法。两类方法均可解决数千变量和约束的线性优化问题。单纯形法虽然计算效率很高，但是随着问题规模的扩大其迭代次数会呈指数型增长，而内点法在这一点上具有优势，因此电力系统中很多线性优化问题都采用内点法。2022-3-7Southeast University182.2单纯形法2.2.1 单纯形迭代原理求解线性规划问题的通用方法。单纯形是美国数学家G.

10、B.丹齐克于1947年首先提出来的。理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。2022-3-7Southeast University19单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组表达成标准型方程组，找出基本可行解作为初始基

11、本可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。2022-3-7Southeast University20例1.2.1 求解下列线性规划问题的最优解004155160203025max211212121xxxxxxxxxz2022-3-7Southeast University21解：化为标准形式041

12、55160203000025max515142132154321xxxxxxxxxxxxxxz2022-3-7Southeast University22第一步：确定一个初始基本可行解；基本可行解就是满足非负条件的基本解，因此要在约束矩阵A中找出一个可逆的基矩阵。10001010150012030A这里m=3，3阶可逆方阵，可以看出x3,x4,x5的系数列向量是线性独立的，这些向量构成一个基2022-3-7Southeast University23),(100010001543)0(pppB对应的基变量为x3,x4,x5，x1,x2为非基变量。将基变量用非基变量表示x3=160-30 x1-

13、20 x2x4=15-5x1-x2 （3）x5=4-x12022-3-7Southeast University24将(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从非基变量转为基变量，称为进基变量进基变量，怎样确定离基变量离基变量：2022-3-7Southe

14、ast University25因为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)=152022-3-7Southeast University26此时非基变量为x2,x4,用非基变量表示基变量，代入(3)x3=70-14x2+6x4x1=3-1/5x2-1/5x4x5=1+1/5x2+1/5x4将(4)代入目标函数得Z=15+x2-x42022-3-7Southeast University2

15、7第三步：继续迭代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)=202022-3-7Southeast University28此时非基变量为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

16、值下降 所以X(2)为最优解，Z*=20, X*=(2,5, 0,0,2)2022-3-7Southeast University29单纯形法的基本步骤：第一步：构造一个初始基本可行解。第一步：构造一个初始基本可行解。对已经标准化的线性模型，设法在约束矩阵 中构造出一个m阶单位阵作为初始可行基，相应就有一个初始可行基，相应就有一个初始基本可行解。2022-3-7Southeast University30第第2步：判断当前基本可行解是否为最优解。步：判断当前基本可行解是否为最优解。求出用非基变量表示基变量及目标函数的表达式，称之为线性规划问题的典式（或称为规范式）。在目标函数的典式中，若至少有

17、一个非基变量前的系数为正数，则当前解就不是最优解；若所有的非基变量前的系数均为非正数，则当前解就是最优解（指最大化问题）。将目标函数的典式中非基变量前的系数称为检验数检验数。故对最大化问题，当所有的检验数 0时，当前解即为最优解。2022-3-7Southeast University31第3步：若当前解不是最优解，则要进行基变换迭代到下一个基本可行解。首先从当前解的非基变量中选一个作进基变量。选择的原则一般是：目标函数的典式中，最大的正检验数所属的非基变量作进基变量。再从当前解的基变量中选一个作离基变量。选择的方法是：在用非基变量表示基变量的典式中，除了可进基变量外，让其余非基变量取值为零，

18、再按最小比值准则确定离基变量。这样就得到了一组新的基变量和非基变量，即已从上一个基本可行解迭代到下一个基本可行解。然后求出关于新基矩阵的线性规划问题的典式，这就完成了基变换的全过程。在新的典式中可求出新基本可行解的取值及目标函数的取值。2022-3-7Southeast University32再回到第2步判断当前新基本可行解是否已达到最优。若已达到最优，停止迭代。若没有达到最优，再进行第3步作新的基变换，再次进行迭代。如此往复，直到求得最优解或判断无（有界）最优解时停止。2022-3-7Southeast University332.2 修正单纯形法算法原理在单纯形算法中，每步都需要计算矩阵

19、B的逆。修正单纯形法通过对旧的矩阵B的逆做行变换，来得到新的矩阵B的逆，从而只需要在迭代的初始需要计算矩阵B的逆，缩短了求解时间。2022-3-7Southeast University342.3 大M法算法原理大M法的求解线性规划的过程和单纯形法一样，不同的是对线性规划的一般形式的处理方法，大M法将线性规划:2022-3-7Southeast University35min. .0fcxAxbstxmin. .,0TfcxMe yAxybstx y转化为2.4 对偶理论随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随着与之配对的、两者有密切联系的另一个线性规划问题。将其中一个称为

20、原问题，另一个称为对偶问题。2022-3-7Southeast University362.4.2 三种形式的对偶关系原问题与其对偶问题之间通常有3种不同的关系形式。以下将原问题记作LP问题，对偶问题记作DP问题。1 对称形式的对偶关系2 非对称形式的对偶关系3 混合形式的对偶关系2022-3-7Southeast University37表2.1 对偶关系相互对照表2022-3-7Southeast University381 对称形式的对偶关系2 非对称形式的对偶关系3 混合形式的对偶关系2022-3-7Southeast University392.4.3 对偶解（影子价格）的经济解释如

21、果把原问题的约束条件看成是广义资源约束，则右端项的值表示每种资源的可用量。对偶解的经济含义就是资源的单位改变量引起目标函数值的增加量。在经济学中，通常用价值量来衡量目标函数值。因此对偶解也具有了价值内涵，通常称对偶解为影子价格影子价格。影子价格是对偶解的一个十分形象的名称，它既表明了对偶解是对系统内部资源的一种客观估价，又表明它是一种虚拟的价格，而不是真实的价格。2022-3-7Southeast University402.4.4 灵敏度分析以上讨论线性规划时，把 等均看成是常数。但实际上这些数据有的是统计数据，有的是测量值，有的是专家评估得到的数据，并非是绝对精确的，且也不是绝对不变的。因

22、此有必要来分析一下当这些数据发生波动时，对目前的最优解与最优值会产生什么样的影响？这就是所谓的灵敏度分析。灵敏度分析通常有两类问题：一是当 中某一部分数据发生给定的变化时，讨论最优解与最优值怎么变？二是研究 中数据在多大范围内波动时，使原有最优解仍为最优解，同时讨论此时最优值如何变动？iijjbac,bAc,bAc,2022-3-7Southeast University412.4用MATLAB 解决线性规划中的优化问题2.4.1 软件包解决线性规划问题1951 年, 国际水平只能求解约束条件为10 个方程的线性规划问题；1963 年, 能求解100010000 个方程的线性规划问题；1984

23、 年, 美国贝尔实验室的数学家卡玛卡把射影几何原理用于大规模线性规划问题的求解；MATLAB是一个通用数学软件包, 除了可以用其中的优化工具箱来求解线性规划外, 还有许多其他的强大功能。2022-3-7Southeast University422.4.2 MATLAB求解步骤线性规划的算法主要是迭代算法, 它从初始的基本可行解开始, 通过多次迭代过程选出最优解，它的迭代过程一般可描述为：2022-3-7Southeast University43求线性规划问题数学模型如下：A不等式约束的系数矩阵Aeq等式约束的系数矩阵b不等式约束的常向量beq等式约束的常向量lb,ub自变量的上下范围线性规

24、划问题又分大型问题与中型问题, 解决方法有些不同, 大型问题的算法的第一步需对涉及到的约束条件进行预处理。2022-3-7Southeast University44min,. .TA xbf xstAeq xbeqlbxub函数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，这个初始值只适应于中型

25、问题； x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options): 通过options选项指定优化参数；x=linprog(problem): 线性规划问题通过构造problem来指定。2022-3-7Southeast University45problem结构字段含义字段字段含义含义字段字段含义含义f目标函数lb变量下界Aineq不等式约束中的系数矩阵ub变量上界bineq不等式约束中的常向量x0初始优化点Aeq等式约束中的系数矩阵solver求解器，为“linprog”beq等式约束中的常向量options优化选项2022-3-7Southeast Univer

26、sity46函数linprog的用法(2)：x,fval=linprog():不但求出最优解，而且返回目标函数的最优值；x,fval,exitflag=linprog(): exitflag参数表示求解的结果;x,fval,exitflag,output=linprog(): output参数包含优化过程中的各种输出信息； x,fval,exitflag,output,lambda=linprog(): lambda参数是一个结构体，包含最优解处的拉格朗日乘子。2022-3-7Southeast University47具体求解时, 首先是给矩阵f , A , b ，Aeq，beq，lb，ub赋值。MATLAB 给矩阵赋值是逐行进行的, 行之间用分号“；”隔开, 每行元素之间可以用“ ,”号，也可用空格隔开,并且用符号“ ,”置于矩阵右上角表示作矩阵的转置运算。赋值完毕, 在命令窗口中调用优化程序lp