供应与选址问题.docVIP

供应与选址问题 供应与选址问题 PAGE PAGE 189 供应与选址问题 实验九　供应与选址问题 【实验目的】 1．了解非线性规划问题的基本概念和求解方法。 2．通过对应用问题的分析、建模、求解，加深对非线性规划理论的理解。 3．学习掌握MATLAB有关非线性规划求解的命令。 【实验内容】 某建筑公司有6个建筑工地要开工，每个工地的位置（用平面坐标，表示，距离单位：千米）及水泥日用量（吨）由表1给出。目前有两个废旧的料场位于（5,1），（2,7）处，现需要重新建设、两个料场，日储存量各为20吨。试问料场、各设在何处，并且如何制定每天的原料供应计划，使得从、两料场分别向各工地运送水泥总的吨千米数最小。 表1　工地的位置（，）及各工地水泥日用量 位置及用量 1 2 3 4 5 6 横坐标 3 纵坐标 5 （吨） 3 5 4 7 6 11 【实验准备】 很多实际问题所归结的优化数学模型中，目标函数或约束条件很难用线性来表达。如果目标函数或约束条件中包含有非线性函数，就称这种优化模型为非线性规划问题。 1．非线性规划问题数学模型的一般表示 　　　　　　　　　≤0　＝1，2，…，　　　　　　　　　　 　（1） 　　　　　　　　　　 ＝0 ＝1，2，…， 其中∈，为目标函数，，为约束函数，在这些函数中至少有一个是非线性函数。令 ＝｛｜≤0　＝1，2，…，；＝0 ＝1，2，…，｝　　 （2） 称为可行集或可行域，中的点称为可行点。这样（1）可用集约束的形式来表示 　　　　　　　　，　∈　　　　　　　　　　　　　　　　（3） 设为目标函数，为可行域，∈，若对每一个∈均有≥，则称为极小化问题（1）的最优解（整体最优解）；若存在的某邻域，使得对该邻域中每个成立≥，则称为极小化问题的局部最优解。 至于求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数，化为（1）所示的一般形式。 库恩－塔克（Kuhn－Tucker）条件：若为问题（1）的可行点，＝｛｜=0｝，和在处可微，（）在点处连续，在连续可微，且有向量集｛▽，▽｜，＝1，2，…，｝线性无关，则存在非负数，…，和，…，，使得 ▽＋▽＋▽＝0；　＝0；　＝0　 上式简称为K－T条件，它也是最优解的必要条件。 2．非线性规划问题的求解方法 求解非线性规划问题要比求解线性规划问题困难得多。非线性规划有着众多的算法，而且仍有新算法不断地被提出来，但它却不像线性规划有单纯形法这一通用解法，各个算法都有特定的适用范围，带有一定的局限性。通常，求解带约束条件的非线性规划问题的常见方法是：将约束问题化为无约束问题，将非线性规划问题化为线性规划问题，以及将复杂问题转化为简单的问题。 非线性规划的线性逼近法 代数方法、如迭代，对于线性等式或不等式非常有效，以致很多非线性规划问题的，可以用与之近似的线性问题来代替，使问题简化。下面介绍的近似规划法就是一种线性化方法。 近似规划法的基本思想：将问题（1）中的目标函数和约束条件≤0（＝1，2，…，）；＝0（＝1，2，…，）近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把符合原始条件的最优解作为（1）的解的近似。每得到一个近似解之后，都从这点出发，重复以上步骤。这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。 罚函数法 罚函数的基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。这类方法称为序列无约束最小化方法。简称为SUMT（其一为SUMT外点法，其二为SUMT内点法）。 3．求解非线性规划的MATLAB命令 （1）及以下版本使用的命令 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的更多用法。 二次规划的标准型为 　　　　　　　　 ＝＋　　　　　　　　　　　　　　　　（4）