2.1 线性规划的基本概念

2.1.1 线性规划的数学模型

在生产管理和经营活动中常常提出一类问题，即如何合理地利用有限的人力、物力、财力及时间等资源，以得到最好的经济效果。这类问题大部分可表示为如下的规划问题：在一定的约束条件(限制条件）下,使得某一目标函数取得最大(或最小）值。当规划问题的目标函数与约束条件都是线性函数时，便称为线性规划问题。下面通过一些具体例子来介绍线性规划的数学模型。

某工厂在计划期内要安排生产A、 B两种产品(假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表 2 -1 所示。问应如何安排生产使该厂获利最大?

首先建立问题的线性规划模型，通常有以下几个步骤:

(1)确定决策变量。决策变量是模型要决定的未知量，或者说是决策者采用的模型所规定的抉择方案。确定合适的决策变量是成功地建立数学模型的关键。在本例中，工厂要确定各种产品的生产数量，因此可设 x ₁ 、 x ₂ 分别表示在计划期内产品A、 B的产量。

(2)确定目标函数，就是将决策者所追求的目标表示为决策变量的函数。很明显，本例的目标函数是使 z = 70 x ₁ + 120 x ₂ 最大。可写为:

(3)确定约束条件。这些约束条件可用决策变量的等式或不等式来表示。在例 1 中，资源的使用量必须受到限制，因此有

此外，显然还应有变量非负约束条件，即 x ₁ ≥0, x ₂ ≥0。

综上所述，我们便得到如下的数学模型:

模型中所用的s. t.是“subject to” (受约束于）的缩写，它表明决策者的行为受后边限制条件的约束。

上述模型的解称为最优解。下面将看出其最优解为 x ₁ = 20, x ₂ = 24;目标函数最优值为 z = 4 280。这说明该厂的最优生产计划是：生产产品A 20 单位，生产产品B 24 单位，可获得最大利润 4 280 元。

某公司饲养实验用的动物以供出售。已经知道这些动物的生长对饲料中的三种营养元素特别敏感，我们分别称它们为营养元素A、 B和C。已求出这些动物每天至少需要 700克营养元素A、 30 克营养元素B,而营养元素C的每天需要量刚好是 200 毫克，不够或者过量都是有害的。现有五种饲料可供选用，各种饲料每千克所含的营养元素及单价如表2 -2所示。为了避免过多使用某种饲料，规定混合饲料中各种饲料的最高含量分别为 50、60、50、70、40 千克。要求确定满足动物需要而费用最低的饲料配方。

解：设 x _j ( j = 1,…,5)为每天混合饲料内包含的第 j 种饲料的千克数，则营养问题的线性规划模型如下:

使用软件求解，可得最优解: x ₁ =50, x ₂ =3, x ₃ =0, x ₄ =70, x ₅ =40，目标函数最优值 z =951。因此，最优饲料配方是每天混合50 千克第1 种饲料，3 千克第2 种饲料，70 千克第4 种饲料以及40 千克第5 种饲料，最低成本为951 元。

某医院根据日常工作统计，每昼夜 24 小时中至少需要下列数量的护士。

护士们分别在各时段开始时上班，并连续工作 8 小时，问应如何安排各个时段开始上班工作的人数，才能使护士的总人数最少?

解：设第 j 时段开始上班的人数为 x _j , j = 1,…,6,则 为护士的总人数，因此有如下模型:

上机求解可得最优解 x ₁ = 50, x ₂ = 20, x ₃ = 50, x ₄ = 0, x ₅ = 20, x ₆ = 10,最优值 z =150。因此，医院至少应配备 150 名护士。

请读者使用例 3 的建模思路，解下列思考题。

思考题： 一家银行每天营业的时间从上午 9 时到下午 5 时。除了管理层外，银行最多可雇用 12 名全职员工，其余均为兼职员工。全职员工上午 9 时上班，下午 5 时下班，中间有 1 小时的午餐休息时间(一半全职员工在 11 时进餐，另一半在中午 12 时进餐）。兼职员工每天连续工作 4 小时，可以安排在上午 9 时到下午 1 时的任意整点时刻上班。一天中各时段所需员工的数目如下:

全职员工的平均工资是每天 250 元，而兼职员工的平均工资是每小时 20 元(每天 80元）。银行规定兼职员工每天的总工作时间不能超过所需工作时间的一半，并允许不雇用一些全职员工。试求该银行支付最少工资的安排方案。

提示：最优安排方案不唯一，其中之一是：雇用 10 名全职员工，并安排 2 名、7 名和5 名兼职员工分别在上午 10 时、11 时和中午 12 时开始上班。每天支付的最少工资额为3 620元。

从以上三个例子可以看出，线性规划问题是寻求满足若干线性等式与不等式的一组变量值以使得某一个线性函数取得最大值或最小值的极值问题。它的一般形式为:

其中, z 称为目标函数,(2.2)、(2.3)称为约束条件;(2.3)也称为变量的非负约束条件。对于所有求解线性规划的软件，条件(2.3)几乎都是默认的。

若向量 X = ( x ₁ , x ₂ ,…, x _n ) ^T 满足所有的约束条件，则称其为可行解，而使目标函数达到最大值(或最小值）的可行解称为最优解。最优解的目标函数值称为最优值。

在此，有必要说一下线性规划问题隐含的假设，这就是比例性、可加性、可分性和确定性假设。

(1)比例性假设：每个决策变量的变化所引起目标函数的改变量及约束条件左端的改变量与该变量的改变量成正比例。

(2)可加性假设：每个决策变量对目标函数和约束条件的贡献是独立于其他变量的。总贡献是每个决策变量单独贡献之和。

(3)可分性假设：每个决策变量都允许取分数值。换言之，决策变量允许为非整数值。

(4)确定性假设：每个参数( c _j , a _ij , b _i )都是确定性已知的。在线性规划问题中不涉及随机因素。

在现实生活中，完全满足这些条件的问题是很有限的。但若问题近似满足这些条件，仍然可使用线性规划进行求解和分析。否则，可考虑使用其他方法，如非线性规划、整数规划、参数规划或随机性分析方法等。

2.1.2 线性规划的图解法

简单的线性规划问题可用图解法求解。图解法虽然实际应用意义不大，但简单直观，有助于初学者了解线性规划问题的几何意义及求解基本原理。现用图解法求解例 1。由于例 1 只有两个变量，我们可以在平面直角坐标系中描述该问题(如图 2 -1 所示)。

首先，变量非负条件 x ₁ , x ₂ ≥0 是指第一象限。每个不等式约束都代表一个半平面，例如，第一个约束表示以直线 9 x ₁ + 4 x ₂ = 360 为边界的左下方的半平面。同时满足所有约束条件的点必然落在由三个半平面与第一象限相交的区域内，即图 2 -1 的阴影部分。阴影区域中的每一个点(包括边界点）都是例 1 线性规划问题的可行解，因而此区域是可行解的集合，称它为可行域。

目标函数 z = 70 x ₁ + 120 x ₂ 在坐标平面上表示以 z 为参数的一族平行线，其法向量是任一与向量(70,120)平行且同向的向量。任选一个 z ,便可得到一条直线，该线上所有可行点都有相同的目标函数值，因此被称为等值线。让等值线沿其法线方向平行移动，目标函数值将逐渐增加，当移到 B 点后，再向外移就会脱离可行域，因此, z 值最大的等值线与可行域的公共点 B 便是最优解。它是两条直线 4 x ₁ + 5 x ₂ = 200 与 3 x ₁ + 10 x ₂ = 300 的交点，其坐标为(20,24),于是可计算出相应的 z = 70 × 20 + 120 × 24 = 4 280。

上例求出的最优解是唯一的，但对一般线性规划问题，求解还可能出现以下几种情况。

(1)无穷多个最优解。若将例 1 中的目标函数改为求max z = 70 x ₁ + 87.5 x ₂ ,则等值线族与可行域的边界线 4 x ₁ + 5 x ₂ = 200 平行(如图 2 -2 所示）。易见，线段 BC 上任意一点都使 z 取得相同的最大值，所以这线性规划有无穷多个最优解。

(2)无界解。

对下述线性规划问题

用图解法的求解结果如图 2 -3,从图中可以看到，在可行域中，目标函数值可以趋向于正无穷大，因此，该问题有可行解但没有最优解。这种情况称为问题具有无界解或问题无界。

(3)无可行解。如果在例 1 的数学模型中增加一个约束条件 x ₁ + x ₂ ≥60,所得到的新问题的可行域为空集，即无可行解，此时当然不存在最优解。

当求解结果出现(2)、(3)两种情况时，一般说明建立的线性规划模型有缺陷或错误，尤其是后者有相互矛盾的约束条件，应对模型进行修改。

从以上的例子，我们可以直观地看到二维线性规划的两个几何特征:

(1)若可行域非空，它是一个凸集。通俗地讲，如果一个集合 S 中任意两个点之间的连线都在 S 中，则称 S 是凸集。例如，图 2 -4 中的( a)和( b)是凸集，而( c)和(d)不是凸集。

(2)若线性规划存在最优解，它一定可在可行域的某个顶点(极点）得到(直观地说，凸集的极点不是凸集中任一线段的内点)。

以后将指出，高维的线性规划也有这两个特征。读者不妨想象一下三维线性规划可行域的形状以及最优解在可行域中的位置。

对于变量数多于三个的线性规划问题，图解法就无能为力了。所以下一节将介绍一种有效的代数法——单纯形法。为了便于讨论，我们先规定线性规划的标准形式。

2.1.3 线性规划的标准型

由上面的例子可知，线性规划问题的具体形式往往很不一致。目标函数可以是求max的，也可以是求min的；约束类型可以是“≥”“≤”或“= ”;决策变量一般有非负限制，但也允许非正或无限制。为了便于统一处理，有必要规定线性规划的标准形式(SLP),本书使用的标准型为:

并规定各约束条件的右端项 b _i ≥0,否则，可在等式两端乘以“-1”。

这样,(SLP)的约束条件由约束方程组和变量非负条件两部分组成。

(SLP)可简写为:

引入下面的记号:

则(SLP)还可表述成以下两种形式。

用矩阵描述:

用向量描述:

一般称 C 为价值向量, B 为资源向量, A 为技术系数矩阵。

实际上，各种线性规划模型都需要转化成标准型后求解。下面介绍各种转化方法。

(1)最小化问题的转化。求min z 等价于求max (- z ),因此，只需改变目标函数的符号就可以实现最大化和最小化之间的转换。

(2)不等式约束的处理。不等式约束可以通过引入松弛变量或剩余变量转化为等式约束，具体为:

其中 x _s 称为松弛(slack)变量。

其中 x _s 称为剩余(surplus)变量。

(3)非正变量与符号无限制变量的处理。

若 x _k ≤0,令 = - x _k ,则新变量 为非负变量。

若 x _k 为符号无限制变量(称为自由变量），可令 ,其中 ， ,即以两个非负变量之差来代替自由变量。

从以上讨论可见，任何形式的线性规划都可转化为标准型，下面举例说明。

只需引入松弛变量 x ₃ , x ₄ , x ₅ 即可转化为标准型:

解：步骤如下:

(1)令 x ₁ = - , x ₃ = x ₄ - x ₅ ,其中 x ₄ , x ₅ ≥0;

(2)在第一个约束不等式“≤”号的左端加入松弛变量 x ₆ ,在第二个约束不等式“≥”号的左端减去剩余变量 x ₇ ;

(3)令 z′ = - z ,把求min z 改为求max z′ ,于是便可以得到该问题的标准型:

上述标准型有三个约束方程、六个非负变量。若我们一开始就从原问题的等式约束3 x ₁ + x _{2 -3} x ₃ = 5 解出自由变量 x ₃ ,代入目标函数与其他约束条件，然后再进行其他变换，将得到只有两个约束方程、四个非负变量的标准型。这样做可减小问题的规模。

由于任何形式的线性规划都能转化为(SLP),以下我们将以(SLP)为主要研究对象。

2.1.4 高斯迭代

此时，技术系数矩阵和资源向量矩阵构成的增广矩阵为:

将 x ₁ , x ₂ 移到右边，左边保留 x ₃ , x ₄ , x ₅ ,则约束条件①变为:

令 x ₁ = x ₂ = 0,则 x ₃ = 360, x ₄ = 200, x ₅ = 300,得到第一个可行解:

在目标函数中，因为 x ₁ , x ₂ 的系数为正，即 σ ₁ = 70, σ ₂ = 120,且 σ ₂ > σ ₁ ,将 x ₂ 换到左边可以改善目标函数的值，此时 x ₁ 仍然保留在右边，即 x ₁ = 0 。

对应条件②,要保持 x ₃ , x ₄ , x ₅ ≥ 0,则对应的 x ₂ ≤ = 90 ; x ₂ ≤ = 40 ; x ₂ ≤ = 30,即 θ = min {90,40,30} = 30,该结果意味着 θ = 30 对应的 x ₅ 趋于零的速度比 x ₃ 、 x ₄ 快。因此，将 x ₅ 换到右边。

左边的变量为 x ₂ , x ₃ , x ₄ ,右边的变量为 x ₁ , x ₅ ,则约束条件①变为:

对③进行行变换，得到

此时，增广矩阵为:

令 x ₁ = x ₅ = 0,则 x ₃ = 240, x ₄ = 50, x ₂ = 30,得到第二个可行解:

同样，在目标函数中，虽然 x ₅ 的系数为负，但是 x ₁ 的系数为正，即 σ ₁ = 34, σ ₅ = -12,将 x ₁ 换到左边可以改善目标函数的值，此时 x ₅ 仍然保留在右边，即 x ₅ = 0 。

对应条件④,要保持 x ₃ , x ₄ , x ₂ ≥0,则对应的 x ₁ ≤7 ≈30.77 ; x ₁ ≤ = 20 ; x ₁ ≤ = 100,即 θ = min {30.77,20,100} = 20,该结果意味着 θ = 20 对应的 x ₄ 趋于零的速度比 x ₃ 、 x ₂ 快。因此，将 x ₄ 换到右边。

左边的变量为 x ₁ , x ₂ , x ₃ ,右边的变量为 x ₄ , x ₅ ,则约束条件①变为:

对⑤进行行变换，得到

此时，增广矩阵为:

令 x ₄ = x ₅ = 0,则 x ₃ = 84, x ₁ = 20, x ₂ = 24,得到第三个可行解:

在目标函数中, x ₄ , x ₅ 的系数为负，即 σ ₄ = - 13.6 < 0, σ ₅ = - 5.2 < 0 ,目标函数的值再也没有改善的空间了，所得到的目标函数值 4 280 为最优目标函数值。

2.1.5 基可行解

考虑线性规划的标准型:

我们假设：约束方程组的系数矩阵 A 的秩为 m ( rank A = m ),且 m < n 。熟悉线性代数的读者不难看出，这个假设条件是非本质的。

对于(SLP)问题，同样有可行解、最优解等概念。由于它的特定结构，我们只需研究一些特殊解。下面讨论基和基可行解的概念。

基 若 B 是矩阵 A 中的 m × m 阶非奇异子矩阵(即 B 的行列式| B | ≠0),则称 B 是(SLP)的一个基。这就是说，基 B 是由 A 中的 m 个线性无关的列向量组成的。

不失一般性，我们可以假定 B 是由 A 的前 m 列组成的，即

B = ( P ₁ , P ₂ ,…, P _m )

称与基相对应的变量 x ₁ ,…, x _m 为基变量，用 X _B 表示。余下的变量称为非基变量。

在方程组(2.5)中，令所有非基变量 x _m + 1 , x _m + 2 ,…, x _n 取零值，则可以解出基变量 x ₁ ,…, x _m ,称 X = ( x ₁ ,…, x _m , ) ^T 为基解。

基解不一定取非负值，因此不一定是可行解。我们引入基可行解的概念。

基可行解 满足非负条件(2.6)的基解称为基可行解( basic feasible solution,简记为bfs)。相应的基称为可行基。

若某基可行解存在取零值的基变量，则称它为退化的基可行解；否则，称为非退化的基可行解。

由基解定义可以看出，基解数目最多是 个，而基可行解的个数又不会超过基解的个数，因此，基可行解的个数是有限的。

解：很显然 X = (0,0,0,0,0)为规划问题的可行解，这里 m = 3, n = 5。约束方程组的系数矩阵为:

易见( P ₃ , P ₄ , P ₅ )= 为一个基。令非基变量 x ₁ , x ₂ = 0,由方程组可解出 x ₃ = 360, x ₄ = 200, x ₅ = 300,因此得到基解 X ⁽⁰⁾ = (0,0,360,200,300) ^T ,也是基可行解。

另外,( P ₂ , P ₄ , P ₅ )也是一个基。令非基变量 x ₁ , x ₃ 取零值，可得到相应的基解 X ⁽¹⁾ = (0,90,0,-250,-600) ^T ,但不是基可行解。

又( P ₂ , P ₃ , P ₄ )也是一个基，相应的基解 X ⁽²⁾ = (0,30,240,50,0) ^T 也是基可行解。

上面求出的两个基可行解 X ⁽⁰⁾ 和 X ⁽²⁾ 都是非退化的。

读者不难发现例 6 的基可行解与图 2 -1 中可行域的各个顶点相对应，具体 X ⁽⁰⁾ 对应于 O 点, X ⁽²⁾ 对应于 A 点……这正是基可行解的几何意义。

在 2.1.2 节中通过对二维线性规划的讨论，得到了线性规划的一些重要的直观几何特征。这些特征对于高维线性规划问题仍然是正确的。由于篇幅所限，这里不详细讨论，有兴趣的读者可参阅有关书目。下面只列出主要的结论:

(1)(SLP)的基可行解对应于其可行域的顶点(极点)。

(2)若(SLP)有最优解，则必有最优基可行解。

根据以上结论，为求解( SLP),我们可以把注意力放在数量有限的基可行解上，并设计一种迭代方法，从一个基可行解转移到另一个“更好”的基可行解（这里“更好”的意义是目标函数值得到改善），直至找到最优基可行解或者获得无最优解的信息为止。这个方法就是我们接下来要介绍的单纯形法。 nWzs1BgRV6efgWSQGmbJVyghGaapjKkaEAnxEvgLlwR2v/W4ljZskb6Zu0lJXV2M