线性规划的定义

数学规划是运筹学的一个分支，它用来研究在给定条件下（约束条件），如何按照一衡量指标（目标函数）来寻求计划、管理工作中的最优方案。

[math]\min [/math]或[math]\max f(x), \text{ s.t. } g_i(x) \leq 0 [/math]（如果是大于的则要手动改为小于0）

这里的[math]x[/math]称为决策变量；[math]f(x)[/math]称为目标函数；[math]g_i(x) \leq 0[/math]称为约束条件。

如果[math]f(x)[/math]和约束条件均为线性表达式，则此时就是线性规划。

线性规划的应用

例 1. 市场上有[math]n[/math]种资产[math]s_i (i = 1, 2, \cdots, n)[/math]可以选择，现用数额为[math]M[/math]的相当大的资金作一个时期的投资。这[math]n[/math]种资产在这一时期内购买[math]s_i[/math]的平均收益率为[math]r_i[/math]，风险损失率为[math]q_i[/math]，投资越分散，总的风险越少，总体风险可用投资的[math]s_i[/math]中最大的一个风险来度量。购买[math]s_i[/math]时要付交易费，费率为[math]p_i[/math]。另外，假定同期银行存款利率是[math]r_0[/math]，既无交易费又无风险[math]r_0 = 5\%[/math]。已知[math]n = 4[/math]时相关数据如下表所列。请你为该公司设计一种投资方案，使净收益尽可能大，总体风险尽可能小。

解题思路

确定目标函数 [math]\begin{cases} \max \sum_{i = 0}^{n} (r_i – p_i) x_i \\ \min \left\{ \max_{1 \leqslant i \leqslant n} \{ q_i x_i \} \right\} \end{cases}[/math], 约束条件为 [math]\begin{cases} \sum_{i = 0}^{n} (1 + p_i) x_i = M, \\ x_i \geqslant 0, \, i = 0, 1, \cdots, n \end{cases}[/math]

我们的目标函数有两个，这并不符合我们的模型，所以这里有一点不同：

实际投资中，我们往往是把风险量化到一个可控的范围内，例如最大可接受风险为 [math] a [/math]，即

[math]\frac {q_i x_i}{M} \leqslant a \ (i = 1, 2, \cdots, n)[/math]

所以调整之后的目标函数是 [math]\max\sum_{i = 0}^{n} (r_i – p_i) x_i [/math]，而此时的约束条件多了一个，最终得到的约束集为 [math]\begin{cases} \sum_{i = 0}^{n} (1 + p_i) x_i = M, \\ x_i \geqslant 0, i = 0, 1, \cdots, n \\ \frac{q_i x_i}{M} \leqslant a \end{cases}[/math]