(3.3)-第三章 规划模型数学建模

第三章规划模型11.线性规划模型2.运输问题3.指派问题4.动态规划5.非线性规划6.多目标规划第一节1.线性规划问题及其标准型线性规划模型2.非标准问题的转化4.案例分析5.蒙特卡洛相关方法的介绍2.Matlab优化工具第一章23一、线性规划问题及其标准型线性规划问题的提出：设某工厂使用机床甲、乙生产A、B两种产品，每生产A一吨需使用设备甲6小时，设备乙2小时，可得利润300元，每生产B一吨需使用设备甲6小时，设备乙3小时，可得利润400元。设备甲每天至多可工作20小时，设备乙每天至多可工作12小时。问每天应当生产A、B各多少吨，才能使总利润最大？

4解：设该厂每天生产产品A、B的产量分别为（吨）和（吨），所得到的总利润为z（元）。（1）确定目标函数：由题意知生产一吨A可得利润300元，生产一吨B可得利润400元，则总利润为：（2）确定约束条件：（i）生产时间约束：

（ii）产品产量不能为负数

可建立数学模型为：

目标函数：

约束条件：5

由此可得出线性规划问题的定义为：1.定义线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题.

线性规划问题是数学规划的重要分支，其特征就是在满足一组线性约束和变量非负的条件下，求多变量线性函数值（最大值或最小值）.这一特征决定了左右两边的线性规划模型可以化为相同的标准形式，这样就可以采用固定的方法求解.62.标准形式目标函数均为非负值.约束条件7若令线性规划问题的标准形式可写为：目标函数约束条件8二、非标准形问题的转换1.目标函数求极小值，即为，等价于求2.当右端的项时，只需将等式两端同以,则等式右端项．3.约束条件为不等式.当约束条件为时，如可以令则此约束条件就成为

4.取值为无约束的变量.若的取值无约束，则令，其中．5.当时，就令，即有．9三、线性规划问题中的Matlab求解8线性规划的目标函数和约束函数标准形式可写为：其中f,x,b,beq,lb,ub为向量，A，Aeq为矩阵。函数linprog格式：[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)11

注：X表示返回决策向量的取值，fval表示返回目标的最优解，exitflag>0表示函数收敛于解x，

exitflag=0表示超过函数估计值或迭代的最大数字，options为指定优化参数选项。四、案例分析12例1：一贸易公司专门经营某种杂粮的批发业务.公司现有库容量5000吨的仓库．1月1日，公司拥有库存1000吨杂粮，并有资金20000元．估计第一季度杂粮价格如下表所示，如果买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望季度末库存为2000吨，问应当采取什么样的买进和卖出政策，才能使三个月总的获利最大？进货价/元出货价/元一月2.853.10二月3.053.25三月2.902.95

问题分析

（1）确定决策变量：要确定每个月买进多少，卖出多少，故设：

一、二、三月买进的杂粮吨数分别为分别为

一、二、三月卖出杂粮的吨数分别为

13（2）确定目标函数：（3）确定约束条件：依题意，共有四类约束即存货约束、库容约束、资金约束、期末库存约束。

②库容约束：由于库容为5000吨，那么每个月的存货数量不能超过5000吨，不妨设贸易公司每个月都在月底进货，或者是当月在将杂粮卖出以后再进货，这样就会减少库存容量，这个假设是合理的．那么库存容量约束为

14①存货约束：由于当月买进的杂粮只能在下月出售，故每个月卖出的杂粮不能超过上个月末的存货量，即得到存货约束为15③资金约束：贸易公司的资金除了初始的以外，每个月都要出售杂粮回收资金，在回收资金以后，再进杂粮，每个月进杂粮的数量不能超过其拥有资金能购买的杂粮数量，即得资金约束为：

④季末库存：题中要求季末的库存为2000吨，得到关系式：

16显然，每个月出售的杂粮数和买进的杂粮数不能为负，即：综上所述，该公司的杂粮采购与销售计划的线性规划数学模型即为17用Matlab编写程序如下：

clearclc

f=[-2.85,-3.05,-2.9,3.1,3.25,2.95];

f=f’;f=-f;%价值向量，并转化为求最小值时对应的价值向量

A=[0,0,0,1,0,0;-1,0,0,1,1,0;-1,-1,0,1,1,1;1,0,0,-1,0,0;1,1,0,-1,-1,0;2.85,0,0,-3.1,0,0;2.85,3.05,0,-3.1,-3.25,0;2.85,3.05,2.9,-3.1,-3.25,-2.95];

b=[1000;1000;1000;4000;4000;20000;20000;20000];%线性不等式约束

aeq=[1,1,1,-1,-1,-1];beq=1000;%线性等式约束

lb=zeros(6,1);%函数值下限

