数学建模(美赛)数学规划

1、 线性规划线性规划 整数规划整数规划 目标规划目标规划非线性规划非线性规划 动态规划动态规划 图图 论论 排排 队队 论论数学规划模型数学规划模型线线 性性 规规 划划目的目的内容内容2. 掌握用数学软件包求解线性规划问题掌握用数学软件包求解线性规划问题.1. 了解线性规划的基本内容了解线性规划的基本内容.2. 用数学软件包用数学软件包MATLAB求解线性规划问题求解线性规划问题.1. 两个引例两个引例. 3. 建模案例：投资的收益与风险建模案例：投资的收益与风险.问题问题 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的

2、数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？ 单位工件所需加工台时数 单位工件的加工费用 车床类 型 工件1 工件2 工件3 工件1 工件2 工件3 可用台时数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 引例引例解解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型： 解答线性规划模型的一般形式线性规划模型的一般形

3、式11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目标函数和所有的约束条件都是设计变量目标函数和所有的约束条件都是设计变量的线性函数的线性函数.min. s.tucxAxbvlbxvub矩矩阵阵形形式式：用用MATLAB优化工具箱解线性规划优化工具箱解线性规划min z=cX s.t.AXb1. 模型：命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式： 存在，则令A= ，b= .bAX 3. 模型：min z

4、=cX s.t.AXbbeqXAeqVLBXVUB命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若没有等式约束: , 则令Aeq= , beq= . 2其中X0表示初始点 beqXAeq4. 命令：x,fval=linprog()返回最优解及处的目标函数值fval.解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.0

5、5 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh1)解解: 编写编写M文件文件xxgh2.m如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh2)123m

6、in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxxs.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X改写为：例例3 问题一的解答 问题问题编写编写M文件文件xxgh3.m如下如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;

7、x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh3)结果结果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800. 投资的收益和风险投资的收益和风险二、基本假设和符号规定二、基本假设和符号规定三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n4. 模型简

8、化：四、模型四、模型1 1的求解的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度.我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,

9、vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To MATLAB（xxgh5）计算结果：计算结果：五、五、 结果分析结果分析返 回4 4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快.在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合， 大约是a*=0.6%，Q*=20% ，所对应投资方案为: 风险度 收益 x0 x1 x2 x3 x4 0.00

10、60 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险.对于不同风险的承受能力，选择该风险水平下的最优投资组合.2 2.当投资越分散时，投资者承担的风险越小，这与题意一致.即: 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资.1.1.风险大，收益也大.整数规划整数规划解解 设在甲车床上加工工件1、2、3的数量分别为整数x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为整数x4、x5、x6,可建立以下整数线性规划模型： 解答）为整数，（且621iix）为整数，（且521iix

11、 目目 标标 规规 划划一、多一、多 目标目标 规规 划划 及及 其其 解解 多目标规划包含有三大要素：多目标规划包含有三大要素： 目标、方案和决策者目标、方案和决策者 多目标规划中的方案即为决策变量，也称为多目标问题的多目标规划中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。有其特征或特性，称之为属性。例题例题 某工厂在一个计划期内生产甲、乙两种产品，某工厂在一个计划期内生产

12、甲、乙两种产品，各产品都要消耗各产品都要消耗A A，B B，C C三种不同的资源。每件产品三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？才能使利润和产值都最大，且造成的污染最小？甲甲乙乙资源限量资源限量资源资源A A单位消耗单位消耗资源资源B B单位消耗单位消耗资源资源C C单位消耗单位消耗9 94 43 34 4

13、5 51010240240200200300300单位产品的价格单位产品的价格400400600600单位产品的利润单位产品的利润7070120120单位产品的污染单位产品的污染3 32 2解：问题的多目标模型如下解：问题的多目标模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf对于此模型的三个目标，工对于此模型的三个目标，工厂确定利润最大为主要目标。厂确定利润最大为主要目标。另两个目标则通过预测预先另两个目标则通过预测预先给定的希望达到的目标值转给定的希望达到的目标值

