姜启源/司守奎Week1:规划问题

阅读数: 23次 2020-07-17

多步决策过程(商人过河)
预测人口：
1. 马尔萨斯指数增长模型
2. 阻止增长模型Logistic模型

数学模型的分类：

应用领域	数学方法	表现特性	建模目的	了解程度
人口	初等数学	确定和随机	描述	白箱
交通	微分方程	静态和动态	优化	灰箱
经济	规划	离散和连续	预测	黑箱
生态	统计	线性与非线	决策
			分类

司守奎：Chapter1线性规划 Chapter2整数规划 Chapter3非线性规划

姜启源：Chapter1建立数学模型 Chapter2初等模型 Chapter3简单的优化模型 Chapter4数学规划模型

优化模型：用数学建模的方法处理优化问题

步骤

确定优化目标
寻求的决策
决策受到的限制
数学工具(变量、常数、函数)的表示

优化模型的分类

静态优化模型：函数极值问题->微分

3.1/3.2优化模型的真正效果
1. 敏感性分析，研究主要参数的微小变化对模型的影响
  
  很多线性规划系数是易变的，故会出现：
  - 当系数变化时，最优解会有什么变化
  - 或系数在什么范围变化，对最优解的影响基本不变。
2. 强健性分析

3.4 效用函数与效用最大化模型

3.5 消费者追求最大效用/生产者追求最大利润

最大利润模型与最优定价模型

经济学中将“导数”称为“边际”。

经济学定律：最大利润在边际产值等于边际成本时达到。

产值最大与费用最小的对偶关系。

Chapter4 数学规划模型

$min_z z=f(x)，x=(x_1,…,x_n)^T\s.t.g_i(x)\le0,i=1,2,…,m$

其中， $x$ 为决策变量 $f(x)$ 为目标函数， $g(x)\le0$ 为约束条件。

分类：

多元函数条件极值问题：

决策变量个数n和约束条件个数m较大

最优解在可行域的边界上取得
数学规划：
1. 线形规划：在一组线性约束的限制下，求一线性目标函数最大或最小的问题。
2. 非线性规划 $NLP$ (non-linear Programming)
  
  Matlab。司守奎Chapter3
3. 整数规划
  
  i.变量全是整数
  
  ii.变量部分是整数
  
  1.3 求解方法分类: (i)分枝定界法—可求纯或混合整数线性规划。 (ii)割平面法—可求纯或混合整数线性规划。 (iii)隐枚举法—求解“0-1”整数规划:
  
  1过滤隐枚举法;
  
  2分枝隐枚举法。 (iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。 (v)蒙特卡洛法—求解各种类型规划。
  
  整数解一般可以采用美剧，但是不好穷举的时候，可以应用概率理论证明求得满意解。
  
  整数规划采用模型软件LINGO

Chapter5微分方程模型

matlab中的各种类型Chapter2-Chapter4规划

线性规划的Matlab解法

Matlab中线性规划的标准型为：

min $C^Tx$

help linprog

利用matlab求解线性规划的简单例子1（ssk P4):

Todo:

$max z=2x_1+3x_2-5x_3$ ,

s.t. $x_1+x_2+x_3=7\2x_1-5x_2+x_3\ge10\x_1+3x_2+x_3\le12\x_1,x_2,x_3\ge0$

这里，先相应地化为标准式，寻找对应参数：

$Tod0:$

$min z=-2x_1-3x_2+5x_3$ ,

x是列向量，这里c也是列向量
Aeq=[1,1,1];
beq=7;
A=[-2,5,-1;1,3,1];
b=[-10;12];
lb=zeros(3,1);

线性规划Outline

基本matlab线性规划
运输问题->产销平衡：康-希表上作业法
指派问题->特殊的0-1规划，求解指派问题的匈牙利算法
对偶理论与灵敏度分析/参数线性规划
投资的收益和风险：

投资的收益和风险：

这是一个多目标线性规划模型：使净收益尽可能大，总体风险尽可能小。

模型

$\begin{cases}max净收益\min总体风险\end{cases}$

模型简化

投资者承受风险无法无限大，给定风险界限 $a$
投资者总盈利至少到达水平 $k$ 之上
结合两者：投资者在权衡投资风险和预期收益两方面，对风险和收益赋予s和（1-S)的投资偏好系数。

模型简化后1 的线性规划求解：

$min f=(−0.05,−0.27,−0.19,−0.185,−0.185)(x_0,x_1,x_2,x_3,x_4)^T$

s.t. $\begin{cases}x_0+1.01x_1+1.02x_2+1.045x_3+1.065x_4=1\0.025x_1\le a\0.015x_2\le a\0.055x_3\le a\0.026x_4\le a\x_i\ge 0(i=0,1,…,4)\end{cases}$

