目录前言一、MATLAB实现二、1三、LINDO在线性规划中的应用四、优化模型与LINGO五、课外习题
目 录 一、 前言 二、 MATLAB 实现 三、LINDO 在线性规划中的应用 四、优化模型与 LINGO 五、课外习题
一． 前言运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。通过实际问题加强学生建立运筹学模型能力的训练，培养学生运用运筹学分析问题及解决实际管理问题的能力，组织学生熟练掌握LinDo、LinGo、Matlab、等运筹学计算软件，并能对所得的结果进行分析及决策。实际问题中的优化模型：Min/Maxz-f(x), x-(x1,..,X.)s.g ;(x)≤0,i=1,2.,mXi,Xn≥0其中x~决策变量，Jx)~目标函数，gi(x）≤0~约束条件数学规划分类：线性规划(LP)二次规划(QP)非线性规划(NLP)连续规划整数规划(IP)：0-1整数规划、一般整数规划、纯整数规划(PIP)、混合整数规划(MIIP)二、MATLAB实现2.1线性规划问题线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB解决的线性规划问题的标准形式为：min f'xXeR"sub.to:A-x<bAeq·x=beqlb≤x≤ub其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵。其它形式的线性规划问题都可经过适当变换化为此标准形式
一． 前言 运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带 有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提 供理论和方法。通过实际问题加强学生建立运筹学模型能力的训练，培养学生运用运筹学 分析问题及解决实际管理问题的能力，组织学生熟练掌握 LinDo、LinGo、Matlab、等运筹 学计算软件，并能对所得的结果进行分析及决策。 实际问题中的优化模型： Min/Max z=f(x), x=(x1,.,xn) T s.t. g i(x)≤0,i=1,2,.,m x1,.,xn≥0 其中 x~决策变量， f(x)~目标函数， gi(x) ≤0~约束条件 数学规划分类： 线性规划(LP) 二次规划(QP) 非线性规划(NLP) 连续规划 整数规划(IP)：0-1 整数规划、一般整数规划、 纯整数规划(PIP)、混合整数规划(MIP) 二、MATLAB 实现 2.1 线性规划问题 线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB 解决的线性规划 问题的标准形式为： min n f′ x x ∈R sub.to： A ⋅ x ≤ b Aeq ⋅ x = beq lb ≤ x ≤ ub 其中 f、x、b、beq、lb、ub 为向量，A、Aeq 为矩阵。 其它形式的线性规划问题都可经过适当变换化为此标准形式
函数linprog格式x=linprog(f,A,b)%求minf*xsub.toA·x≤b线性规划的最优解。x=linprog(f,A,b,Aeq,beq）%等式约束Aeq·x=beq，若没有不等式约束A·x≤b,则A-[],b=[]。x=linprog(f,A,b,Aeq,beq,lb,ub）%指定x的范围lb≤x≤ub，若没有等式约束Aeq·x=beq，则Aeq=[],beq=[]x=linprog(f,A,b,Aeq,beq,lb,ub,x0)%设置初值xo%options为指定的优化参数x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(）%返回目标函数最优值，即fval=f*x。[xlambda,exitflag]=linprog()%lambda为解x的Lagrange乘子。[x，lambda,fval,exitflag]=linprog(）%exitflag为终止选代的错误条件。[x,fval,lambda,exitlag,output]=linprog(）%output为关于优化的一些信息说明若exitflag>0表示函数收敛于解x，exitflag=0表示超过函数估值或迭代的最大数字，exitflag>f= [-5; -4; -6];>>A= [1-1 1;324;3 2 0];>>b =[20; 42; 30];>>Ib = zeros(3,1);
函数 linprog 格式 x = linprog(f,A,b) %求 min f ' *x sub.to A ⋅ x ≤ b 线性规划的最优解。 x = linprog(f,A,b,Aeq,beq) %等式约束 Aeq ⋅ x = beq ，若没有不等式约束 A ⋅ x ≤ b ，则 A=[ ]，b=[ ]。 x = linprog(f,A,b,Aeq,beq,lb,ub) %指定 x 的范围lb ≤ x ≤ ub ，若没有等式约束 Aeq ⋅ x = beq ，则 Aeq=[ ]，beq=[ ] x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值 x0 x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) % options 为指定的优化参数 [x,fval] = linprog(.) % 返回目标函数最优值，即 fval= f ' *x。 [x,lambda,exitflag] = linprog(.) % lambda 为解 x 的 Lagrange 乘子。 [x, lambda,fval,exitflag] = linprog(.) % exitflag 为终止迭代的错误条件。 [x,fval, lambda,exitflag,output] = linprog(.) % output 为关于优化的一些信息 说明 若 exitflag>0 表示函数收敛于解 x，exitflag=0 表示超过函数估值或迭代的最大数 字，exitflag>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,,[l,Ib)结果为：X=%最优解0.000015.00003.0000fval =%最优值-78.0000%收敛exitflag=1output =%选代次数iterations: 6cgiterations: 0%所使用规则algorithm:'lipsol'lambda =ineqlin: [3x1 double]eqlin: [Ox1 double]upper: [3x1 double]lower: [3x1 double]>> lambda.ineqlinans =0.00001.50000.5000>>lambda.lowerans =1.00000.00000.0000表明：不等约束条件2和3以及第1个下界是有效的
>>[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb) 结果为： x = %最优解 0.0000 15.0000 3.0000 fval = %最优值 -78.0000 exitflag = %收敛 1 output = iterations: 6 %迭代次数 cgiterations: 0 algorithm: 'lipsol' %所使用规则 lambda = ineqlin: [3x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double] >> lambda.ineqlin ans = 0.0000 1.5000 0.5000 >> lambda.lower ans = 1.0000 0.0000 0.0000 表明：不等约束条件 2 和 3 以及第 1 个下界是有效的
2.2非线性规划问题2.2.1有约束的一元函数的最小值单变量函数求最小值的标准形式为minf(x)sub.toXi0，表示函数收敛于x，若exitflag=0，表示超过函数估计值或迭代的最大数字，exitflag>[x,fval,exitflag,output)=fiminbnd((x^3+cos(x)+x*log(x)/exp(x),0,1)x=0.5223fval =0.3974exitflag=1output =iterations: 9funcCount:9algorithm:'golden section search,parabolic interpolation
2.2 非线性规划问题 2.2.1 有约束的一元函数的最小值 单变量函数求最小值的标准形式为 min f(x) x sub.to x1 0，表示函数收敛于 x，若 exitflag=0，表示超过函数估计值或迭 代的最大数字，exitflag> [x,fval,exitflag,output]=fminbnd('(x^3+cos(x)+x*log(x))/exp(x)',0,1) x = 0.5223 fval = 0.3974 exitflag = 1 output = iterations: 9 funcCount: 9 algorithm: 'golden section search, parabolic interpolation
例2.3在[0，5]上求下面函数的最小值f(x)=(x-3)3-1解：先自定义函数：在MATLAB编辑器中建立M文件为：function f= myfun(x)f= (x-3).^2 - 1;保存为myfun.m，然后在命令窗口键入命令：>> x=fminbnd(@myfun,0,5)则结果显示为：X=32.2.2无约束多元函数最小值多元函数最小值的标准形式为minf(x)其中：x为向量，如x=[x,X2,",x]在MATLAB5.x中使用fimins求其最小值。命令利用函数fiminsearch求无约束多元函数最小值函数fminsearch格式x=fiminsearch(fun,xO)%xo为初始点，fun为目标函数的表达式字符串或MATLAB自定义函数的函数柄。%options查optimsetx=fminsearch(fun,x0,options)[x,fval]=fiminsearch(）%最优点的函数值[x,fval,exitflag]=fiminsearch(）%exitflag与单变量情形一致[x,fval,exitflag,output]=fiminsearch(）%output与单变量情形一致注意：fiminsearch采用了Nelder-Mead型简单搜寻法。例2.4求y=2x+4xx-10xX2+x的最小值点解：>>X=fminsearch(2*x(1)^3+4*x(1)*x(2)^3-10*x(1)*x(2)+x(2)^2′,[0,0)结果为X=
例 2.3 在[0，5]上求下面函数的最小值f(x) (x 3) 1 3 = − − 解：先自定义函数：在 MATLAB 编辑器中建立 M 文件为： function f = myfun(x) f = (x-3).^2 - 1; 保存为 myfun.m，然后在命令窗口键入命令： >> x=fminbnd(@myfun,0,5) 则结果显示为： x = 3 2.2.2 无约束多元函数最小值 多元函数最小值的标准形式为 min f(x) x 其中：x 为向量，如 x = [x1, x2,L, xn] 在 MATLAB5.x 中使用 fmins 求其最小值。 命令 利用函数 fminsearch 求无约束多元函数最小值 函数 fminsearch 格式 x = fminsearch(fun,x0) %x0 为初始点，fun 为目标函数的表达式字符串或 MATLAB 自定义函数的函数柄。 x = fminsearch(fun,x0,options) % options 查 optimset [x,fval] = fminsearch(.) %最优点的函数值 [x,fval,exitflag] = fminsearch(.) % exitflag 与单变量情形一致 [x,fval,exitflag,output] = fminsearch(.) %output 与单变量情形一致 注意：fminsearch 采用了 Nelder-Mead 型简单搜寻法。 例 2.4 求 2 1 2 2 3 1 2 3 y = 2x1 + 4x x −10x x + x 的最小值点 解：>>X=fminsearch('2*x(1)^3+4*x(1)*x(2)^3-10*x(1)*x(2)+x(2)^2', [0,0]) 结果为 X =
1.00160.8335或在MATLAB编辑器中建立函数文件function f-myfun(x)f=2*x(1)^3+4*x(1)*x(2)^3-10*x(1)*x(2)+x(2)^2保存为myfun.m，在命令窗口键入>>X=fiminsearch (myfun',[0,0])或>>X=fiminsearch(@myfun,[0,0])结果为：X=1.00160.8335命令利用函数fiminunc求多变量无约束函数最小值函数fminunc格式x=fminunc(fun,x0)%返回给定初始点x0的最小函数值点x=fminunc(fun,x0,options）%options为指定优化参数[x,fval]=fiminunc(）%fval最优点x处的函数值[x,fval,exitflag]=fiminunc(）%exitlag为终止选代的条件，与上同。[x,fval,exitflag,output]=fiminunc(）%output为输出优化信息[x,fval,exitflag,output,grad]=fiminunc(%grad为函数在解x处的梯度值[x,fval,exitlag,output,grad,hessian]=fiminunc(）%目标函数在解x处的海赛（Hessian）值注意：当函数的阶数大于2时，使用fminunc比fminsearch更有效，但当所选函数高度不连续时，使用fiminsearch效果较好。例2.5求f(x)=3x+2xix2+x2的最小值。>> fun=3*x(1)/2+2*x(1)*x(2)+x(2)^2;>> x0=[1 1];>>[x,fval,exitflag,output,grad,hessian]-fminunc(fun,x0)结果为：x=1.0e-008 *-0.75910.2665
1.0016 0.8335 或在 MATLAB 编辑器中建立函数文件 function f=myfun(x) f=2*x(1)^3+4*x(1)*x(2)^3-10*x(1)*x(2)+x(2)^2; 保存为 myfun.m，在命令窗口键入 >> X=fminsearch ('myfun', [0,0]) 或 >> X=fminsearch(@myfun, [0,0]) 结果为： X = 1.0016 0.8335 命令 利用函数 fminunc 求多变量无约束函数最小值 函数 fminunc 格式 x = fminunc(fun,x0) %返回给定初始点 x0 的最小函数值点 x = fminunc(fun,x0,options) % options 为指定优化参数 [x,fval] = fminunc(.) %fval 最优点 x 处的函数值 [x,fval,exitflag] = fminunc(.) % exitflag 为终止迭代的条件，与上同。 [x,fval,exitflag,output] = fminunc(.) %output 为输出优化信息 [x,fval,exitflag,output,grad] = fminunc(.) % grad 为函数在解 x 处的梯度值 [x,fval,exitflag,output,grad,hessian] = fminunc(.) %目标函数在解 x 处的海赛 （Hessian）值 注意：当函数的阶数大于 2 时，使用 fminunc 比 fminsearch 更有效，但当所选函数高度 不连续时，使用 fminsearch 效果较好。 例 2.5 求 2 1 2 2 2 f(x) = 3x1 + 2x x + x 的最小值。 >> fun='3*x(1)^2+2*x(1)*x(2)+x(2)^2'; >> x0=[1 1]; >> [x,fval,exitflag,output,grad,hessian]=fminunc(fun,x0) 结果为： x = 1.0e-008 * -0.7591 0.2665
fval =1.3953e-016exitflag =1output =iterations: 3funcCount: 16stepsize: 1.2353firstorderopt:1.6772e-007algorithm:'medium-scale:Quasi-Newton line search'grad =1.0e-006 *-0.16770.0114hessian =6.00002.00002.00002.0000或用下面方法：>> fun=inline(3*x(1)^2+2*x(1)*x(2)+x(2)2)fun =Inline function:fun(x) = 3*x(1)2+2*x(1)*x(2)+x(2)2>>x0=[1 1];>>x=fminunc(fun,x0)x=1.0e-008 *-0.75910.2665
fval = 1.3953e-016 exitflag = 1 output = iterations: 3 funcCount: 16 stepsize: 1.2353 firstorderopt: 1.6772e-007 algorithm: 'medium-scale: Quasi-Newton line search' grad = 1.0e-006 * -0.1677 0.0114 hessian = 6.0000 2.0000 2.0000 2.0000 或用下面方法： >> fun=inline('3*x(1)^2+2*x(1)*x(2)+x(2)^2') fun = Inline function: fun(x) = 3*x(1)^2+2*x(1)*x(2)+x(2)^2 >> x0=[1 1]； >> x=fminunc(fun,x0) x = 1.0e-008 * -0.7591 0.2665
2.2.3有约束的多元函数最小值非线性有约束的多元函数的标准形式为：minf(x)4sub.toC(x)≤0Ceq(x)=0A.x≤bAeq·x=beqlb≤x≤ub其中：X、b、beq、Ib、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是返回向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。在MATLAB5.x中，它的求解由函数constr实现。函数fmincon格式x=fmincon(fun,x0,A,b)x =fimincon(fun,x0,A,b,Aeq,beq)x = fimincon(fun,x0,A,b,Aeq,beq,Ib,ub)x=fmincon(fun,xo,A,b,Aeq,beq,lb,ub,nonlcon)x=fmincon(fun,xo,A,b,Aeq,beq,b,ub,nonlcon,options)[x,fval] = fmincon()[x,fval,exitflag] = fmincon(--- [x,fval,exilag,output] = fimincon(-..)[x,fval,exitflag,output,lambda] = fimincon(.)[x,fval,exitlag,output,lambda,grad] = fmincon(---)[x,fval,exitlag,output,lambda,grad,hessian] =fmincon(.)参数说明：fiun为目标函数，它可用前面的方法定义；xO为初始值；A、b满足线性不等式约束A·x≤b，若没有不等式约束，则取A=[]，b=[];Aeq、beq满足等式约束Aeq·x=beq，若没有，则取Aeq=[]，beq=[];1b、ub满足1b≤x≤ub，若没有界，可设Ib=[]，ub=[];nonlcon的作用是通过接受的向量x来计算非线性不等约束C(x)≤0和等式
2.2.3 有约束的多元函数最小值 非线性有约束的多元函数的标准形式为： min f(x) x sub.to C(x) ≤ 0 Ceq (x) = 0 A ⋅ x ≤ b Aeq ⋅ x = beq lb ≤ x ≤ ub 其中：x、b、beq、lb、ub 是向量，A、Aeq 为矩阵，C(x)、Ceq(x)是返回向量的函数， f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。 在 MATLAB5.x 中，它的求解由函数 constr 实现。 函数 fmincon 格式 x = fmincon(fun,x0,A,b) x = fmincon(fun,x0,A,b,Aeq,beq) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) [x,fval] = fmincon(.) [x,fval,exitflag] = fmincon(.) [x,fval,exitflag,output] = fmincon(.) [x,fval,exitflag,output,lambda] = fmincon(.) [x,fval,exitflag,output,lambda,grad] = fmincon(.) [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(.) 参数说明：fun 为目标函数，它可用前面的方法定义； x0 为初始值； A、b 满足线性不等式约束 A ⋅ x ≤ b ，若没有不等式约束，则取 A=[ ]，b=[ ]； Aeq、beq 满足等式约束 Aeq ⋅ x = beq ，若没有，则取 Aeq=[ ]，beq=[ ]； lb、ub 满足lb ≤ x ≤ ub ，若没有界，可设 lb=[ ]，ub=[ ]； nonlcon 的作用是通过接受的向量 x 来计算非线性不等约束C(x) ≤ 0和等式
约束Ceq(x)=0分别在x处的估计C和Ceq,通过指定函数柄来使用，如：>>x=fmincon(@myfun,xo,A,b,Aeq,beq,lb,ub,@mycon)，先建立非线性约束函数，并保存为mycon.m：function[C,Ceq]=mycon(x)C=...%计算x处的非线性不等约束C(x)≤0的函数值。Ceq=*%计算x处的非线性等式约束Ceq(x)=0的函数值。lambda是Lagrange乘子，它体现哪一个约束有效。output输出优化信息；grad表示目标函数在x处的梯度；hessian表示目标函数在x处的Hessiab值。例2.6求下面问题在初始点（0，1）处的最优解minx +x2-XjX2-2x1-5x2sub.to-(j-1)+x2≥02xl-3x2+6≥0解：约束条件的标准形式为sub.to(xi-1)2-x2≤0-2xI +3x2≤6先在MATLAB编辑器中建立非线性约束函数文件：function[c, ceq]-mycon (x)c=(x(1)-1)2-x(2);ceq-[];%无等式约束然后，在命令窗口键入如下命令或建立M文件：%目标函数>>fun=x(1)>2+x(2)/2-x(1)*x(2)-2*x(1)-5*x(2):>>x0=[0 1];>>A=[-2 3];%线性不等式约束>>b=6;>>Aeq=[];%无线性等式约束>>beq=[];>>Ib=[];%x没有下、上界
约束Ceq (x) = 0 分别在x处的估计C和Ceq，通过指定函数柄来使用， 如：>>x = fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon)，先建立非 线性约束函数，并保存为 mycon.m：function [C,Ceq] = mycon(x) C = . % 计算 x 处的非线性不等约束C(x) ≤ 0的函数值。 Ceq = . % 计算 x 处的非线性等式约束Ceq (x) = 0 的函数值。 lambda 是 Lagrange 乘子，它体现哪一个约束有效。 output 输出优化信息； grad 表示目标函数在 x 处的梯度； hessian 表示目标函数在 x 处的 Hessiab 值。 例 2.6 求下面问题在初始点（0，1）处的最优解 min 1 2 1 2 2 2 2 x1 + x − x x − 2x − 5x sub.to (x 1) x2 0 2 − 1 − + ≥ 2x1 − 3x2 + 6 ≥ 0 解：约束条件的标准形式为 sub.to (x 1) x2 0 2 1 − − ≤ − 2 x1 + 3x2 ≤ 6 先在 MATLAB 编辑器中建立非线性约束函数文件： function [c, ceq]=mycon (x) c=(x(1)-1)^2-x(2); ceq=[ ]; %无等式约束 然后，在命令窗口键入如下命令或建立 M 文件： >>fun='x(1)^2+x(2)^2-x(1)*x(2)-2*x(1)-5*x(2)'; %目标函数 >>x0=[0 1]; >>A=[-2 3]; %线性不等式约束 >>b=6; >>Aeq=[ ]; %无线性等式约束 >>beq=[ ]; >>lb=[ ]; %x 没有下、上界