数学建模

LincZero大约 7 分钟

数学建模

线性规划模型（LP，Linear Programming）

常用来解目标规划问题

简概

基本原理

简概
在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题
此类问题构成了运筹学的一个重要分支——数学规划，而**线性规划（Linear Programming，简记LP）**则是数学规划的一个重要分支
自从1947年G.B.Dantzig提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入
特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一
线性规划问题定义
- 目标函数及约束条件均为线性函数，故称为线性规划问题
- 线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题

案例（问题转模型）

案例题目
某机床厂生产甲、乙两种机床，每台销售后的利润分别为4千元与3千元
生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时
生产乙机床需用A、B、C三种机器加工,加工时间为每台各一小时
若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时
问该厂应生产甲、乙机床各儿台，才能使总利润最大?
数学模型
设该厂生产 $x_1$ 台甲机床和 $x_2$ 乙机床时总利润 $z$ 最大，则 $x_1，x_2$ 应该满足
$\max z=4x_1+3x_2~~~(1.1)\\~\\ \left\{\begin{aligned} 2x_1+x_2&\leq10\\ x_1+x_2&\leq8\\ x_2&\leq7\\ x_1,x_2&\geq0 \end{aligned}\right.~~~~~(1.2)$
概念
- 变量 $x_1，x_2$ 称之为决策变量
- （1.1）式被称为问题的目标函数
- （1.2）中的几个不等式是问题的约束条件，记为s.t.（即 subject to）（subject除了科目，遭受，还有在......条件下的意思）

求解

标准形式

线性规划问题的标准型
$\max z=\sum^n_{j=1}c_jx_j\\~\\ s.t.\left\{\begin{aligned} \sum^n_{j=1}a_{ij}x_j&=b_i，&i=1,2,\cdots,m\\ x_j&\geq0，&j=1,2,\cdots,n \end{aligned}\right.$

编程解线性规划（Matlab求）

线性规划问题的Matlab标准型（规范，矩阵表述）

\min_x=c^Tx\\~\\ s.t.\left\{\begin{aligned} &Ax\leq b&&（线性不等式约束）\\ &Aeq\cdot x=beq&&（线性等式约束）\\ &lb\leq x\leq ub&&（决策向量取值范围） \end{aligned}\right.\\~\\ 其中c和x为n维列向量，A、Aeq为适当维数的矩阵，b、beq为适当维数的列向量\\ 规范：c、x、b、beq、lb、ub为列向量；f称为价值向量；b称为资源向量；A、Aeq为矩阵

Matlab中求解线性规划

命令

[x,fval] = linprog(c,A,b)
[x,fval] = linprog(c,A,b,Aeq,beq)
[x,fval] = linprog(c,A,b,Aeq,beq,lb,ub)

其中

x 返回：决策向量的取值列矩阵
fval 返回：目标函数的最优值值
c（/f）对应：为价值向量列矩阵
A、b 对应：线性不等式约束矩阵、列矩阵
Aeq，beq 对应：线性等式约束矩阵、列矩阵
lb、ub 对应：决策向量的下界向量和上界向量列矩阵、列矩阵

x	返回：决策向量的取值	列矩阵
fval	返回：目标函数的最优值	值
c（/f）	对应：为价值向量	列矩阵
A、b	对应：线性不等式约束	矩阵、列矩阵
Aeq，beq	对应：线性等式约束	矩阵、列矩阵
lb、ub	对应：决策向量的下界向量和上界向量	列矩阵、列矩阵

实战举例

题目
$\max z=2x_1+3x_2-5x_3\\~\\ s.t.\left\{\begin{aligned} x_1+x_2+x_3&=7\\ 2x_1-5x_2+x_3&\geq10\\ x_1+3x_2+x_3&\leq12\\ x_1,x_2,x_3&\geq0 \end{aligned}\right.$

Matlab程序

f=[-2;-3;5]; 								% 注意一下规范是求min，所以这里全部要取相反数
a=[-2,5,-1;1,3,1];  b=[-10;12];				% 注意一下规范里是<=，所以这里有部分要取相反数
aeq=[1,1,1];  beq=7;
[x,y]=linprog(f,a,b,aeq,beq,zeros(3,1));	% 注意一下这里的zeros(3,1)
x,y=-y										% 因为前面求的其实是-y的最小值，所以要变回正才是y的最大值

%{ 输出
x =
    6.4286
    0.5714
    0.0000
y =
   14.5714
%}

编程解线性规划（Lingo求）

[暂略]，好像会比Matlab简单很多

实战

技巧：转化为线性规划问题

将非线性规划问题转换为线性规划问题

司守奎书上例子，好像是运筹学知识，挺妙的而且容易理解容易用

（下面的u,v应该是大于等于0，写错了）

完整流程案例——投资规划

问题提出
- 市场上有n种资产 $S_i（i=1,2,\cdots,n）$ 可以选择，现用数额为 $M$ 的相当大的资金作一个时期的投资
  这 $n$ 种资产在这一时期内购买 $S_i$ 的平均收益率为 $r_i$ ，风险损失率为 $q_i$ ，
  投资越分散，总的风险越少，总体风险可用投资的 $S_i$ 中最大的一个风险来度量
  购买 $S_i$ 时要付交易费，费率为 $P_i$ ，当购买额不超过给定值 $u_i$ 时，交易费按购买 $u_i$ 计算
  另外，假定同期银行存款利率是 $r_0$ ，既无交易费又无风险（ $r_0=5%$ ）
  已知 $n=4$ 时相关数据如表1.1
- 图表，投资的相关数据
  $s_i$ $r_i$ (%) 收益率 $q_i$ (%) 风险损失率 $p_i$ (%) 购买费率 $u_i$ (%) 最小购买额
  $s_1$ 28 2.5 1 103
  $s_2$ 21 1.5 2 198
  $s_3$ 23 5.5 4.5 52
  $s_4$ 25 2.6 6.5 40
符号规定
- $s_i$ 表示第 $i$ 种投资项目，如股票，债券等， $i=0,1,\cdots,n$ 。其中 $s_0$ 指存入银行
  $r_i、p_i、q_i$ 分别表示 $s_i$ 的平均收益率（非净），交易费率，风险损失率 $（i=0,1,\cdots,n）$ 。其中 $p_0= 0，q_0= 0$
  $u_i$ 表示 $s_i$ 的交易定额， $i=1,\cdots,n$
  $x_i$ 表示投资项目 $s_i$ 的资金， $i=0,1,\cdots,n$
  $a$ 表示投资风险度
  $Q$ 表示总体收益
基本假设
1. 投资数额M相当大，为了便于计算，假设M=1
2. 投资越分散，总的风险越小
3. 总体风险用投资项目 $s_i$ 中最大的一个风险来度量（这里的表述有点问题，应该叫 “风险额”）
4. n+1种资产 $s_i$ 之间是相互独立的
5. 在投资的这一时期内 $r_i、p_i、q_i$ 为定值，不受意外因素影响
6. 净收益和总体风险只受 $r_i、p_i、q_i$ 影响，不受其它因素干扰
模型分析
- 总体风险用所投资的 $s_i$ 中最大的一个风险来衡量，即 $\max\{q_ix_i~|~i=1,2,\cdots,n\}$
- 购买 $s_i（i=1,\cdots,n）$ 所付交易费是一个分段函数，即 $交易费=\left\{\begin{aligned} &p_ix_i,&x_i>u_i\\ &p_iu_i,&x_i\leq u_i \end{aligned}\right.$
- 要使净收益尽可能大，总体风险尽可能小，这是一个多目标规划模型
模型建立
- $目标函数\left\{\begin{aligned} &\max\sum^n_{i=0}(r_i-p_i)x_i\\ &\min\max \{q_ix_i\} \end{aligned}\right.\\~\\ ~~~~~~~s.t.\left\{\begin{aligned} &\sum^n_{i=0}(1+p_i)x_i=M\\ &x_i\geq0 \end{aligned}\right.\\~\\i=0,1,\cdots,n ~~~~~~~$
- 模型一：固定风险水平，优化收益
要点：简化规划，转多目标规划模型为线性规划
在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险 $\frac{q_ix_i}{M}\leq a$
可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划
$\max\sum^n_{i=0}(r_i-p_i)x_i\\~\\ s.t.\left\{\begin{aligned} &\frac{q_ix_i}{M}\leq a\\ &\sum^n_{i=0}(1+p_i)x_i=M\\ &x_i\geq0 \end{aligned}\right.\\~\\i=0,1,\cdots,n$
- 模型二：固定盈利水平，极小化风险
  同理
- 模型三：投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合
  因此对风险、收益分别赋予权重 $s （0<s≤1）$ 和 $（1-s）$ ， $s$ 称为投资偏好系数
  $\min s\{\max\{q_ix_i\}\}-(1-s)\sum^n_{i=0}(r_i-p_i)x_i\\ s.t. ~\sum^n_{i=0}(1+p_i)x_i=M，~~x_i\geq0，i=0,1,\cdots,n$
模型求解
- [略]

$s_i$	$r_i$ (%) 收益率	$q_i$ (%) 风险损失率	$p_i$ (%) 购买费率	$u_i$ (%) 最小购买额
$s_1$	28	2.5	1	103
$s_2$	21	1.5	2	198
$s_3$	23	5.5	4.5	52
$s_4$	25	2.6	6.5	40