数学规划1.doc

数学规划模型

一、 基本理论：
运筹学理论的重要组成部分——数学规划理论，是数学建模广泛运用的理论工具。求一个目标函数的极大或极小的优化模型，叫做数学规划。视决策变量有无约束条件而分别称做约束数学规划或者无约束数学规划。
问题形式：约束数学规划的一般形式是：

其中为向量，即；如果目标函数和约束条件中的函数都是线性函数，则称为线性规划；否则就称为非线性规划；如果变量限制取整数值，称为整数线性规划；如果决策变量限制只取0或1，则称为0-1规划；如果只限制决策变量中的部分变量取整数，则称为混合整数规划。如果同时考虑几个目标函数在某种意义下的最优化问题，则称之为多目标规划问题。
目标求解与结果：约束目标规划的求解首先应确定满足所有约束条件的点，本身称为可行解，可行解的点集称之为可行域。充分利用可行域中元素的基本性质，改变目标函数的取值形式，从而对目标函数的取值大小进行判断。如果使得在S上达到最小或最大值，则称为最优解，；函数值称为最优值。

二、 数学规划的计算求解方法
线性规划
基本形式：将下面的形式称之为标准形式

其他各种形式的线性规划问题都可以化成上述问题形式。这种问题的基本解法为单纯形法。这里不介绍单纯形法了，因为在MATLAB软件工具箱里有线性规划的程序

（1）单纯形方法手工解法的中心子块方法
根据线性规划的标准形式：作出表格形式

（底线）
右列
中心部位
A b
右下端
底行

0
CT

对上面的表格进行运算：底线以上部分进行行变换；底线以上的某一行乘上某个非零常数；底线以上的行进行倍加运算；把底线以上的行乘上常数后全部加到底行（包括右下端）。
上面的运算直到化到这样的形式：中心部位具有单位子块，即有一个m阶单位子块；右列元素全部非负；底行上对应于单位子块的列的位置处元素都为零；底行上其它元素非负。
此时可以从上表读出线性规划问题的最优解：单位子块中元素1所在列对应的变量取这个1所在行右列的数值。其它变量取零。而此时右下端处的元素的负值就是问题的最小值。

1947年美国运筹学家Dantzig创立的单纯形法就是在保证前三个特点不变的前提下，逐步调出第四个特点的步骤：

假设变到了如下的当前形式

-

