第三章 数学规划模型.doc

68第三章 数学规划模型 数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。 数学规划模型的一般表达式：为目标函数，为约束函数，为可控变量，为已知参数， 为随机参数。本章主要介绍线性规划、整数规划、非线性规划的基本概念与基本原理、无约束问题的最优化方法、约束问题的最优化方法、动态规划。3.1线性规划线性规划模型是运筹学的重要分支，是20世纪三四十年代初兴起的一门学科。1947年美国数学家丹齐格G.B.Dantzig及其同事提出的求解线性规划的单纯形法及有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。随着1979年前苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家卡玛卡尔H.Karmarkar算法的相继问世，线性规划的理论更加完备成熟，实用领域更加宽广。线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。 就模型而言，线形规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。线性规划模型的求解方法目前仍以单纯形法为主要方法。本节介绍的主要内容有：线性规划模型的建立以及求解，线性规划的matlab解法，线性规划问题的建模实例。3.1.1 线性规划模型的建立以及求解一、线性规划模型的建立例1、某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？建立上述问题的数学模型：设该厂生产台甲机床和乙机床时总利润最大，则应满足：（目标函数） (1)s.t.（约束条件） （2）这里变量称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。一般线性规划问题的标准型为 (3) (4)二、线性规划模型的求解求解线性规划模型时，我们来了解一下定义。可行解 满足约束条件（4）的解，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。可行域 所有可行解构成的集合称为问题的可行域，记为。1.图解法图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。如上图所示，阴影区域即为LP问题的可行域R。对于每一固定的值，使目标函数值等于的点构成的直线称为目标函数等位线，当变动时，我们得到一族平行直线。让等位线沿目标函数值减小的方向移动，直到等位线与可行域有交点的最后位置，此时的交点（一个或多个）即为LP的最优解。对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为，最优目标值。2. 单纯形法单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。三、典型的线性规划问题1.运输问题(产销平衡)例2 某商品有个产地、个销地，各产地的产量分别为，各销地的需求量分别为。若该商品由产地运到销地的单位运价为，问应该如何调运才能使总运费最省？解：引入变量，其取值为由产地运往销地的该商品数量，数学模型为 s.t. 显然是一个线性规划问题，当然可以用单纯形法求解。对产销平衡的运输问题，由于有以下关系式存在：其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康希表上作业法）。 表上作业法是单纯形法在求解运输问题时的一种简化方法，其求解工作在运输表上进行逐步迭代如下：先按某一规则找出一个初始解（初始调运方案）；再对现行解作最优性判断；若这个解不是最优的，就在运输表上对它进行调整改进，得一新解；再判断，再改进，直到得到最优解。2.指派问题（又称分配问题Assignment Problem）2.1指派问题模型建立例3 拟分配人去干项工作，每人干且仅干一项工作，若分配第人去干第项工作，需花费单位时间，问应如何分配工作才能使工人花费的总时间最少？容易看出，要给出一个指派问题的实例，只需给出矩阵，被称为指派问题的系数矩阵。引入变量，若分配干工作，则取，否则取。上述指派问题的数学模型为 s.t. (5)(5)的可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用中的一个置换表示。(5)的变量只能取0或1，从而是一个0-1规划问题。一般的0-1规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为），其非负可行解的分量只能取0或1，故约束可改写为而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中，。2.2 求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法匈牙利算法。算法主要依据以下事实：如果系数矩阵一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵，则以或为系数矩阵的指派问题具有相同的最优指派。利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B，而最优解不变。若能在B 中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。下面通过一例子来说明该算法。例4 求解系数矩阵的指派问题 解：先作等价变换如下 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：对未选出0元素的行打；对行中0元素所在列打；对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。3.1.2求解线性规划的Matlab解法一、求解线性规划的Matlab解法Matlab5.3中线性规划的标准型为 基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。 例1 求解下列线性规划问题 解 （i）编写M文件c=2;3;-5;a=-2,5,-1; b=-10;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c*x（ii）将M文件存盘，并命名为example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。二、可以转化为线性规划的问题很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如：例2 问题为其中，和为相应维数的矩阵和向量。要把上面的问题变换成线性规划问题，只要注意到事实：对任意的，存在满足 ，。事实上，我们只要取，就可以满足上面的条件。这样，记，从而我们可以把上面的问题变成 3.1.3 线性规划问题的建模举例营养配餐问题。每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表2-3中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少kg？问题分析与模型建立设 （i=1,2,6）分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：min 约束条件：铁的需求量至少6个单位数：磷的需求量至少25个单位数：维生素A的需求量至少17500个单位：维生素C的需求量至少245个单位：烟酸的需求量至少5个单位数：每周需供应140千克蔬菜，即该问题的线性规划模型为：Min s.t. 040,i=1,.,6问题是满足营养素要求的条件下，所需费用最小，是一个线性规划模型。 利用Matlab软件编程序： % 营养配餐ch61,文件名： ch61.mc=5;5;8;2;6;3;A=(-1)*1,1,1,1,1,1;0.45,0.45,1.05,0.40,0.50,0.50;10,28,59,25,22,75;415,9065,2550,75,15,235;8,3,53,27,5,8;0.30,0.35,0.60,0.15,0.25,0.80;b=(-1)*140;6;25;17500;245;5;xLB=zeros(6,1);xUB=40;40;40;20;40;40;nEq=1;x0=0*ones(6,1);x=lp(c,A,b,xLB,xUB,x0,nEq);disp(青豆需要的份数)x(1)disp(胡罗卜需要的份数 )x(2)disp(菜花需要的份数 )x(3)disp(白菜需要的份数 )x(4)disp(甜菜需要的份数 )x(5)disp(土豆需要的份数)x(6)执行后输出青豆需要的份数ans = 40胡罗卜需要的份数 ans = 40.0000菜花需要的份数 ans = 0白菜需要的份数 ans = 20.0000甜菜需要的份数 ans = 0土豆需要的份数ans = 40最小费用 ans = 560.0000习 题 3.11. 某厂生产三种产品I，II，III。每种产品要经过两道工序加工。设该厂有两种规格的设备能完成工序，它们以表示；有三种规格的设备能完成工序，它们以表示。产品I可在任何一种规格设备上加工。产品II可在任何规格的设备上加工，但完成工序时，只能在设备上加工；产品III只能在与设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润最大。设备产 品设备有效台时满负荷时的设备费用(元)IIIIII5764710981211600010000400070004000300321250783200原料费(元/件)单 价(元/件)0.251.250.352.000.502.802. 有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表： 工作工人甲乙丙丁15192619182317212122162324181917 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？3.2 整数规划在许多线性规划模型中，变量取整数时才有意义。例如，不可分解产品的数目，如汽车、房屋、飞机等，或只能用整数来记数的对象。这样的线性规划称为整数线性规划，简称整数规划，记为IP。本节介绍的主要内容有：整数规划模型的建立以及求解，整数规划的计算机解法。3.2.1整数规划模型的建立以及求解一、概论1. 定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。2. 整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：1、变量全限制为整数时，称纯（完全）整数规划。2、变量部分限制为整数的，称混合整数规划。3、变量只能取0或1时，称之为0-1整数规划。 整数规划特点（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。（ii） 整数规划最优解不能按照实数最优解简单取整而获得。二、求解方法分类：（i）分枝定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）隐枚举法求解型整数规划： 过滤隐枚举法； 分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划。下面将简要介绍常用的几种求解整数规划的方法。1.分枝定界法对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。设有最大化的整数规划问题，与它相应的线性规划为问题，从解问题开始，若其最优解不符合的整数条件，那么的最优目标函数必是的最优目标函数的上界，记作；而的任意可行解的目标函数值将是的一个下界。分枝定界法就是将的可行域分成子区域再求其最大值的方法。逐步减小和增大，最终求到。现用下例来说明：例3 求解下述整数规划 s.t. 解 （i）先不考虑整数限制，即解相应的线性规划，得最优解为：可见它不符合整数条件。这时是问题的最优目标函数值的上界，记作。而显然是问题的一个整数可行解，这时，是的一个下界，记作，即。（ii）因为当前均为非整数，故不满足整数要求，任选一个进行分枝。设选进行分枝，把可行集分成2个子集：，因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题： s.t. 最优解为：。问题： s.t. 最优解为：。再定界：。（iii）对问题再进行分枝得问题和，它们的最优解为再定界：，并将剪枝。（iv）对问题再进行分枝得问题和，它们的最优解为无可行解。将剪枝。于是可以断定原问题的最优解为：从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题，将与它相应的线性规划问题称为问题。（i）解问题可能得到以下情况之一： （a）没有可行解，这时也没有可行解，则停止 （b）有最优解，并符合问题的整数条件，的最优解即为的最优解，则停止。 （c）有最优解，但不符合问题的整数条件，记它的目标函数值为。（ii）用观察法找问题的一个整数可行解，一般可取，试探，求得其目标函数值，并记作。以表示问题的最优目标函数值；这时有 进行迭代。第一步：分枝，在的最优解中任选一个不符合整数条件的变量，其值为，以表示小于的最大整数。构造两个约束条件 和 将这两个约束条件，分别加入问题，求两个后继规划问题和。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无作用。第二步：比较与剪枝，各分枝的最优目标函数中若有小于者，则剪掉这枝，即以后不再考虑了。若大于，且不符合整数条件，则重复第一步骤。一直到最后得到为止。得最优整数解。3.2.2 隐枚举法求解型整数规划隐枚举法是求解型整数规划的方法之一，我们先介绍引入变量的实际问题，再研究隐枚举法。3.2.2.1 型整数规划型整数规划是整数规划中的特殊情形，它的变量仅取值0或1。这时称为变量，或称二进制变量。仅取值0或1这个条件可由下述约束条件：，整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。引入变量的实际问题 1）投资场所的选定相互排斥的计划 例4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）可供选择。规定 在东区：由三个点中至多选两个； 在西区：由两个点中至少选一个；在南区：由两个点中至少选一个。 如选用点，设备投资估计为元，每年可获利润估计为元，但投资总额不能超过元。问应选择哪几个点可使年利润为最大？解题时先引入变量，令 .于是问题可列写成： s.t. 2）相互排斥的约束条件 有两个相互排斥的约束条件 或 。为了统一在一个问题中，引入变量，则上述约束条件可改写为： 其中是充分大的数。 约束条件 或 可改写为 如果有个互相排斥的约束条件：为了保证这个约束条件只有一个起作用，我们引入个变量和一个充分大的常数，而下面这一组个约束条件 （1） （2）就合于上述的要求。这是因为，由于（2），个中只有一个能取0值，设，代入（1），就只有的约束条件起作用，而别的式子都是多余的。3.2.2.2 型整数规划解法之一（隐枚举法）解型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的个组合。对于变量个数较大（例如），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。下面举例说明一种解型整数规划的隐枚举法。 例5 s.t. 求解思路及改进措施：（i） 先试探性求一个可行解，易看出满足约束条件，故为一个可行解，且相应的目标函数值为。（ii） 因为是求极大值问题，故求最优解时，凡是目标值的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：，称该条件为过滤条件(Filtering Contraint)。从而原问题等价于： s.t. 若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(a)(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)(e)即可行性条件不必再检验；若它满足(a)(e)且相应的目标值严格大于3，则进行（iii）。（iii） 改进过滤条件。（iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。按上述思路与方法，例5的求解过程可由下表来表示：目标值约束条件过滤条件a b c d e 03 -25 18 63从而得最优解，最优值。3.2.2.3 蒙特卡洛法（随机取样法）前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而有效的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。例6 已知非线性整数规划为：s.t. 对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算个点，其计算量非常之大。然而应用蒙特卡洛去随机计算个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？下面就分析随机取样采集个点计算时，应用概率理论来估计一下可信度。不失一般性，假定一个整数规划的最优点不是孤立的奇点。假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算个点后，有任一个点能落在高值区的概率分别为，。解 （i）首先编写M文件mente.m定义目标函数f 和约束向量函数g，程序如下：function f,g=mengte(x);f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1)-2*x(2)-3*x(3). -x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)=2*x(1)+x(2)+6*x(3)-200;g(4)=x(3)+x(4)+5*x(5)-200;（ii）编写如下程序求问题的解：rand(state,sum(clock);p0=0;ticfor i=1:105 x=99*rand(5,1);x1=floor(x);x2=ceil(x);f,g=mengte(x1);if sum(g=0)=4 if p0=f x0=x1;p0=f; endendf,g=mengte(x2);if sum(g=0)=4 if p0=f x0=x2;p0=f; endendendx0,p0toc3.2.2.4 整数规划的计算机解法整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题或约束矩阵是幺模矩阵时，有时可以直接利用Matlab的函数linprog。例7 求解下列指派问题，已知指派矩阵为 解：编写Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5 8 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(25,1)求得最优指派方案为，最优值为21。习 题 3.21.某市场研究小组考虑下一步如何选择广告竞争计划，在进行大量的调查研究后，制定了各种可供选择的方案，方案的特征数字如下：广告计划的目的是使受影响的顾客数为最大。上表所给出的资源限制（资金、设计员和推销员）外，还有如下约束条件： （1）如果决定发起推销运动，那么必须同时用电台或流行杂志配合； （2）公司不能同时在商业杂志和流行杂志上作广告。 假定各种广告手段所影响的顾客不同，不重复（即每一顾客只受一种广告手段影响），问如何开展广告宣传？3.3非线性规划非线性规划是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本理论问题，使数学中的如凸分析、数值分析等也得到了发展。还有一种规划问题和时间有关，叫做“动态规划”。近年来在工程控制、技术物理和通讯中的最佳控制问题中，已经成为经常使用的重要工具。一、 非线性规划的实例与定义如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不像线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。例1 （投资决策问题） 某企业有个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金元，投资于第个项目需花费资金元，并预计可收益元，试选择最佳投资方案。 解 设投资决策变量为 ，.则投资总额为，投资总收益为。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金，故有限制条件为.另外，由于 只取值0或1，所以还有约束. 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NLP）。可概括为一般形式 其中称为模型（NLP）的决策变量，称为目标函数，和称为约束函数。另外， 称为等式约束，称为不等式约束。 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点： （ i ）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。 （ ii ）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。 （ iii ）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。 （ iv ）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。 二、线性规划与非线性规划的区别如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。三、非线性规划的Matlab解法Matlab中非线性规划的数学模型写成以下形式 其中 是标量函数，是相应维数的矩阵和向量， 是非线性向量函数。 Matlab中的命令是 :X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 它的返回值是向量，其中FUN是用M文件定义的函数；X0是的初始值；A, B, Aeq, Beq定义了线性约束,如果没有等式约束，则A=,B=,Aeq=,Beq=；LB和UB是变量的下界和上界，如果上界和下界没有约束，则LB=，UB=，如果 无下界，则LB=-inf，如果无上界，则UB=inf；NONLCON是用M文件定义的非线性向量函数,；OPTIONS定义了优化参数，可以使用Matlab缺省的参数设置。 求下列非线性规划问题（ i ）编写M文件fun1.m function f=fun1(x); f=x(1)2+x(2)2+8; 和M文件fun2.m function g,h=fun2(x); g=-x(1)2+x(2); h=-x(1)-x(2)2+2; %等式约束 （ ii ）在Matlab的命令窗口依次输入 options=optimset; x,y=fmincon(fun1,rand(2,1),zeros(2,1), . fun2, options) 就可以求得当,时，最小值.四、求解非线性规划的基本迭代格式记（NP）的可行域为。若，并且 ,则称 是（NP）的整体最优解， 是(NP)的整体最优值。如果有则称 是（NP）的严格整体最优解，是(NP)的严格整体最优值。若 ，并且存在 的邻域 ，使 ，则称 是（NP）的局部最优解， 是(NP)的局部最优值。如果有则称 是（NP）的严格局部最优解， 是(NP)的严格局部最优值。由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点 出发，按照某一特定的迭代规则产生一个点列 ，使得当 是有穷点列时，其最后一个点是(NP)的最优解；当 是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。设是某迭代方法的第轮迭代点，是第 轮迭代点，记 （1）这里，显然是由点与点确定的方向。式（1）就是求解非线性规划模型(NP)的基本迭代格式。通常，我们把基本迭代格式（1）中的称为第轮搜索方向，为沿方向的步长，使用迭代方法求解(NLP)的关键在于，如何构造每一轮的搜索方向和确定适当的步长。设 ，若存在 ，使，则称向量 是在点处的下降方向。设 ，若存在 ，使，则称向量 是点 处关于 的可行方向。一个向量，若既是函数在点处的下降方向，又是该点关于区域的可行方向，则称之为函数在点处关于的可行下降方向。现在，我们给出用基本迭代格式（1）求解(NLP)的一般步骤如下：0 选取初始点，令。1 构造搜索方向，依照一定规则，构造在点处关于的可行下降方向作为搜索方向。2 寻求搜索步长。以为起点沿搜索方向寻求适当的步长，使目标函数值有某种意义的下降。3 求出下一个迭代点。按迭代格式（1）求出 。若已满足某种终止条件，停止迭代。 4 以代替，回到1步。 五、凸函数、凸规划设为定义在维欧氏空间中某个凸集上的函数，若对任何实数 以及中的任意两点和，恒有，则称 为定义在上的凸函数。若对每一个和恒有，则称为定义在上的严格凸函数。考虑非线性规划假定其中为凸函数，为凸函数，这样的非线性规划称为凸规划。可以证明，凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优解的集合形成一个凸集。当凸规划的目标函数为严格凸函数时，其最优解必定唯一（假定最优解存在）。由此可见，凸规划是一类比较简单而又具有重要理论意义的非线性规划。3.4动态规划动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由到距离最短（或费用最省）的路线。例2 生产计划问题工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。3.4.1 基本概念、基本方程和计算方法一、 动态规划的基本概念和基本方程一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。1）阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用表示。在例1中由出发为，由出发为，依此下去从出发为，共个阶段。在例2中按照第一、二、三、四季度分为，共四个阶段。2）状态状态（state）表示每个阶段开始时过程所处的自然状况。描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用表示第阶段的状态变量，它可以是一个数或一个向量。用表示第阶段的允许状态集合。在例1中可取，或将定义为，则或，而。个阶段的决策过程有个状态变量，表示演变的结果。在例1中取，或定义为，即。3）决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用表示第阶段处于状态时的决策变量，它是的函数，用表示的允许决策集合。在例1中可取或，可记作，而。4） 策略决策组成的序列称为策略（policy）。由初始状态开始的全过程的策略记作，即.由第阶段的状态开始到终止状态的后部子过程的策略记作，即，.类似地，由第到第阶段的子过程的策略记作.可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用表示。5） 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作 （1）在例1中状态转移方程为。6）指标函数和最优值函数指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用表示，。指标函数应具有可分离性，即可表为的函数，记为并且函数对于变量是严格单调的。过程在第阶段的阶段指标取决于状态和决策，用表示。指标函数由组成，常见的形式有：阶段指标之和，即，阶段指标之积，即，阶段指标之极大（或极小），即.这些形式下第到第阶段子过程的指标函数为。根据状态转移方程指标函数还可以表示为状态和策略的函数，即。在给定时指标函数对的最优值称为最优值函数（optimal value function），记为，即，其中可根据具体情况取或。7）最优策略和最优轨线使指标函数达到最优值的策略是从开始的后部子过程的最优策略，记作。是全过程的最优策略，简称最优策略（optimal policy）。从初始状态出发，过程按照和状态转移方程演变所经历的状态序列称最优轨线（optimal trajectory）。8）递归方程如下方程称为递归方程 （2）在上述方程中，当为加法时取；当为乘法时，取。动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由逆推至，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解法。这时，状态转移方程和递归方程分别为：，纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首先建立起动态规划的数学模型：（i）将过程划分成恰当的阶段。（ii）正确选择状态变量，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合。 （iii）选择决策变量，确定允许决策集合。（iv）写出状态转移方程。（v）确定阶段指标及指标函数的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。二、逆序解法的计算框图以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。一般化的自由终端条件为 (3)其中为已知。固定始端条件可表示为。如果状态和决策是连续变量，用数值方法求解时需按照精度要求进行离散化。设状态的允许集合为.决策的允许集合为.状态转移方程和阶段指标应对的每个取值和的每个取值计算，即，。最优值函数应对的每个取值计算。基本方程可以表为 （4）按照（3），（4）逆向计算出，为全过程的最优值。记状态的最优决策为，由和按照状态转移方程计算出最优状态，记作。并得到相应的最优决策，记作。于是最优策略为。算法程序的框图如下。图的左边部分是函数序列的递推计算，可输出全过程最优值，如果需要还可以输出后部子过程最优值函数序列和最优决策序列。计算过程中存是备计算之用，在算完后可用将替换掉；存是备右边部分读之用。图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略和最优轨线。三、 动态规划与静态规划的关系动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。动态规划可以看作求决策使指标函数达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明。例3 用动态规划解下列非线性规划 ； s.t. .其中为任意的已知函数。解 按变量的序号划分阶段，看作段决策过程。设状态为，取问题中的变量为决策。状态转移方程为取为阶段指标，最优值函数的基本方程为（注意到）；.按照逆序解法求出对应于每个取值