实验九-供应与选址问题

数学实验数学系309宿舍实验九供应与选址问题实验九供应与选址问题【实验目的】1．了解非线性规划问题的基本概念和求解方法。2．通过对应用问题的分析、建模、求解，加深对非线性规划理论的理解。3．学习掌握MATLAB有关非线性规划求解的命令。实验九供应与选址问题【实验内容】某建筑公司有6个建筑工地要开工，每个工地的位置（用平面坐标，表示，距离单位：千米）及水泥日用量（吨）由表1给出。目前有两个废旧的料场位于（5,1），（2,7）处，现需要重新建设、两个料场，日储存量各为20吨。试问料场、各设在何处，并且如何制定每天的原料供应计划，使得从、两料场分别向各工地运送水泥总的吨千米数最小。实验九供应与选址问题【实验内容】表1工地的位置（a，b）及各工地水泥日用量位置及用量123456横坐标a1.258.750.55.7537.25纵坐标b1.250.754.7556.57.75d（吨）3547611实验九供应与选址问题【实验准备】很多实际问题所归结的优化数学模型中，目标函数或约束条件很难用线性来表达。如果目标函数或约束条件中包含有非线性函数，就称这种优化模型为非线性规划问题。实验九供应与选址问题【实验准备】1．非线性规划问题数学模型的一般表示minf(x),s.t.g()01,2,,h()01,2,,.ijximxjk其中x∈，f(x)为目标函数，为约束函数，在这些函数中至少有一个是非线性函数。令称S为可行集或可行域，S中的点称为可行点。这样（1）可用集约束的形式来表示g()h()ijxx，nR{g()01,2,,;h()01,2,,.}(2)ijSxximxjkminf(x),s.t.xS(3)【实验准备】设f（x）为目标函数，S为可行域，,若对每一个均有，则称为极小化问题（1）的最优解（整体最优解）；若存在的某邻域，使得对该邻域中每个x成立，则称为极小化问题的局部最优解。至于求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数，化为（1）所示的一般形式。*xSxS*f(x)f(x)*x*x*f(x)f(x)*x库恩－塔克（Kuhn－Tucker）条件：若为问题（1）的可行点，,f(x)和在处可微，在点处连续，在连续可微，且有向量集▽▽线性无关，则存在非负数和使得▽▽▽上式简称为K－T条件，它也是最优解的必要条件。*x{g()0}iIix【实验准备】g()ix*x*x*xg()()ixiIh()jx**{(),(),1,2,,}ijgxhxiIjk11,,,,,mk***11()()()0;mkiijjijfxgxhx**()0;()0iijjgxhx【实验准备】2．非线性规划问题的求解方法求解非线性规划问题要比求解线性规划问题困难得多。非线性规划有着众多的算法，而且仍有新算法不断地被提出来，但它却不像线性规划有单纯形法这一通用解法，各个算法都有特定的适用范围，带有一定的局限性。通常，求解带约束条件的非线性规划问题的常见方法是：将约束问题化为无约束问题，将非线性规划问题化为线性规划问题，以及将复杂问题转化为简单的问题。非线性规划的线性逼近法代数方法、如迭代，对于线性等式或不等式非常有效，以致很多非线性规划问题的，可以用与之近似的线性问题来代替，使问题简化。下面介绍的近似规划法就是一种线性化方法。【实验准备】近似规划法的基本思想：将问题（1）中的目标函数f(x)和约束条件近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解，把符合原始条件的最优解作为（1）的解的近似。每得到一个近似解之后，都从这点出发，重复以上步骤。这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。()0,(1,2,,);()0,kijgximhx（j=1，2，，）【实验准备】罚函数法罚函数的基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。这类方法称为序列无约束最小化方法。简称为SUMT（其一为SUMT外点法，其二为SUMT内点法）。3．求解非线性规划的MATLAB命令（1）MATLAB5.2及以下版本使用的命令【实验准备】x=constr('fun',x0)求解非线性规划模型（1）；x=constr('fun',x0,options)参数options的定义由实验一中的表1给出x=constr('fun',x0,options,vlb,vub)指定决策变量的上下界vlb≤x≤vub；[x,options]=constr('fun',x0,...)同上，同时返回参数options的值必须先用M–文件定义函数fun，其格式如下function[f,g]=fun(x)f=f(x);g=[g1(x);g2(x);…;gm(x)]可调用help文件来了解constr的更多用法。【实验准备】二次规划的标准型为b　　s.t.4　　＋21zminAxxcHxxTT）（x=qp(H,c,A,b)求解二次规划模型（4）；x=qp(H,c,A,b,vlb,vub)指定决策变量的上下界vlb≤x≤vub；x=qp(H,c,A,b,vlb,vub,x0)指定迭代的初始值x0；x=qp(H,c,A,b,vlb,vub,x0,n)n表示中前n个约束条件等式约束；程序qp其使用格式和线性规划中所讲的lp命令相似，可以用helpqp来查阅有关该命令的详细信息。bAx【实验准备】（2）MATLAB5.3以上版本使用命令求解的非线性规划模型：(5)x=fmincon(fun,x0,A,b)求解非线性规划模型（5），目标函数非线性；x=fmincon(fun,x0,A,b,Aeq,beq)求解模型（5），有等式约束条件；x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)求解线性规划模型（5），指定了决策变量的上下界；x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)非线性约束条件写成M函数形式（nonlcon.m）；function[c,ceq]=nonlconc=c(x)；ceq=ceq(x)；用［x,Fval］代替上述各命令行中左边的x，则可得到在最优解x处的函数值Fval；可以在MATLAB帮助文件中查阅有关该命令的更多用法。min()..fxstAxb,()0cxAeqxbeqlbxup【实验准备】（2）MATLAB5.3以上版本使用命令求解的非线性规划模型：(5)x=fmincon(fun,x0,A,b)求解非线性规划模型（5），目标函数非线性；x=fmincon(fun,x0,A,b,Aeq,beq)求解模型（5），有等式约束条件；x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)求解线性规划模型（5），指定了决策变量的上下界；x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)非线性约束条件写成M函数形式（nonlcon.m）；function[c,ceq]=nonlconc=c(x)；ceq=ceq(x)；用［x,Fval］代替上述各命令行中左边的x，则可得到在最优解x处的函数值Fval；可以在MATLAB帮助文件中查阅有关该命令的更多用法。min()..fxst【实验方法与步骤】1．引例问题的分析记工地的位置为（ai，bi），水泥日用量为di，i＝1，…，6；料场位置为（xj，yj），日储量为ej，j＝1，2；从料场j向工地i的运送量为Cij。这个优化问题的目标函数（总吨千米数）可表为（6）各工地的日用量必须满足，所以（7）各料场的运送量不能超过日储量，所以（8）则该问题的决策变量为料场位置xj，yj和A、B两料场往各工地的运送量Cij，问题归结为在约束条件（7）、（8）及决策变量为非负的情况下求料场位置（xj，yj）和运送量Cij使（6）的总吨千米数最小。由于目标函数f对xj，yj是非线性的，所以在求新建料场位置和用料时是非线性规划模型。262211min()()ijjijijifcxayb61,1,2ijjicej21,1,,6ijijcdi【实验方法与步骤】2．MATLAB计算机求解首先定义非线性规划的M文件函数：function[f,g]=liaoch(x)a=[1.25,8.75,0.5,5.75,3,7.25];b=[1.25,0.75,4.75,5,6.5,7.75];d=[3,5,4,7,6,11];e=[20,20];f1=0;%f1是料场A到各工地的吨千米总数，其中x(1)至x(6)为料场A往各工地的运送量,(x(13),x(14))为A的位置fori=1:6s(i)=sqrt((x(13)-a(i))^2+(x(14)-b(i))^2);f1=s(i)*x(i)+f1;endf2=0;%f2是料场B到各工地的吨千米总数，其中x(7)至x(12)为料场B往各工地的运送量,(x(15),x(16))为B的位置fori=7:12s(i)=sqrt((x(15)-a(i-6))^2+(x(16)-b(i-6))^2);f2=s(i)*x(i)+f2;endf=f1+f2;fori=1:6g(i)=x(i)+x(i+6)-d(i);%各工地用量必须满足endg(7)=sum(x(1:6))-e(1);%各料场运送量不超过日储量g(8)=sum(x(7:12))-e(2);然后，在MATLAB命令框里输入求解命令：x0=[zeros(1,12)5127]';%取零为往各工地运送量的初值，取废弃料场位置为新料场的初值vlb=zeros(1,16);%求解下界为零op(13)=6;op(14)=2000;%确定等式约定的数目和命令求解的最大迭代次数[x,op]=constr('liaoch',x0,op,vl),y=op(8)【实验方法与步骤】将结果作成列表的形式为最小的总吨千米数为89.8835。工地i123456新料场位置Ci1354710（5.6959，4.9284）Ci20000511（7.2500，7.7500）【结果分析】在命令框输入命令text(1.25,1.25,'+3');text(8.75,0.75,'+5');text(0.5,4.75,'+4')text(5.75,5,'+7');text(3,6.5,'+6');text(7.25,7.75,'+11')text(5.6959,4.9284,'A')text(7.2500,7.7500,'B')【结果分析】0123456789012345678+3+5+4+7+6+11AB图9.1个工地用量、新料场位置图图9.1画出了工地、新料场的位置（+为工地，旁边的数字为用量，A、B分别表示新料场的位置，可以看出，新料场应建在两个用量最大的工地旁边，这个结果预先估计到了吗？所求得的解是全局最优解吗？实际上改变决策变量的初始值，那么给各工地的供应量和新料场的位置都要发生变化，不妨试试。【练习与思考】1．某公司经营两种物品，第一种物品每吨（t）售价30元，第二种物品售价450元/t，根据统计，售出每吨第一种物品所需要的营业时间平均是0.5h（小时），第二种物品是2+0.25（h）,其中是第二种物品售出的数量。已知该公司在这段时间内的总营业时间为800h，试决定使其营业额最大的营业计划。2．一基金管理者的工作是，每天将现有的美元、英镑、马克、日元四种货币按当天的汇率相互兑换，使在满足需要的条件下，按美元计算的价值最高。设某天的汇率、现有货币和当天需求如下：美元英镑马克日元现有量（）需求量（）美元1.589281.743138.386英镑1.69712.9579234.713马克.57372.33808179.34681日元