进行如下的步骤：（1`）假设当前的表格满足前三个特点，现从底行负元素中任选一个，设为；（2）再从所选元素对应的列在底线以上的正元素中，按下列规则选取一个元素 ；（3）用行初等变换将处变为1，该列其它元素变为零。这时可以保证中心部位中仍有一个单位子块。这样的步骤进行到满足四个特点要求后就会得到最优解。
如果开始时没有满足前三个特点的表。可以用大M方法，进行人工构作，进行求解。下面举例说明：
例：求下面的线性规划问题：
，取很大的数M，把问题化为
由于M特别大，在新的问题中，达到最优解时必有，不然的话新问题的最小值将会大于原来问题的最小值，这是矛盾的。从而正好得到了原来问题的最小值。
表格计算的过程如下：
3 2 -3 1 0 6

1 -2 1 0 1 4

-3-4M 1 2+2M 0 0 10M
3 2 -3 1 0 6

1-2 1 0 1 4

-3 1 2 M M 0

1 -2/3 0 1/2 1/6 3

0 -4/3 1 1/2 -1/6 1

0 5/3 0 3/2+M 1/2+M 7
1 2/3 -1 1/3 0 2

0 -8/3 2 -1/3 1 2

0 3+8/3M -1-2M 14/3M 0 6-2M

这样就得到了最优解：,最小值为-7
（2） 线性规划的Matlab求解方法
首先将问题化为形式：
转化方式：；
先给矩阵进行赋值，然后调用命令
，得到最优解；再键入，得到最优值。
线性规划问题还需要进行灵敏度分析，即：分析问题中的一些 参数发生变化时，对最优值的影响程度大小。或者考虑，增加或 减少一些约束、增加或减少一些变量对于最优值的影响程度分析。
灵敏度分析可以用数学软件LINGGO进行。
2 无约束非线性规划
基本形式化为：
（1）局部极小点的必要条件是：在极小点处，函数的梯度为零：
(2)无约束极值的数值解法：从确定的某个初始点出发，去找 下一个点，它从某种意义上比上一个点更接近最优解。常用的一 个手段是，寻找函数值的下降方向，在这个方向上求出最小函数值，进而找出最优解，实现了一次迭代，如此下去就可以不断获得接近于最小值的解。
(3)常用的数值解法有：最速下降法；针对二次函数的共轭梯度 法；牛顿法；变尺度算法中的DFP算法；信赖域法等等。
(4)应用MATLAB解无约束非线性规划：
举例说明：求
解：首先定义函数

在命令窗口键入：
%给出初始点
%使用缺省参数

回车后即执行，执行完毕后键入：

得到最优解：

0，5000 -1.000
键入

3 约束非线性规划
从基本原理上看，约束非线性规划的一般形式是：

基本解法有：
（1）最优性条件 根据分析可知：根据多元函数的拉格郎日乘数法原理可知，上述问题的最优解应当满足，条件，即：

其中

（2）可行方向法：可行方向法（见《最优化方法》有关参考书）
（3） 惩罚函数法，分为：外点法、内点法（见《最优化方法》有关参考书）
(4)应用MATLAB解约束非线性规划
方法1 解二次规划
MATLAB工具箱中函数qp(H,C,A,B)对应的二次规划是矩阵形式：

将原问题变换为标准形式：，，，
求解该问题的MATLAB程序是：先给H，C，A， 进行赋值
H=[2,0;0,2];
C=[6,0];
A=[-2,-1;-1,0;0,-1];
B=[-4,0,0];
再调用优化程序qp x=qp(H,C,A,b); 即得最优解 1.0 2.0 和最优值ans=11.0
或者：直接调用程序：
方法2 (约束非线性规划)先将问题化为标准形式

解：MATLAB程序为：先定义目标函数、约束函数，给出将来程序中的基本数据模块
function[f,g]=fun(x)(即给出了fun的构成)(fun的作用对象是向量x)
f=exp(x(1)*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
g(1)=1.5+x(1)*x(2)-x(1)-x(2);
g(2)=-x(1)*x(2)-10;
再调用优化程序：x0=[-1,1];%给定初值（便于下一步函数fun程序执行）
options=[ ];%使用缺省参数
[x,options]=constr('fun',x0,options);(有一个现成的程序执行fun中提供的数据，即f,g)
输出最优解：x 得到结果：x= -9.5474 1.0474
输出最优解： options(8) 得到的结果为：ans=0.0236
输出总的计算次数：options(10) 得到的结果为：ans=29
方法3 调用梯度算法求约束非线性规划的MATLAB程序
优化程序的语句为：[x，options]=constru('fun',x0,options,'grad');（实际上是对里面的数据进行计算），其中的数据要先予以赋值：
fun的定义在上例中已演示，表示了约束函数；
grad的定义形式为：function[df,dg]=grad(x)
df=[t+4*exp(x(1)*(2*x(1)+x(2)),4*exp(x(1)*x(2)_0.5));%目标函数的梯度函数
dg=[x(2)-1,-x(2);x(1)-1,-x(1)]; %定义约束条件的梯度函数
方法4 （自变量有上下界约束的非线性规划）
求解：（问题形式属于标准形式）
MATLAB程序是：
function[f,g]=fun(x)%（首先定义目标函数和约束函数的数据形式）
f=(4-x(2)*(x(1)-3)^2;(给出了f的具体形式)
g(1)=x(1)+x(2)-3;%（必须把等式约束的函数放在前面，并且g是向量函数）
g(2)=x(1)^2-4*x(1)*x(2)-2;
vlb=[0,0]%给出了两个变量的下界
vub=[2,2];%给出了两个变量的上界
x0=[1,2];%（给出了进行计算的约束变量的初始取值，这是迭代的开始）
options(13)=1;%说明只有一个等式约束，即执行程序时程序默认几个约束条件中哪几个是等式约束；
[x,options]=constr['fun',x0，options,vlb,vub];这是主要程序语句，对后面的五个数据进行计算
结果为：最优解 x=2.0 1.0
输出最优值：用命令 options(8) 得：ans=3.0

4 多目标规划
问题的一般形式：
通过引入向量集的优化问题：有效点（最小向量）、弱有效点（弱最小向量），从而引入PARETO最优解的概念，它也是较好地反映多目标对象的大小比较的较好的概念，是求解多目标规划的基本理论基础。
(1) 理想点法
首先求每个单目标规划的最优解：，最优值为
称为原问题的理想点。但是实际上一般来讲是不存在实际的x达到这个向量的。不过这确是我们希望能够去作到的一件事情，尽管有点想好事，但是却是不得不去考虑的事情。这也是发挥想象力的重要的一个环节。现在的想法是：即使求不到这样的最优解，我们可以去求与这个解最接近的解，因此可以构造评价函数，求解问题，所求出的最优解可以作为PARETO意义下的最优解。

（2）线性加权法

对于多目标问题，在希望所有目标都达到最优解的同时，如果确实达不到，那就要有所侧重，就是说首先让某些我们认为重要的目标达到相对最大值，这样的话，就需要构作加权变量，使重要目标的权重大，从而在加权变量达到最大值的时候，重要目标也达到了相当大的程度。权重的选择有时要客观，有时也可用专家调查的方式获得。更确切的方法可用调查比例的方式来大致确定。
构造如下形式的评价函数：令
，称之为权向量集。
令 ，再求解：
可见这种处理方法就是将多目标问题转化成单目标问题，利用单目标达到最大值而使得目标向量也达到相对优化的程度。并且照顾到了特别的目标。
（3） 极大极小法
极大极小法的思想是：要求目标向量集的极小状态，理想状况是每个分量都达到最小值，但是实际是做不到的，我们的一个最基本的思想是求接近于这个状态的解，即近似解。现在找一个标准，使得这个解比那一个“小”，自然可以考虑每一个向量函数在决策变量取定以后，各个分量的最大值小，那这说明这个向量状态总体上是偏小的，因此显得较优。但问题是这个标准也有很大的漏洞，因为：有可能只有最大的比较，显得较优，而其它的分量都较大，故不是好解。（可以考虑用第二最大值来进行比较分析）
作评价函数：，然后求解：
将它的最优解作为（vp）问题意义下的最优解。

5 整数规划的分支定界法

分支定界法：整数规划问题表面上似乎可以用穷举的方法进行，但是对于规模稍大的问题这是不行的，因为所有整数的组合数目太大。一种自然的想法是设法只检查一部分少数取值组合，然后进行对比分析。
分支定界法的基本步骤为：开始时将原来的问题称之为问题A，将其中的整数限制去掉，形成了一般的线性规划问题，称之为与A相应的线性规划问题B
（1）求解问题B：如果无可行解，则原问题也没有可行解；如果B有最优解，并且是整数解，符合A的条件要求，则此解就是B的最优解；如果B有最优解，但是有的变量的取值不是整数，这时记最优解的值为。
（2）首先用观察法找到A的一个可行解，一般可取 ，记其目标函数值为 ，则问题A的最优函数值满足：。可见这一步给出了最优解的近似值，如果这时区间的长度很小，则可求得最优值的较好近似值；同样如果最优解中只有极少部分的变量不取整数，那么就取这几个变量的解相近的几个整数，组合成若干个可行解，并计算它们的目标函数取值，比较它们从中获得较好近似的最优解，因为此时的目标函数值已经很小（或很大）了，因此整数限制下的最优取值就应当离此点不远了，在此点的附近与这个最优值非常接近（目标函数是连续的）。但是这种方法毕竟是近似的，我们希望获得精确的最优解。因此，要进行下面的迭代：
第一步：分支 B的最优解中任选一个不符合整数条件的变量，其值为，构造两个约束条件：
将这两个约束条件分别加入问题B，求解两个后继规划问题。
定界：求出到目前为止所有刚分支后所得最优目标函数值的最大者作为新的上界，显然它是减少的；而取满足整数条件要求的分支中，找出目标函数的最大者作为新的下界，
第二步：比较与剪支：各分支的最优函数值中若有小于者，则剪掉这支，因为从这里面已无法找到更好的解了，故就不再考虑这个分支了。若大于，且不符合整数条件，则重复第一步。一直到不能改进即：=为止，这是得到了最优解。
分支定界法适合于求解纯整数规划问题，同时也适合于混合整数规划问题。它的主要思想就是：首先扩大搜索范围，使之可解性比较强；如果最优解中有不合适的解，就从这个解的附近去寻找，或者再划块来分别寻找，实际上就是把原来的寻找范围进行划分，再扩大各自的寻找范围，对结果的大小进行比较分析。

6 动态规划的基本方法

一 动态规划理论和方法解决的是多阶段决策过程最优化问题。动态规划的基本想法是把整个优化问题进行特定的分解，分解成若干个一些列的子问题，这些问题相对于原来的问题来看具有同等地位，表现为只是问题规模变小了，本质上没有变。可见这个方法仍然是建立在原来已有的基本求解方法基础之上的方法，利用已有的线性规划、非线性规划、整数规划、指派问题等等，把要求解的问题进行巧妙适当的分解，化整为零，使得每一个子问题都能够规模不大，方法求解方便，甚至必要时可以采取较笨的穷举方法。

下面结合一个实际问题的求解过程介绍动态规划的基本方法和步骤：
问题：某工业部门根据国家计划的按排，拟将某种高效率的设备5台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表所示。问：这5台设备如何分配给各个工厂，才能使国家获得的利益最大。

工
设备台数 厂

甲

乙

丙
0
1
2
3
4
5
0
3
7
9
12
13

0
5
10
11
11
11
0
4
6
11
12
13

求解过程：

（1）阶段划分：将问题分成三个阶段 ：第一阶段把全部设备分配给三个工厂；第二阶段是把全部设备分配给乙和丙两个工厂；第三阶段是把全部设备分配给丙工厂。实际上直观来看，我们的选优方法就是想进行全部地罗列各种潜在的可能。
（2）状态分析。状态就是每个阶段开始时的出发位置。是前一个阶段的终点，又是后一个阶段的起点。描述过程状态的量称为状态变量，它是表示状态的量化标志，是进行这个阶段各种优化分析的条件，它的取值可达集合称为可达状态集合。
本问题中记状态变量为分配给第k个工厂到第n个工厂的设备台数，记为。这其中要用到分配给每个工厂的台数，记为：，
（3）决策。在每个阶段根据开始时的状态数据进行目标优化。因为这时的问题是原来问题的子问题。用表示第k阶段当状态处于 时的决策变量,即这时选择的决策数据，即达到阶段最优的决策变量取值。
（4）策略。从第k阶段开始到终止状态为止的过程称之为问题的后部子过程，或称为k子过程。子策略记为：。实际上它的所有取值就是全部各个阶段可能的状况的组合。由他们可以决定目标函数值。决策变量的取值是从状态变量的可能取值中选取的。
（5）状态转移方程。它反映了相邻阶段的状态变量取值的关系。因为要计算第k阶段的优化结果，由于第k+1阶段的问题是第k阶段问题中所有可能的子问题分支,故必须用到第k+1阶段的优化结果，那么第k+1阶段的状态起始变量是由第k阶段的起始状态和这个阶段的决策变量完全决定的。一般可表达为：
在本问题中，，即：第k阶段有台设备要分配，如果分给第k个厂家台，余下的要作为第k+1阶段的起始状态变量，这时已经得到了第k+1阶段的最优结果。进行累加并比较各种可能即可得到第k阶段各个起始状态下的决策变量。
（6）指标函数与最优值函数
它是定义在全过程和所有后部子过程上的函数。常用
这个函数一般需要满足递推关系：即的同一函数关系。它往往是各个阶段的指标的和（除了起始目标外，后面阶段目标都是已经最优化了的目标）；或者是子过程中各个阶段的指标的乘积。
在本问题中，记为将台设备分配给第k个工厂所得的赢利，而用表示台设备分配给第 k个工厂到第个n工厂所得的最大赢利。显然这是两个最基本的数据，正是由它们进行计算表示分析。
递推关系的建立：将原来问题分解成了n个小型的同样问题，从其内在关系来看，这些问题呈现互相包含的关系，因此最优值函数之间必有相应的关系。经分析可知：

(7) 第三阶段（最后阶段或者叫做最简阶段）：将台设备（=0，1，2，3，4，5）分配给工厂 丙时，对应于每一种初始状态，最大赢利为：，其中
计算和记录的表格如下：
x3

p3(x3)

f3(s3)

0
1
2
3
4
5

0
1
2
3
4
5
0

4

6

11

12

13
0
4
6
11
12
13
0
1
2
3
4
5
其中为使得达到最大值时的最优决策。
第二阶段：设把台设备（，分配给工厂乙和工厂丙时，则对每个值，有一种最优分配方案，使最大赢利为：，其中即：这个阶段首先作的是分给乙工厂，正好指标函数具有可加性，因此产生的效益加上余下的再进行分配产生最大效益，即后的所有各种情形已经检查完了，取其已经累加的最优结果即可。由于的计算需要两个变量的取值，需要用二维表格来表示。

x2

P2(x2)+f3(s2-x2)

f2(s2)

0
1
2
3
4
5

0
1
2
3
4
5
0+4
0+4
0+6
0+11
0+12
0+12

5+0
5+4
5+6
5+11
5+12

10+0
10+4
10+6
10+11

11+0
11+4
11+6

11+0
11+4

11+0
0
5
10
14
16
21
0
1
2
2
1,2
2
第一阶段：
设把台设备分配给甲乙丙三个工厂，则对于每一个的取值，对应的最大赢利为
，其中，这是整个决策过程中的第一个决策变量。计算结果为：

x2

P1(x1)+f2(s1-x1)

f1(s1)

0
1
2
3
4
5

5
0+21
3+16
7+14
9+10
12+5
13+0
21
0,2

最后结果：
（1） 从最后的阶段知：则，查表知：；所以，故：甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。
（2） 第二种最优分配方案：用上述相同的方法可得：甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。

小结：动态规划的实质仍然是优化问题，相当于：分配问题，即：将某个总量分配到n个对象上，并且在每个对象上的分配可以使总量的任意分配，分配方式是一样的。

二 动态规划建模
动态规划的本质仍然是数学规划。就是要确定影响决定目标变量的决策变量取什么样的数值时，目标函数能达到最大或者最小值。线性规划单纯形方法的本质是将所有的可行解统一表达出来，然后将目标函数改变形式，使得形成一种特别好的形式，能直接看出最大值来，如果一次不行的话，就进行改进：使得下一个这种形式合乎要求。动态规划模型实际上是建立在其它模型基础上的一种形式，它也可以看成是一种求解数学规划的方法。
经过分析我们发现：如果将数学规划的决策变量的所有可能的取值进行罗列展示，可以进行分层表现：即排成这样的形状

X4

X3
X2