跳至主要內容

数学建模

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小时

    问该厂应生产甲、乙机床各儿台，才能使总利润最大?

  • 数学模型

    设该厂生产x1x_1台甲机床和x2x_2乙机床时总利润zz最大，则x1，x2x_1，x_2应该满足

    max⁡z=4x1+3x2   (1.1) {2x1+x2≤10x1+x2≤8x2≤7x1,x2≥0     (1.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)

  • 概念

    • 变量x1，x2x_1，x_2称之为决策变量
    • （1.1）式被称为问题的目标函数
    • （1.2）中的几个不等式是问题的约束条件，记为s.t.（即 subject to）（subject除了科目，遭受，还有在......条件下的意思）

求解

标准形式

  • 线性规划问题的标准型

    max⁡z=∑j=1ncjxj s.t.{∑j=1naijxj=bi，i=1,2,⋯ ,mxj≥0，j=1,2,⋯ ,n \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求）

min⁡x=cTx s.t.{Ax≤b（线性不等式约束）Aeq⋅x=beq（线性等式约束）lb≤x≤ub（决策向量取值范围） 其中c和x为n维列向量，A、Aeq为适当维数的矩阵，b、beq为适当维数的列向量规范：c、x、b、beq、lb、ub为列向量；f称为价值向量；b称为资源向量；A、Aeq为矩阵 \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对应：决策向量的下界向量和上界向量列矩阵、列矩阵

  • 实战举例

    • 题目

      max⁡z=2x1+3x2−5x3 s.t.{x1+x2+x3=72x1−5x2+x3≥10x1+3x2+x3≤12x1,x2,x3≥0 \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，写错了）

image-20210419162319472
image-20210419162319472

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

  • 问题提出

    • 市场上有n种资产Si（i=1,2,⋯ ,n）S_i（i=1,2,\cdots,n）可以选择，现用数额为MM的相当大的资金作一个时期的投资

      这nn种资产在这一时期内购买SiS_i的平均收益率为rir_i，风险损失率为qiq_i，

      投资越分散，总的风险越少，总体风险可用投资的SiS_i中最大的一个风险来度量

      购买SiS_i时要付交易费，费率为PiP_i，当购买额不超过给定值uiu_i时，交易费按购买uiu_i计算

      另外，假定同期银行存款利率是r0r_0，既无交易费又无风险（r0=5r_0=5%）

      已知n=4n=4时相关数据如表1.1

    • 图表，投资的相关数据

      sis_irir_i(%) 收益率qiq_i(%) 风险损失率pip_i(%) 购买费率uiu_i(%) 最小购买额
      s1s_1282.51103
      s2s_2211.52198
      s3s_3235.54.552
      s4s_4252.66.540

  • 符号规定

    • sis_i表示第ii种投资项目，如股票，债券等，i=0,1,⋯ ,ni=0,1,\cdots,n。其中s0s_0指存入银行

      ri、pi、qir_i、p_i、q_i分别表示sis_i的平均收益率（非净），交易费率，风险损失率（i=0,1,⋯ ,n）（i=0,1,\cdots,n）。其中p0=0，q0=0p_0= 0，q_0= 0

      uiu_i表示sis_i的交易定额，i=1,⋯ ,ni=1,\cdots,n

      xix_i表示投资项目sis_i的资金，i=0,1,⋯ ,ni=0,1,\cdots,n

      aa表示投资风险度

      QQ表示总体收益

  • 基本假设

    1. 投资数额M相当大，为了便于计算，假设M=1
    2. 投资越分散，总的风险越小
    3. 总体风险用投资项目sis_i中最大的一个风险来度量（这里的表述有点问题，应该叫 “风险额”）
    4. n+1种资产sis_i之间是相互独立的
    5. 在投资的这一时期内ri、pi、qir_i、p_i、q_i为定值，不受意外因素影响
    6. 净收益和总体风险只受ri、pi、qir_i、p_i、q_i影响，不受其它因素干扰

  • 模型分析

    • 总体风险用所投资的sis_i中最大的一个风险来衡量，即max⁡{qixi ∣ i=1,2,⋯ ,n}\max\{q_ix_i~|~i=1,2,\cdots,n\}
    • 购买si（i=1,⋯ ,n）s_i（i=1,\cdots,n）所付交易费是一个分段函数，即交易费={pixi,xi>uipiui,xi≤ui交易费=\left\{\begin{aligned} &p_ix_i,&x_i>u_i\\ &p_iu_i,&x_i\leq u_i \end{aligned}\right.
    • 要使净收益尽可能大，总体风险尽可能小，这是一个多目标规划模型

  • 模型建立

    • 目标函数{max⁡∑i=0n(ri−pi)ximin⁡max⁡{qixi}        s.t.{∑i=0n(1+pi)xi=Mxi≥0 i=0,1,⋯ ,n        目标函数\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，使最大的一个风险qixiM≤a\frac{q_ix_i}{M}\leq a

    可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划

    max⁡∑i=0n(ri−pi)xi s.t.{qixiM≤a∑i=0n(1+pi)xi=Mxi≥0 i=0,1,⋯ ,n \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）s （0<s≤1）和（1−s）（1-s），ss称为投资偏好系数

      min⁡s{max⁡{qixi}}−(1−s)∑i=0n(ri−pi)xis.t. ∑i=0n(1+pi)xi=M，  xi≥0，i=0,1,⋯ ,n \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

  • 模型求解

    • [略]