MATLAB线性规划(LP)

——线性规划的一般形式：目标函数和约束条件都是设计变量的线性函数

1、求解思路

• 结合题目得到目标函数（一般为min型，max型利用求相反值转化为min型）
• 列出约束条件
• 将线性函数函数以及条件转换成矩阵形式
• 编写程序求解
• 要求最优解符合要求

2、例题练习

练习${\mathcal{L}}_1$

思路

• c数组A矩阵b数组均已知，有$(x_1...x_6{)}^T$;
• 有不等式约束，无等式约束，$x\ge 0$.

线性形式

• 目标函数：$minZ={\sum }_{i=1}^6{c}_i{x}_i$
• $s.t.=\{\begin{array}{l}{\sum }_{k=1}^6{a}_{ik}{x}_k\le b_k,i=1,2...n\\ x_i\ge 0,i=1,2...n\end{array}$

矩阵形式

• 目标函数：$minZ=cX$

• 约束条件：$s.t.=\{\begin{array}{l}Ax\le b\\ vlb\le x\le vub\end{array}$

代码

c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08];
b=[850;700;100;900];
Aeq=[];
beq=[];
vlb=[0;0;0;0;0;0];
vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
% minZ=cX z为cX的求和的最小值，c为各项x的系数    
% AX≤b，A、X、b均为数组，这是不等式约束条件
% AeqX=beq，Aeq、beq均为数组，为等式约束条件，Aeq为各项x的系数
% 若没有不等式存在，则令A=[]，b=[].
% 若没有等式约束 则令Aeq=[], beq=[].
% vlb≤X≤vub，是对变量X的约束
% 返回最优解x以及x处目标函数值fval

答案

x =

   1.0e+04 *

    3.5000
    0.5000
    3.0000
         0
         0
         0


fval =

      -25000

练习${\mathcal{L}}_2$

思路

• c数组A矩阵b数组均已知，有$x_1-x_3$;
• 有不等式约束，有等式约束，$x\ge 0$.

线性形式

• 目标函数：$minZ={\sum }_{i=1}^6{c}_i{x}_i$
• $s.t.=\{\begin{array}{l}{\sum }_{k=1}^3{a}_{ik}{x}_k\le b_k,i=1,2,3\\ x_1\ge 30\\ x_2\ge 0\\ x_3\ge 20\end{array}$

矩阵形式

• 目标函数：$minZ=cX$

• 约束条件：$s.t.=\{\begin{array}{l}Ax\le b\\ vlb\le x\le vub\\ Aeqx=beq\end{array}$

代码

c=[6 3 4];
A=[0 1 0];
b=[50];
vlb=[30 0 20];
vub=[];
Aeq=[1 1 1];
beq=[120];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub);

答案

x =

    30
    50
    40


fval =

   490

3、实际建模

3.1 提出问题

3.2 基本假设&符号规定

3.2.1 基本假设

• 总投资数额M很大，为了计算方便将M设为1；
• n种资产$s_i$相互独立，互不相干；
• 投资越分散，总体风险越小；
• 银行存款无交易费也无风险($p_0=q_0=0$)；
• 在投资期间的$r_i,q_i,p_i,r_0$不受外界环境因素干扰，均为定值；
• 净收益与总体风险只与$r_i,q_i,p_i,r_0$相关，不受其他无关因素干扰；
• 总体风险用n种投资项目$S_i$中风险最大的一个来度量。

3.2.2 符号规定

• $S_i$ —— 投资的第$i$种资产
• $M$ —— 投资总额
• $r_i{q}_i{p}_i$ —— 某一资产的平均收益率、风险损失率、交易费率
• $r_0$ —— 同期银行的存款利率
• $u_i$ —— 某一资产$S_i$的交易定额
• $x_i$ —— 某一资产$S_i$的投资额
• $a$ —— 投资风险度
• $k$ —— 可接受的最低总收益
• $Q$ —— 总体收益
• $\Delta Q$—— 总体收益的增量
• $L$ —— 总体风险损失
• $s$ —— 权重因素

3.3 建立并分析模型

3.3.1 基本模型

• 总体风险用n种投资项目$S_i$中风险最大的一个来度量，则$max\{q_i{x}_i|i=1,2...n\}$;

• 购买$Si$($i=1,2...n$)的交易费为：
  $$\{\begin{array}{l}{p}_i{x}_i,x_i\ge u_i\\ p_i{u}_i,x_i<u_i\end{array}$$
  且投资数额$M$相较于$p_i{u}_i$非常大，则可忽略不计，交易费记为$p_i{x}_i$，则购买某资产$S_i$的净收益为$x_i(r_i-p_i)$;

• 投资越分散，总体风险越小，所以总体收益的线性规划是一个多目标的线性规划，

  目标函数：
  $$\begin{gathered} Q=max\sum _{i=0}^n{x}_i(r_i-p_i) \\ L=min\{max\{q_i{x}_i\}\},(i=1,2...n) \end{gathered}$$
  ps:根据不同的建模需求，目标函数会被一定程度地组合成新的目标函数，或被改造成约束条件。

  约束条件：
  $$\begin{gathered} \sum _{i=0}^n{x}_i(1+p_i)=M \\ {x}_i\ge 0,(i=0,1...n) \end{gathered}$$

3.3.2 简化模型

模型1 固定风险水平，优化收益

要求：

• 满足总体风险度$\max \{q_i{x}_i\}/M\le a,(i=1,2...n)$，且作为限制条件；
• 目标函数为Q.

模型2 固定收益，降低风险

要求：

• 满足总体收益$Q={\sum }_{i=0}^n{x}_i(r_i-p_i)\ge k$，且作为限制条件；
• 目标函数为L.

模型3 根据赋予的权重因素s进行预期收益与资产风险的取舍

要求：

• 约束条件同基本模型
• $0<s\le 1$
• 此题中$s$为投资偏好系数，目标函数为$sL-(1-s)Q$.

3.4 求解模型

以模型1为例：

• 目标函数：$minfval=(-0.05-0.27-0.19-0.185-0.185)(x_0{x}_1{x}_2{x}_3{x}_4{)}^T$

• 约束条件：$\{\begin{array}{l}{x}_0+0.01x_1+0.02x_2+0.045x_3+0.065x_4=M=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{array}$

• $a$不定，则令$a=0$，步长$\Delta a=0.0001$进行循环搜索，得到结果，编写函数如下：

  a=0;
  while (1.1-a)>1
      c=[-0.05 -0.27 -0.19 -0.185 -0.185];
      A=[0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026];
      b=[a;a;a;a];
      Aeq=[1 1.01 1.02 1.045 1.065];
      beq=[1];
      vlb=[0;0;0;0;0];
      vub=[];
      [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub);
      Q=-fval;            % 负值才为净利益
      plot(a,Q,'-r.');    % 制图
      axis([0 0.1 0 0.5]);% 坐标轴
      hold on;            % 不清理前面循环过程的作图
      a=a+0.001;          % 循环
  end
  xlabel('a');
  ylabel('Q');
  title('模型1求解');
  

• 结果

3.5 总结与分析

• 风险越大，利益越大；

• 分析图中散点图可知，投资越分散，风险越小，投资越密集，风险越大；

• (a,Q)=(0.006,0.2019)为图中曲线的拐点，拐点往左，风险小利益较少，但在持续增加，拐点往右，风险大，且利益增长缓慢，如果对利益没有特殊追求追求的话，应该选择该点作为投资参照；

• 则模型1的最优解为：

x =

         0
    0.2400
    0.4000
    0.1091
    0.2212


Q =

    0.2019

4、实验作业

4.1 提出问题

4.2 建立模型

4.2.1 思路

• $Q$单位万元，$x_i$单位百箱；
• 使用min模型求解；
• 有不等式约束，无等式约束，x均为正数。

4.2.2 线性形式

• 目标函数：$maxQ=10x_1+9x_2$
• $s.t.=\{\begin{array}{l}6x_1+5x_2\le 60\\ 10x_1+20x_2\le 150\\ 0\le x_1\le 8\\ 0\le x_2\end{array}$

4.2.3 矩阵形式

• 目标函数：$maxQ={\sum }_{i=1}^{2}cX$

• 约束条件：$s.t.=\{\begin{array}{l}Ax\le b\\ vlb\le x\le vub\end{array}$

4.3 求解模型

4.3.1 代码

% c=[-10 -9];
% A=[6 5;10 20;1 0];
% b=[60;150;8];
% Aeq=[];
% beq=[];
% vlb=[0;0];
% vub=[];
% [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub);
% Q=-fval;

a=60
while(62-a>0)
    c=[-10 -9];
    A=[6 5;10 20;1 0];
    b=[a;150;8];
    Aeq=[];
    beq=[];
    vlb=[0;0];
    vub=[];
    [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub);
    Q=-fval;
    plot(a,Q,'-r.');% 制图
    axis on;        % 坐标轴
    hold on;        % 不清理前面循环过程的作图
    a=a+0.01; 
end
xlabel('a');
ylabel('Q');

% c=[-11 -9];
% A=[6 5;10 20;1 0];
% b=[60;150;8];
% Aeq=[];
% beq=[];
% vlb=[0;0];
% vub=[];
% [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub);
% Q=-fval;

4.3.2 答案

问题0：考虑到工人人数为整数，所以应该左右寻找满足$10x_1$以及$5x_2$为整数的$x_1、x_2$.

x =

    6.4286
    4.2857


Q =

  102.8571
%优化后
x =

    6.5000
    4.2000


Q =

  102.8000

问题1：由图知，应该作这项投资。

问题2：修改系数可得$x、Q$，且正好满足$10x_1$以及$5x_2$为整数，则应该改变生产计划。

x =

    8.0000
    2.4000
    
    
Q =

  109.6000