Linear Programming

线性规划（Linear programming，简称 LP），是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，是最优化问题中的一个重要领域，也是辅助人们进行科学管理的一种数学方法。在作业研究中所面临的许多实际问题都可以用线性规划来处理，特别是某些特殊情况，例如：网络流、多商品流量等问题。

线性规划问题所建立的数学模型具有以下特点：

1. 每个模型都有若干个决策变量（，，…，），其中 n 为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。

2. 目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。

3. 约束条件也是决策变量的线性函数（等式或不等式）。

一般线性规划问题的数学模型可表示为：

$MAX(min)z=\sum_{j=1}^{n}c_{j}x_{j}$

$\begin{array}{c} &s.t.\quad\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \leq (or \geq, =) b_i & (i=1,2,3,\cdots, m)\\x_j \geq 0 & (j=1,2,3,\cdots,n)\end{cases} \end{array}$

其中， ， 和 和均为固定常数

因此，当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。