数学规划模型

作者: Acapella_Zhang | 来源:发表于2019-04-15 17:50 被阅读0次

数学规划模型
最优化模型
数学建模——优化模型
系统分析与设计
如何做出好的决策读后感
模型概念与数学和逻辑
管理规划工具模型总结
规划模型价值几何 !
数学建模系列笔记6：聚类和判别分析
建模之一

1.线性规划的求解方法

线性规划问题的标准形式为：
$\left\{\begin{array}{l}{\min z=c_{1} x_{1}+c_{2} x_{2}+\cdots+c_{n} x_{n}} \\ {a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 n} x_{n}=b_{1}} \\ {a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n}=b_{2}} \\ {\dots} \\ {a_{m 1} x_{1}+a_{m 2} x_{2}+\cdots+a_{m n} x_{n}=b_{m}} \\ {x_{1}, x_{2}, \cdots, x_{n} \geqslant 0}\end{array}\right.$
或者写成矩阵形式：
$\left\{\begin{array}{l}{\min Z=C x} \\ {A x=b} \\ {x \geqslant 0}\end{array}\right.$
一般来说线性规划包括单纯形规划和多目标规划

1.1单纯形线性规划

单纯形法时从所有基本的可行解的一个较小部分中通过迭代过程选出最优解
matlab中求解线性规划的函数时linprog,使用方法如下：
一般情况下，Linprog命令的参数形式为[x,fval] = linprog(f,A,b,Aeq,beq,lb,ub,x0)，下面分别介绍各参数的含义.

[x,fval,exitflag,output,lamnda]：返回值中x为最优解，fval为最优值,output包含优化信息的输出变量
f：表示目标函数中各个变量前面的系数向量，如果是求最小值问题，那么f就是各个变量的系数，如果是求最大值问题，那么f就是各个变量的系数的相反数.
A,b:表示不等式约束 $Ax\leq b$ 中的矩阵A和向量b,若不存在不等式关系
Aeq,beq:表示线性等式约束Aeq*x =beq中的矩阵Aeq和向量beq，若等式约束不存在则令Aeq=[ ],beq=[ ]
lb,ub :分别表示自变量的上下界组成的向量，如果没有上下界，该选项用[]表示，如果只有部分变量有上下界，其余的变量没有，那么可以把没有上下界的变量的上下界设为-inf或者inf使lb或者ub的长度符合要求.
x0:表示变量的初始值，可以缺省。

有如下例子：
$min f(x)=-5 x_{1}-4 x_{2}-6 x_{3}$
$\left\{\begin{array}{l}{x_{1}-x_{2}+x_{3} \leqslant 20} \\ {3 x_{1}+2 x_{2}+4 x_{3} \leqslant 42} \\ {3 x_{1}+2 x_{2} \leqslant 30} \\ {0 \leqslant x_{1}, 0 \leqslant x_{2}, 0 \leqslant x_{3}}\end{array}\right.$
由于没有等式约束，所以Aeq=[ ],beq=[ ]
不等式的条件系数为：
$A=\left[ \begin{array}{rrr}{1} & {-1} & {1} \\ {3} & {2} & {4} \\ {3} & {2} & {0}\end{array}\right], \quad b=\left[ \begin{array}{l}{20} \\ {42} \\ {30}\end{array}\right]$
由于没有上界要求：
$l b=\left[ \begin{array}{l}{0} \\ {0} \\ {0}\end{array}\right], \quad u b=\left[ \begin{array}{l}{\text { inf }} \\ {\text { inf }} \\ {\text { inf }}\end{array}\right]$

clear all
clc
f=[-5;-4;-6];
A=[1 -1 1;3 2 4;3 2 0];
b=[20;42;30];
lb=zeros(3,1);
[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb)

>>
x =

    0.0000
   15.0000
    3.0000


fval =

  -78.0000

exitflag =

     1

exitflag =1表示正常收敛于解x处。

1.2 多目标线性规划

多目标线性规划有着两个或两个以上的目标函数
$\max \left\{\begin{array}{c}{z_{1}=c_{11} x_{1}+c_{12} x_{2}+\cdots+c_{1 n} x_{n}} \\ {z_{2}=c_{21} x_{1}+c_{22} x_{2}+\cdots+c_{2 n} x_{n}} \\ {\vdots \quad \vdots} \\ {z_{r}=c_{r 1} x_{1}+c_{r 2} x_{2}+\cdots+c_{m} x_{n}}\end{array}\right.$
约束条件为：
$\left\{\begin{array}{l}{a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 n} x_{n} \leqslant b_{1}} \\ {a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n} \leqslant b_{2}} \\ {\vdots \quad \vdots} \\ {a_{m 1} x_{1}+a_{m 2} x_{2}+\cdots+a_{m n} x_{n} \leqslant b_{m}} \\ {x_{1}, x_{2}, \cdots, x_{n} \geqslant 0}\end{array}\right.$
给出如下例子：
$\begin{equation} \begin{array}{l}{\max f_{1}(x)=3 x_{1}-2 x_{2}} \\ {\max f_{2}(x)=-4 x_{1}-3 x_{2}}\end{array} \end{equation}$
$s.t.\begin{equation} \left\{\begin{array}{l}{2 x_{1}+3 x_{2} \leq 18} \\ {2 x_{1}+x_{2} \leq 10} \\ {x_{1}, x_{2} \geqslant 0}\end{array}\right. \end{equation}$

1.2.1 理想点法

$max Z = Cx$
先求解r个单目标问题，设其最优值分别为 $Z^*_j$ ,称为值域中的一个理想点，寻求距离 $Z^*_j$ 最近的Z作为近似值，最直接的方法就是构造最短距离理想点法，构造评价函数：
$\phi(Z) = \left(\sum_{i=1}^r[Zi-Z^*_j]^2\right)^{\frac{1}{2}}$
然后最小化评价函数，将他的最优解 $x^*$ 作为最优解.
在matlab中流程如下，先单个求解

clear all
clc
f=[3;-2]; 
A=[2,3;2,1]; 
b=[18;10];
lb=[0;0];
[x,fval]=linprog(f,A,b,[],[],lb)
>>
fval =

  -12.0000

clear all
clc
f=[-4;-3]; 
A=[2,3;2,1]; 
b=[18;10];
lb=[0;0];
[x,fval]=linprog(f,A,b,[],[],lb)
>>
fval =

  -24.0000

于是得到理想点（12，24）
然后求解如下模型：
$min\phi[f(x)] = \left([f_1(x)-12]^2+[f_2(x)-24]^2\right)^{\frac{1}{2}}$
$s.t.\begin{equation} \left\{\begin{array}{l}{2 x_{1}+3 x_{2} \leq 18} \\ {2 x_{1}+x_{2} \leq 10} \\ {x_{1}, x_{2} \geqslant 0}\end{array}\right. \end{equation}$

clear all
clc
A = [2,3;2,1];
b = [18,10];
x0 = [1,1];
lb = [0,0];
x = fmincon('((-3*x(1)+2*x(2)-12)^2+(4*x(1)+3*x(2)-24)^2)^(1/2)',x0,A,b,[],[],lb,[])
>>
x =

    0.5268    5.6488

得到最优的x

1.2.2 线性加权和方法

人们总希望给重要的指标较大的权重，将多目标问题转化为了所有目标加权求和的单目标问题
构造评价函数如下：
$minZ(x) = \sum_{i=1}^rw_iZ_i(x)$
$maxZ = Cx$
对于前面例子权重系数分别取0.5和0.5，进行求解
$min[0.5\times(3x_1-2x_2)+0.5\times(-4x_1-3x_2)]$

clear all
clc
f=[-0.5;-2.5];
A=[2,3;2,1]; 
b=[18;10]; 
lb=[0;0];
[x,fval]=linprog(f,A,b,[],[],lb)
>>
x =

    0.0000
    6.0000
fval =

  -15.0000

1.2.3 最大最小法

在决策时采用保守策略时最为稳妥的，在最坏的情况下，寻求最好的结果，可以构造如下的评价函数
$\phi(x) = maxZ_i$
$min\phi[Z(x)] = min maxZ_i(x)$
然后求解
$max Z = Cx$

function f = ex1019(x)
f(1) = 3*x(1)-2*x(2);
f(2) = -4*x(1)-3*x(2);

clear all
clc
x0=[1;1];
A=[2,3;2,1];
b=[18;10];
lb=zeros(2,1);
[x,fval]=fminimax('ex1019',x0,A,b,[],[],lb,[]) %这里使用fminimax函数

1.3 整数规划

当在实际问题中，部分自变量取整数时可以使用整数规划的方法，通过调用matlab中的intlinprog()实现,调用格式如下：

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options)：需要注意其中的intcon，intcon = [1,2,7] 表示 x(1), x(2), x(7) 只能取整数

给出例子如下：
$\min _{x}\left(-3 x_{1}-2 x_{2}-x_{3}\right)$
$\begin{equation} \left\{\begin{array}{l}{x_{3} ,\text { binary }} \\ {x_{1}, x_{2} \geq 0} \\ {x_{1}+x_{2}+x_{3} \leq 7} \\ {4 x_{1}+2 x_{2}+x_{3}=12}\end{array}\right. \end{equation}$

clc
clear all
intcon = 3;
f = [-3;-2;-1];
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf,Inf,1]; % x3的上界为1保证x3只能取0，1
[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
x
fval

>>
x =

         0
    5.5000
    1.0000


fval =

  -12.0000

2.非线性规划

非线性规划安约束条件可以分为以下三类：

无约束非线性规划
等式约束非线性规划
不等式约束非线性规划

2.1 非线性规划的标准形式

2.2 二次规划

非线性规划的目标函数为自变量的二次函数，约束条件全是线性函数，这种规划称为二次规划。
其标准数学模型为：
$\begin{equation} \min _{x} \frac{1}{2} x^{\mathrm{T}} \boldsymbol{H} x+f^{\mathrm{T}} \boldsymbol{x} \end{equation}$
$s.t.\begin{equation} \left\{\begin{array}{l}{A \cdot x \leqslant b} \\ {A e q \cdot x=b e q} \\ {l b \leqslant x \leqslant u b}\end{array}\right. \end{equation}$
其中 $H,A和Aeq$ 为矩阵，其余为列向量
matlab中利用quadprog求解二次规划问题，调用格式为：

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options): 其中lb,ub为上下界，options为指定优化方法。
[x,fval,exitflag,output,lambda] = quadprog(...): 基本与此前函数类似，其中lambda为拉格朗日函数的乘子。

【例】求解以下最优化问题
目标函数为：
$\begin{equation} f(x)=\frac{1}{2} x_{1}^{2}+x_{2}^{2}-x_{1} x_{2}-2 x_{1}-6 x_{2} \end{equation}$
$\begin{equation} \left\{\begin{array}{l}{x_{1}+x_{2} \leqslant 2} \\ {-x_{1}+2 x_{2} \leqslant 2} \\ {2 x_{1}+x_{2} \leqslant 3} \\ {x_{1} \geqslant 0, x_{2} \geqslant 0}\end{array}\right. \end{equation}$
目标函数可以修改为：
$\begin{equation} \begin{aligned} f(x) &=\frac{1}{2} x_{1}^{2}+x_{2}^{2}-x_{1} x_{2}-2 x_{1}-6 x_{2} \\ &=\frac{1}{2}\left(x_{1}^{2}-2 x_{1} x_{2}+2 x_{2}^{2}\right)-2 x_{1}-6 x_{2} \end{aligned} \end{equation}$
其中：
$\begin{equation} H=\left[ \begin{array}{rr}{1} & {-1} \\ {-1} & {2}\end{array}\right], \quad f=\left[ \begin{array}{l}{-2} \\ {-6}\end{array}\right], \quad x=\left[ \begin{array}{c}{x_{1}} \\ {x_{2}}\end{array}\right], \quad A=\left[ \begin{array}{rr}{1} & {1} \\ {-1} & {2} \\ {2} & {1}\end{array}\right], \quad b=\left[ \begin{array}{c}{27} \\ {2} \\ {3}\end{array}\right] \end{equation}$

clc
clear all
H = [1,-1;-1,2];
f = [-2,-6];
A = [1,1;-1,2;2,1];
b = [27,2,3];
lb = [0,0];
[x,fval,exitflag] = quadprog(H,f,A,b,[],[],lb,[]);
x
fval

>>
x =

    0.8000
    1.4000


fval =

   -8.8400

2.3 无约束规划

1. fminbnd函数
用来求固定区间内单变量函数的最小值
其调用格式如下：

x = fminbnd(fun,x1,x2,options,p1,p2...) : 其中x1,x2为区间，options为优化方法，如果没有options，令options = [ ].
[x,fval,exitflag,output] = fminbnd(...) :与之前函数类似

clc
clear all
[x,f_min] = fminbnd('sin(2*x)',0,2pi);

2. fminsearch函数
用于求多变量无约束的函数的最小值，格式为：

[x,fval,exitflag,options] = fminsearch(fun,x0,options): x0为初值

【注意】：

对于求解二次以上问题，fminunc更加有效，但对于高度非线性不连续问题则相反
fminsearch不适合求平方和问题，lsqnonlin更有效

3. fminunc函数(重要)
常用于求多变量无约束的函数的最小值

[x,fval,exitflag,output,grad,hessian] = fminunc(fun,x0,options): grad是解x处的梯度值，hessian将解x处的Hessian矩阵返回

clear all
clc
x0=[-1.2,1];
[x,fval]=fminunc('100*(x(2)-x(1)^2)^2+(1-x(1))^2',x0)
>>
x =

    1.0000    1.0000


fval =

   2.8336e-11

2.4 有约束规划

1. fmincon函数
求解多变量有约束的非线性函数的最小值，调用格式如下：

[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,noncon,options) ：其中noncon是计算非线性等式约束 $c(x)\leq0$ 和非线性不等式约束 $ceq = 0$
给出丧心病狂的例子如下：
【例】
$\begin{equation} \min f\left(x_{1}, x_{2}, x_{3}\right)=x_{1}^{2}\left(x_{2}+2\right) x_{3} \end{equation}$
$s.t.\begin{equation} \left\{\begin{array}{l}{350-163 x_{1}^{-2.86} x_{3}^{0.86} \leqslant 0} \\ {10-4 \times 10^{-3} x_{1}^{-4} x_{2} x_{3}^{3} \leqslant 0} \\ {x_{1}\left(x_{2}+1.5\right)+4.4 \times 10^{-3} x_{1}^{-4} x_{2} x_{3}^{3}-3.7 x_{3} \leqslant 0} \\ {375-3.56 \times 10^{5} x_{1} x_{2}^{-1} x_{3}^{-2} \leqslant 0} \\ {4-x_{3} / x_{1} \leqslant 0} \\ {1 \leqslant x_{1} \leqslant 4} \\ {4.5 \leqslant x_{2} \leqslant 50} \\ {10 \leqslant x_{3} \leqslant 30}\end{array}\right. \end{equation}$
创建目标函数：

function f = ex10_6a(x)
f = x(1)*x(1)*(x(2)+2)*x(3);

创建非线性约束条件函数：

function[c,ceq] = ex10_6b(x)
c(1) = ...
c(2) = ...
c(3) = ...
c(4) = ...
c(5) = ...
ceq = 0;

求解程序如下：

clear all
clc
x0=[2 25 20]';
lb=[1 4.5 10]';
ub=[4 50 30]';
[x,fval,exitflag]=fmincon(@ex10_6a,x0,[],[],[],[],lb,ub,@ex10_6b)

2. fseminf 函数
$\min _{x}\{F(x) | C(x) \leq 0, \operatorname{Ceq}(x)=0, \operatorname{PHI}(x, w) \leq 0\}$
$s.t.\left\{\begin{array}{l}{A^{*} x \leq B} \\ {A e q^{*} x=B e q}\end{array}\right.$
上述问题的 Matlab 命令格式为：
X=FSEMINF(FUN,X0,NTHETA,SEMINFCON,A,B,Aeq,Beq)
其中 FUN 用于定义目标函数，X0 为 x 的初始值；NTHETA 是半无穷约束 $PHI(x,w)$ 的个数；函数 SEMINFCON 用于定义非线性不等式约束 $C(x)$ ,非线性等
式约束 $Ceq(x)$ 和半无穷约束 $PHI(x)$ 的每一个分量函数，函数 SEMINFCON 有两个输入参量 X和S,S是推荐的取样步长，也许不被使用。
【例】
$min f(x) = \sum_{i=1}^3(x_i-0.5)^2$
约束为：
$K_{1}\left(x, w_{1}\right)=\sin \left(w_{1} x_{1}\right) \cos \left(w_{1} x_{2}\right)-\frac{1}{1000}\left(w_{1}-50\right)^{2}-\sin \left(w_{1} x_{3}\right)-x_{3} \leq 1\\ K_{2}\left(x, w_{2}\right)=\sin \left(w_{2} x_{2}\right) \cos \left(w_{2} x_{1}\right)-\frac{1}{1000}\left(w_{2}-50\right)^{2}-\sin \left(w_{2} x_{3}\right)-x_{3} \leq 1\\1 \leq w_{1} \leq 100,1 \leq w_{2} \leq 100$

function f = fun6(x)
f = sum((x-0.5).^2);

function [c,ceq,k1,k2,s]=fun8(x,s);
c=[];ceq=[];
if isnan(s(1,1))
    s=[0.2,0;0.2 0];
end
%取样值
w1=1:s(1,1):100;
w2=1:s(2,1):100;
%半无穷约束
k1=sin(w1*x(1)).*cos(w1*x(2))-1/1000*(w1-50).^2-sin(w1*x(3))-x(3)-1;
k2=sin(w2*x(2)).*cos(w2*x(1))-1/1000*(w2-50).^2-sin(w2*x(3))-x(3)-1;
%画出半无穷约束的图形
plot(w1,k1,'-',w2,k2,'+');

[x,y]  =  fseminf(@fun6,rand(3,1),2,@fun7)
>>
x =

    0.9525
    0.8183
    0.3714


y =

    0.3227

3.fminimax()函数

上述问题的 Matlab 命令为
X=FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON)
【例】
求函数族取最大最小值时得x值

function f=fun9(x);
f=[2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304
    -x(1)^2-3*x(2)^2
    x(1)+3*x(2)-18
    -x(1)-x(2)
    x(1)+x(2)-8];

[x,y] = fminimax(@fun9,rand(2,1))
>>
x =

    4.0000
    4.0000


y =

    0.0000
  -64.0000
   -2.0000
   -8.0000
   -0.0000

数学规划模型
1.线性规划的求解方法线性规划问题的标准形式为：或者写成矩阵形式：一般来说线性规划包括单纯形规划和多目标规划 1...
最优化模型
数据挖掘之优化模型 1.1数学规划模型线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2微分方程...
数学建模——优化模型
优化模型数学规划模型整数线性规划在线性规划模型中，规划中的变量限制为整数时称为整数线性规划。 1. 变量全部...
系统分析与设计
系统需求建模项目规划系统分析做什么系统设计怎么做系统实施支持可供使用的模型数学模型描述模型图形模...
如何做出好的决策读后感
方法一：完全理性决策（理想状态）运筹学：用数学模型分析得出最优解。下面给出相关的工具 1.规划论：研究给定...
模型概念与数学和逻辑
导读：通常所说的数学建模或数学模型背后就是整个现代科学的一个基本框架。然而这个“数学模型”本身并非数学概念；数学与...
管理规划工具模型总结
管理规划工具模型总结
规划模型价值几何 !
所有规划都是建立在模型上的。最复杂的规划采用计算机建模。其他模型存在于规划师的头脑之中。模型是现实的简化，但这种简...
数学建模系列笔记6：聚类和判别分析
@[toc] 6-1-1 模糊聚类原理简介：现实中的数学模型可以分为三大类：确定性数学模型、随机性数学模型、模糊...
建模之一
什么是数学模型？近藤次郎（日本）的定义—数学模型是将现象的特征或本质给以数学表述的数学关系式。 E.A.Bend...

数学规划模型

1.线性规划的求解方法

1.1单纯形线性规划

1.2 多目标线性规划

1.2.1 理想点法

1.2.2 线性加权和方法

1.2.3 最大最小法

1.3 整数规划

2.非线性规划

2.1 非线性规划的标准形式

2.2 二次规划

2.3 无约束规划

2.4 有约束规划

相关文章

数学规划模型

最优化模型

数学建模——优化模型

系统分析与设计

如何做出好的决策读后感

模型概念与数学和逻辑

管理规划工具模型总结

规划模型价值几何 !

数学建模系列笔记6：聚类和判别分析

建模之一

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读