《供应与选址问题.ppt》由会员分享，可在线阅读，更多相关《供应与选址问题.ppt（22页珍藏版）》请在三一办公上搜索。
1、1,数学建模实 验,王汝军河西学院数学与统计学院,2,实验九 供应与选址问题,王汝军河西学院数学与统计学院,实验目的,1了解非线性规划问题的基本概念和求解方法。2通过对应用问题的分析、建模、求解，加深对非线性规划理论的理解。3学习掌握MATLAB有关非线性规划求解的命令。,3,实验内容,某建筑公司有6个建筑工地要开工，每个工地的位置（用平面坐标 a,b 表示，距离单位：千米）及水泥日用量 d（吨）由表1给出。目前有两个废旧的料场位于(5,1),(2,7)处，现需要重新建设 A,B两个料场，日储存量各为20吨。试问料场 A,B各设在何处，并且如何制定每天的原料供应计划，使得从 A,B 两料场分别
2、向各工地运送水泥总的吨千米数最小。,4,实验内容,5,表1工地的位置(a,b)及各工地水泥日用量,，,实验准备,很多实际问题所归结的优化数学模型中，目标函数或约束条件很难用线性来表达。如果目标函数或约束条件中包含有非线性函数，就称这种优化模型为非线性规划问题。为目标函数，为约束函数，在这些函数中至少有一个是非线性函数。令称S为可行集或可行域，S中的点称为可行点。,6,实验准备1,这样原问题可用集约束的形式来表示设f(x)为目标函数，S为可行域，x*S，若对每一个xS均有 f(x)f(x*)，则称x*为极小化问题（1）的最优解（整体最优解）；若存在x*的某邻域，使得对该邻域中每个x成立有 f(x
3、)f(x*)，则称x*为极小化问题的局部最优解至于求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数，化为（1）所示的一般形式。,7,实验准备1,库恩塔克（KuhnTucker）条件：若x*为问题（1）的可行点，在x*处可微，在x*点处连续，在x*连续可微，且有向量集线性无关，则存在非负数 和，使得上式简称为KT条件，它也是最优解的必要条件。,8,实验准备1,2非线性规划问题的求解方法求解非线性规划问题要比求解线性规划问题困难得多。非线性规划有着众多的算法，而且仍有新算法不断地被提出来，但它却不像线性规划有单纯形法这一通用解法，各个算法都有特定的适用范围，带有一定的局限性。通常
4、，求解带约束条件的非线性规划问题的常见方法是：将约束问题化为无约束问题，将非线性规划问题化为线性规划问题，以及将复杂问题转化为简单的问题。,9,非线性规划的线性逼近法代数方法、如迭代，对于线性等式或不等式非常有效，以致很多非线性规划问题的，可以用与之近似的线性问题来代替，使问题简化。下面介绍的近似规划法就是一种线性化方法。近似规划法的基本思想：将问题（1）中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把符合原始条件的最优解作为（1）的解的近似。,10,每得到一个近似解之后，都从这点出发，重复以上步骤。这样，通过求解一系列
5、线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。罚函数法罚函数的基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。这类方法称为序列无约束最小化方法。简称为SUMT（其一为SUMT外点法，其二为SUMT内点法）。,11,求解的非线性规划模型：,12,13,x=fmincon(fun,x0,A,b)从X0开始寻找FUN的最小x，约束于线性不等式 A*X=Bx=fmincon(fun,x0,A,b,Aeq,beq)同上，增加等式约束条件Aeq*X=Beq；x=fmincon(fun,x0,A,b,Aeq,
6、beq,lb,ub)同上，指定了决策变量的上下界，没有可空；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帮助文件中查阅有关该命令的更多用法。,实验方法1,记工地的位置为(ai,bi),水泥日用量为 di,i=1,2,6；料场位置为(xj,yj),日储量为 ej=1,2；从料场j向工地i的运送量为 cij。这个优化问题的目标函数
7、（总吨千米数）可表为各工地的日用量必须满足，所以有,14,各料场的运送量不能超过日储量，所以则该问题的决策变量为料场位置 xj,yj和A,B两料场往各工地的运送量cij，问题归结为在约束条件（7）、（8）及决策变量为非负的情况下求料场位置(xj,yj)和)运送量cij,使（6）的总吨千米数最小。由于目标函数f对xj,yj是非线性的,所以在求新建料场位置和用料时是非线性规划模型。,15,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=
8、3,5,4,7,6,11;e=20,20;f1=0;%f1是料场A到各工地的吨千米总数，其中x(1)至x(6)为料场A往各工地的运送量,(x(13),x(14)为A的位置for i=1:6 s(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的位置,16,for i=7:12 s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2);f2=s(i)*x(i)+f2;endf=f1+f2;for
9、 i=1:6 g(i)=x(i)+x(i+6)-d(i);%各工地用量必须满足endg(7)=sum(x(1:6)-e(1);%各料场运送量不超过日储量g(8)=sum(x(7:12)-e(2);,17,然后，在MATLAB命令框里输入求解命令：x0=zeros(1,12)5 1 2 7;%取零为往各工地运送量的初值，取废弃料场位置为新料场的初值vlb=zeros(1,16);%求解下界为零op(13)=6;op(14)=2000;%确定等式约定的数目和命令求解的最大迭代次数 x,op=constr(liaoch,x0,op,vl),y=op(8),18,将结果作成列表的形式为,19,text
10、(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)text(5,1,F1)text(2,7,F2),20,实验方法2,21,图画出了工地、新料场的位置（+为工地，旁边的数字为用量，A、B分别表示新料场的位置，可以看出，新料场应建在两个用量最大的工地旁边，这个结果预先估计到了吗？所求得的解是全局最优解吗？实际上改变决策变量的初始值，那么给各工地的供应量和新料场的位置都要发生变化，不妨试试。,22,