[x,y]=linprog(f,A,b,aeq,beq,lb);%输出x中后三项分别代表y1,y2,y3

x=reshape(x,1,6),-y%重新组合矩阵x，取负求得原本的最大值

结果如下：

x=

1.0e+03*

5.00000.00002.00001.00005.00000.0000

y=

-700.0000

18用Lingo编写程序如下：

model:

sets:

col/1..6/:c,x,aeq;!x中后三项代表y1,y2,y3；

row/1..8/:b;!不等式约束条件中位于右方的常数项;

link(row,col):a;!不等式约束条件中的位于左方的x的系数;

endsets

data:

c=-2.85,-3.05,-2.9,3.1,3.25,2.95;

a=0,0,0,1,0,0,-1,0,0,1,1,0,-1,-1,0,1,1,1,1,0,0,-1,0,0,1,1,0,-1,-1,0,2.85,0,0,3.1,0,0,2.81,3.05,0,3.1,3.25,0,2.85,3.05,2.9,3.1,3.25,2.95;

b=1000,1000,1000,4000,4000,20000,20000,20000;

aeq=1,1,1,-1,-1,-1;

enddata

max=@sum(col:c*x);!目标方程;

@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));!不等式约束条件;

@sum(col:aeq*x)=1000;!等式约束条件

@for(col(i):x(i)>=0);!函数下限约束;

end19

五、蒙特卡洛相关方法的介绍

20

蒙特卡洛方法也称为计算机随机模拟方法，它是基于对大量事件的统计结果来实现一些确定性问题的计算。使用蒙特卡洛方法必须使用计算机生成相关分布的随机数，Matlab给出了生成各种随机数的命令。例：与x轴在第一象限围成一个曲边三角形。设计一个随机实验，求该图形面积的近似值。

解：设计的随机试验的思想如下：在矩形区域[0,12]x[0,9]上产生服从均匀分布的n个随机点，统计随机点落在曲边三角形的频数，则曲边三角形的面积近似为上述矩形的面积乘以频率。

21计算的Maltab程序如下：

clc,clearx=unifrnd(0,12,[1,10000000]);y=unifrnd(0,9,[1,10000000]);Pinshu=sum(y<x.^2&x<=3)+sum(y<12-x&x>=3);Area_appr=12*9*pinshu/10^7运行结果在49.5附近，由于是随机模拟，因此每次的结果都是不一样的。第二节1.平衡运输问题2.不平衡运输问题运输问题

第一章

3.有转运的情形22一、平衡运输问题1.平衡运输问题的数学模型

有某种物资有

个产地

，生产某种物资，供给个销地,从第

个产地向第

个销地运输每单位物资的运价为,具体见表3.3.

已知产地

的供应量为

;销地

的需求量为

,且总产量等于总销售量,即

设产地

运到销地

的物资为

个单位，求使总运费最小的运输方案。23表3.3产地Ai

运到销地Bi

的单位运费表

销地产地产量销量24由题意，可建立如下线性规划模型25可作如下变换，将原线性规划问题化为矩阵形式：26则运输问题用矩阵形式表示即为：其中,且272.运输问题具有的一些特点：1、约束条件的系数矩阵中元素等于0或1；

2、约束调节的系数矩阵的每一列有两个非0元素；这对应于每一个变量在前个约束方程中出现一次，在后个方程中出现一次；

3、所有的约束条件为等式；

4、各产地量之和等于各销地量之和；283.求解运输问题的方法——表上作业法确定初始基可行解最优解的判定方案的调整

最小元素法、伏格尔法闭回路法、位势法闭回路调整法29STEP1

确定初始基可行解

最小元素法

最小元素法的基本思想是优先满足单位运价最小的供销业务.

首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务.同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止.30

销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案表运价表31例题以此，得到一初始方案：X13=4

，X14=3，

X21=3，X23=1，X32=6，

X34=3（有数格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：（ⅰ）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；（ⅱ）如果填上一个变量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待.初始方案运费Z0=3×1+6×4+4×3+1×2+3×10+3×5=8632STEP2

最优解的判定闭回路法

在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数.在运输问题中，每个空格对应一个非基变量.因此，我们需要求出每个空格的检验数.由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案.33

①对方案表中每一空格，确定一条由空格出发的闭回路。

闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。B1B2B3B4A143A231A363

可以证明，对每一个空格都存在而且唯一存在这样一条封闭回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A36335②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。B1B2B3B4A143A231A363

11=3-1+2-3=1

22=9-2+3–10+5–4=1

31=7-5+10–3+2–1=10

12=11-10+5-4=2

24=8–10+3–2=-1

33=10-5+10-3=1236③当所有空格检验数

σij≥0则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整。

若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。

