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

[e-mail]2020/7/3SoutheastUniversity1本章框架1.线性优化概念2.单纯形法3.Matlab工具箱应用4.电力系统中的应用2020/7/3SoutheastUniversity21939年苏联数学家L.V.坎托罗维奇;从40年代到50年代中期，美国由于军事和生产的需要迅速地发展了这一分支;1947年美国空军数学顾问G.B.丹齐克首次提出线性规划的概念，并且提出求解线性规划的单纯形法；2020/7/3SoutheastUniversity32.1什么是线性规划2.1.1线性规划的初步认识在生产和管理经营活动中，经常遇到这样的两类问题：（1）如何合理地使用有限的劳动力、设备、资金等资源，以得到最大的效益（如生产经营利润）；（2）为了达到一定的目标（生产指标或其他指标），应如何组织生产，或合理安排工艺流程，或调整产品的成分……，以使消耗资源（人力、设备台数、资金、原材料等）为最少。2020/7/3SoutheastUniversity4(1)配载问题：某种交通工具（车、船、飞机等）的容积和载重量一定，运输几种物资，这些物资有不同的体积和重量，如何装载可以使这种运输工具所装运的物资最多？(2)下料问题：某厂使用某种圆钢下料，制造直径相同而长度不等的三种机轴，采用什么样的下料方案可以使余料为最少？(3)物资调运：某种产品有几个产地和销地，物资部门应太如何合理组织调运，从而既满足销地需要，又不使某个产地物资过分积压，同时还使运输费用最省？(4)营养问题：各种食品所含营养成分各不相同，价格也不相等，食堂应该如何安排伙食才能既满足人体对各种营养成分得需要，同时又使消费者得经济负担最少？此外，在地质勘探、环境保护……等方面也都有与上述情况类似的问题。2020/7/3SoutheastUniversity5例2.1.1生产安排问题某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量分别为30Kg，20Kg，所占设备时间分别为5台班，1台班，该厂每周所能得到的维生素量为160kg，每周设备最多能开15个台班。且根据市场需求，甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？每吨产品的消耗每周资源总量甲乙维生素/kg3020160设备/台班51152020/7/3SoutheastUniversity6解：设该厂每周安排生产甲、乙两种药品的产量分别为x1,x2吨，则有：004155162325max211212121xxxxxxxxxz2020/7/3SoutheastUniversity7例2.1.2喜糖问题设市场上有甲级糖和乙级糖，单价分别为20元/斤，10元/斤。现在要筹办一桩婚事，筹备小组计划怎样花费不超过200元，使糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定采购方案，使糖的总斤数最大。2020/7/3SoutheastUniversity8解：设采购甲、乙两种糖各x1,x2斤:00502001020max211212121xxxxxxxxxz2020/7/3SoutheastUniversity92.1.2线性规划问题的数学模型（1）每一个问题都有一组变量——称为决策变量，一般记为x1，x2，…，xn。对决策变量的每一组值：代表了一种决策方案。通常要求决策变量取值非负，即。（2）每个问题中都有决策变量需满足的一组约束条件——线性的等式或不等式。（3）都有一个关于决策变量的线性函数——称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。001Txxx02n，，…，012,jxjn，…,2020/7/3SoutheastUniversity10将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。线性规划的一般数学模型为：1122maxminnnzcxcxcx…1111221121122222112212,,...................................................;,,,0.nnnnmmmnnmnaxaxaxbaxaxaxbstaxaxaxbxxx…………2020/7/3SoutheastUniversity112.1.3两个变量问题的图解法对于只有两个决策变量的线性规划问题，可以用图解法来求解。应用图解法求解线性规划问题可能出现的结果：(1)有唯一最优解；(2)有无穷多个最优解；(3)无最优解；(4)无可行解。2020/7/3SoutheastUniversity122.1.4线性规划数学模型的标准形式一般线性规划问题可写成下列标准形式：2020/7/3SoutheastUniversity1311min..,1,,0,1,,njjjnijjijjcxstxbimxjn2020/7/3SoutheastUniversity14min..,0cxstAxbxA是m*n矩阵，c是n维行向量，b是m维列向量2.1.4将非标准形式化为标准形式如何从实际问题得到的线性规划非标准形式的数学模型转化为标准形式的数学模型：1）目标函数为求最大化；2）约束条件是小于等于型；3）约束条件是大与等于型；4）有个约束方程右端项；5）决策变量无非负要求。0ib2020/7/3SoutheastUniversity15例：将下列线性规划模型化为标准形式：32132minxxxz.,0,,523,2,7.321321321321无约束xxxxxxxxxxxxts2020/7/3SoutheastUniversity16标准形式：7654210032maxxxxxxxz.0,,,,,,5223,2,7.76542154217542165421xxxxxxxxxxxxxxxxxxxxts2020/7/3SoutheastUniversity17线性优化法简而言之，目标函数和约束条件均为线性的，即为线性优化。线性优化可简单分为两类：单纯形法与内点法。两类方法均可解决数千变量和约束的线性优化问题。单纯形法虽然计算效率很高，但是随着问题规模的扩大其迭代次数会呈指数型增长，而内点法在这一点上具有优势，因此电力系统中很多线性优化问题都采用内点法。2020/7/3SoutheastUniversity182.2单纯形法2.2.1单纯形迭代原理求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。2020/7/3SoutheastUniversity19单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成标准型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。2020/7/3SoutheastUniversity20例1.2.1求解下列线性规划问题的最优解004155160203025max211212121xxxxxxxxxz2020/7/3SoutheastUniversity21解：化为标准形式04155160203000025max515142132154321xxxxxxxxxxxxxxz2020/7/3SoutheastUniversity22第一步：确定一个初始基本可行解；基本可行解就是满足非负条件的基本解，因此要在约束矩阵A中找出一个可逆的基矩阵。10001010150012030A这里m=3，3阶可逆方阵，可以看出x3,x4,x5的系数列向量是线性独立的，这些向量构成一个基2020/7/3SoutheastUniversity23),,(100010001543)0(pppB对应的基变量为x3,x4,x5，x1,x2为非基变量。将基变量用非基变量表示x3=160-30x1-20x2x4=15-5x1-x2（3）x5=4-x12020/7/3SoutheastUniversity24将(3)代入目标函数得Z=5x1+2x2+0令非基变量x1=x2=0,代入x3=160-30x1-20x2x4=15-5x1-x2（3）x5=4-x1得到一个基可行解X(0)X(0)=(0,0,160,15,4)第二步：从当前基可行解转换为更好的基可行解从数学角度看，x1,x2的增加将会增加目标函数值，从目标函数值中x1,x2前的系数看，x1前的系数大于x2前的系数，所以让x1从非基变量转为基变量，称为进基变量，怎样确定离基变量：2020/7/3SoutheastUniversity25因为x2仍为非基变量，故x2=0则(3)式变为x3=160-30x1160/30=16/3x4=15-5x115/5=3x5=4-x14/1=4min=3，所以当x1=3时，x4第一个减少到0，所以x4出基则X(1)=(3,0,70,0,1)Z(1)=152020/7/3SoutheastUniversity26此时非基变量为x2,x4,用非基变量表示基变量，代入(3)x3=70-14x2+6x4x1=3-1/5x2-1/5x4x5=1+1/5x2+1/5x4将(4)代入目标函数得Z=15+x2-x42020/7/3SoutheastUniversity27第三步：继续迭代x2进基，x4仍为非基变量，令x4=0，则(4)式表示为x3=70-14x270/14＝5x1=3-1/5x23/(1/5)＝15x5=1+1/5x2min=5，所以当x2=5时，x3首先减少到0，所以x3出基则X(2)=(2,5,0,0,2)Z(2)=202020/7/3SoutheastUniversity28此时非基变量为x3,x4,用非基变量表示基变量，代入(4)x2=5-1/14x3+3/7x4x1=2+1/70x3-2/7x4x5=2-1/70x3+2/7x4将(5)代入目标函数得Z=20-1/14x3-4/7x4此时若非基变量x3,x4的值增加，只能使Z值下降所以X(2)为最优解，Z*=20,X*=(2,5,0,0,2)’2020/7/3SoutheastUniversity29单纯形法的基本步骤：第一步：构造一个初始基本可行解。对已经标准化的线性模型，设法在约束矩阵中构造出一个m阶单位阵作为初始可行基，相应就有一个初始可行基，相应就有一个初始基本可行解。2020/7/3SoutheastUniversity30第2步：判断当前基本可行解是否为最优解。求出用非基变量表示基变量及目标函