工科基础数学-第十章-线性规划初步.doc

《工科基础数学-第十章-线性规划初步.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章线性规划初步线性规划是运筹学的重要分支之一，它可以用来解决以下两类问题：一是对已确定的任务如何统筹安排，使完成该任务的人力、物力和资源最少，二是如何安排一定的人力、物力和资源，使完成的任务最多。也就是在科学研究、工程设计、活动安排、经济管理、军事指挥等方面的问题中寻求最优解问题。本章我们将简单介绍建立线性规划问题的数学模型和方法，及如何求线性规划问题的解。第一节线性规划问题及数学模型一、什么是线性规划问题1．问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理的利用有限的人力、物力、财力等资源，以

2、便得到最好的经济效果。我们首先考察下列问题：例1某工厂计划生产甲、乙两种产品。已知生产单位产品所需的设备及（台时）、两种原材料消耗如下表：生产产品甲每件获利2元，生产产品乙每件获利3元，问应如何安排计划使该厂获利最高？这个问题可以用下列数学模型来描述：解设、分别表示在计划内产品甲、乙的产量，因为设备的有效台时是8，所以在生产时要考虑到不要超过设备的有效台时数，既要满足不等式同理，因原材料、的限量，又要满足以下不等式，。若用表示利润，则，于是该工厂在有限资源的限制条件下获得最大利润的最优解可表示如下：目标函数满足

3、的约束条件。例2某两个煤场、，每月分别进煤60吨和100吨，他们担负着3个居民区的供煤任务，3个居民区每月用煤量分别是45吨、75吨、40吨，场到三个居民区的距离是10、5、6，场到三个居民区的距离是4、8、15，问如何分配两煤场的供煤，才能使运输费用最小。解设表示第个煤场向第个居民区的供煤量，，，因为两个煤场的供煤能力的限制，于是有，，同时三个居民区的用煤量也是有限的，于是有：，，。设运输费用为，则=，于是在保证用煤的前提下最省的运输费用的最优解可表示如下目标函数=满足的约束条件，。上面两个问题都是求一组变量

4、最优解的问题，这组变量称为决策变量，而这些决策变量的最优解受到一些条件的约束，最优解是完全满足约束条件的最优解。于是在寻求这些问题的最优解之前，要找出最优解的表达式和这个最优解受到哪些条件约束的表达式。最优解的表达式和这个最优解受到的全部条件约束的表达式共同构成该问题的数学模型，其中最优解的表达式称为目标函数，最优解受到的全部条件约束的表达式称为约束条件。把在一组线性等式或不等式的约束之下，求一个线性函数的最大值或最小值问题称为线性规划问题。线性规划问题的数学模型包括两个部分：一是目标函数，二是约束条件。目标函

5、数是一个寻求“最佳”的有关量组成的一个线性关系式，在式前根据问题的意义冠以“”、或“”，表示以求达到最大值或最小值。约束条件是一组对目标函数达到最佳所限制的条件不等式，一般记为。例3已知有一批长为180的钢管，现需要70长的不少于100根，52长的不少于150根，35长的不少于100根，经过试算已知有八种下料方法，问如何下料才能使边料最少？解设为第种下料法所截得的钢管根数，列表如下：设为边料的总长，其数学模型为例4某河流域有两个化工厂（如下图）流经甲厂的流量为500万/天，甲厂与乙厂之间有一支流流量为200万/

6、天，甲厂每天排污2万，乙厂每天排污1.4万，从甲厂排出的污水流到乙厂前有20%自然净化，根据环保要求，河流中的污水含量不能超过0.2%。这两个工厂要各自处理一部分工业污水，甲厂的成本是1000元/万，乙厂的成本是800元/万，问在满足环保的要求下，两厂要处理多少工业污水才能使总费用最小？。工厂甲。工厂乙500万立方200万立方解设两厂各自处理万时费用最小，甲厂到乙厂之间，河流中的含污量不能超过0.2%，则有：流经乙厂后，河流中的含污量不能超过0.2%，则有：两个工厂的污水量不会超过各自的排放量，则有：两厂处理污

7、水的总费用为：则该问题的数学模型为：从上面的实例中可以看出，这些问题有一些共同特征：（1）每个问题都是有一组决策变量表示某一方案，一般这些变量的取值都是非负的；（2）存在一些约束条件，这些约束条件可以用一组线性的等式或不等式来表示；（3）都有一个要求达到目标，可用决策变量的线性函数来表示的目标函数；一般地，线性规划问题的数学模型可表为：目标函数满足约束条件试一试写出下面线性规划问题的数学模型：某公司要将、两种成分的原料合成一种产品，该产品必须重50克，其中成分不得少于20克，成分不得多于40克，的成本是2.5元

8、/克，的成本是1元/克，求、的用量各为多少时可使成本最低？二、线性规划问题的标准形式为了便于求线性规划的解，定义线性规划问题的数学模型的标准形式为：目标函数满足约束条件线性规划的标准形式有以下四个特征：（1）目标函数的最大化；（2）所有的约束方程都是等式；（3）所有的决策变量都非负；（4）约束方程等式右端的常数（称为约束常数）都是非负的。设称为约束矩阵，目标函数的系数组成的向量称为价值