1.1　线性规划模型的基础知识

线性规划模型是运筹学中研究较早、发展较快、应用较广、方法成熟的一个重要分支。它是辅助人们进行科学管理的一种数学方法，为合理地利用有限的人力、物力、财力等资源并做出最优决策提供科学的依据，具有较强的实用性。

就模型而言，线性规划模型形式类似于高等数学所学的条件极值问题表达，只是其目标函数和约束条件都被限定为线性函数。线性规划模型的特点如下：

1.目标函数是由决策变量构成的线性函数。

2.约束条件都是决策变量构成的线性等式或线性不等式。

具有以上结构特点的模型就是线性规划模型，简记为LP(Linear Programming)。它具有如下一般数学形式：

首先，让我们分析线性规划具有哪些特征，或实际问题具有什么性质，所建立的数学模型才可被称为线性规划模型。

比例性：每个决策变量对目标函数的“贡献”与该决策变量取值成正比；每个决策变量对每个约束条件右端项的“贡献”与该决策变量取值成正比。

可加性：每个决策变量对目标函数的“贡献”与其他决策变量取值无关；每个决策变量对每个约束条件右端项的“贡献”与其他决策变量取值无关。

连续性：每个决策变量在连续范围内进行取值。

然后，我们简单介绍线性规划模型的理论求解方法。对于线性规划模型而言：满足全部约束条件的决策向量x∈Rn称为可行解；全部可行解构成的集合（它是n维欧氏空间Rn中的点集，而且是一个凸多面体）称为可行域；使目标函数达到最优值（最大值或最小值，并且有界）的可行解称为最优解。当线性规划模型存在最优解时，其一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，至少其中有一个最优解是可行域的一个顶点。1947年，美国数学家丹捷格及其同事提出的求解线性规划的单纯形法及有关理论具有划时代的意义。他们的工作为建立线性规划学科奠定了重要的理论基础。丹捷格提出了一种在凸多面体的顶点中有效地寻求最优解的迭代策略。凸多面体顶点所对应的可行解称为基本可行解，单纯形法的基本思路为：先找出一个基本可行解，对它进行鉴别，判断该基本可行解否是为模型的最优解；若不是最优解，则按照一定法则转换到另一个改进的基本可行解，再次判断该基本可行解是否为模型的最优解；若仍不是最优解，则再次进行转换，按此思路重复进行。由于基本可行解的数量有限，故经有限次转换必能得出问题的全局最优解。随着1979年苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家卡玛卡尔的Karmarkar算法相继问世，线性规划理论更加完备、成熟，实用领域更加宽广。目前，线性规划模型的求解理论已经非常完善。在数学建模过程中，建立线性规划模型并求解已经不再是一件困难的事情。建议学有余力的读者可以参考运筹学相关书籍学习线性规划的基础理论知识。掌握线性规划理论知识有助于读者更好地建立以及求解线性规划模型。