14、转化为约束条件。经研究，工化为约束条件。经研究，工厂认为总产值至少应达到厂认为总产值至少应达到2000020000个单位，而污染控制个单位，而污染控制在在9090个单位以下，即个单位以下，即9023)(20000600400)(213212xxXfxxXf （一）任何多目标规划问题，都由两个（一）任何多目标规划问题，都由两个基本部分组成基本部分组成: : （1 1）两个以上的目标函数；）两个以上的目标函数； （2 2）若干个约束条件。）若干个约束条件。 （二）对于多目标规划问题，可以将（二）对于多目标规划问题，可以将其数学模型一般地描写为如下形式：其数学模型一般地描写为如下形式： （2 2）)

15、(max(min)(max(min)(max(min)(max(min)21XfXfXfXFZkmmgggGXXXX2121)()()()(（1 1）式中：式中： 为决策变量向量。为决策变量向量。 TnxxxX,21 （三）多目标规划解的特点（三）多目标规划解的特点 对于上述多目标规划问题，求解就意味着需要对于上述多目标规划问题，求解就意味着需要做出如下的复合选择：做出如下的复合选择： （1 1）每一个目标函数取什么值，原问题可以得）每一个目标函数取什么值，原问题可以得到最满意的解决？到最满意的解决？ （2 2）每一个决策变量取什么值，原问题可以得）每一个决策变量取什么值，原问题可以得到最满意

16、的解决到最满意的解决 ？ 多目标规划问题的求解不能只追求一个目标的多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其它目标。最优化（最大或最小），而不顾其它目标。 当目标函数处于冲突状态时，就不会当目标函数处于冲突状态时，就不会存在使所有目标函数同时达到最大或最小存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解）。（又称非支配解或帕累托解）。 非劣解：可以用图非劣解：可以用图3 3说明。说明。图图3 多目标规划的劣解与非劣解多目标规划的劣解与非劣解二、多二、多 目目 标标 规规 划划 问问 题题

17、 的的 建建 模模 方方 法法 为了求得多目标规划问题的非劣解，为了求得多目标规划问题的非劣解，常常需要将多目标规划问题转化为单目标常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化，有如下规划问题去处理。实现这种转化，有如下几种建模方法。几种建模方法。（三）约束模型三）约束模型 理论依据理论依据 ：若规划问题的某一目标可以给：若规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约作为约束条件而被排除出目标组，进入约束条件组中。束条件组中。假如，除第一个目标外，其余目标都可以假如，除第一个目标外，其余

18、目标都可以提出一个可供选择的范围，则该多目标规提出一个可供选择的范围，则该多目标规划问题就可以转化为单目标规划问题：划问题就可以转化为单目标规划问题： 用目标达到法求解多目标规划的计用目标达到法求解多目标规划的计算过程，可以通过调用算过程，可以通过调用MatlabMatlab软件系统软件系统优化工具箱中的优化工具箱中的fgoalattainfgoalattain函数实现。函数实现。三、多目标规划问题的求解(化多为少的方法)1 1、主要目标法、主要目标法 在有些多目标决策问题中，各种目标的重在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最要性程度往往不一样。其中一个重

19、要性程度最高和最为关键的目标，称之为主要目标法。其高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。余的目标则称为非主要目标。0)(0)(. .)(. .)(),.,(),()(21XhXgtsorGXtsXfXfXfXoptFjiTk例如，在上述多目标问题中，假定例如，在上述多目标问题中，假定f1(X)为主要为主要目标，其余目标，其余p p-1-1个为非主要目标。这时，希望个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足主要目标达到极大值，并要求其余的目标满足一定的条件，即一定的条件，即1,.,2 , 1,)(,.,2 , 1, 0)(,.,2 , 1, 0

20、)(. .)(max1pkXfmjXhniXgtsXfkkji例题例题 某工厂在一个计划期内生产甲、乙两种产品，某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗各产品都要消耗A A，B B，C C三种不同的资源。每件产品三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？才能使利润和产值都最大，且造成的污染最小？甲

21、甲乙乙资源限量资源限量资源资源A A单位消耗单位消耗资源资源B B单位消耗单位消耗资源资源C C单位消耗单位消耗9 94 43 34 45 51010240240200200300300单位产品的价格单位产品的价格400400600600单位产品的利润单位产品的利润7070120120单位产品的污染单位产品的污染3 32 2解：问题的多目标模型如下解：问题的多目标模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf对于此模型的三个目标，工对于此模型的三个目标，工厂确定利润

22、最大为主要目标。厂确定利润最大为主要目标。另两个目标则通过预测预先另两个目标则通过预测预先给定的希望达到的目标值转给定的希望达到的目标值转化为约束条件。经研究，工化为约束条件。经研究，工厂认为总产值至少应达到厂认为总产值至少应达到2000020000个单位，而污染控制个单位，而污染控制在在9090个单位以下，即个单位以下，即9023)(20000600400)(213212xxXfxxXf由主要目标法化为单目标问题由主要目标法化为单目标问题0,300103200542404990232000060040012070)(max212121212121211xxxxxxxxxxxxxxXf用单纯形

23、法求得其最优解为用单纯形法求得其最优解为90)(,20750)(,4025)(,25.26, 5 .1232121xfxfxfxx2 2、线性加权和目标规划、线性加权和目标规划0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp在上述目标规划中，假定在上述目标规划中，假定f1 1(X),(X),f2 2(X),(X),fp p(X)(X)具有具有相同的量纲相同的量纲, ,按照一定的规则分别给按照一定的规则分别给f fi i赋予相同的权赋予相同的权系数系数i，作线性加权和评价函数，作线性加权和评价函数piiiXfXU1)()(0)(0)(. .)()(max1

24、XhXgtsXfXUjipiii则多目标问题化为如下的单目标问题则多目标问题化为如下的单目标问题例如，某公司计划购进一批新卡车，可供选择的卡车有例如，某公司计划购进一批新卡车，可供选择的卡车有如下如下4 4种类型：种类型：A1A1，A2A2，A3A3，A4A4。现考虑。现考虑6 6个方案属性：个方案属性：维修期限维修期限f1 1，每，每100100升汽油所跑的里数升汽油所跑的里数f2 2，最大载重吨数，最大载重吨数f3 3，价格（万元），价格（万元）f4 4，可靠性，可靠性f5 5，灵敏性，灵敏性f6 6。这。这4 4种型号的种型号的卡车分别关于目标属性的指标值卡车分别关于目标属性的指标值fi

25、jij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先对不同度量单位和不同数量级的指标值进行标准首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：化处理。先将定性指标定量化：变换后的指标值矩阵为：变换后的指标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001设权系数向量为设权系数向

26、量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则则925.57)(max*27.40)(925.57)(6 .40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最优方案为选购故最优方案为选购A3A3型卡车型卡车4 4、步骤法（、步骤法（STEMSTEM法）法） 这是一种交互方法，其求解过程通过分析者与决策这是一种交互方法，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。者之间的对话逐步进行，故称步骤法。 步骤法的基本思想是，首先需要求出原多目标问题步骤法的基本思想是，首先需要求出原多目标问题的一组理想解的一组理

27、想解(f(f1 1* *,f,f2 2* *,f,fk k* *) )。实际上，这些解。实际上，这些解f fi i* *(i=1,2,k)(i=1,2,k)无法同时达到，但可以当作一组理想的无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直到决策的约束条件加入原来的约束条件中去重新计算，直到决策者得到满意的解。者得到满意的解。把上述计算结果列入下表把上述计算结果列入下表

28、*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX例题：例题：某公司考虑生产两种光电太阳能电池：产品甲和某公司考虑生产两种光电太阳能电池：产品甲和产品乙。这种生产过程会在空气中引起放射性污染。因产品乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品的收射性污染。已知在一个生产周期内，每单位甲产品的收益是益是1 1元，每单位乙产品的收益是元，每单位乙产品的收益是3 3元。而放射性污染的元。而放射性污染的数量，每

29、单位甲产品是数量，每单位甲产品是1.51.5个单位个单位, ,每单位乙产品是每单位乙产品是1 1个个单位单位. .由于机器能力由于机器能力( (小时小时) )、装配能力（人时）和可用、装配能力（人时）和可用的原材料（单位）的限制，约束条件是的原材料（单位）的限制，约束条件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料装配能力机器能力xxxxxx)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料装配能力机器能力xxxxxxxxXfxxXfXfXfXFT目标有两个目标有两个:

30、 :一是利润最大一是利润最大, ,二是污染最小二是污染最小. .该问题该问题的多目标规划模型如下的多目标规划模型如下: :解解: :首先首先, ,分别求解两个单目标问题的最优解分别求解两个单目标问题的最优解, ,由它们由它们得到的目标函数值组成理想解得到的目标函数值组成理想解. .)(725)(42 . 02 . 0)(825. 05 . 03)(max212121211原材料装配能力机器能力xxxxxxxxXf)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(max212121212原材料装配能力机器能力xxxxxxxxXf46*)13, 7(1*1fX0*)0 ,

31、 0(1*2fX由此由此, ,构造支付表构造支付表Xf1*f2*(7,13)(0,0)460-23.50由此计算两个目标与理由此计算两个目标与理想值偏离的权重：想值偏离的权重：637. 0,363. 0,555. 0,316. 02121解下列线性规划问题解下列线性规划问题: :0,7254)2 . 02 . 08)25. 05 . 0)230(637. 0)346(363. 0min212121212121xxxxxxxxxxxx0,7254)2 . 02 . 08)25. 05 . 0192.21310)5 . 1346min21212121212121xxxxxxxxxxxxxx进行下一