σij具有确切的经济意义，它表示由往增运1单位时，引起的总运输成本的变化数。

B1B2B3B4A143A231A36337STEP3

方案的调整

若在检验数上有某空格的检验数为负，则可改进方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行调整，即在保持方案可行的条件下，尽量增加空格上的运量。闭回路调整法38

从σij

为最小负值的空格出发.对其闭回路上的奇数顶点运量增加θ,偶数顶点的运量减少θ(这才能保证新的平衡)，其中调整量θ为该空格闭回路中偶数顶点的最小值.B1B2B3B4A143A231A363注：若闭回路的偶数顶点中同时有两个格以上运量为θ，则调整后其中一个变空格，其余填0。（保证基变量个数不变）B1B2B3B4A152A231A363

24

=-1，作x24

的闭回路，调整数=1，调整得39再用闭回路法或位势法求各空格的检验数，B1B2B3B4A152A231A363x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余的xij=0总运费为f=5×3+2×10+3×1+1×8+6×4+3×5=85销产B1B2B3B4A102A221A3912表中的所有检验数都非负，故上表中的解为最优解.检验数表方案表401、产量大于销量

对于产大于销问题

，可得到下列运输问题的模型：二、不平衡运输问题41

可增加一个假想的销地

,其销量为：

某个产地

运到这个假想销地

的物资量

，实际上就意味着将这些物资在原产地贮存，其相应的运价

，转化为产销平衡的问题，其数学模型为：42

对于销大于产问题

可增加一个假想的产地,其产量为：其相应的运费为

，上述不平衡问题就转化为平衡的问题：

2、销量大于产量43三、有转运的情形1.有转运问题的描述如果某产品从生产地先运到某中间站，或者是先运到另外一个产地，或者是先运到另外一个销地，然后再运往目的地，这样的情形应该如何处理呢？这就是有转运的情形。442.转运问题的解决方法

解决这类问题，我们首先要将其化为无转运的运输问题。

假设有个产地

和

个销地,另外还有

个中转地，这

个地点既可以作为产地也可以作为销地。我们假设：

：第个地点的产量；：第个地点的销量；：第个地点的转运费；：由地点运到地点的产品量；：由地点到地点的单位运价．45

将产地、销地、中转地同时编号，产地在前，销地排第二，中转地在后，则有为了方便，我们只考虑平衡运输问题，即则有转运的运输问题可以被认为：（1）产地

可以看成为一个销售量为的销地，产量为

的产地；（2）销地

可以看成是一个产量为的产地，销售量为

的销地；（3）中转站可以看成是一个产量和销量都为的产地和销地。46因此，得到的数学模型为：47四.案例分析

某种产品有三个产地销售到四个地点,由各产地运到各销售地的运价表3.4，问如何调运才能使运价最小？

销量产地产量412411162103910851622销量8141214481、符号定义：为运往的运费，为运往的供应量为地的产量，为地的销量48492、模型的建立50sets:Sale/1..4/:d;Position/1..3/:e;link(position,sale):G,x;!G为3*4的矩阵;endsetsdata:G=412411210398516;d=8,14,12,14;e=16,10,22;enddatamin=@sum(link:G*x);!目标函数;@for(Sale(j):@sum(position(i):x(i,j))=d(j));！销量条件;@for(Position(i):@sum(sale(j):x(i,j))=e(i));!产量条件;@for(link(i,j):x(i,j)>=0);@for(link:@gin(x));！限制X为整数end3、模型的求解①利用所给数据，将这一模型输入Lingo:②利用所给数据，将这一模型输入Matlab:clearclcc=[4,12,4,11;2,10,3,9;8,5,1,6];c=c';c=c(:);%取c的转置；c取矩阵内所有数值Aeq=zeros(7,12);%将a赋值为7*12的零矩阵%fori=1:3Aeq(i,4*i-3:4*i)=1;Aeq(i+3,i:4:12)=1;Aeq(7,4:4:12)=1;%等式系数向量endbeq=[16;10;22;8;14;12;14];lb=zeros(12,1);intcon=1:12;%lu取12*1的零矩阵；intcon从1取到12%[x,y]=intlinprog(c,intcon,[],[],Aeq,beq,lb;[]);x=reshape(x,[1,12]),y%重新调整矩阵的行数、列数%51结果为x=

00124800201408y=244第三节

第一章指派问题1.指派问题的数学模型2.指派问题的匈牙利算法3.一般指派问题4.整数规划52一、指派问题的数学模型

设有

个人被分配去完成

项工作，每人完成一项工作．因各人的专长不同，每个人去完成同一项工作所花费的时间也不相同．设

是第

个人完成第

项工作所花费的时间，现在应当如何分配他们的工作，才能使完成任务所花费的总时间最少，这就是指派问题或分派问题。

