结构优化设计第五章线规划.doc

第五章 线性规划 线性规划属于有约束的优化问题，特点是目标函数和约束函数都是线性的。线性规划问题在理论和方法上都十分成熟，在工程管理和经济管理中应用十分广泛。虽然大多数机械设计和工程设计属于非线性规划问题，但在求解非线性规划中却常用到线性规划的算法，如可行方向法中可行方向的确定就是采用线性规划方法求解。因此了解线性规划的理论和原理是必要的。5.1 线性规划的标准形式与基本性质5.1.1 线性规划的标准形式以下三种形式都是标准形式。第一种形式：求满足以下约束条件的一组变量X=x1,x2,xnT， 这组变量使得目标函数有最小值。将第一种形式写成如下求和形式，即得第二种形式：将第一种形式写成矩阵形式，即得第三种形式：在以上各种形式中，n为线性规划的维数，m为线性规划的阶数，一般mn。注意，标准形式中约束条件是等式约束，设计变量均为非负,都是求目标函数的最小值。A 若线性规划问题中除变量外还存在不等式约束条件应通过引入松弛变量将不等式约束化成等式约束。例：设约束条件为 在第一式中引入松弛变量，得到若约束条件为则减去一个非负的松弛变量，即B 若设计变量可正可负设该变量为,则引入两个非负变量，令C 若目标函数为求最大值maxF(X)等价于min-F(X)另，为什么要求mn？因为只有当mn时，无解。5.1.2 线性规划的基本性质通过例子说明线性规划的基本概念和基本性质。设有线性规划问题为：用图解法求解：由本例可以看出：线性规划的可行域是一个凸多边形，凸多边形的某一个顶点就是最优解。凸多边形的顶点是有限的。-此为线性规划的性质。由此性质可知，求线性规划的最优不必在整个可行域内搜索，只要在它的有限个基本可行解（顶点）中寻找即可。现从代数角度考查线性规划的解。将上述线性规划问题转化为标准形式，得到变量个数（5）比约束方程个数（3）多2，可令任意2个变量为零，由此得到的解称为基本解（基本解有10种可能的取值，见下表）。若基本解落在可行域内，则称之为基本可行解。则基本可行解中的变量可分为两类：一类为正，一类为零。为正值的变量称为基本变量或基变量，为零的变量称为非基本变量或非基变量。基本可行解处于凸多边形的各顶点上。（对于本例，三个等式约束代表三个平面，不同的三个平面可以交于一点。同时满足三个等式约束的点必然在三个平面的交点上） 表中列出了本例中全部基本解，共10个，但基本可行解只有5个：序号为1、3、5、9、10，对应图中的ODABC五个顶点。与1号解对应的基本变量为x3=360,x4=300,x5=200，非基本变量为x1=0,x2=0。若约束方程的系数矩阵为A（m行，n列），从A中选择m列线性无关向量构成mm阶非奇异子矩阵B，则称B是线性规划的一个基。矩阵A可能有多少个基？答：本例题中约束方程的系数矩阵为取A的前三列，得到A的一个基为，其中为三个基向量，它们所对应的变量x1、x2、x3即为基变量，x4、x5为非基变量。若取A的后三列，得到另一个基,它是一个单位阵，称为标准基。在此情况下，x3、x4、x5为基变量，x1、x2为非基变量。5.2 单纯形法5.2.1 单纯形法的基本思路先求一个基本可行解X0及目标函数V（X0），检验X0是否为最优，若不是最优，则换另一个基本解X1，并使目标函数值下降。用单纯形法求解线性规划问题需要解决如下三个问题：（1） 如何给出第一个基本可行解？（2） 如何判断某一基本可行解不否为最优？（3） 如何从一个基本可行解转换至另一基本可行解，并使目标函数下降？通过一个例子来说明。5.2.2 简单单纯形法例：o.f. s.t. (本题中三个不等式有什么特点？)解：先将线性规划化成标准型：s.t.用表格表示为-2-3000Z-11100212010103100115A矩阵中已存在一个标准基（单位子块），若无，可通过行变换使A矩阵中出现单位子块。且单位子块对应的变量在目标函数中的系数为0，由上表可知，0,0,2,10,15T为基本可行解，即是可行域边界上的一个顶点。若o.f.形式为,其中，则可知它的最小值为V0。现o.f.中x1,x2的系数（-2，-3）不为正，则与此对应的解不是最优解。为使o.f.值较快下降，对-2、-3中绝对值较大的数-3进行处理，即通过行变换使其为0。即将-3对应的基向量通过变换进入标准基。即-3下面的三个数有一个要变为1，另两个变为0。但哪一个为1？其原则是应使行变换后的b矩阵保持非负。为此选取第一个约束条件中的1。-50300Z+6-11100230-210640-10113此步的基本可行解为0,2,0,0,6,13T目标函数为：Z=-5x1+3x300-1/35/30Z+16011/31/30410-2/31/302005/3-4/3150007/51/5Z+170103/5-1/53100-1/52/54001-4/53/53由此得到最优解为4,3,3,0,0T，Z*=17.回顾前面的三个问题：（1） 如何给出第一个基本可行解？（2） 如何判断某一基本可行解是否为最优？（3） 如何从一个基本可行解转换至另一基本可行解，并使目标函数下降？单纯形法的要点是：一，形成单位子块；二，单位子块对应的目标函数中的变量系数为0；三，保持常数项为正。5.2.3 两阶段法如果A矩阵中不存在一个单位子块，则简单单纯形不起作用。例：o.f. s.t. 化为标准型：o.f. s.t.第一阶段，在第一个约束方程中增加一个人工变量，并将原来的目标函数换成伪目标函数V，得到：o.f. s.t.用单纯形法求之，如果minV=0，意味着所有人工变量为0，即人工变量为非基变量。这时我们得到一个以原有变量的一部分为基变量的新的基本可行解。于是可以去掉人工变量，把原来的目标函数换上，再用单纯形正式求解。如果V0,表明原问题无解。00000111-100121-20100123001012-1-1100011-100121-201001230010120-3110003-1-10111-201001070-2101000000101-1/3-1/301/31/310-2/31/302/35/3007/31/31-7/323/3此时x6=0, minV=0,第一阶段结束。第二阶段：将目标函数换成原样，并去掉x6所对应的项。4300001-1/3-1/301/310-2/31/305/3007/31/3123/3利用行变换，将o.f.行中的4、3变为0。4011001-1/3-1/301/310-2/31/305/3007/31/3123/30011/3-1/3001-1/3-1/301/310-2/31/305/3007/31/3123/3继续利用单纯形法：将-1/3变为0，1/3变为1。1030011-100230-2105-103016由此得X*=0，2，0，5，6T，V*=65.2.4 大M法如果A矩阵中不存在一个单位子块，也可用大M法。以下用例题说明该法。例：o.f. s.t. 化为标准型：o.f. s.t.A矩阵中无单位子块,为形成单位子块，在第一个约束方程中增加一个变量x6,再在o.f.中增加一个松弛变量，其系数为正的大数M，得：o.f. s.t.只有x6的最取0时o.f.