任务一　线性规划的概念

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

1.1.1　问题的提出

在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。

例2-1-1　生产计划问题　某工厂在计划期内要安排甲、乙两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如表2-1-1所示，工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元，问工厂应如何安排生产任务才能使获利最多？

表2-1-1

1.1.2　数学模型的建立

线性规划的研究对象是稀缺资源最优分配问题，即将有限的资源以最佳的方法，分配于相互竞争的活动之中。一般体现为在一定的资源条件下，如何合理使用，达到效益的最大化；或者在给定任务下，如何统筹安排，尽量降低成本，使资源消耗最小化。由于这些问题从本质上看很多都是线性的，所以我们称之为线性规划。

那么接下来我们建立例2-1-1的数学模型。

第一步，设定变量。题目中要求我们决策两种产品的生产计划，所以我们可以设生产产品甲、乙的数量分别为x1和x2。这些变量是由决策部门加以确定的，我们把它们称为决策变量。决策变量的取值均为非负。

第二步，建立目标函数，即我们在具体问题中要达到的目标。在例2-1-1中，我们的目标是要获得最大利润，即

maxz＝2x1＋3x2

第三步，建立约束条件。约束条件是我们在安排规划的过程中所受到的资源限制。在本例中，该生产计划受到一系列现实条件的约束。

设备台时数：生产所用的设备台时不得超过所拥有的设备台时，即

x1＋2x2≤8

原材料数：生产所用的两种原材料A、B不得超过所拥有的原材料总数，即

4x1≤16

4x2≤12

非负约束：生产的产品数不可能为负值，即

x1，x2≥0

综上所述，我们可以把该问题的数学模型表示为

例2-1-2　营养配餐问题　营养学家指出，成人良好的日常饮食应该至少提供0.075kg的碳水化合物、0.06kg的蛋白质、0.06kg的脂肪。1kg食物A含有0.105kg碳水化合物、0.07kg蛋白质、0.14kg脂肪，花费28元；而1kg食物B含有0.105kg碳水化合物、0.14kg蛋白质、0.07kg脂肪，花费21元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用多少食物A和食物B？

解：设每天食用xkg食物A，ykg食物B，总成本为z，那么

minz＝28x＋21y

而这些食物中所含有的碳水化合物、蛋白质和脂肪都要达到需求，因此

1.2　线性规划模型的概念

上述两个例题虽然在内容上不尽相同，但其数学模型都有着共同的特征，它们都是要求一组变量（一般是非负的）在一组线性的约束条件下，使得一个线性的目标函数取得最大值或最小值。我们把这类问题统称为线性规划问题。

根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是不等式，也可以是等式；决策变量一般是非负的。因此，我们可以抽象出线性规划的一般形式

其中，我们要达到的最大化或最小化的目标式称为目标函数，下边的方程组称为约束条件，表明在规划中将要受到的资源限制，求出的使目标达到最优的x1到xn的取值叫做最优解，把最优解代入目标函数求出的目标函数值称为最优值。