53为指派问题的系数矩阵．其中称矩阵为建数学模型，我们引入变量，若指派第

人完成第项工作，则否则

，其中

．，54于是指派问题的数学模型为上述模型中若将条件改为

型就是一个特殊的运输问题：是的一个特殊运输问题．，则模55二、指派问题的匈牙利算法定理1

将系数矩阵中的某一行（列）中的每一个元素都减去常数，得到一个新矩阵．若以为系数矩阵的指派问题的最优解为，则原指派问题的最优解也为，且对任意的可行解都有56证明设从的第行减去元素，得到由于对任意的可行解都有，故有57由于是以为系数矩阵的指派问题的最优解，所以对于任意的可行解都有即故从而为原问题的最优解．58定理2

将系数矩阵的第行各元素减去，第列各元素减去常数常数得到一个新矩阵，即，若，中有个不同行不同列的零元素，即有且的一个排列使．取矩阵，其中，其余的，则就是以为系数矩阵的指派问题的最优解，也是原指派问题的最优解．59证明

由已知条件可知而对于任意的可行解

，由于

，故另明显地有故为新指派问题的最优解，根据定理一，它也是原指派问题的最优解．60

根据定理1和定理2，我们将指派问题的匈牙利算法表述如下：(1)变换系数矩阵．先将系数矩阵的每一行的所有元素都减无本行中的最小元素，然后将每一列的所有元素都减去本列中的最小元素．这样所得的变换矩阵的每一行每一列至少有一个“0”元素,而且没有负元素．61

(2)在变换后的系数矩阵中确定独立的“0”元素

（即不同行不同列的“0”元素）．若某行（或某列）

只有一个“0”元素，则对此“0”元素画

把位于此“0”元素的同行同列的其他“0”元素划去

（记为，同时）．若遇到所有的行列中的“0”元素都不只

一个，我们任意选取一个“0”元素加，同时划

去其同行同列的其他“0”元素，如此反复进行，直到62

所有的“0”元素都被画上

或者是划去为止．画上的“0”元素就是矩阵中独立的“0”元素．如果独立的“0”元素有

个，则令解矩阵中与独立“0”元素对应的位置上的变量取1，其他变量取0，此对应的指派方案总费用为0，从而一定是最优解．如独立的“0”元素少于

列中没有画

的“0”元素，采取如下的步骤进行变换：个，即至少有一行或者一63①对没有的行打；②对有的行中的所在的列打；③对有的列中的所在的行打；④重复②③的步骤，直到不能再打为止；64

(3)继续变换矩阵．找出未被直线覆盖的元素中的最小元素，令打

的行中的所有元素都减去这个最小

元素，打

的列元素都加上这个最小元素．则原先选⑤将没有打的行和已经打的列画直线，这样所得的直线集合就是覆盖住矩阵中所有“0”元素的最小条数直线集合．中的“0”元素不变，而未被直线覆盖的元素中至少有一个元素已经变为“0”元素，且新矩阵的指派问题与原指派问题有相同的最优解．反复上面的步骤，直到找出个独立的“0”元素为止．例6求下面系数矩阵对应的指派问题的最优解．

解我们将第一行减去7，第二行减去6，第三行减去7，第四行减去6，第五行减去4，就得到行列式

.65则上面矩阵中的第一、二、四行和第一列被直线覆盖，未被直线覆盖的行列中的最小元素是2，故将第三、五行的元素减去2，第一列的元素加上2，得到

故得到相应的解为，

其他的,661．最大化指派问题若目标函数是求最大不是求最小，设三、一般指派问题令，则以

为系数矩阵的最小化指派问题就与原问题同解．，2．人与事的数目不等

若人多于事或者是事多于人,则添上相应数目的虚拟“事”或者是虚拟“人”，使得人与事的数目相等，67不过人做虚拟的事或者是虚拟的人做事的费用都为0．3．一个人可以做几件事若一个人可以做几件事，则将该人化为相同的几个人，这几个人做事的费用也完全相同．4．某事一定不能由某人来做某事一定不能由某人来做，可取此人做该事时的费用是一个足够大的数．68案例分析

背包问题背包问题是近年来运筹学界研究的热点问题，在材料切割、货物装载、预算控制、战略计划、信息加密等问题中有着广泛的应用。一般的背包问题是假设一个背包有一个最大承重限制，设承重量为有件物品可供选择，每个物品的重量分别是每件物品的价值是若在不超过背包承重限制的条件下，在这件物品种中选择哪些装入背包中才能使背包中的所有物品价值最大？69

