1.1 线性规划问题的提出及其数学模型

线性规划是应用数学模型对所研究问题的一种数学模型描述。线性是指模型中数学表达式的形式，规划是计划的意思。因此，线性规划是指用线性的数学模型来描述管理活动的计划。线性规划研究的问题是在一定的资源制约条件下，找出管理活动的最佳资源利用组合，以产生最大的经济和社会效益。线性规划主要解决这样的问题：如何分配利用有限的资源，以最好地达到组织目标。

1.1.1 线性规划问题的提出

例1-1 生产计划问题

某工厂用3种原料M1,M2,M3生产3种产品N1,N2,N3。已知单位产品所需原料数量及原料的可用量见表1-2，试制订出使该工厂利润最大的生产计划。

解：设产品Nj的产量为xj个单位，j=1,2,3，首先，它们不能取负值，即必须有xj≥0,j=1,2,3；其次，根据题设，3种原料的消耗量分别不能超过它们的可用量，即它们又必须满足：

在以上约束条件下，求出x1,x2,x3，使总利润z=3x1+5x2+4x3达到最大，故求解该问题的数学模型为：

例1-2 混合配料问题

某饲养厂每天需要1000千克饲料，其中至少要含7000克蛋白质、300克矿物质、1000毫克维生素。现有5种饲料可供选用，各种饲料每千克营养含量及价格见表1-3：

试制订费用最为节省的饲料混合方案。

解：设每天各种饲料的选用量分别为：x1,x2,x3,x4,x5千克根据问题求解目标和资源约束，可以写出以下数学模型：

1.1.2 线性规划问题的数学模型

上面建立了2个案例的数学模型，虽然问题各不相同，但是它们的数学模型却有相同的特征：

（1）问题中都有一组变量（决策变量），这组变量的一组定值就代表一个问题的具体方案；

（2）存在一定的限制条件（约束条件），这些限制条件可以用一组线性等式或不等式来表示，表示约束条件的数学式子都是线性等式或线性不等式；

（3）有一个目标要求（目标函数），可以表示为决策变量的线性函数，并且要求这个目标函数达到最优（最大或最小），表示问题最优化指标的目标函数都是线性函数。

满足上述3个条件的数学模型称为线性规划的数学模型，一个线性规划问题的数学模型包括三部分：目标函数、约束条件和决策变量。

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

其中，式（1-1）称为目标函数，式（1-2）称为约束条件，式（1-3）称为非负约束条件。式中，z称为目标函数，xj(j=1,2,…,n)称为决策变量，cj(j=1,2,…,n)称为价值系数或目标函数系数，bj=(j=1,2,…,m)称为限额系数或右端系数，aij=(i=1,2,…,m,j=1,2,…,n)称为技术系数，由技术系数aij=(i=1,2,…,m,j=1,2,…,n)组成的矩阵称为技术系数矩阵。这里，cj(j=1,2,…,n)，bi(i=1,2,…,m)，aij(i=1,2,…,m,j=1,2,…,n)均为常数。

可行解：将满足线性规划约束条件式（1-2）和式（1-3）的解(x1,x2,…,xn)称为线性规划问题的可行解，由所有可行解组成的集合称为可行域。

最优解：称使目标函数取到最优值的可行解为最优解。最优解对应的目标函数值称为最优值。