运筹学课程中线性规划问题解的概念教学探讨

孙祥凯+唐莉萍

收稿日期：2015-11-10

基金项目：重庆市教委研究项目（KJ1500626）。

作者简介：孙祥凯 （1984— ），男，山东青州人，副教授，博士后，主要从事最优化理论与方法以及教学方法的研究。

运筹学课程是经管类本科生的必修课程，而线性规划是运筹学中的一个重要分支。为了让初学者对线性规划问题的解概念有更清晰的认识和理解，本文将通过实例对解概念进行讲解。因为可行解、可行域、最优解以及最优值这几个概念理解相对比较容易，所以本文将重点通过实例讲解线性规划问题的基、基向量、基变量、非基变量、基解、基可行解以及可行基矩阵这几个概念。

1.线性规划问题模型及相关概念

线性规划问题的标准形式为

max（min）Z=CX

AX=B

X≥0

其中价值系数C=（c1c2…cn）， 系数矩阵：

a11   …   a1n                         x1                          b1

A=                    ，X =        ，B =         。

am1  …   amn                        xn                          bm

下面首先简单回顾一下相关概念。课本中相关概念虽然表达十分严谨，但是对经管类文科生来说理解起来相对困难。为便于理解，本文用最直白的语言来重新描述这些概念。[1][2]

（1）基矩阵的概念。教材中第22页中描述的是系数矩阵A中的非奇异子矩阵，称为线性规划问题的一个基矩阵，简称基。实际上，基矩阵就是系数矩阵中行列式不等于零的子阵。

（2）基向量的概念。将基矩阵按列分块， 每一列称为基向量。通俗地来说，基向量就是系数矩阵中行列式不等于零的子阵的每一列。特别的、不同的基矩阵对应不同的基向量。

（3）基变量与非基变量的概念。与基向量所对应的变量称为基变量，剩下的变量称为非基变量。通俗地来讲，基变量就是系数矩阵中行列式不等于零的子阵的每一列所对应的变量。剩下的变量当然是非基变量。此处大家也要注意，由于不同的基矩阵对应不同的基向量，所以基变量与基矩阵也是一一对应的。因此一个变量在不同的基矩阵里有可能是基变量，也有可能是非基变量。

（4）基解的概念。令非基变量等于0，所得到的解，称为基解。通俗地来讲，基解就是在约束条件中令非基变量等于0，对其求解所得解。

（5）基可行解的概念。若基解还是可行的，即满足非负性条件，则称为基可行解。通俗地来讲，基可行解就是要保证每一个变量都要不小于零。

（6）可行基矩阵的概念。与基可行解所对应的基矩阵，称为可行基矩阵。

2.实例分析

例，已知某线性规划问题约束条件

x1+2x2+3x3=1

2x1+x2+3x4=3

x1，…，x4≥0

试列举出其基矩阵、基向量、基变量、非基变量、基解、基可行解以及可行基矩阵。

解：按照线性规划标准形式可得

1    2    3    0

2    1    0    3

由于该系数矩阵的任意二阶子矩阵均是可逆的，即行列式不等于零，所以该线性规划问题的基矩阵共有六个，分别是：

1   2

2   1   ，         ，          。

1   0

2   3   ，         ，          。

本文仅对第一个基矩阵进行详细分析。

对于基矩阵          ， 将该矩阵按列分块，所以基向量为      与     。因为基向量  和      在约束条件中对应的变量分别为x1与x2，所以基变量为x1与x2，从而非基变量为x3和x4。令非基变量x3=x4=0，并将其代入约束条件中易得x1=    ，x2=-   。从而基解为                     。由于x2=-        < 0    不满足非负性条件，所以                         不是基可行解。从而此基矩阵不是可行基矩阵。

通过上述例子，不仅能够很容易地理解线性规划问题的解的这几个概念，而且可以得到这些概念之间的如下关系：①系数矩阵中可找出若干个基矩阵;②每个基矩阵都对应于一个基解;③非负的基解就是基可行解;④基可行解所对应的基矩阵就是可行基矩阵。

本文对线性规划问题的解的相关概念以及它们之间的相互关系进行了分析和讲解，以消除初学者对这些概念之间的困惑，加深初学者对线性规划问题解概念的深入认识。

参考文献：

[1]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社，2012.

[2]胡运权. 运筹学基础及运用[M]. 北京： 高等教育出版社， 2008.