背包问题中如果每种物品的数量不是一一件，而是大于1的整数件，这种背包问题叫多重背包问题。多重背包问题中的决策变量不再是0-1整数变量而是小于等于的非负整数变量，其模型可描述如下:70clearclcP[-p1,-p2,-p3,-p4,...,-pn];%目标系数矩阵,标准形式Intcon=1:n；%整数约束变量位置A=[w1,w2,w3,w4,...,wn];%约束条件矩阵B=W;lb=zeros(n,1);%变量xi大于等于0[x,y]=intlinprog(P,intcon,A,B,[],[],lb,[]);%xi最大约束值未知，ub为空X=reshape(x,n,1),y=-y将这一模型输入Matlab:71四、整数规划

1.定义：数学规划中的变量(部分或全部)限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

2.分类：如不加特殊说明，则一般指整数线性规划。整数线性规划模型大致可分为两类:72

(1)变量全限制为整数时，称纯(完全)整数规划。(2)变量部分限制为整数时，称混合整数规划。3.特点：(1)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况。①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。③有可行解(当然就存在最优解)，但最优解值变差。(2)整数规划最优解不能按照实数最优解简单取整而获得。73案例分析

问题某班准备从

名游泳队员中选择

人组成接

力队，参加学校的混合冰接力比赛.名队员

种泳姿的百米平均成绩如表

所示，问应如何选拔队员组成接力队如果最近队员丁的蛙泳成绩有较大退步，只有;而队员戊经过艰苦训练自由泳成绩有所进步，达到,组成接力队的方案是否应该调整例混合泳接力队的选拔74

表1

名队员种泳姿的百米平均成绩

甲乙丙丁戊蝶泳1’06’’857’’21’18’’1’10’’1’07’’4仰泳1’15’’61’06’’1’07’’81’14’’21’11’’蛙泳1’27’’1’06’’41’24’’61’09’’61’23’’8自由泳58’’653’’59’’457’’21’02’’4

问题分析从名队员中选出人组成接力队，每人一种泳姿，且人的泳姿各不相同，使接力队的成绩最好.容易想到的是穷举法，组成接力队的方案共有种,逐计算并作比较，即可找出最优方案.75显然这不是解决这类问题的好办法，随着问题规模

的变大，穷举法的计算量将是无法接受的.可以用变量表示一个队员是否人选接力队，从

而建立这个问题的规划模型，借助现成的数学软件求解.

模型的建立与求解记甲乙丙丁戊分别为队员记蝶泳仰泳、蛙泳、自由泳分别为泳姿.记队员i的第

j种泳姿的百米最好成绩为,即有7666.857.2787067.475.66667.574.2718766.484.669.683.858.65359.457.262.4引入变量，若选择队员参加泳姿的否则记根据组成接力队的应满足两个约束条件：1.每个人最多只能入选种泳姿之一，即对于应有比赛，记要求，772.每种泳姿必须有

人而且只能有

人入选，即对应有当队员入选泳姿时，表示他的成绩，否则.于是接力队的成绩可表示为

此为该问题的目标函数.78综上，这个问题的规划模型可写作79利用所给数据，将这一模型输入Matlab:c=[66.8,75.6,87,58.6;57.2,66,66.4,53;78,67.8,84.6,59.4;70,74.2,69.6,57.2;67.4,71,83.8,62.4];c=c‘;%转置成与x对应的系数c=c(:);intcon=1:20;%变量总数a=zeros(5,20);%先分配空间，再赋对应值fori=1:5%开始对每一行赋值a(i,(i-1)*4+1:i*4)=1;%根据约束条件列出矩阵系数endb=ones(5,1);aeq=zeros(4,20);fori=1:4aeq(i,i:4:20)=1;%根据约束条件列出矩阵系数endbeq=ones(4,1);lb=zeros(20,1);%整数变量范围0、1ub=ones(20,1);[x,z]=intlinprog(c,intcon,a,b,aeq,beq,lb,ub);80LP:

Optimal

objective

value

is

253.20000

x=reshape(x,4,5)，z%此时x列代表人，行数代表事情

01000001000001010000

求得结果为，其他变量为

，即应当选派甲乙丙丁四人组成接力对，分别参

加自由泳、蝶泳、仰泳、蛙泳比赛.成绩为81将这一模型输入Lingo，其程序为

:model:sets:model:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.470,74.2,69.6,57.2,67.4,71,83.8,62.4;82/176输出结果如下：Globaloptimalsolutionfound.Objectivevalue:253.2000Objectivebound:253.2000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:083/176enddata

min=@sum(link:c*x);（目标函数）

@for(person(i):@sum(position(j):x(i,j))<=1;);（约束条件）

@for(position(i):@sum(person(j):x(j,i))=1;);

@for(link:@bin(x));

End