因为这里a是任意给定的风险度，即threshold是如何的本在一开始没有一个准则，故 *需要从a=0开始，以步长 $\Delta a=0.001$ *进行循环搜索，编写matlab程序：

Step1:注意要将模型转换成matlab的linprog的形式：

X=linprog(f,A,b,Aeq,beq,LB,UB)

注意这里 $LB$ 、 $UB$ 是lower bound/upper bound.

故这题的标准形式。注意那个对角阵拼接的形式。

Chapter2 整数规划

LINGO软件

Chapter3非线性规划

名词与具体形式：

$min f(x)$ s.t. $h_j(x)\le0,j=1,…,q\g_i(x)=0,i=1,..,p$

其中 $x=[x_1,…,x_n]^T$ 为模型NLP的决策变量。

$f$ 为目标函数

$h_j(j=1,…,q)$ 称为约束函数，约束函数分为等式约束与不等式约束。

实际中的NLP问题

确定提供方案
提出追求目标
给出价值标准
寻求限制条件

线性规划和非线性规划的区别

如果线性规划的最优解存在，那么最优解只能在可行域的边界上达到。

而非线性规划的最优解如果存在 是在可行域的任意一点达到。

非线性规划的Matlab解法

这里， $AX\le B,AeqX=Beq$ 是线性约束

NONLCON是用M文件定义的非线性向量函数 $C(x).Ceq(x)$ 。

利用matlab求解非线性规划的简单例子1（ssk P33):

$minf(x)=x_1^2+x_2^2+x_3^2+8$

matlab程序未复现。

无约束问题

一维搜索方法

当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点

一维极小化问题的形式如下：

$min_{a<=t<=b} f(t)$ ,即通过不断地缩短变量区间[a,b]的长度。

应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快的缩短？

Fibonacci法

Step1.确定单峰区间，给出搜索京都，确定搜索次数。

例子：试用fibonacci求f(t)= $t^2-t+2$ 的近似极小点。

0.618法

二次插值法

对于之前所示的极小化问题，当 $f(t)$ 在[a,b]上连续时，可以考虑用多项式插值来进行一维搜索。

在搜索区间中，不断用低次(不超过3次)多项式来近似目标函数，用插值多项式的极小点来逼近。

无约束极值

解析法

梯度下降Gradient Descent

按照基本迭代格式，每一轮从点 $x^k$ 出发沿最速下降方向- $\nabla f(x^k)$ 作一维搜索。

例：用最速下降法求解无约束非线性规划问题

$min f(x)=x_1^2+25x_2^2$

$x=(x_1,x_2)^T,x^0=(2,2)^T$

详见代码detaf.m和zuisu.m

原来matlab是写代码然后在命令行运行的呀！

Newton法

按照基本迭代格式，每一轮从点 $x^k$ 出发沿Newton方向作一维搜索。

例，用Newton法求解

min f(x)= $x_1^4+25x_2^4+x_1^2x_2^2$

$x^0=(2,2)^T$

优缺点

如果目标函数是非二次函数，一般地说，用Newton法通过有限轮迭代不一定能得到最优解。

Newton法的优点是收敛速度快，缺点是不好用，维数高贼难用

变尺度法

DFP法

既避免了二次导数矩阵和它的求逆，又比梯度法的收敛速度快，适合高维度问题。

直接法：目标函数不可导，导函数的解析式难以表示。

主要由基本搜索，加速搜索和调整搜索方向三部分组成。

利用matlab求解无约束问题

fminunc和fminsearch

求解的问题形如下：

求函数的极小值

$min_x f(x)$ ，其中x可以是标量或向量。

fminuc

例子：求解 $f(x)=100(x_2-x_1^2)^2+(1-x_1)^2$ 的最小值

本质上是一个多元函数求极值的问题。

fminsearch

例子，就 $f(x)=sin(x)+3$

约束极值问题：规划问题

优化工具箱使用

二次规划：目标函数是x的二次函数，约束条件是线性的

罚函数法：转化为求解一系列无约束极值问题

SUMT：序列无约束最小化技术

内外罚函数。

Matlab求约束极值问题

fminbnd/fmincon/quadprog/fseminf/fminimax

fminbnd:求单变量非线性函数在区间上的极小值

minF(x),x $\in[x_1,x_2]$

Fseminf

fminimax

matlab优化工具箱

在命令行中输入ver可以查看matlab已经安装的工具箱

优化工具箱：optimtool

神经网络工具箱:nnstart

曲线拟合工具箱cftool

有关matlab工具箱的连接

Lingo/Lindo与matlab.