32、轮迭代进行下一轮迭代. .首先设首先设2 2=0,=0,并计算得并计算得1 1=1.=1.将将模型修改为模型修改为由此求得由此求得: :10,3010, 02121ffxx决策者把这一结果与前一轮的解及理想值作比较决策者把这一结果与前一轮的解及理想值作比较, ,认为两个目标值都比较满意认为两个目标值都比较满意, ,则迭代结束则迭代结束. .线线 性性 目目 标标 规规 划划 模模 型型 线性规划问题都是处理单个目标的情况，但是在现实世界线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，中有许多问题具有多个目标，这些目标的重要性各不相同，往往有

33、不同的量纲，有的目标相互依赖，例如决策者既希望往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论性时，我们称其为线性目标规划问题。

34、在这里我们主要讨论线性目标规划问题。线性目标规划问题。一、线性目标规划模型的建立一、线性目标规划模型的建立 例例1 1：某一个企业利用某种原材料和现有设备可生某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价产甲、乙两种产品，其中，甲、乙两种产品的单价分别为分别为8 8元和元和1010元；生产单位甲、乙两种产品需要元；生产单位甲、乙两种产品需要消耗的原材料分别为消耗的原材料分别为2 2个单位和个单位和1 1个单位，需要占用个单位，需要占用的设备分别为的设备分别为1 1台时和台时和2 2台时；原材料拥有量为台时；原材料拥有量为1111个个单位；可利用的设备总台时为

