Matlab最优化计算方法

线性规划最优化方法专题无约束规划非线性规划课程目的课程内容2、掌握用数学软件包求解线性规划问题。1、了解线性规划的基本内容。3、实验作业。2、用数学软件包求解线性规划问题。1、两个引例。问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？单位工件所需加工台时数单位工件的加工费用车床类型工件1工件2工件3工件1工件2工件3可用台时数甲0.41.11.013910800乙0.51.21.311128900两个引例解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：6543218121110913minxxxxxxz6,,2,1,09003.12.15.08001.14.0500600400x..654321635241ixxxxxxxxxxxxtsi解答问题二：某厂生产甲、乙两种产品，已知制成一吨产品甲需用资源A3吨资源B4m3；制成一吨产品乙需用资源A2吨，资源B6m3，资源C7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源的限制量分别为90吨、200m3和210个单位。试应生产这两种产品各多少吨才能使创造的总经济价值最高？解：这是个最优化问题，其目标为经济价值最高，约束条件为三种资源的数量有限，决策为生产甲、乙产品的数量。令生产产品甲的数量为x1，生产产品乙的数量为x2。由题意可以建立如下的线性规划模型。故目标函数为：2157maxxxz约束条件为：0,021072006490232122121xxxxxxx问题2线性规划模型：解答返回2157maxxxz0,02107200649023..2122121xxxxxxxts设置决策变量，它们体现解决问题的方案。小结1：建模的基本步骤•确定目标函数，它是决策变量的函数。•确定决策变量的取值范围，给出优化方向。•确定约束条件，它们是含有决策变量的不等式或等式。小结2：数学模型的共同结构1.存在一组决策变量，称为决策变量，对它们可有非负要求；2.存在一个以决策变量为自变量的目标函数，且它为线性函数；3.存在一组约束条件，且每个条件都是由决策变量构成的线性不等式或等式；4.结构要求出这样的变量组，或者说决策向量X，在满足约束条件和非负约束的同时，使相应的目标函数值达到最大或者最小。简言之，在一定条件下使目标函数优化。具有上述结构的数学模型为线性规划模型线性规划数学模型三要素：决策变量、目标函数、约束条件0,012453402..250300maxBAABABABAxxxxxxxtsxxzBxAx1020304010203040402BAxx453BAxx12AxBAxxz2503006350,11,12zxxBA例,通过图解法求下列线性规划问题的最优解。maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2例通过图解法求下列线性规划问题的最优解。2122maxxxZ0,02224..21212121xxxxxxxxts-x1+2x2=2x1-x2=2x1+x2=401234x1x2G4321FEHABCDI多重最优解例通过图解法求下列线性规划问题的最优解。12max2Zxx0,0302..21121xxxxxtsx1+2x2=4x1+2x2=601234x1x1=3X2321-x1+2x2=0无界解例通过图解法求下列线性规划问题的最优解。12max2Zxx0,0302..21121xxxxxts01234x1x1=3X2321-x1+2x2=0无界解例通过图解法求下列线性规划问题的最优。212maxxxZx1+x2=101234x1X2321-x1+2x2=40,0142..212121xxxxxxts无可行解例通过图解法求下列线性规划问题的最优。总结：线性规划问题解的状况唯一最优解无穷多最优解无界解无可行解我们通常把无界解或无可行解统称为无最优解c1x10c2x20Ct=……..….0=……cnxn0并且r(A)=mn.线性规划标准型的矩阵形式：MaxZ=CXs.t.AX=bX,b≥0a11a12….a1nb1A=a21a22….a2nb=b2……………………………………am1am2….amnbmX=关于标准型解的若干基本概念假若标准型有n个变量，m个约束行且m=n“基”的概念在标准型中，系数矩阵有n列，即A=(P1,P2,…,Pn)A中线性独立的m列，构成该标准型的一个基，即基矩阵B=(P1,P2,…,Pm)，|B|0P1,P2,…,Pm称为基向量与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称非基变量，记为XN=(xm+1,xm+2,…,xn)T，故有X=(XB,XN)T基解、基可行解●线性规划的基矩阵、基变量、非基变量=目标函数约束条件行列式≠0基矩阵右边常数例:012233..23max32143214321xxxxxxxtsxxxxz000032020001010x1x2x4x3001300321=目标函数约束条件行列式≠0基矩阵X1,x2,x3为基变量,x4为非基变量可行解满足约束条件和非负条件的解X称为可行解.n基解(基本解)n令非基变量XN=0，求得基变量XB的值称为基本解即XB=B1bAX=b令A=(B,N),X=(XB,XN)TBXB+NXN=b令XN=0得XB=B1b因此基解为X=（B1b，0）T基本可行解符合非负性要求的基解，称为基本可行解，否则为基本非可行解基本可行解的非零分量个数m时（基本可行解中存在取零值的基变量），称为退化基本可行解maxz=2x1+3x2+x3s.t.x1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30例:写出下列线性规划问题的基解，并判断是否为基可行解。x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个顶点。目标函数值为：z=20x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x5，非基变量x3、x4、x6但不是基可行解，不是一个顶点。基解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）x1+3x2=152x1+3x2=18x1-x2+x6=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个顶点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3约束方程的解空间基解可行解非可行解基可行解退化解1.3.2线性规划标准型问题解的关系1、线性规划的标准型有特点（）。A、右端项非零；B、目标求最大；C、有等式或不等式约束；D、变量均非负。2下面命题不正确的是（）。A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解；C、线性规划一定有可行解；D、线性规划的最优值至多有一个。3若某线性规划问题中，变量个数为n，基变量个数为m（mn），则该问题基本可行解的最大数目为（）①②③④nmmCnmnCnmCmnC4若线性规划问题的最优解同时在可行域的两个顶点上达到，则最优解有()①无穷多个②过这两点的整条直线③不可能发生④两个5当线性规划问题的可行集非空时一定（）A包含原点X=(0,0,…,0)B有界C无界D是凸集2.1单纯形算法基本思想：从可行域的一个基本可行解(顶点)出发，判别它是否已是最优解，如果不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无界为止。2.1单纯形思想举例maxZ=1500x1+2500x2s.t.3x1+2x2652x1+x2403x275x1,x20化成标准形：maxZ=1500x1+2500x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x20321002101003001A=（P1，P2，P3，P4，P5）例P3，P4，P5线性无关，x3,x4,x5是基变量，x1,x2是非基变量。100010001B=（P3，P4，P5）用非基变量表示的方程：Z=1500x1+2500x2x3=65-3x1-2x2x4=40-2x1-x2(I)x5=75-3x2令非基变量（x1,x2）t=（0，0）t得初始基可行解：x(1)=(0,0,65,40,75)tZ=0经济含义：不生产产品甲和乙，利润为零。（x3，x4，x5）分析：Z=1500x1+2500x2分别增加单位产品甲、乙，目标函数分别增加1500、2500，即利润分别增加1500元、2500元。同时由目标函数可以看出增加单位产品乙（x2）比甲（x1）对目标函数的贡献大（最大检验数原则），把非基变量x2换成基变量，称x2为进基变量。同时为保证基变量的个数必须确定一个出基变量。（在选择出基变量时，只考虑aij是正的方程）（最小比值原则）用非基变量表示的方程：x3=65-2x2≥0x4=40-x2≥0(II)x2＝minx5=75-3x2≥0当x2＝25时，x5＝0，即x5由原来的基变量变为现在的非基变量。65/2,40/175/3确定了进基变量x2，出基变量x5以后，用非基变量表示基变量得到新的方程组：Z=62500+1500x1-(2500/3)x5x3=15-3x1+（2/3）x5x4=15-2x1+（1/3）x5(II)x2=25-（-1/3）x5令新的非基变量（x1，x5）=（0，0）t得到新的基本可行解：x(2)=(0,25,15,15,0)tZ=62500经济含义：生产乙产品25个，获得利润62500元。这个方案比前方案好，但是否是最优？分析：Z=62500+1500x1-(2500/3)x5非基变量x1系数仍为正数，确定x1为进基变量。在保证所有的变量非负的情况下，确定x3为出基变量。得到新的基本可行解：x(3)=(5,25,0,5,0)tZ=70000-500x3-500x5由Z的表达式可以看出，该解已是最优解。经济含义：生产甲产品生产5个乙产品25个，获得利润70000元。c1x10c2x20Ct=……..….0=……cnxn0并且r(A)=mn.2.2单纯形法的基本原理MaxZ=CXs.t.AX=bX≥0a11a12….a1nb1A=a21a22….a2nb=b2……………………………………am1am2….amnbmX==maxz=CXAX=