运筹学复习 (3).doc

MATLAB基础及在运筹学中的应用第3章 应用MATLAB解线性规划问题关于MATLAB的基础请参看：王翼、王歆明：MATLAB基础及在经济学与管理科学中的应用 第1章。这里介绍3点。1. 开始应用，矩阵、向量的输入，“；“的使用。阅读第1章的前10页2. Help的应用：Helpproduct help 然后可以搜索所需项目。3. 编辑器的应用：MATLAB打开后File/New/M-File单击M-File后即弹出编辑器窗口Editor。在编辑器中编写程序比较方便，方便修改。3.1 MATLAB函数linprog处理的线性规划问题的标准形式线性规划的数学模型有各种不同的形式，MATLAB处理的一般形式为： 目标函数都化为求最小，可以有不等式约束，也可以有等式约束，变量不一定要求非负可以给出变量的上下界。由目标函数的系数构成向量由系数组成的矩阵称为不等式约束矩阵，由系数组成的矩阵称为等式约束矩阵，列向量和为右端向量，条件给出变量取值的上下限，当为无穷大，时，退化为非负约束。引入向量 变量的上下界的约束可简写为一个满足约束条件的向量，称为可行解，所有可行解的集合称为可行区域，达到目标函数值最大的可行解称为该线性规划的最优解，相应的目标函数值称为最优目标函数值，简称最优值。引进以上向量矩阵符号，MATLAB函数linprog处理的线性规划问题的标准形式化为下面介绍如何利用MATLAB求解线性规划问题。在MATLAB中有一个专门的函数linprog来解决这类问题，线性规划问题有求最大和求最小两种，在MATLAB中以求最小为标准形式。求Z的最大值的问题需化为求-Z最小的问题。MATLAB可以处理很一般的线性规划问题，约束条件除不等式外还可以包括等式约束和上下限约束，应用MATLAB解线性规划问题，首先要将线性规划问题化成上述MATLAB能处理的标准形式。3.2应用函数linprog解线性规划问题1. 函数linprog及其调用格式MATLAB中解线性规划问题的函数是linprog。函数linprog有以下几种调用格式：(1) x=linprog(f,A,b) ：用于求解只有不等式约束的问题： 这里输入中没有变量的非负约束，函数默认这一点。应用linprog解例1-1： f=-2 -3;A=2 2;1 2;4 0;0 4;b=12;8;16;12;x=linprog(f,A,b)Optimization terminated.（最优化结束）x = 4.0000 2.0000 f=-2;-3;A=2 2;1 2;4 0;0 4;b=12;8;16;12;x=linprog(f,A,b)Optimization terminated.x = 4.0000 2.0000两次计算的差别是：上面是将f作为行向量，下面是将f作为列向量，linprog函数都接受。(2)x=linprog(f,A,b,Aeq,beq) :用于求解包含等式约束的问题：(3)x=linprog(f,A,b,Aeq,beq,lb,ub) :用于求解问题：当的某个分量没有上界时则置ub(i)=inf,当的某个分量没有下界时则置lb(i)=-inf。(4)x=linprog(f,A,b, , ,lb,ub) :用于求解不包含等式约束的问题：(5) x=linprog(f,Aeq,beq,lb,ub) :用于求解不包含不等式约束的问题:(6)x,fval=linprog(.): 用于将最优目标值返回到变量fval中。(7) x,fval,exitfalg,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub)输出中其他项的含义说明如下：输出项 exitfalg的值描述程序运行的情况，当exitfalg的值为时说明程序收敛于解，当exitfalg的值为时说明函数的计算达到了最大次数，当exitfalg的值小于时不收敛，说明的情况比较多读者可以在MATLAB的help中通过搜索linprog查看。输出项output中的iterations表示程序的迭代次数，output中的algorithm表示程序所用的算法。Cgiterations给出共轭梯度迭代的次数（仅对大规模算法）。输出项lambda为解处的Lagrange乘子,其中lower是对应于lb的，upper是对应于ub的,ineqlin是对应于不等式约束的，eqlin是对应于等式约束的。在经济问题中Lagrange乘子的含义是影子价格。（8）x,fval,exitflag,output,lambda = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)输入中x0是初始点，大规模算法和单纯形法不需要初始点。Options是选择项，应用optinset函数设置选项，其调用格式是options = optimset(param1,value1,param2,value2,.)例如对于问题c=-5 -1.5;A=0 5;6 2;1 1;b=15;24;5;指定用单纯形法求解：用options = optimset(LargeScale, off, Simplex, on)这样程序为 c=-5 -1.5;A=0 5;6 2;1 1;b=15;24;5;Aeq=;beq=;lb=0;0;ub=;x0=;options = optimset(LargeScale, off, Simplex, on);x,fval,exitflag,output,lambda=linprog(c,A,b,Aeq,beq,lb,ub,x0,options)Optimization terminated.x = 4 0fval = -20exitflag = 1output = iterations: 1 algorithm: medium scale: simplex cgiterations: message: Optimization terminated.lambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 2x1 double lower: 2x1 double如果不指定采用单纯形法，程序将执行内点算法： c=-5 -1.5;A=0 5;6 2;1 1;b=15;24;5;Aeq=;beq=;lb=0;0;ub=;x,fval,exitflag,output,lambda=linprog(c,A,b,Aeq,beq,lb,ub)Optimization terminated.x = 4.0000 0.0000fval = -20.0000exitflag = 1output = iterations: 5 algorithm: large-scale: interior point cgiterations: 0 message: Optimization terminated.lambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 2x1 double lower: 2x1 double2.应用举例【例3-1】总产值最大化问题 设某公司生产两种产品：食品和服装，生产这两种产品需要的投入品有三种：土地，劳动和资本。按照这个公司的生产技术，生产一个单位的食品需要3单位的土地，2单位劳动和1单位资本；生产一个单位的服装需要2单位的土地，2单位劳动和2单位资本。现已知公司拥有54单位土地，40单位劳动和35单位资本，还知道食品的单价为元，服装的单价为元，求一个最优生产计划使得公司的总产值最大。这个问题归结为：是公司的总产值，是这个线性规划问题的目标函数，为Subject to的缩写，表示服从于下面的约束条件（s.t.后面的不等式）。由于这个规划问题中目标函数和约束条件都是线性的，因此是一个线性规划问题。这个线性规划问题写成矩阵形式为：其中 用MATLAB函数解例3-1，写成标准形式：其中应用程序：f=-40 ；-30;A=3 2;2 2;1 2;b=54;40;35;lb=0;0;ub=; x,fval=linprog(f,A,b,lb,ub)z=fval*(-1)得到x = 14.0000 6.0000fval = -740.0000z = 740.0000应用linprog解例1-1： f=-2 -3;A=2 2;1 2;4 0;0 4;b=12;8;16;12;x,val=linprog(f,A,b), z=-valOptimization terminated.x = 4.0000 2.0000val = -14.0000z = 14.0000与图解法得到的结果相同。3.关于影子价格在微积分中约束极值问题可以用Lagrange乘子法求解，lambda.ineqlin显示不等式约束极值问题的Lagrange乘子。在线性规划中，Lagrange乘子就是对偶问题的解，并且有特殊的经济意义：影子价格。利用MATLAB函数 x,fval,exitfalg,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub)解例3-1的程序是f=-40 -30;A=3 2;2 2;1 2;b=54;40;35;lb=0;0;ub=;x,fval,exitflag,output,lambda=linprog(f,A,b,lb,ub)z=fval*(-1)运行得到Optimization terminated.x = 14.0000 6.0000fval = -740.0000exitflag = 1output = iterations: 6 algorithm: large-scale: interior point cgiterations: 0 message: Optimization terminated.lambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 2x1 double lower: 2x1 doublez= 740.0000lambda =给出影子价格，可以应用以下程序查看影子价格的值： lambda.ineqlinans = 10.0000 5.0000 0.0000结果显示土地的影子价格是10，劳动的影子价格是5，资本的影子价格为0。由前面的分析在最优解上，关于土地的约束是成立等式，关于劳动的约束也是成立等式，关于资本的约束是不等式成立。事实上 上面的结果表明第一个不等式的Lagrange乘子是10，经济意义是土地的影子价格为10，即当公司在拥有54单位土地的基础上再多拥有1单位土地时它将多获得10元的最大利润。这可以由以下程序验证：将程序中的土地54单位改为55，增加一个单位，运行程序 f=-40 -30;A=3 2;2 2;1 2;b=55;40;35;x,fval=linprog(f,A,b)Optimization terminated.x = 15.0000 5.0000fval = -750.0000z = 750.0000目标函数的最大值确实增加了10元,这就验证了关于土地的影子价格的论述。类似地，当公司在拥有40单位劳动的基础上再多拥有1单位劳动时它将多获得5元的最大利润。这可以由以下程序验证：将程序中的土地40单位改为41，增加一个单位，运行以下程序得到 f=-40 -30;A=3 2;2 2;1 2;b=54;41;35;x,fval=linprog(f,A,b)Optimization terminated.x = 13.0000 7.5000fval = -745.0000目标函数的最大值确实增加了5元,这就验证了关于劳动的影子价格的论述。当公司在拥有35单位劳动的基础上再多拥有1单位劳动时它将不会影响公司的最大利润。这可以由以下程序验证：将程序中的资本由35单位改为36，增加一个单位，运行以下程序得到 f=-40 -30;A=3 2;2 2;1 2;b=54;40;36;x,fval=linprog(f,A,b)Optimization terminated.x = 14.0000 6.0000fval = -740.0000目标函数的最大值没有改变。可以利用函数linprog验证对偶问题的解就是要素的影子价格，反之原问题的解是对偶问题的要素的影子价格，并且原问题与对偶问题的最优值相等。下面通过解例3-4和它的对偶问题进行此项验证：【例3-3】解线性规划问题：这个问题写成矩阵向量标准形式为：其中 应用文件名为Li3_3的程序： f = -5; -4; -6;A=1 -1 1;3 2 4;3 2 0;b = 20; 42; 30;lb = zeros(3,1);x,fval,exitflag,output,lambda = linprog(f,A,b,lb)Optimization terminated.x = 0.0000 15.0000 3.0000fval = -78.0000exitflag = 1output = iterations: 6 algorithm: large-scale: interior point cgiterations: 0 message: Optimization terminated.lambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 3x1 double lower: 3x1 double lambda.ineqlinans = 0.0000 1.5000 0.5000 lambda.lowerans = 1.0000 0.0000 0.0000相应的lambda.ineqlin给出不等式约束的影子价格，lambda.lower给出下界的影子价格。两个列向量中的非0元素，表示相应的最优解上，这个约束是起作用的，即解是在相应的约束的边界上。这个例子的结果表明：最优解在第2和第3个不等式的边界上，即对于最优解 在第1个变量在下界上，（）。这个例中，lambda.ineqlin的第2个分量是1.5表明第2种要素的影子价格是1.5,即当第2种要素增加1单位时，总利润（目标函数的最大值）增加1.5。在上面的程序中将第2种要素的限量由42提高到43，将验证这个事实：f = -5; -4; -6;A = 1 -1 1；3 2 4；3 2 0;b = 20; 43; 30;lb = zeros(3,1);x,fval,exitflag,output,lambda = linprog(f,A,b,lb)运行结果如下：Optimization terminated.x = 0.0000 15.0000 3.2500fval = -79.5000exitflag = 1output = iterations: 6 algorithm: large-scale: interior point cgiterations: 0 message: Optimization terminated.lambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 3x1 double lower: 3x1 double目标函数增加了1.5恰好等于影子价格的值。可以利用函数linprog验证对偶问题的解就是要素的影子价格，原问题的解也是对偶问题的要素的影子价格，并且原问题与对偶问题的最优值相等。下面通过解例3-2和它的对偶问题进行此项验证：【例3-2】利润最大化问题 设企业生产甲乙两种产品，生产时需要A、B两种要素投入，已知制造甲产品每件需A要素3个单位，需B要素2个单位，甲产品每件可获利2元。制造乙产品每件需A要素6个单位，需B要素1个单位，乙产品每件可获利3元。现企业有A要素24个单位，B要素10 个单位。试安排最优生产计划，使企业所获利润最大。解：设计划生产甲产品单位，乙产品单位，用表示企业所获的利润，则目标函数为。问题是在约束条件：下，求，使利润最大。 写成矩阵形式为：其中 这个问题称为原问题。解例3-2（原问题）的程序为：f=-2;-3;b=24;10;A=3 6;2 1;lb=0;0;ub=;x,fval,exitfalg,output,lambda=linprog(f,A,b,lb,ub)运行这个程序得到原问题的解：x = 4.0000 2.0000fval = -14.0000exit