最优控制课件第3章线性规划.

第3章线性规划1第3章线性规划线性规划问题属于静态最优化问题。静态，是指系统处于稳定的工作状态，其数学模型是代数方程。因此，静态最优化问题，就是不考虑时间因素情况下，选择系统参数，使其处于最优状态下工作。所谓最优是用一个能反映控制效果的目标函数来衡量的。而目标函数的确定要从经济效果、设备性能、政策界限等方面综合考察来求得。线性规划问题的目标函数和约束条件都是线性函数，是最优化问题中最简单，又重要，而且实用上具有普遍意义的问题。第3章线性规划23.1线性规划的数学模型3.2图解法3.3线性规划的数学基础3.4线性规划的单纯形法3.5线性规划的对偶问题第3章线性规划33.1线性规划的数学模型例3-2(最低成本问题)（※）：某种饲料要求由y1，y2，y3和y4四种原料组成，这些原料中可消化成分的比率对应为a11，a12，a13和a14，粗蛋白含量比为a21，a22，a23和a24，粗纤维含量比为a31，a32，a33和a34，原料单位价格为c1，c2，c3和c4。要求每公斤饲料中可消化成分的含量不得小于b1，粗蛋白的含量不得小于b2，粗纤维的含量不得大于b3。问每公斤饲料中各种原料用量是多少时成本最低。第3章线性规划4解：设在每公斤饲料中y1，y2，y3和y4四种原料用量依次为x1，x2，x3和x4。每公斤饲料的成本为f(x)。该问题的数学表达式如下：目标函数：约束条件：变量约束：11223344min()fxcxcxcxcx111122133144121122223324423113223333443axaxaxaxbaxaxaxaxbaxaxaxaxb0,14ixi第3章线性规划5一、线性规划问题的标准形式（※）1.标准形式目标函数：约束条件：变量约束：1maxnjjjzcx001,1,2,,,(0)nijjiijaxbimb0,1,2,,jxjn通常把上述三个式子描述的问题称为标准线性规划问题，简称标准线性规划。第3章线性规划6标准线性规划的矩阵形式：目标函数：约束条件：变量约束：maxTzcx00(0)Axbb0x其中：12nxxxx111212122212nnmmmnaaaaaaaaaA010200mbbbb12ncccc第3章线性规划72.将一般线性规划转换为标准形式（※）线性规划标准数学模型要点（1）目标函数求极大值：maxTzcx（2）所有变量约束均为非负约束：0jx（3）约束条件均为等式约束：0Ax=b（4）等式约束右侧向量b0的各元素值均为非负：00ib第3章线性规划8转换方法（※）(1)如果是目标函数求极小值问题，只需将原目标函数反号，即等价为；min()Tcxmax()Tcx(0,0)bcxx(2)关于变量的非负限制：若xa为自由变量（即xa的符号不定），则可令xa等于两个新的非负变量xb，xc之差，即xa=xb-xc非正变量用它的反号变量来代替，即若，则可令xa等于一个非负变量xb的相反数，即xa=-xb0ax(0)bx第3章线性规划9(3)如果约束等式右侧常数为负值，则要化为正值。方法是表达式两边同时反号，若此时约束为不等式约束，则不等号改变方向。0(1,2,,)ibim01nijjijaxb010nijjniijniaxxbx(4)若约束条件为不等式约束,需转化为等式约束。若第i个约束条件为则在约束中添加一个非负变量xn+i，等价地考虑这里xn+i称为松弛变量。第3章线性规划10若第i个约束条件为则在约束中减去一个非负变量xn+i，等价地考虑这里xn+i称为剩余变量。01nijjijaxb010nijjniijniaxxbx第3章线性规划11例3-3(※)将给出的线性规划问题的数学模型规范成标准形式1231212123min345214100zxxxxxxxxxx自由，，解:245624572458max4335214102,4,5,6,7,8izxxxxxxxxxxxxxi，第3章线性规划123.2图解法求解线性规划问题的图解法反映了线性规划的几何意义。对于简单的二变量的线性规划问题可以用图解法（二维图形）来求解，且用图解法求解时不用将数学模型规范成标准形式。第3章线性规划13注：如果线性规划问题有最优解x*，那么x*一定属于所有满足各项约束条件的点x的集合，该集合称为解的可行域。变量作为坐标轴构成直角坐标系;不等式约束条件用坐标系中的半平面表示；可行域是一个凸多边形；目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。图解法的主要思路：第3章线性规划14例3-4用图解法求解下列线性规划问题121212212max50100()300()2400()250()0,0()zxxaxxbxxcxdxxe*[50,250]x解：最优解在可行域的一个顶点上，最优值为z=27500.1x2x122400xx12300xx02003002250x250300400ABmaxd12501000xx●第3章线性规划15结合例3-4，直观认识线性规划问题解的四种形式：1.唯一解。如本例3-4所示。2.无穷多个解。若把例3-4的目标函数改为则凸多边形的边AB上的所有点都是问题的解。因此，解是无穷多个。12maxzxx1x2x122400xx12300xx02003002250x250300400AB第3章线性规划163.无最优解(目标函数值为无穷大或无穷小)。若例3-4中式(b),(c)的约束条件不存在，则解的可行域是开区域，不能限制目标函数取值，目标函数值为无穷大。1x2x2250x02504.无解。若例3-4中式(c)的约束条件改为则约束条件(b)和(c)冲突，不存在同时满足约束条件的区域，即无可行域，故问题无解。12400xx第3章线性规划17简而言之，可能出现的情况：•可行域是空集，无解；•可行域无界，无最优解；•最优解存在且唯一，则一定在可行域顶点上达到；•最优解存在且不唯一，一定存在可行域的顶点是最优解。第3章线性规划183.3线性规划的数学基础一.基本定义1.凸集：设D是n维空间的一个点集，若集合D中任意两点x1和x2连线上的所有点都属于集合D，则称集合D是n维空间的一个凸集。任意两点连线上的点x，可表示为称x是x1和x2的凸组合。12(1),01xxx(a)凸集(b)凸集(c)非凸集(d)非凸集(e)非凸集第3章线性规划192.极点：设集合D为凸集，，如果对于x找不到，使得成立,则称x为凸集D的极点。即在凸集上不能表示成相异两点凸组合的点，称为极点；在线性规划问题的凸集上的极点称之为顶点。xD1212,()xxDxx12(1),(01)xxx第3章线性规划203.基本解：对于有n个变量、m个约束方程的标准线性规划问题，取其m个变量，若这些变量在约束方程中的系数列向量线性无关，则它们组成一组基本变量。确定了一组基本变量后，其它n-m个变量称为非基本变量。令非基本变量都为0，解约束方程，可唯一得到基本变量的值，从而得到一个满足约束方程的解，称为基本解。注：1.基本解的个数最多有个。2.基本解不一定满足变量约束条件。!!()!mnnCmnm第3章线性规划214.可行解：满足约束条件和变量约束的一组变量值称为可行解。0,(1)jxjn0Ax=b5.基本可行解：如果基本解中的每一个变量都是非负的，即满足变量约束的基本解称为基本可行解。如果在基本可行解中至少有一个基本变量为零，则该解称为退化的基本可行解，反之，称为非退化的基本可行解。注：基本可行解既是基本解、又是可行解，它对应于标准线性规划问题可行域的顶点。6.最优解:使目标函数达到最优值的可行解称为最优解.0,(1)jxjn第3章线性规划22例：已知约束条件：123124230218xxxxxx0,14ixi变量约束：1234562930000140018150,,,,,02106030004203182xxxxxx分析:(1)可行域上有无穷多个可行解。(2)有6个基本解：(3)这6个基本解中只有x1,x2,x5,x6是基本可行解。第3章线性规划23二.基本定理1.定理3-1：线性规划问题所有可行解的集合是凸集.2.定理3-2：线性规划问题若存在最优解，则最优解必然会出现在可行域的一个顶点上.3.定理3-3：设A是秩为m的m×n矩阵，b0是m维向量。约束的可行域为D，则上式的基本可行解x一定是D的顶点。0,0Ax=bx第3章线性规划244.结论：如果标准线性规划问题存在最优解，则可以先找出所有基本可行解，并计算相应的目标函数值，比较它们的值，与目标函数最大值相对应的基本可行解就是最优解。第3章线性规划25例3-5：求解线性规划问题121212112max230240250,0zxxxxxxxxx解：(1)将上述LP问题化为规范形式，即121231241512345max230240250,0,0,0,0zxxxxxxxxxxxxxxx第3章线性规划26约束条件的矩阵形式为：12345111003012010401000150xxxxx最优解在顶点上，最优值为z=55。*255Tx第3章线性规划27补充题(※)：某项工程需成套横截面相同而长度不同的钢梁，每一套由1根2.9米长、1根2.1米长和1根1.5米长的钢梁组成。这些钢梁是由7.4米长的钢坯截成的，现要生产100套钢梁，问应如何下料使用料最省，建立这一问题的数学模型，并给出线性规划的标准形式。第3章线性规划28123123123min233461zxxxxxxxxx120,0,xx3x补充题(※)：给出下列线性规划问题的标准形式自由变量第3章线性规划293.4线性规划的单纯形法(※)图解法只适用于求解二变量线性规划问题，对于多变量的线性规划问题，则无法应用图解法求解。标准线性规划问题如果存在最优解，更通用的求解思路为：可以先找出基本可行解（最多为个），计算相应的目标函数值并进行比较，与目标函数最大值相对应的基本可行解就是最优解。然而，当线性规划问题的基本可行解的数目很多时，一一求解并不现实，因此必须寻求一种更有效的方法。单纯形法是线性规划中最主要、最基本的一种方法。它的基本思路是：从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。mnC第3章线性规划30对于标准线性规划问题maxTzcx00(0)Axbb0x解题的基本步骤如下：(1)选取基本变量，计算基本解，从中找出满足变量约束的基本可行解；(2)计算基本可行解对应的目标函数值；(3)比较目标函数值的大小，与目标函数最大值相对应的基本可行解就是最优解。第3章线性规划31预备知识：基本变量、基本解、目标函数值及其相互关系的数学表达已知，即,,mnARnmrankAm12jnAaaaa12imBbbbbmmBR从A中任选m个线性无关的列组成基底，即其中：矩阵B中的列bi就是A中的某一列aj，下标j表示A中的列在矩阵A中的序号，下标i表示A的列在矩阵B中的序号。第3章线性规划32例3-5：求解线性规划问题121212112max230240250,0zxxxxxxxxx