1 基本原理

1.1 线性规划问题概述

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支——数学规划，而线性规划(Linear Programming简记LP)则是数学规划的一个重要分支。

自从1947年G.B.Dantzig提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

1.2 线性规划的实例与定义

例如 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4千元与3千元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时;生产乙机床需用A、B、C三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大?

上述问题的数学模型：设该厂生产$x_1$台甲机床和$x_2$乙机床时总利润$z$最大，则$x_1,x_2$应满足：

变量$x_1,x_2$称之为决策变量，$z=4x_1+3x_2$被称为目标函数，$z$为最优值，不等式为约束条件，记为s.t.(subject to).

三部分组成：

  1. 目标函数：max $z = 4x_1 + 3x_2$

  2. 决策变量：$x_1,x_2$

  3. 约束条件：

目标函数及约束条件均为线性函数，故被称为线性规划问题。线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，往往也是很困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。

1.3 线性规划问题的解的概念

其中：

  • $c$ 和 $x$ 为 $n$ 维列向量

    例如上例：$z = 2x_1+x_2$

    对应这里：$c^T = [2,1]$，因为为转置矩阵，所以$c=[2;1]$

    $x=[x_1;x_2]$

  • $A$、$Aeq$为适当维数的矩阵

    $A$为不等式约束。例如上式：$A=[2,1; 1,1; 0,1]$

    $Aeq$为等式约束。上式没有。

  • $b$、$beq$为适当维数的列向量

    $b$是和$A$配对的不等式约束。例如上式：$b=[10; 8; 7]$

    $beq$为和$Aeq$配对的等式约束。上式没有。

  • $lb$、$ub$为n维列向量

    用来约束$x$的范围。例如上式：$lb=[0;0]$、$ub=[8;7]$

一般线性规划问题的数学标准型为：

1.3.1 可行解

满足上式条件的解$x=[x_1,\cdots,x_n]^T$，称维线性规划问题的可行解，而使目标函数$z$达到最大值或最小值的解叫作最优解。z的最大值或者最小值为最优值

1.3.2 可行域

所以可行解构成的集合称为问题的可行域，记为$R$。

1.4 线性规划的Matlab标准形式及软件求解

线性规划的目标函数可以是求最大值，也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab中规定线性规划的标准形式为：

其中 $f,x,b,beq,lb,ub$都是列向量（上面解释过了）,$f$称为价值向量，$b$称为资源向量，$A,Aeq$为矩阵。

1.4.1 Matlab 的求解命令：

1
2
3
4
[x, fval] = linprog(f, A, b)
[x, fval] = linprog(f, A, b, Aeq, beq)
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub, x0, OPTIONS)

其中：

  • 返回值：

    • x：决策向量的取值，即最优解
    • fval：目标函数的最优解

  • 参数：

    • f：价值向量
    • A和b：不等式约束
    • Aeq和beq：等式约束
    • lb和ub：列向量，x的取值范围
    • x0：x的初始值
    • OPTIONS：指定参数进行最小化
      • Display：若为 off 则不显示输出；若选择 Iter （iteration的缩写）即显示每一步的迭代过程；若选择 final 即只显示最终结果。
      • MaxFunEvals：函数评价的最大允许次数
      • Maxiter：最大的允许迭代次数
      • Tolx：x处的终止容限

  • 其他返回值：

    [x, fval, exitflag, output, lambda]

    • exitflag：收敛数
    • optput：迭代次数
    • lambda：x处的拉格朗日乘子
      • lambda.lower：lambda的下界
      • lambda.upper：lambda的上界
      • lambda.ineqlin：lambda的线性不等式
      • lambda.eqlin：lambda的线性等式

1.5 练习

1.5.1 例1

化为Matlab标准形式（注意是最小值，所以fval有负号）：

matlab代码：

1
2
3
4
5
6
7
8
9
f = [-2; -3; 5];
a = [-2, 5, -1; 1, 3, 1];
b = [-10; 12];
Aeq = [1, 1, 1];
beq = 7;
lb = zeros(3, 1)
[x, favl] = linprog(f, a, b, Aeq, beq, lb)
x
z = -favl % 因为求最大值

结果：

image-20230111191230508

即：最优解为：$x_1=6.4286,x_2=0.5714,x_3=0$；最优值为：$z=14.5714$。

1.5.2 例2

化为Matlab标准形式：

matlab代码：

1
2
3
4
f = [2, 3, 1];
A = [-1,-4,-2;-3,-2,0]
b = [-8;-6]
[x, fval] = linprog(f, A, b, [], [], zeros(3, 1))

结果：

image-20230111195651964

即最优解为：$x_1=2.0000,x_2=0,x_3=3.0000$；最优值为：$z=7$。

