工程最优化课件第二章

第二章线性规划lixgi,,1,0)(mxhj,,1j,0)(minf(x)s.t.☆在模型中当f(x),gi(x),(i=1,…l),hj(x),(j=1,…m)均为线性函数时，称为线性规划问题LP二维问题的图解法线性规划的基本定理单纯形法大M法要点：基本定理、顶点、标准形式、典范形式、可行基本解、价值系数、最优性准则、单纯形表格法§2.1建立LP问题数学模型的实例（1）确定自变量建模的三个步骤（2）把问题的约束条件表示成等式或不等式（3）写出目标函数☆研究重要性（1）一些NLP问题可简化为LP问题求解（2）是开发一些较复杂NLP算法的基础（3）是所有最优化方法中最常用的技术(占47％；科学计算中，LP的计算时间占1/4）☆1939年苏联数学家提出并解决了一个线性规划问题☆1947年美国数学家提出了单纯形法后，LP的理论和算法趋于成熟例2.1.1确定职工编制问题某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准是：速度25件/小时，正确率98％，计时工资4元/小时；二级检验员的标准是：速度15件/小时，正确率95％，计时工资3元/小时。检验员每错验一次，工厂要损失2元。现可供厂方聘请的检验员人数为一级8人和二级10人。为使总检验费用最省，该工厂应聘一级和二级检验员各多少名？分析：设应聘一级检验员x1，二级检验员x2约束一：可聘两级检验员人数x18x210约束二：每日产量要求8(25)x1+8(15)x218005x1+3x245目标函数一级检验员每小时费用4＋25(0.02)(2)=5元/小时二级检验员每小时费用3＋15(0.05)(2)=4.5元/小时f(x)=8(5x1+4.5x2)=40x1+36x2minf(x)=40x1+36x2s.t.5x1+3x245x1≤8x2≤10x1,x2≥0数学模型隐含的约束条件§2.2二维问题的图解法图解步骤（1）在x10x2坐标平面上画出可行域；（2）作目标函数的等高线(为一组平行的直线)，根据等高线函数值的变化规律及目标函数的要求，确定等高线的移动方向，按此方向移动等高线，使其达到可行域的极限点（最优点）；（3）根据最优点的位置，联立求解对应的约束方程，求出最优点坐标；（4）将最优点坐标代入目标函数，求出最优值。ABCDP19例：maxf(x)=4x1+3x2s.t.3x1+4x2≤123x1+3x2≤104x1+2x2≤8x1,x2≥00x1x2343x1+4x2=123x1+3x2=104x1+2x2=8f=7f=52/5最优点(x1*=4/5,x2*=12/5)f*=52/5ABCD例：maxf(x)=4x1+2x2s.t.3x1+4x2≤123x1+3x2≤104x1+2x2≤8x1,x2≥00x1x23x1+4x2≤123x1+3x2≤104x1+2x2≤8f=4f=8最优点：CD上的所有点f*=8§2.3线性规划问题的几种特殊情况§2.3.1有无限个最优解例：maxf(x)=4x1+3x2s.t.3x1+4x2≥123x1+3x2≥104x1+2x2≥8x1,x2≥00x1x23x1+4x2=123x1+3x2=104x1+2x2=8§2.3.2无界可行域f增大方向数学上存在但对于实际问题，可能是遗漏或写错了约束条件！0x1x23x1+4x2=123x1+3x2=104x1+2x2=8§2.3.3可行域为空集例：maxf(x)=4x1+3x2s.t.3x1+4x2≤123x1+3x2≥104x1+2x2≤8x1,x2≥0§2.4线性规划的基本定理§2.4.1凸集与顶点☆凸集：设M为Rn中的一个集合，如果对M中任意两点为端点的线段全部含于M中，则称M为凸集。x(1)x(2)x(1)x(2)☆直观定义：内部没有“洞”，边界不向内凹的形体非凸集实例x(1)x(2)ABCDFEGH（球面上的所有点都是顶点）☆凸集的基本性质若M1和M2为凸集，λ为正实数，则集合（1）{y|y=λx,x∈M1}（2）{y|y=x+z,x∈M1,z∈M2}（3）M1和M2的交集M1∩M2都为凸集。☆顶点如果凸集M中的一个点x不是M中任一线段的内点，则x是M的一个顶点K§2.4.2线性规划的两个重要性质☆基本定理（1）线性规划的可行域是一个凸集；（2）线性规划若存在可行点，则必存在可行域的顶点；若存在最优点，则至少有一个顶点是最优点。☆定理的重要意义（1）保证了顶点的存在性；（2）把一般要从无限个可行点中寻优最优点的问题简化为仅在有限个顶点中确定最优点的问题问题：为什么顶点只有有限个？怎样找出顶点？§2.5线性规划的标准形式一般LP标准LP单纯形法求解标准LP思路：minz=c1x1+c2x2+．．．+cnxns.t.a11x1+a12x2+．．．+a1nxn=b1a21x1+a22x2+．．．+a2nxn=b2．．．．．．．．．．．．．am1x1+am2x2+．．．+amnxn=bm目标函数x1≥0,x2≥0,．．．,xn≥0b1≥0,b2≥0,．．．,bm≥0非负条件约束方程组LP的标准形式：用矩阵和向量表示的LP的标准形式：c=[c1,c2,．．．,cn]T价值系数向量x=[x1,x2,．．．,xn]T决策向量b=[b1,b2,．．．,bn]T要求向量a11a12．．．a1na21a22．．．a2n．．．．．．am1am2．．．amnA=系数矩阵minz=cTxs.t.Ax=bx0b0目标函数非负条件约束方程组n―LP的维数m―LP的阶数§2.5.1将等式约束的右端化为非负若某等式约束的bi0，在该约束两端乘上（－1），化为－(ai1x1+ai2x2+．．．+ainxn)=－bi0§2.5.2化不等式约束为等式约束（1）若第i个约束条件为ai1x1+ai2x2+．．．+ainxnbi则引入“剩余变量”wi0，将不等式化为等式ai1x1+ai2x2+．．．+ainxn－wi=bi（2）若第i个约束条件为ai1x1+ai2x2+．．．+ainxnbi则引入“松弛变量”wi0，将不等式化为等式ai1x1+ai2x2+．．．+ainxn＋wi=bi不利方面：维数增加了！（在LP中存在可取任意值的自由变量xj，在标准形式中不允许存在）方法一：引进新变量xj’≥0,xj”≥0,作变换xj=xj’－xj”，代入原问题消除xj（参见PP25例2.5.1)§2.5.3自由变量的处理方法二：（消去法）（1）先用松驰变量或剩余变量将约束条件中的不等式变为等式；（2）把自由变量xj从某个等式约束中解出；（3）把已解出的xj代入其余约束及目标函数，新问题中消去了xj。§2.5.4化最大值问题为最小值问题若原问题为maxz’=d1x1+d2x2+……+dnxn则引入新目标函数z=－z’，而约束条件不变，原问题等价为minz=-d1x1-d2x2-……-dnxn§2.6单纯形法1947年由美国数学家GeorgeDantzig提出，实践证明实用有效，但理论上不能保证不出现退化和迭代循环的问题。后有人提出了修正单纯形法，有所简化，计算量小了，且能避免无限循环问题求解条件：在LP标准形式中，系数矩阵A的秩＝m（即m个约束方程相互独立）否则，n=m，约束方程组只有唯一解或无解nm，约束方程组无解无最优可言而且nm,在A中任选m×m方阵，其行列式至少有一个不等于0自由度大于零§2.6.1基本概念(一)基本解对于标准形式的LP，如何求min?开始解方程组Ax=b是否满足非负条件？否将解x代入目标函数是目标函数值还能减小吗？是否得出最优解？变量数n方程个数m，可见其中的n－m变量可任意取值非基本变量基本变量基本解（基本解的个数≤Cnm个）令某n－m个变量等于0解出剩余的m个变量(x1,x2,…,xm,0,…0)(二)可行基本解称满足非负条件（xi≥0,i=1,2,…,n）的基本解为可行基本解?可行基本解有什么用？考察下列线性规划问题：minz=－200x1－500x2s.t.1.5x1+5x2≤402x1+4x2≤40x1,x2≥0x20x1102030AB2468101.5x1+5x2≤402x1+4x2≤40DC图解法可知顶点D为最优点x1*=10,x2*=5,z*=－4500z=–2000引入松弛变量，将上述LP化为标准形式：minz=－200x1－500x2s.t.1.5x1+5x2+x3=402x1+4x2+x4=40x1,x2,x3,x4≥0非基本变量基本变量目标函数值z是否为可行基本解x1＝x2=0x3=40,x4=400是x1＝x3=0x2=8,x4=8–4000是x1＝x4=0x2=10,x3=–10否–5000x2＝x3=0x1=80/3,x4=–40/3否–16000/3x2＝x4=0x1=20,x3=10是–4000x3＝x4=0x1=10,x2=5是–45000基本解的个数≤C42＝6个x18246102030Cx20AB10D（最优）EFC对应于右图中的点BAEFCD(最优)☆LP的重要性质：可行域的每一个顶点与一个可行基本解相对应☆根据LP的基本定理，可知，只须在有限个可行基本解中寻优！☆LP的重要性质：可行域的每一个顶点与一个可行基本解相对应☆根据LP的基本定理，可知，只须在有限个可行基本解中寻优！上次课回顾§2.2二维问题的图解法§2.3线性规划问题的几种特殊情况§2.4线性规划的基本定理（1）线性规划的可行域是一个凸集；（2）线性规划若存在可行点，则必存在可行域的顶点；若存在最优点，则至少有一个顶点是最优点。§2.5线性规划的标准形式☆“可行基本解”从LP的一般标准形式出发如何？minz=c1x1+c2x2+．．．+cnxns.t.a11x1+a12x2+．．．+a1nxn=b1a21x1+a22x2+．．．+a2nxn=b2．．．．．．．．．．．．．am1x1+am2x2+．．．+amnxn=bmx1≥0,x2≥0,．．．,xn≥0b1≥0,b2≥0,．．．,bm≥0？如何最简便地得到可行基本解？(三)线性规划的典范形式x1+a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2……………………xm+am,m+1xm+1+…+amnxn=bm假设在LP标准形式中的m个约束方程的形式是优点：令m个特殊变量为基本变量，其余n－m个为非基本变量，从而可立即求得一个可行基本解xi=bi,i=1,2,…,mxj=0,j=m+1,…,n?如何最简便地得到典范形式?特点：在m个约束方程中有m个特殊变量，它们分别只在一个方程中出现，且系数为1☆每一个典范形式与一个可行基本解相对应☆xi=bi,i=1,2,…,mxj=0,j=m+1,…,n§2.6.2单纯形法的基本思路开始初始可行基本解x(0)z0=z(x(0))下一个可行基本解x(i)要求zi=z(x(i))≤zi－1目标函数值还能减小吗？是否得出最优解(一)迭代过程的一般描述初始顶点下一个顶点在一小撮可行基本解中寻优初始典范形式下一个典范形式目标函数值下降(二)由一个典范形式化为另一个典范形式的迭代过程x1+a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2……………………xm+am,m+1xm+1+…+amnxn=bm假设初始典范形式是xi=bi,i=1,2,…,m基本变量xj=0,j=m+1,…,n非基本变量初始可行基本解为[x1,x2,…,xm,0,…,0]T或迭代过程分为两步：（1）从原来的非基本变量中选出一个（称为进基变量）使其成为新的基本变量（2）从原来的基本变量中选出一个（称为离基变量）使其成为新的非基本变量选进基变量和离基变量的原则：使目标函数下降最快minz=c1x1+c2x2+…+cmxm+…+csxs+…+cnxnx1+a1,m+1xm+1+…+a1sxs+…+a1nxn=b1x2+a2,m+1xm+1+…+a2sxs+…+a2nxn