第二节线性规划问题及其数学模型

应用线性规划解决经济、管理领域的实际问题，最重要的一步是建立实际问题的线性规划模型。建立数学模型既要对需要解决的实际问题有深入的了解和分析，同时还要掌握模型的结构特点，因为任何一种模型及其求解方法的使用都是有一定条件的。一般来讲，一个经济、管理领域的实际问题需要满足以下条件，才能建立线性规划模型：

(1)要求解问题的目标函数能用数值指标来反映，且为线性函数；

(2)存在着多种可供选择的方案；

(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。

在建立线性规划模型时，要仔细了解和分析实际问题，整理已知数据和相关信息，然后按以下步骤建立适当的模型：

(1)分析问题：确定决策内容、要实现的目标以及所受到的约束条件。

(2)设立合适的决策变量并规定其取值范围。决策变量的选取很关键，直接影响到模型的建立及是否能方便地求解。

(3)建立目标函数。用决策变量的线性函数来表示实际问题的目标，标出对函数是取极大还是极小的要求。

(4)用关于决策变量的线性等式或不等式来表示约束条件。当约束条件多且背景比较复杂时，可用图示或表格形式列出所有的已知数据和信息，避免遗漏或重复。

1.2.1问题引入

【例1.1】某企业在计划期内要安排生产甲、乙两种产品，已知每吨产品的生产利润及原材料消耗量如表1-1，问应如何安排生产计划使该企业获得的利润最大？

表1-1 某企业在计划期内生产产品、资源信息

解：这个生产计划问题可用数学语言来描述，即可用数学模型表示。设计划期内产品甲、乙的生产量分别为：吨，用表示两种产品带来的利润，则，企业追求的目标是使利润达到最大值，用数学表达式描述为：

式中，表示对利润函数求最大值。

资源消耗不能超过资源限制量，用数学表达式描述为：

对原材料 A：

对原材料 B：

对原材料 C：    

最后，产品的产量不能小于零，用数学表达式描述为：。

综合上述，该生产计划问题可用数学模型表示为：

【例1.2】某工地租赁甲、乙两种机械来安装A、B、C三种构件，这两种机械每天的安装能力见表1-2。工程任务要求安装250根A构件，300根B构件和700根C构件。又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁甲、乙机械各多少天，才能使总租赁费最少？

表1-2 机械安装能力

解：设租赁机械甲天，机械乙天。为满足A、B、C三种构件的安装要求，必须满足以下条件：

若用表示总租赁费，则该问题的目标函数可表示为。

该问题的数学模型可表示为：

上述两个数学模型中，都存在一组变量，且变量受线性不等式的约束，需要解决的问题是求由变量组成的线性函数的最大值或最小值。

1.2.2线性规划数学模型的一般形式

满足以下三个条件的数学模型称为线性规划的数学模型。

(1)每个问题都用一组决策变量()表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。

(2)存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。

(3)都有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。

线性规划数学模型的一般式为：

或者写成缩写形式：

上述模型中，是subject to的缩写，即“满足于”的意思；称为决定变量；式(1-1)中的函数称为目标函数，为价值系数；式(1-2)、式(1-3)称为约束条件，称为技术系数，由系数构成的矩阵A称为约束矩阵，即：

称为限额系数；式(1-3)也称为变量的非负约束条件。

1.2.3线性规划数学模型的标准形式

从线性规划数学模型的一般式中可以看出，目标函数有求最大值的，也有求最小值的；约束条件可是等式也可以是不等式；决定变量一般是非负约束，但也允许在(−∞，∞)范围内取值，即无约束。为了便于讨论和求解，需要将线性规划问题的数学模型写成一个统一格式，称为线性规划问题的标准型。其统一格式规定如下：

(1)目标函数取最大化(也可最小化)；

(2)所有约束条件用等式来表示；

(3)所有决策变量取非负值；

(4)每一约束条件的右端常数(限额系数)为非负值。

由此，线性规划问题的标准型为：

也可用以下形式表示：

为了方便起见，引进下列矩阵符号：

价值变量：

决策变量：

资源向量：

约束条件的系数矩阵：

于是，线性规划模型可以写为：

对非标准形式的线性规划模型，可分别通过下列方法化为标准形式：

目标函数的标准化。若目标函数为求极小值，即为。因为求等价于求，所以只需令=，即，就与标准形式的目标函数一致了。

(2)决策变量的标准化。当≤0时，令＝－，则≥0；当无符号限制时，令＝－，其中，≥0。

(3)右端系数的标准化。约束条件右端的系数为负数时，将约束条件两端同乘(-1)就可得到非负的。

(4)约束条件的标准化。当约束条件为“≤”型时，在不等式的左端加入一个非负变量(称为松弛变量)，即可把原不等式变为等式；当约束条件为“≥”型时，则在不等式的左端减一非负变量(称为剩余变量，也可称为松驰变量)，即可把原不等式变为等式。

以下所涉及到的线性规划问题，如无特别说明，都指的是标准型。

【例1.3】将例1.1的线性规划数学模型化为标准型。

解：例1.1的数学模型为：

在前三个约束条件的左边分别加上一个非负的松驰变量，使“”型的不等式变为等式，即可得到标准的线性规划模型：

【例1.4】将下述线性规划数学模型化为标准型。

解：因为目标函数为极小值型，先令=，目标函数写成；因为决策变量无约束，令其中，将新引入的变量代替原来相应的变量；在第一、第二个约束条件的左端分别减去非负剩余变量，在第三个约束条件的左端加上非负松驰变量，最后将第一个约束条件两端同乘以(-1)，使右端的系数化为正数。通过以上步骤，得到该线性规划模型的标准型如下：

1.2.4线性规划问题的有关概念

线性规划问题：

其中A为×阶矩阵，≤，A的秩为。

(1)可行解

满足约束条件(1-10)、(1-11)的解称为线性规划问题的可行解，全部可行解的集合称为可行域。

(2)最优解

满足(1-9)的可行解称为最优解，即使得目标函数达到最大值的可行解称为最优解。

(3)基

若A中阶子矩阵B的秩为，则称B是该线性规划的一个基(或称基矩阵)。B由A中任何一组个线性无关的列向量构成，当时，基是唯一的，当时，基会有多个，但数目不超过。

(4)基向量、非基向量、基变量、非基变量

基矩阵对应的列向量称为基向量，其余向量称为非基向量。基向量对应的变量为基变量，一般用表示；非基向量对应的变量为非基变量，一般用表示。

(5)基本解(基解)

对某一确定的基B，令非基变量为零，利用约束条件(1-10)解出基变量的值，称这组解为基B的基本解，也称为基解。

(6)基本可行解(基可行解)

满足非负条件(1-11)的基解称为基本可行解，也称为基可行解。

(7)可行基、最优基

基可行解对应的基称为可行基；最优解对应的基为最优基。

(8)退化解

若基可行解中某基变量为零，称其为退化解。非退化解中只有非基变量为零，共有个。退化解中零分量的个数超过个，即非零分量的个数小于个。

在例1.1的数学模型的标准式中，约束方程(1-5)、(1-6)、(1-7)的系数矩阵为3×5矩阵

容易看出是A中3×3子矩阵，且B的秩为3，即B是该线性规划问题的一个基，为基向量，对应的变量为基变量，为非基向量，对应的变量为非基变量。

令非基变量，代入给约束条件(1-5)式、(1-6)式、(1-7)式，可求得，则为一个基解，又因为它满足非负条件(1-8)式，所以也是基可行解，矩阵B是基可行基，但不是最优基。

(8)凸集

若集合C中任意两点，其连线上的所有点也都是集合C中的点，则称C为凸集。直观地看，就是区域内任两点的连线仍然在区域内。用数学解析式可表述为：若∈C，∈C，有+()∈C，(0≤≤1)，则称C为凸集。图1-1中，()，()是凸集，()，()不是凸集。

()          ()              ()            ()

图1-1

(9)凸组合

是集合C中的个点，若有一组正数，满足：，使，则称为的凸组合。

(10)顶点

设C是凸集，点，若找不到两个不同的点，使得()，则称为C的顶点。

1.2.5线性规划问题的基本定理

定理1-1：若线性规划问题存在非空的可行域C，则C一定是凸集。

证：设线性规划问题的可行域为集合C：C={|，³0}

任取，则：(0≤≤1)

又因为，，

所以

则，C为凸集，证毕。

引理1：线性规划问题的可行解为基可行解的充要条件是的正分量所对应的系数列向量是线性独立的。

定理1-2：线性规划问题的可行解为基可行解的充要条件是点是可行域的顶点。

证：分别用反证法证上述定理的充分性和必要性。

设基可行解的前个分量为正。则：         (1-12)

先证若不是基可行解，则它一定不是可行域的顶点。根据引理1，若不是基可行解，则其正分量所对应的系数列向量线性相关，即存在一组不全为零的数，使得

                             (1-13)

用一个的数乘(1-13)式再分别与(1-12)式相加和相减，可得到：

现取：

由可以得到，即是连线的中点。

当充分小时，，，即是可行解，这证明了不是可行域的顶点。

再证若不是可行域的顶点，则它一定不是基可行解。因为不是可行域的顶点，故在可行域中可找到不同的两点：,

使，()

设是基可行解，对应向量组线性独立。当时，有，由于是可行域的两点。应满足：

将这两式相减，即得：

因，所以上式系数不全为零，故向量组线性相关，与假设矛盾，即不是基可行解，证毕。

引理2：若K是有界凸集，则任何一点可表示为的顶点的凸组合。

定理1-3：若线性规划问题的可行域有界，则目标函数一定可以在可行域的顶点上达到最优。

证：设是可行域的顶点，若不是顶点，且目标函数在处达到最优=(标准型是)。

因不是顶点，所以它可以用可行域C的顶点线性表示为：，

代入目标函数得：

在所有的顶点中必然能找到某一个顶点，使是所有中最大者。并且将代替上式中的所有，这就得到：

由此得到：

根据假设是最大值，所以只能有，即目标函数在顶点处也达到最大值。

由以上基本定理可知，线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在可行域的顶点上得到。应用线性规划解决经济、管理领域的实际问题，最重要的一步是建立实际问题的线性规划模型。建立数学模型既要对需要解决的实际问题有深入的了解和分析，同时还要掌握模型的结构特点，因为任何一种模型及其求解方法的使用都是有一定条件的。一般来讲，一个经济、管理领域的实际问题需要满足以下条件，才能建立线性规划模型：

(1)要求解问题的目标函数能用数值指标来反映，且为线性函数；

(2)存在着多种可供选择的方案；

(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。

在建立线性规划模型时，要仔细了解和分析实际问题，整理已知数据和相关信息，然后按以下步骤建立适当的模型：

(1)分析问题：确定决策内容、要实现的目标以及所受到的约束条件。

(2)设立合适的决策变量并规定其取值范围。决策变量的选取很关键，直接影响到模型的建立及是否能方便地求解。

(3)建立目标函数。用决策变量的线性函数来表示实际问题的目标，标出对函数是取极大还是极小的要求。

(4)用关于决策变量的线性等式或不等式来表示约束条件。当约束条件多且背景比较复杂时，可用图示或表格形式列出所有的已知数据和信息，避免遗漏或重复。

1.2.1 问题引入

【例1.1】某企业在计划期内要安排生产甲、乙两种产品，已知每吨产品的生产利润及原材料消耗量如表1-1，问应如何安排生产计划使该企业获得的利润最大？

表1-1 某企业在计划期内生产产品、资源信息

解：这个生产计划问题可用数学语言来描述，即可用数学模型表示。设计划期内产品甲、乙的生产量分别为：吨，用表示两种产品带来的利润，则，企业追求的目标是使利润达到最大值，用数学表达式描述为：

式中，表示对利润函数求最大值。

资源消耗不能超过资源限制量，用数学表达式描述为：

对原材料 A：

对原材料 B：

对原材料 C：    

最后，产品的产量不能小于零，用数学表达式描述为：。

综合上述，该生产计划问题可用数学模型表示为：

【例1.2】某工地租赁甲、乙两种机械来安装A、B、C三种构件，这两种机械每天的安装能力见表1-2。工程任务要求安装250根A构件，300根B构件和700根C构件。又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁甲、乙机械各多少天，才能使总租赁费最少？

表1-2 机械安装能力

解：设租赁机械甲天，机械乙天。为满足A、B、C三种构件的安装要求，必须满足以下条件：

若用表示总租赁费，则该问题的目标函数可表示为。

该问题的数学模型可表示为：

上述两个数学模型中，都存在一组变量，且变量受线性不等式的约束，需要解决的问题是求由变量组成的线性函数的最大值或最小值。

1.2.2 线性规划数学模型的一般形式

满足以下三个条件的数学模型称为线性规划的数学模型。

(1)每个问题都用一组决策变量()表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。

(2)存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。

(3)都有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。

线性规划数学模型的一般式为：

或者写成缩写形式：

上述模型中，是subject to的缩写，即“满足于”的意思；称为决定变量；式(1-1)中的函数称为目标函数，为价值系数；式(1-2)、式(1-3)称为约束条件，称为技术系数，由系数构成的矩阵A称为约束矩阵，即：

称为限额系数；式(1-3)也称为变量的非负约束条件。

1.2.3 线性规划数学模型的标准形式

从线性规划数学模型的一般式中可以看出，目标函数有求最大值的，也有求最小值的；约束条件可是等式也可以是不等式；决定变量一般是非负约束，但也允许在(−∞，∞)范围内取值，即无约束。为了便于讨论和求解，需要将线性规划问题的数学模型写成一个统一格式，称为线性规划问题的标准型。其统一格式规定如下：

(1)目标函数取最大化(也可最小化)；

(2)所有约束条件用等式来表示；

(3)所有决策变量取非负值；

(4)每一约束条件的右端常数(限额系数)为非负值。

由此，线性规划问题的标准型为：

也可用以下形式表示：

为了方便起见，引进下列矩阵符号：

价值变量：

决策变量：

资源向量：

约束条件的系数矩阵：

于是，线性规划模型可以写为：

对非标准形式的线性规划模型，可分别通过下列方法化为标准形式：

目标函数的标准化。若目标函数为求极小值，即为。因为求等价于求，所以只需令=，即，就与标准形式的目标函数一致了。

(2)决策变量的标准化。当≤0时，令＝－，则≥0；当无符号限制时，令＝－，其中，≥0。

(3)右端系数的标准化。约束条件右端的系数为负数时，将约束条件两端同乘(-1)就可得到非负的。

(4)约束条件的标准化。当约束条件为“≤”型时，在不等式的左端加入一个非负变量(称为松弛变量)，即可把原不等式变为等式；当约束条件为“≥”型时，则在不等式的左端减一非负变量(称为剩余变量，也可称为松驰变量)，即可把原不等式变为等式。

以下所涉及到的线性规划问题，如无特别说明，都指的是标准型。

【例1.3】将例1.1的线性规划数学模型化为标准型。

解：例1.1的数学模型为：

在前三个约束条件的左边分别加上一个非负的松驰变量，使“”型的不等式变为等式，即可得到标准的线性规划模型：

【例1.4】将下述线性规划数学模型化为标准型。

解：因为目标函数为极小值型，先令=，目标函数写成；因为决策变量无约束，令其中，将新引入的变量代替原来相应的变量；在第一、第二个约束条件的左端分别减去非负剩余变量，在第三个约束条件的左端加上非负松驰变量，最后将第一个约束条件两端同乘以(-1)，使右端的系数化为正数。通过以上步骤，得到该线性规划模型的标准型如下：

1.2.4线性规划问题的有关概念

线性规划问题：

其中A为×阶矩阵，≤，A的秩为。

(1)可行解

满足约束条件(1-10)、(1-11)的解称为线性规划问题的可行解，全部可行解的集合称为可行域。

(2)最优解

满足(1-9)的可行解称为最优解，即使得目标函数达到最大值的可行解称为最优解。

(3)基

若A中阶子矩阵B的秩为，则称B是该线性规划的一个基(或称基矩阵)。B由A中任何一组个线性无关的列向量构成，当时，基是唯一的，当时，基会有多个，但数目不超过。

(4)基向量、非基向量、基变量、非基变量

基矩阵对应的列向量称为基向量，其余向量称为非基向量。基向量对应的变量为基变量，一般用表示；非基向量对应的变量为非基变量，一般用表示。

(5)基本解(基解)

对某一确定的基B，令非基变量为零，利用约束条件(1-10)解出基变量的值，称这组解为基B的基本解，也称为基解。

(6)基本可行解(基可行解)

满足非负条件(1-11)的基解称为基本可行解，也称为基可行解。

(7)可行基、最优基

基可行解对应的基称为可行基；最优解对应的基为最优基。

(8)退化解

若基可行解中某基变量为零，称其为退化解。非退化解中只有非基变量为零，共有个。退化解中零分量的个数超过个，即非零分量的个数小于个。

在例1.1的数学模型的标准式中，约束方程(1-5)、(1-6)、(1-7)的系数矩阵为3×5矩阵

容易看出是A中3×3子矩阵，且B的秩为3，即B是该线性规划问题的一个基，为基向量，对应的变量为基变量，为非基向量，对应的变量为非基变量。

令非基变量，代入给约束条件(1-5)式、(1-6)式、(1-7)式，可求得，则为一个基解，又因为它满足非负条件(1-8)式，所以也是基可行解，矩阵B是基可行基，但不是最优基。

(8)凸集

若集合C中任意两点，其连线上的所有点也都是集合C中的点，则称C为凸集。直观地看，就是区域内任两点的连线仍然在区域内。用数学解析式可表述为：若∈C，∈C，有+()∈C，(0≤≤1)，则称C为凸集。图1-1中，()，()是凸集，()，()不是凸集。

()          ()              ()            ()

图1-1

(9)凸组合

是集合C中的个点，若有一组正数，满足：，使，则称为的凸组合。

(10)顶点

设C是凸集，点，若找不到两个不同的点，使得()，则称为C的顶点。

1.2.5 线性规划问题的基本定理

定理1-1：若线性规划问题存在非空的可行域C，则C一定是凸集。

证：设线性规划问题的可行域为集合C：C={|，³0}

任取，则：(0≤≤1)

又因为，，

所以

则，C为凸集，证毕。

引理1：线性规划问题的可行解为基可行解的充要条件是的正分量所对应的系数列向量是线性独立的。

定理1-2：线性规划问题的可行解为基可行解的充要条件是点是可行域的顶点。

证：分别用反证法证上述定理的充分性和必要性。

设基可行解的前个分量为正。则：         (1-12)

先证若不是基可行解，则它一定不是可行域的顶点。根据引理1，若不是基可行解，则其正分量所对应的系数列向量线性相关，即存在一组不全为零的数，使得

                             (1-13)

用一个的数乘(1-13)式再分别与(1-12)式相加和相减，可得到：

现取：

由可以得到，即是连线的中点。

当充分小时，，，即是可行解，这证明了不是可行域的顶点。

再证若不是可行域的顶点，则它一定不是基可行解。因为不是可行域的顶点，故在可行域中可找到不同的两点：,

使，()

设是基可行解，对应向量组线性独立。当时，有，由于是可行域的两点。应满足：

将这两式相减，即得：

因，所以上式系数不全为零，故向量组线性相关，与假设矛盾，即不是基可行解，证毕。

引理2：若K是有界凸集，则任何一点可表示为的顶点的凸组合。

定理1-3：若线性规划问题的可行域有界，则目标函数一定可以在可行域的顶点上达到最优。

证：设是可行域的顶点，若不是顶点，且目标函数在处达到最优=(标准型是)。

因不是顶点，所以它可以用可行域C的顶点线性表示为：，

代入目标函数得：

在所有的顶点中必然能找到某一个顶点，使是所有中最大者。并且将代替上式中的所有，这就得到：

由此得到：

根据假设是最大值，所以只能有，即目标函数在顶点处也达到最大值。

由以上基本定理可知，线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在可行域的顶点上得到。