1.6 可转化为线性规划的问题

例如：规划问题为：

其中：$x=[x_1, \cdots,x_n] ^ T$，$A$和$b$为相应维数的矩阵和向量。

​ 要把上面的问题编程线性规划问题，要考虑到：

所以，只需要取 $u_i=\frac{x_i+\left|x_i\right|}{2}$ , $v_i=\frac{\left| x_i \right| - x_i}{2}$ ,就可以满足上面的条件。

​ 这样：记$u=[u_1,\cdots,u_n]^T,v=[v_1,\cdots,v_n]^T$，从而我们可以把上面的问题变成：

2 实际案例

2.1 投资的收益和风险

2.1.1 问题

​ 市场上有$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$时相关数据如表：

$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

​ 试给该公式设计一种投资组合方案，即用给定资金$M$，有选择第购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。

2.1.2 解答

2.1.2.1 符号规定：

  • $s_i$表示第$i$种投资项目，如股票，债券等，$i=0,1,\cdots,n$，其中$s_0$表示存入银行；
  • $r_i,p_i,q_i$分别表示$s_i$的平均收益率，交易费率，风险损失率，$i=0,\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$表示总体收益；

2.1.2.2 基本假设：

  • 投资数额$M$相当大，为了便于计算，假设$M=1$；
  • 投资越分散，总的风险越小；
  • 总体风险用投资项目$s_i$中最大的一个风险来度量；
  • $n+1$种资产$s_i$之间是相互独立的；
  • 在投资的这一时期内，$r_i,p_i,q_i$为定值，不受意外因素影响；
  • 净收益和总体风险只受$r_i,p_i,q_i$影响，不受其它因素干扰。

2.1.2.3 模型的分析与建立

  1. 总体风险用所投资的$s_i$中最大的一个风险类衡量，即

  2. 购买$s_i(i=1,\cdots,n)$所付交易费是一个分段函数，即

    而题目所给的定值$u_i$（单位：元）相对总投资$M$很少($u_i\ll M$)，$p_iu_i$更小，这样购买$s_i$的净收益可以简化为$(r_i - p_i)x_i$。

  3. 总净收益为银行利息加$s_i$的净收益

    其中因为银行没有交易费率，所以令$p_0 = 0$，则：

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

2.1.2.3.1 归纳模型

目标函数为：

约束条件为：

这是一个多目标规划模型。

2.1.2.3.2 多目标规划模型转化为一个目标的线性规划

  1. 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限$a$，使最大的一个风险$\frac{q_ix_i}{M} \leqslant a$（$q_ix_i$为$s_i$的风险费，这里表示风险损失费占比总金额小于一个阈值），可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。

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

    数学模型

    化为Matlab标准形式（$M=1$）：

    Matlab核心代码：

    1
    2
    3
    4
    5
    6
    7
    f = [-0.05;-0.27;-0.1;,-0.185;-0.185];
    A = [zeros(4,1),diag([0.025,0.015,0.055,0.026])];
    b = a*ones(4,1); 		% 但是这里的a没有赋值，老哥利用循环遍历，最终绘制曲线
    Aeq = [1, 1.01, 1.02, 1.045, 1.065];
    beq = 1;
    lb = zeros(5, 1)
    [x, fval] = linprog(f, A, b, Aeq, beq, lb);

    因为$a$没有赋值，令$a = 0$，步长$\Delta a = 0.001$进行循环搜索并绘图。

    matlab绘制曲线：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    a = 0;
    hold on
    while a < 0.05
    	f = [-0.05;-0.27;-0.19;-0.185;-0.185];
    	A = [zeros(4,1),diag([0.025,0.015,0.055,0.026])];
    	b = a*ones(4,1);
    	Aeq = [1, 1.01, 1.02, 1.045, 1.065];
    	beq = 1;
    	lb = zeros(5,1)
    	[x, fval] = linprog(f, A, b, Aeq, beq, lb);
    	Q = -fval;
    	plot(a, Q, '*k');
    	a = a + 0.001;
    end
    xlabel('a');
    ylabel('Q');

    结果：

    image-20230111213013690

  2. 在实际投资中，可以固定一个盈利水平，例如盈利$\sum\limits_{i=0}^n (r_i - p_i)x_i \geqslant k$总盈利大于阈值$k$，之后就专注于降低风险度。可找到相应的投资方案。

    模型二 固定盈利水平，极小化风险

    数学模型

  1. 投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。此时对风险、收益率分别赋予权重$s(0<s\leqslant 1)$ 和 $(1-s)$，$s$称为投资偏好系数。

    模型三 利用投资偏好系数平衡风险和收益率

    数学模型