84讨论考虑到丁、戊最近的状态，c43由原来的69.6s变为75.2s,c54由原来的62.4s变为57.5s,讨论对结果的影响，对于整数规划模型一般没有与线性规划相类似的理论，于是我们用c43,c54的新数据重新输人模型即可求解得到:x21=x32=x43=x54=1，其他变量为0,成绩为257.7s=4'17"7.即应当选派乙丙丁戊4人组成接力队，分别参加蝶泳、仰泳、蛙泳、自由泳的比赛.

第四节动态规划

第一章1.基本概念和基本理论2.基本方程3.基本思想4.基本步骤5.基本应用85A35495431571584644242697512引例

最短路线问题如图，给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由A到F的铺管线路，使总距离为最短（或总费用最少）。861.基本概念和基本理论

动态规划是数学规划的一个分支，是用来解决多阶段决策过程的最优化问题的一种方法。主要涉及以下八个基本概念：(1)阶段：将所给的问题根据时间或者是空间划分成若干个相互联系的阶段，以便按次序去求解。k表示阶段变量，n表示总的阶段数。

引例可以分为五个阶段，k分别等于1、2、3、4和587状态具有无后效性引例中S2可取三个值，B1、B2、B3(2)状态：各阶段开始时的客观状况，称为状态。它既是前一阶段的一个终点，也是这一阶段的一个起点。描述状态的变量称为状态变量，常用表示第k阶段的状态变量。状态变量的取值集合称为状态集合，用

表示。

88(3)决策：当阶段和状态决定以后，从该状态到下状态的某状态的选择称为决策.描述决策的变量称为决策变量，用或是来表示第k阶段处于状态时的决策变量.决策变量的取值范围称为允许决策集合，记为或者是，.引例中，在第二阶段，若从B1出发，则可作两种不同的决策，而其允许决策集合为UK（B1）={C1,C2}，若选取的点为C2，则u2（B1）=C2(4)策略：策略是一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列，称为k子过程策略，记为

。当k等于1时，此决策函数序列称为全过程的一个策略，简称为策略。使问题得到最优解的策略称为最优策略。

89(6)效用函数：在状态时所采用决策所得的效用

称为效用函数。(7)目标函数：用于衡量所选定策略优劣的函数,又叫指标函数。(5)状态转移方程：描述状态转移规律的函数称为状态转移方程。用来表示状态转移方程。例如引例中，vk(sk,uk)表示在第k阶段由点sk至点sk+1=uk(sk)的距离

90(8)最优化原理：一个过程的最优化策略具有的性质，无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的决策也应当构成最优策略。

对于要构成动态规划模型的指标函数，应具有可分离性，且满足递推关系。即

可以表示为

的函数:可分离性

在实际问题中，很多指标都满足这个性质。常见的指标函数：

91A35495431571584644242697512

如果一条路线是最短路线，那么从这条路线任一点开始到终点的子路线，也必是最短路线。由此性质，寻找最短路径的方法，就是从最后一段开始，用从后往前逐步递推的方法，求出各点到G点的最短路径，最后求得A到F的最短路线。所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。92k=1，表示第一阶段：S1={A};k=2，表示第二阶段：S2={B1,B2,B3};k=3，表示第三阶段：S3={C1,C2,C3};k=4，表示第四阶段：S4={D1,D2,D3};k=5，表示第五阶段：S5={E1,E2};首先

k=5，第五阶段时，最优路径为E1→F

93

k=4，第四阶段时，最优路径为D1→E2最优路径为D2→E1最优路径为D3→E2

94以上述方法依算出第三、二、一阶段的最优路径。经过回溯得到从A到F的最短路径为：总长度为14.

由此可以看出，在求解的各阶段，都利用了第k段和第k+1段的如下关系：第二个式子为临界条件。

95引例程序：

clearclc

q=cell(6,3);%设置单元矩阵，存储最短路上的点

v=zeros(6,3);

fork=5:-1:1

forx=1:3;

[v,path]=objF_1(k,x,v);%求最短路程;并存储在V中

q=tranF_1(k,x,path,q);%求最短路径，存储在q中

end

end

y=find(v==min(v(1,:)));%找到第一阶段对应的最短路时的状态

road=q{1,y};%找到最终的最短路径

shortline=min(v(1,:));%找到最短路程

road,shortline

96functionu=DecisF_1(k,x)%u为输出在k阶x状态下的决策向量

a=[0,0,0,0,0,0,0,0,0;3,0,0,5,0,0,4,0,0;9,4,0,5,3,1,0,5,7;1,8,4,5,4,4,0,6,2;4,6,7,2,9,5,0,0,0;1,2,0,0,0,0,0,0,0];%两点间的路程

a(find(a==0))=inf;%对不存在的路径赋予无穷大%

fori=1:3%i为在x状态下下一段的对应的状态