35、单位；可利用的设备总台时为1010台时。试问：如何台时。试问：如何确定其生产方案？确定其生产方案？ 但是，在实际决策时，企业领导者必须考虑市场但是，在实际决策时，企业领导者必须考虑市场等一系列其它条件，如：等一系列其它条件，如：根据市场信息，甲种产品的需求量有下降的趋势，根据市场信息，甲种产品的需求量有下降的趋势，因此甲种产品的产量不应大于乙种产品的产量。因此甲种产品的产量不应大于乙种产品的产量。超过计划供应的原材料，需用高价采购，这就会使超过计划供应的原材料，需用高价采购，这就会使生产成本增加。生产成本增加。应尽可能地充分利用设备的有效台时，但不希望加应尽可能地充分利用设备的有效台时，但不希

36、望加班。班。应尽可能达到并超过计划产值指标应尽可能达到并超过计划产值指标5656元。元。 这样，该企业生产方案的确定，便成为一个多这样，该企业生产方案的确定，便成为一个多目标决策问题，这一问题可以运用目标规划方法进目标决策问题，这一问题可以运用目标规划方法进行求解。行求解。目标规划模型的有关概念目标规划模型的有关概念2 2、绝对约束和目标约束、绝对约束和目标约束 绝对约束：绝对约束：必须严格满足的等式约束和不等必须严格满足的等式约束和不等式约束，譬如，线性规划问题的所有约束条件都式约束，譬如，线性规划问题的所有约束条件都是绝对约束，不能满足这些约束条件的解称为非是绝对约束，不能满足这些约束条件

