Page 122 - 数学建模算法与应用
P. 122
Mathematical Modeling Algorithms and Applications
数学建模算法与应用
其中，cc 是目标函数的系数向量，AA 和 AeqAeq 是不等式和等式约束的系
数矩阵，bb 和 beqbeq 是等式和不等式约束的右手向量，xx 是决策变量向量。
在人们的生产实践中，他们经常遇到如何利用现有资源安排生产以实现最大
经济效益的问题。这类问题构成了运筹学的一个重要分支——数学规划，而线性
规划（LP）是数学规划的重要分支。自 1947 年 G B.Dantzig 提出求解线性规划
的单纯形法以来，线性规划在理论上日益成熟，在实践中得到了广泛的应用。特
别是随着计算机能够处理具有数千个约束和决策变量的线性规划问题，线性规划
的适用性变得更加广泛，已成为现代管理中常用的基本方法之一。
二、线性规划条件化为标准形式的步骤
将线性规划问题化为标准形式通常需要经过以下几个步骤：
（一）目标函数标准化
如果目标函数是最大化问题，可以通过取相反数将其转化为最小化问题。
例如，如果目标函数是 maximize cTxmaximize cTx，则可以转换为 minimize
cTxminimize cTx。
（二）约束条件标准化
将所有不等式约束转换为等式约束。这可以通过引入松弛变量（对于 ≤≤ 约束）
或剩余变量（对于 ≥≥ 约束）来实现。例如，对于不等式约束 Ax≤bAx≤b，可以
引入松弛变量 ss 使其变为等式 Ax+s=bAx+s=b，其中 s≥0s≥0。
（三）变量非负化
确保所有决策变量都是非负的。如果变量 xixi 可以取负值，则可以用两个非
负变量之间的差替换它，即 xi=xi+-xi-xi =xi+ -xi- ，其中 xi+，xi-≥0xi+ ，xi- ≥0。
三、 基本概念
在求解线性规划问题时，有几个基本概念需要明确：
基：指线性规划问题中约束矩阵 AA 的子集，其中列向量是线性独立的。
112