u(i)=a(k,3*x+i-3);%k阶段在x状态变量向下一阶段时状态i的决策

end

end

function[v,path]=objF_1(k,x,v)%求得在k阶段时x状态下的目标即指标函数

b=[];

forj=1:3%j为对应的上一阶段的状态

97

u=DecisF_1(k+1,j);%输出上一阶段某一状态时的决策向量

b(j)=v(k+1,j)+u(x);%求得上一阶段不同状态时所得到的当前状态的路程值

end

v(k,x)=min(b);%求得当前状态的最短路程

path=find(b==min(b));%记录最短路程时所经过的点

end

functionq=tranF_1(k,x,path,q)%存储不同阶段不同状态下最短路程所对应的路径

q{k,x}=[x,q{k+1,path}];

end

结果如下：road=

12112

shortline=

14982.基本方程根据最优原理，可以得出动态规划递推方程。设

表示在k阶段，以

为初始状态出发到最终状态时所使用最优策略所得的最佳效益值，则可以得到递推方程：式中可取为min或max

993.基本思想可以将动态规划方法的基本思想归纳为三点：(1)动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。(2)在多阶段决策过程中，动态规划方法既是把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。(3)在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。100(1)将问题的过程划分为恰当的阶段；(2)正确的选择状态变量，使它既能描述过程的演变，又要满足无后效性；(3)确定决策变量

及每阶段的允许决策集合；(4)正确写出状态转移方程；(5)确定阶段目标函数，建立动态规划基本方程。5.基本应用

动态规划的研究对象是多阶段决策问题，它广泛用于经济管理，最优路径，资源分配，库存管理，排序，生产计划等问题上。4.基本步骤101例.设有600万资金用于四个工厂的扩建。已知每个工厂的利润增长额同投资额的大小有关，详细数据见表一。问应如何确定对这四个工厂的投资额，使工厂总的利润增长额为最大。

01002003004005006001020426075859020

2545576570733018396178909540284765748085投资额利润增长额工厂102

解

把对四个厂的投资依次看成4个阶段的决策过程，对第k个工厂投资看作第k个阶段的决策，k=1,2,3,4。符号说明

103

01002003004005006000000100028281002000284747200300028476565300400028476574744005000284765748080500600028476574808585600

k=4时，得到下表：表一104

010020030040050060000+0001000+2818+02802000+4718+2839+04703000+6518+4739+2861+0672004000+7418+6539+4761+2878+0893005000+8018+7439+6561+4778+2890+01083006000+8518+8039+7461+6578+4790+2895+0126300

k=3时，得到下表：表二105得到下表：表三

010020030040050060000+0001000+2825+02802000+4725+2845+0531003000+6725+4745+2857+073100或2004000+8925+6745+4757+2865+092100或2005000+10825+8945+6757+4765+2870+01141006000+12625+8045+8957+6765+4770+2873+0134200

k=2时，106

01002003004005006006000+13420+11442+9260+7375+5385+2890+01340或100或200

k=1时，得到下表：表四最优解或总利润最大增长额为134万元。或或107例题程序：

clcclear

c=[0,20,42,60,75,85,90;0,25,45,57,65,70,73;0,18,39,61,78,90,95;0,28,47,65,74,80,85];

%不同厂不同投资的收益

a=zeros(7,7);x=zeros(4,6);

fork=4:-1:1

fori=7:-1:1

b=0;

forj=1:i

a(i,j)=max(c(k,j)+a(i-j+1,:));

%当前状态的总投资额及对当前厂的不同投资下的最大收益

ifj>1

ifa(i,j)>a(i,j-1)

b=j-1;

%记录当前状态下当前的投资的最大化投资方案，储存在b中

end

end

108end

x(k,i)=b;

end

end

[m,n]=find(a==max(max(a)));d=[];

%寻找最终最大收益所在的位置，n为当前状态对当前厂的的投资量

fork=1:4%按照从前往后的不同阶段逐阶段寻找最大收益投资方案，并储存在d中

fori=1:3

ifk==1

d(k,i)=n(i,1)-1;

end

ifk>1

m(i,1)=m(i,1)-d(k-1,i);

d(k,i)=x(k,m(i,1));

end

end

end

运行结果：d=

012

211

332

111109第五节非线性规划

第三章1.非线性规划的概念2.无约束非线性规划的求解3.约束非线性规划的求解4.几种特殊的非线性规划5.案例分析110一、非线性规划的概念定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题。

一般形式:

其中是维欧氏空间中的点(向量)，而

中至少有一个是非线性函数。记可行域为

。111二、无约束非线性规划的求解1.一维搜索法一维搜索法是用来求解单变量最优化问题的近似方法。即求解问题：

若，对任何都有，称为全局最优解.

若，对任何都有，称为局部最优解。