37、的解称为非可行解，所以它们是硬约束。可行解，所以它们是硬约束。 目标约束：目标约束：目标规划所特有的，可以将约束目标规划所特有的，可以将约束方程右端项看作是追求的目标值，在达到此目标方程右端项看作是追求的目标值，在达到此目标值时允许发生正的或负的偏差值时允许发生正的或负的偏差 ，可加入正负偏，可加入正负偏差变量，是软约束。差变量，是软约束。 线性规划问题的目标函数，在给定目标值和线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可以转化为目标约束，也加入正、负偏差变量后可以转化为目标约束，也可以根据问题的需要将绝对约束转化为目标约束可以根据问题的需要将绝对约束转化为目标约束。 目标规划

38、模型的有关概念目标规划模型的有关概念目标规划模型的有关概念目标规划模型的有关概念目标规划模型的有关概念目标规划模型的有关概念b) b) 要求不超过目标值，即允许达不到目标要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能小，即值，就是正偏差变量要尽可能小，即)(mindfZ（23） c) c) 要求超过目标值，也就是超过量不限，要求超过目标值，也就是超过量不限，但负偏差变量要尽可能小，即但负偏差变量要尽可能小，即 )(mindfZ（24） 在实际问题中，可以根据决策者的要求，在实际问题中，可以根据决策者的要求，引入正、负偏差变量和目标约束，并给不同引入正、负偏差变量和目标约束，并给不

39、同目标赋予相应的优先因子和权系数，构造目目标赋予相应的优先因子和权系数，构造目标函数，建立模型。标函数，建立模型。 例例2 2：在例在例1 1中，如果决策者在原材料供中，如果决策者在原材料供应受严格控制的基础上考虑：首先是甲应受严格控制的基础上考虑：首先是甲种产品的产量不超过乙种产品的产量；种产品的产量不超过乙种产品的产量；其次是充分利用设备的有限台时，不加其次是充分利用设备的有限台时，不加班；再次是产值不小于班；再次是产值不小于5656元。并分别赋元。并分别赋予这三个目标优先因子予这三个目标优先因子 。试建立。试建立该问题的目标规划模型。该问题的目标规划模型。321,PPP在以上各式中，在以

40、上各式中， 、 分别为赋予分别为赋予 优先因子的第优先因子的第 个目标的正、负个目标的正、负偏差变量的权系数，偏差变量的权系数， 为第为第 个目标的预期值，个目标的预期值， 为决策变量，为决策变量， 、 分别为第分别为第 个目标的正、负偏差变量，个目标的正、负偏差变量，（2525）式为目标函数，（）式为目标函数，（2626）式为目标约束，（）式为目标约束，（2727）式）式为绝对约束，（为绝对约束，（2828）式和（）式和（2929）式为非负约束，）式为非负约束， 、 、 分别为目标约束和绝对约束中决策变量的系数及约束值。分别为目标约束和绝对约束中决策变量的系数及约束值。其中，其中， ； ；

41、； 。 lklklpkkgkjxkdkdk)(kjcijaibmi, 2 , 1nj, 2 , 1Ll, 2 , 1Kk, 2 , 1非线性规划非线性规划 实验目的实验目的实验内容实验内容2、掌握用数学软件求解优化问题。、掌握用数学软件求解优化问题。1、直观了解非线性规划的基本内容。、直观了解非线性规划的基本内容。1 1、非线性规划的基本理论。、非线性规划的基本理论。4 4、实验作业。、实验作业。2、用数学软件求解非线性规划。、用数学软件求解非线性规划。3、钢管订购及运输优化模型、钢管订购及运输优化模型*非线性规划的基本解法非线性规划的基本解法非线性规划的基本概念非线性规划的基本概念非线性规划

42、非线性规划 返回返回 定义定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题非线性规划的基本概念非线性规划的基本概念 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式计算机求解方法 1. 首先建立M文件fun.m,定义目标函数F（X）:func

43、tion f=fun(X);f=F(X);标准型为： min F(X) s.t AX0的的 最短路问题最短路问题(2) Lij)P(vP(vi i)+)+w wijij ，则把，则把T T(v(vj j) )改变为改变为P P( (v vi i)+)+w wijij，把，把( (v vj j) )改变为改变为i i，否则转入（，否则转入（3 3）（3 3）令）令T(T(v vj j)=min)=minT T( (v vl l) ) v vl l S Si i ，如果，如果T T( (v vj ji i)+)+，则把，则把v vj j的的T T 标号改变为标号改变为P P 标号标号P P( (v

44、 vj j)=)=T T( (v vj j) )，令，令S Si+1i+1= =S Si iv vj j ，k k= =j j，把，把i i换成换成i i+1+1，转入（转入（1 1）；否则结束。）；否则结束。这时，对每一个这时，对每一个v v S Si i，d d( (v vs s, ,v v)=)=P P( (v v) )。对每一个。对每一个v v不属于不属于S Si i，d d（v vs s, ,v v）= =T T（v v）。）。 现在用现在用DijkstraDijkstra算法求例算法求例1 1中从中从v vs s到各个点的最短路，到各个点的最短路，此时此时S S=1=1。i i=0

