2013数学建模周末培训-matlab课件第7讲约束优化

数学实验约束优化问题实验目的实验内容2、用Matlab求解线性规划问题.1、了解约束优化问题.1、生产计划、投资策略2、线性规划的基本原理和解法3、用Matlab求解线性规划问题

§1两个实例

（一）生产规划问题

（二）投资策略问题实例一生产规划问题某厂生产甲乙两种口味的饮料，每百箱甲饮料需用原料6千克，工人10名，可获利10万元，每百箱乙饮料需用原料5千克，工人20名，可获利9万元，今工厂共有原料60千克，工人150名，又由于其他条件所限甲饮料产量不能超过8百箱，问如何安排生产计划，即两种饮料各生产多少使获利最大？数学模型设决策变量为甲乙两种饮料的产量，分别为x1,x2（以百箱为单位，但可以为小数），目标函数是总获利，约束条件是原料，工人及对甲饮料产量的限制，则有：实例二投资策略问题某部门现有资金10万元，五年内有以下投资项目供选择：项目A从第一年到第四年每年初投资，次年末收回本金且获利15%；项目B第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；项目C第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；项目D每年初投资，年末收回本金且获利6%。问如何确定投资策略使第五年末本息总额最大？目标函数是第五年末的本息总额，决策变量是每年初各个项目的投资额，约束条件是每年初拥有的资金，用xij表示第i年初（i=1,2,…,5）项目j（j=1,2,3,4分别代表A,B,C,D）的投资额，根据所给条件只有下表中的xij才是需要求解的。表投资方案选择中的决策变量

年份

项目ABCD1X11X142X21X23X243X31X32X344X41X445X54因为项目D每年初可以投资，且年末能收回本息，所以每年初都应把字金全部投出去，由此可得如下的约束条件：第1年初：10万元全部投向A,D，有

第2年初：拥有的资金为项目D第1年投资x14收回的本息，全部投向A,C,D，有：第3年初：拥有的资金为项目A第1年投资x11和D第2年投资x24收回的本息，全部投向A,B,D，有：第4年初：类似地有：第5年初：此外，项目B,C对投资额有限制，即第五年末的本息总额为

数学模型§2线性规划的基本原理和解法实际问题一般都是有约束的，即使是最小二乘拟合，对拟合的系数也常常有所要求（如大于零）。反之，有些有约束的问题作为无约束优化求解时优化模型的一般形式：（1）

（2）

（2）式所界定的x的取值范围是模型的可行域，满足（2）的解是可行解，满足（1）的可行解才是约束优化的最优解。一般问题都是有约束的，即使是最小二乘拟合，对拟合的系数也常常有所要求（如大于零），当然，有些有约束的问题作为无约束优化求解时，得到的最优解也许会满足约束条件，多半是这个解在可行域的内部，那么它当然也是约束问题的最优解。但也有最优解在可行域的边界上取得的情况，此时不能用无约束优化的方法求解，必须研究最优解位于可行域边界上时的性质，进而寻求解法，当变量数目n和约束数目m较大时，通常使用的是数值解法。线性规划的一般模型为：其中，均为已知。2.1线性规划的图解法

由于A、B、C三种元素都是原料市场上十分紧缺的货品,工厂每月所能得到的这些元素的供应量分别为200kg、200kg和360kg.工厂生产每吨甲种合金的利润为30万元，生产每吨乙种合金的利润为40万元.

例1某合金工厂生产甲、乙两种合金，生产每A元素20kg、B元素40kg和C元素90kg，吨甲种合金需用而生产每吨乙种合金需用A元素100kg、B元素80kg和C元素60kg.

试问：该工厂应如何安排生产，才能获得最大利润？数学模型

设每月生产甲种合金x1

吨，乙种合金x2

吨，利润为u万元,那么

u=30x1+40x2

要求何时有

maxu=max(30x1+40x2)

x1,x2满足约束条件线性规划问题求最优解

二元一次方程a1x1+a2x2=b代表x1x2平面上的一条直线，而二元一次不等式a1x1+a2x2

b则代表了以此直线为界的半平面图解法a1x1+a2x2=ba1x1+a2x2

b

这问题中约束条件意味着五个半平面的交集.它是一个包含边界的凸多边形OPQRS线性规划的容许集x2

pQ

R0Sx1x2

pQ

R

0Sx1

30x1+40x2=u

将u视作参数，则30x1+40x2=u代表一条直线，随着u的增或减，直线向右上或左下方平移.若直线经过容许集的某顶点时再增减将使直线离开容许集，则此临界状态直线所对应的u的就是所求的最大值，所过顶点的坐标就是问题的最优解从图看出最优解应为R点