是

的邻域。112

设是定义在区间上的单峰函数，在区间取两点，不如假设,则最优点必定落在区间中。

令，即

,令经计算，得出λ=0.618

黄金分割就是以0.618的比率逐步缩小搜索区间，最后得到最优点的近似值。黄金分割法：1132.高维无约束问题高维无约束极值问题可以表述为：求解方法有两类：由于利用到解析函数的解析性质，称为解析法，这类方法中常用到的有梯度法、牛顿法等；因为在迭代过程中仅用到函数，而不用到函数的解析性质，称为直接法。114(1)梯度法（最速下降法）

定义3

若在中的某一开集中有一阶连续的偏导数，称向量为函数的梯度。定义4

若在上具有二阶连续偏导数，称矩阵为的黑赛矩阵梯度方向是函数增加最快的方向115

定义5多元函数的泰勒展开式：设有元函数在的某邻域内有连续的二偏导数，则有如下的泰勒展开式：其中

定理3设具有连续的一阶偏导，为的局部极值，则

定理4设在中有连续的二阶偏导数，且，正定，则为的严格局部极小值点．116具体步骤：给定初始点和允许误差，令k=1.计算，若，则停止迭代，最小点就是;否则，转入③．求，得到极小值，令，用k+1代替k转入②，继续迭代．117例

求解解,则，所以继续迭代：k123456211得到结果：取,初始点由得到.令因为118(2)模式搜索法

在每一轮的迭代中采用轴向移动和模式移动相结合，故称为模式搜索法.其步骤为：取点作为初始点，允许误差为

，对每个变量选定搜索步长，其中是第个分量。记，令．②从出发，依此对各分量进行搜索：若，记．否则，若，就记；若,，则记，即119

然后从出发对第二个分量进行类似的探索．一般地，从出发对个分量进行探索得到：其中.若,则转入③，否则转入④．③记，则为的下降方向．从出发，沿方向达到点，其中称为加速系数，我们取其为2，则这称为模式移动．以代替，转入②．120④检验是否有，若满足，则停止迭代，；否则，令，，以代替，代替，转入②继续．二、约束非线性规划的求解1．罚函数法121根据上述问题构造函数其中是一个充分大的正数，称为罚因子，函数称为罚函数。

从直观上看，由于很大,当时，不可能取得极小值，故只有当时，才会取得极小值。这样约束非线性规划问题就可以化为如下无约束非线性规划问题：1222.线性逼近法

该方法是将目标函数和约束条件作线性近似，所以称为线性逼近法，其具体步骤：定理5设问题的最小点存在，且(1)连续；(2)正数序列单调增加且趋于；(3)由上面所定义的函数存在最小点，且，则是问题的最小点，且.123然后求出最优解.①取初始点,精确度及初始步长,置k=1．②将目标函数和约束函数在处线性化，得线性规划问题③若,

,则转入④；否则，取代替转回②．④若，则;否则，用k+1代替k返回②．124三、几种特殊的非线性规划1.正定几何规划（简单情形）2.正定几何规划（一般情形）其中，，为任意实数．其中中的各项系数均为正数，为任意的实数．1253.符号几何规划4.二次规划其中为1或-1，，为任意的实数．126四、非线性规划问题的MATLAB求解

127

1.有约束的一元函数的最小值

单变量函数求最小值的标准形式为：使用fminbnd函数求值。函数fminbnd格式

[x,fval,exitflag,output]=fminbnd('fun',x1,x2,options)参数说明：

fun为目标函数的表达式字符串或MATLAB自定义函数炳；

返回自变量x在区间函数fun取最小值时x值；128

options为指定优化参数；

fval为目标函数的最小值；

exitflag为终止迭代条件；

output为优化信息；例计算下面函数在区间(-5，5)内的最小值和函数取最小值时x的值．解：>>[x,fval,exitflag,output]=fminbnd('(x^3+x^2-1)/exp(x)+exp(-x)',-5,5)x=-4.9999fval=-1.4840e+041292.无约束多元函数问题

多元函数最小值的标准形式为，其中x为向量，如，在MATLAB中使用fminsearch求其最小值。

函数

fminsearch：

格式

[x,fval,exitflag,output]=fminsearch('fun',x0,options)

参数说明：

x0为初始点，

fun为目标函数的表达式字符串或MATLAB自定义函数炳

options查optimset

fval为最优点的函数值

exitflag与单变量情形一致

output

与单变量情形一致130

例求的最小值点解：>>X=fminsearch('sin(x(1))+cos(x(2))',[0,0])结果为

X=-1.57083.1416或在MATLAB编辑器中建立函数文件

functionf=myfun(x)f=sin(x(1))+cos(x(2);保存为myfun.m，在命令窗口键入