45、=0：S S0 0=v v1 1 ，P P( (v v1 1)=0,)=0,( (v v1 1)=0)=0，T T( (v vi i)=+)=+，( (v vi i)=)=m m，i i=2,3,=2,3,9 9，k k=1=1。 （ 2 2 ） 因 为 （） 因 为 （v v1 1, v, v2 2） A A，v v2 2不 属 于不 属 于S S0 0，P P( (v v1 1)+)+w w1212 )w w3232+ +P P( (v v3 3) )，将，将T T( (v v2 2) )改变为改变为P P( (v v3 3)+)+w w3232=5=5，( (v v2 2) )改变为改变

46、为3 3。（3 3）在所有的）在所有的T T标号中，标号中，T T( (v v2 2)=5)=5最小，于是令最小，于是令P P( (v v2 2)=5)=5，S S3 3=v v1 1, ,v v4 4, ,v v3 3 ，k k=2=2。 i i=3=3：（2 2）将）将T T( (v v5 5) )改变为改变为P P( (v v2 2)+)+w w2525=6=6，( (v v5 5) )改变为改变为2 2。（3 3）在所有的）在所有的T T标号中，标号中，T T( (v v5 5)=6)=6最小，于是令最小，于是令P P( (v v5 5)=6)=6，S S4 4=v v1 1, ,v

47、v4 4, ,v v3 3 ，k k=5=5。 i i=4:=4: （2 2）将）将T T( (v v6 6) )，T T( (v v7 7) )，T T( (v v8 8) )分别改变为分别改变为1010， 9 9，1212，将，将( (v v0 0) )，( (v v7 7) )，( (v v8 8) )改变为改变为5 5。 （3 3）在所有的）在所有的T T标号中，标号中，T T( (v v7 7)=9)=9最小，于最小，于 是令是令P P( (v v7 7)=9)=9，S S5 5=v v1 1, ,v v4 4, ,v v3 3, ,v v2 2, ,v v5 5, ,v v7 7