最优解在R点，由R是直线40x1+80x2=200与直线90x1+60x2=360的交点,可得最优解为x1=3.5,x2=0.75,此时有最大值为u=135.说明安排月生产甲、乙种合金分别为3.5吨、0.75吨t，才能获得最大利润135万元问题的解答例2求解解：前3个约束条件的不等号改成等号，是如下的3条直线：（书中210页）

可以看出，由于线性规划的约束条件和目标函数均为线性函数，所以对2维情形，可行域为直线组成的凸多边形，目标函数的等值线为直线，这样，最优解一定在凸多边形的某个顶点取得。从2维例子的几何意义可以看出，还会有下列情形：（1）若可行域为空集（如第3个约束条件改为：-3x1+2x2≥14），则无最优解（对于实际问题往往是模型或输入数据有误所致）（2）若可行域无界（如将第3个约束条件去掉），则可能无最优解（对于实际问题可能是漏掉了某些约束条件所致），不过对于此例，若z取极小，则仍有最优解。（3）最优解在凸多边形的一条边上取得（如第3个约束条件改为3x1+x2≤14，L3将与目标函数等值线平行），则有无穷多个最优解。将2维推广到n维，可以想到，线性规划的可行域是超平面组成的凸多边形，等值线是超平面，最优解在凸多面体的某个顶点取得，由此我们得到求解线性规划的基本思路为：从可行域的某一个顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。图解法的局限画图并不方便，可以不画图而求出容许集所有的顶点，再将目标函数在这些顶点上的值加以比较来求出最优解.但在约束条件多或多变量时，也是难以做到的。2.2线性规划的标准形和基本性质2.2.1标准形（1）目标函数一律化为求极小（如果求极大，则利用maxz＜=＞min(-z)）.（2）对约束条件中Ax≤b的不等式，利用加入松弛变量的方法化为等式，如对于上例，可增加变量x3,x4,x5，将3个不等式的约束化为：如果原来约束条件中Ax≥b的不等式，可以利用加负号变为-Ax≤-b。线性规划的标准形式为：

式中x≥0的约束一般实际问题都存在，如果数学上某个xj无此约束，可令如果原来约束为

可令

2.2.2基（本）解与基可行解线性方程组Ax=b的基本（解）可以如下求得：任取m个独立的列向量组成基AB（AB可逆），其余列向量为非基AN，将A的列向量重排次序后可写作A=（ABAN），相应地重排x的分量有x=（xB，xN）T，xB，xN分别称为基变量和非基变量，于是

Ax=ABxB+ANxN=b一般地，当基变量xB≥0时（令非基变量xN=0），Ax=b的基解x=(xB,xN)T也满足约束x≥0,称为基可行解。

2.2.3线性规划的基本性质（1）若存在可行域，它必须是凸集（凸多面体）；（2）基可行解对应于可行域的顶点；（3）若有最优解，必在可行域的顶点取得；由此可知，求最优解只需在基可行解（可行域顶点）中寻找。

3用Matlab优化工具箱解线性规划用Matlab优化工具箱解线性规划时，必须首先化为如下形式：有如下程序：x=lp(c,A,b);x=lp(c,A,b,v1);x=lp(c,A,b,v1,v2);x=lp(c,A,b,v1,v2,x0);x=lp(c,A,b,v1,v2,x0,ne);x=lp(c,A,b,v1,v2,x0,ne,dis);[x,lag]=lp(c,A,b,…)[x,lag,how]=lp(c,A,b,…)参数说明：c,A,b为规划的系数向量，系数矩阵，常数项向量。输出x为最优解；v1，v2为x的下界和上界，即有约束v1≤x≤v2(v1或v2的维数k可以小于x的维数n，此时v1或v2仅表示x前k个分量的下界或上界)；x0为初始解（缺省时程序自动取x0=0）；ne为等式约束的个数，且须将等式约束置于不等式约束前面；dis给出警告信息，如解无界或不可行，当中间某个输入参数缺省时，需用[]占据其位置。输出参数lag为拉格朗日乘子，维数等于约束条件的个数，其非零分量对应于起作用的约束条件；how给出错误信息：无可行解(infeasible)；无有界解（unbounded）或问题顺利解决(ok)。例1：

C=-[3,1];%加负号将求极大化为求极小A=[-1,1;1,-2;3,2];B=[2,2,14];v1=[0,0];x=lp(c,a,b,v1)z=-c*x;得到最优解x=（4，1），最大值z=13；如用[x,lag]=lp(c,a,b,v1)，可得lag=(0,0.3750,0.8750,0,0)，lag的第2，3分量非零，表示第2，3个约