线性规划模型

[拼音]：xianxing guihua moxing

[外文]：linear programming model

一种特殊形式的数学规划模型，即目标函数和约束条件是待求变量的线性函数、线性等式或线性不等式的数学规划模型。它可用于解决各种领域内的极值问题。它所描述的典型问题是怎样以最优的方式在各项活动中间分配有限资源的问题。

任何一个线性规划问题可以按下列方式表述：假设有м项有限的资源要在n项活动中间进行分配。给各项资源规定脚标1，2，…，м，给各项活动规定脚标1，2，…，n，设x _j（即决策变量，有时亦称控制变量）为j项活动的水平，j=1，2，…，n。决策变量x₁，x₂，…，x _n的一组数值代表一个方案（或计划）。设 z为选定的某个效益量度（总效益指标），它的数值衡量当采取一组活动水平（x₁，x₂，…，x _n）时所得到的总效益。设c _j为每一单位的x _j所提供的效益。设 b _j为i项资源在分配时可被利用的量，最后，设a _ij（i=1，2，…，м；j=1，2，…，n）为i项资源被每单位j 项活动所消耗（或使用）的量。于是，将各项资源分配给各项活动以获得最优化结果的规划问题具有下列数学模型：

选择x₁，x₂，…，x _n的值，借以使z=c₁x₁+c₂x₂+……+c _n x _n达到最大，且满足下列各项限制条件：a₁₁x₁+ a₁₂x₂+……a_1n x _n≤b₁

a₂₁x₁+ a₂₂x₂+……+a_2n x _n≤b₂

a _m1x₁+a _m2x₂+……+a_mnx_n≤b_m

及x₁≥0，x₂≥0，…，x_n≥0

这个数学模型可以等价地表述为下列更为简洁的矩阵形式：

选择x的值，借以使z=c^Tx达到最大，且满足下列条件：A X≤b

x≥0

式中x =（x₁，x₂…，x _n）^T（n维列向量）

c^T=（c₁，c₂，…c _n）（n维行向量）

b=（b₁，b₂，…b _m）^T（m维列向量）

（м×n矩阵）

线性规划模型的几何意义是：在R^（n）内给定了一个多面体Ω ={x/（A x ≤b，x≥0）}，同时还给定了一个向量c，要求找出向量x∈Ω，使得x与c的内积达到最大。

线性规划模型中z称为目标函数，A x≤b和x≥0称为约束条件；x是决策变量，A、b以及c称为模型的参数。

以上是线性规划模型的典型形式。

然而，在实际工作中，并不是所有的线性规划问题都能表述为典型形式的数学模型，而可能出现下列情形：

（1）使目标函数z达到最小，而不是使z达到最大；

（2）约束条件组A x≤b被破坏，即其中有些约束条件是“≥”的不等式；

（3）有些约束条件是等式；

（4）非负性约束条件 x≥0被破坏。

在上述几种情况下，只需将模型的有关部分加以改写，便可使模型等价地变成典型形式。