48、，v v=7=7。 i i=5=5： （2 2）（）（v v7 7, ,v v8 8）A A，v v8 8不属于不属于S S5 5， 但但T T( (v v8 8)w w7878+ +P P( (v v7 7) )，故，故T T( (v v8 8) )不变。不变。 （3 3）在所有的）在所有的T T标号中，标号中，T(T(v v6 6)=10)=10最小，于最小，于 是是, ,令令P P( (v v6 6)=10)=10，S S6 6=v v1 1,v,v4 4,v,v3 3,v,v2 2,v,v5 5,v,v7 7, v, v6 6 ， k k=6=6。 i i=6=6：（2 2）从）从v

49、v6 6出发没有弧指向不属于出发没有弧指向不属于S S6 6的点，因此转的点，因此转入（入（3 3）。）。3 3）在所有的）在所有的T T标号中，标号中，T T( (v v8 8)=12)=12最小，令最小，令P P( (v v8 8)=12)=12，S S7 7=v v1 1,v,v4 4,v,v3 3,v,v2 2,v,v5 5,v,v7 7, v, v6 6,v,v8 8 ， k k=8=8。 i i=7=7： 这时，仅有这时，仅有T T标号的点为标号的点为v v9 9，T T（v v9 9）=+=+，算法，算法结束。结束。此时，把此时，把P P标号和标号和值标在图中，如图值标在图中，如

50、图8.158.15所示所示图8.16P(VP(V4 4) )=1=1 (V(V4 4) )=1=1v4v2v8v7v6v5v963623410231262410P(VP(V6 6) )=10=10P(VP(V7 7) )=9=9 (V(V1 1)=0)=0P(VP(V1 1) )=0=0 (V(V6 6) )=5=5 (V(V5 5) )=2=2P(VP(V2 2) )=5=5P(VP(V5 5) )=6=6P(VP(V8 8) )=12=12 (V(V7 7) )=5=5 (V(V2 2) )=3=3 (V(V8 8) )=5=5T(VT(V9 9) )=+=+ (V(V9 9) )=M=M

51、P(VP(V3 3) )=3=3 (V(V3 3) )=1=11最短路：最短路：V V1 1-(V-(V4 4-)V-)V3 3-V-V2 2-V-V5 5-(V-(V6 6-V-V7 7-)V-)V8 8 从图从图8.168.16中，不难看出从中，不难看出从v v1 1到到v v8 8的最短路。因为的最短路。因为（v v8 8）=5=5，故最短路经过点，故最短路经过点v v5 5有因为有因为（v v5 5）=2=2，故最短路经过点，故最短路经过点v v2 2。依次类推，。依次类推，（v v2 2）=3=3，（v v3 3）=1=1于是，最短路经过点于是，最短路经过点v v3 3，v v1 1

52、。这样，从。这样，从v v1 1到到v v8 8的最短路是（的最短路是（v v1 1，v v3 3，v v2 2，v v5 5，v v8 8）。同理，可）。同理，可以求出从以求出从v v1 1到任一点到任一点v vi i的最短路，显然不存在从的最短路，显然不存在从v v1 1到到v v9 9的最短路。的最短路。 （二）逐次逼近法（二）逐次逼近法适用于网络中带负权的边，求指定点 v1 到网络中任意点的最短路 基本原理基本原理 如果v1 到vj 的最短路总是沿着该路从v1先到某一点vi ，然后再沿边(vi , vj)到达vj ，则v1 到vi的这条路必然也是v1 到v i的最短路。 步骤步骤 若令

53、P1j表示从v1 到vj 的最短路长， P1i为v1 到vi的最短路长，则必有下列方程 用迭代法解这个方程。 开始时令即用v1 到vj 的直接距离做初始解，若v1 到vj 间无边，则记v1 到vj 的最短路长为+ 。), 2 , 1(1)1(1njlPjj )(min11ijiijlPP 从第二步起，使用迭代公式求 ，当进行到第t步，若出现则停止， 即为点v1 到各点的最短路长。), 3 , 2(min)1(1)(1nklPPijkiikj )(1kjP), 2 , 1()1(1)(1njPPtjtj ),2 , 1()(1njPtj 递推公式中的 实际意义为从v1 到vj 点、至多含有 k-

54、1个中间点的最短路权，所以，在含有n 个点的图中，如果不含有总权小于零的回路，求v1 点到任一点的最短路权，用上述算法最多经过n-1次迭代必定收敛。如果图中含有总权小于零的回路，最短路权没有下界。)(1kjP例10 （见书本P253），求图8-34中，V1点到各点的最短路。254-364-3372-1-24解：全部计算过程用表表示如下： 最短路问题的应用设备更新问题设备更新问题 某工厂使用一台设备，每年年初都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费，及不同机器役龄时的残值和维修费如下表所示。项目第1年第

55、2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210 此问题可用动态规划方法求解。下面介绍用最短路径此问题可用动态规划方法求解。下面介绍用最短路径方法求解。方法求解。 令令Vi表示第表示第i年年初，边（年年初，边（ Vi， Vj ）表示在第）表示在第i年购买年购买一台设备，一直使用到第一台设备，一直使用到第j-1年年末。边（年年末。边（ Vi， Vj ）上的权表示在第上的权表示在第i年购买一台设备，一直使用到第年购买一台设备，一直使用到第j-1年年末所花出的总费用，于是设备更新问题变为求图年年末所花出的总费用，于是设备更新问题

56、变为求图8-35中点中点 V1到到 点点V6的最短路。的最短路。121314151559213020192840294122V1V2V3V4V5V6图图8-35计算过程用表表示如下：所以最优策所以最优策略为在第一略为在第一年和第三年年和第三年年初各购买年初各购买一台新设备一台新设备为最优策略为最优策略，总费用为，总费用为49.121314151559213020192840294122V1V2V3V4V5V6 例例12的分析（见的分析（见P256） （三）（三）FloydFloyd算法算法用于求解任意两点之间的最短路.算法的基本思想及步骤算法的基本思想及步骤（1 1） 先写出网络的权矩阵先写出

57、网络的权矩阵D=(dD=(dijij) )n nn,lij表示表示Vi到到Vj的距离。的距离。(,)ijijlV i V jEd其 他（2）D（k）=( dij(k)dij(k） =mindij(k-1),dil(k-1)+ dlj(k-1)（3） 若若D（k）=D（k-1），），的的 ，则算法，则算法终止。终止。例例13 13 求下图中任意两点间的最短路求下图中任意两点间的最短路 解解：用：用Floyd算法算法, ,首先写出其首先写出其( (对称的对称的) )权矩权矩阵阵A = (dij )88. . 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 8 1 0 2

58、 8 1 1 1 2 0 6 1 2 0 6 1 2 2 8 6 0 7 5 1 2 8 6 0 7 5 1 2 3 3 1 7 0 9 1 7 0 9 4 4 1 5 0 3 8 1 5 0 3 85 5 1 3 0 4 6 1 3 0 4 66 6 2 9 4 0 3 2 9 4 0 37 7 8 6 3 0 8 6 3 0D= 用用Floyd算法算法, ,首先写出首先写出D D（1 1） 如下如下 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 8 1 3 9 10 0 2 8 1 3 9 10 1 1 2 0 6 3 1 4 8 9 2 0 6 3 1 4

59、8 92 2 8 6 0 7 4 1 2 5 8 6 0 7 4 1 2 53 3 1 3 7 0 12 8 9 12 1 3 7 0 12 8 9 124 4 3 1 4 12 0 3 7 8 3 1 4 12 0 3 7 85 5 9 4 1 8 3 0 3 6 9 4 1 8 3 0 3 66 6 10 8 2 9 7 3 0 3 10 8 2 9 7 3 0 37 7 9 5 12 8 6 3 0 9 5 12 8 6 3 0D(1)= 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 7 1 3 6 10 11 0 2 7 1 3 6 10 111 1 2

60、0 5 3 1 4 7 9 2 0 5 3 1 4 7 92 2 7 5 0 7 4 1 2 5 7 5 0 7 4 1 2 53 3 1 3 7 0 5 7 9 12 1 3 7 0 5 7 9 124 4 3 1 4 5 0 3 6 8 3 1 4 5 0 3 6 85 5 6 4 1 7 3 0 3 6 6 4 1 7 3 0 3 66 6 10 7 2 9 6 3 0 3 10 7 2 9 6 3 0 37 7 11 9 5 12 8 6 3 0 11 9 5 12 8 6 3 0D(2)= 求出求出D D（2 2） 如下如下 0 1 2 3 4 5 6 70 1 2 3 4 5 6