高等工程数学第十一、十三章电子稿.doc

第十一章 线性规划问题概述11.1 线性规划问题举例及数学模型例11.1.1（生产安排问题）某厂生产A,B两种产品。生产一吨A需用煤九吨，电力4千瓦，劳动力三个（以劳动日计算）；生产一吨B需用煤3吨，电力五千瓦，劳动力10个。已知一吨A可获利C1元，一吨可获利C2元。该厂现有煤360吨，电力200千瓦，劳动力300个，问：生产A,B各多少吨获利最大，试建立这一问题的数学模型。解：首先列出数据表：表11.1.1原料种类单位产品所需原料（单位）原料总数AB煤94360电力45200劳动力310300收益C1C2设生产A 为吨，B为吨，而现在煤，电力，劳动力的消耗均有限制，所以应满足限制条件：煤耗： 电耗： 劳动力耗： 生产数量： 注意：约束条件两边单位一致从而此问题的数学模型为：求一组变量，值，使满足：例11.1.2设有钢材150根，长15米，需轧成配套钢料。每套由7根2米长与2根7米长的钢梁组成，问如何下料使钢材废料最少（设不计下料损耗）？解：依题意，每根钢材的下料有三种可能情形： 1）截7米长0根，2米的7根，余1米废料。 2）截7米长1根，2米长4根，无废料。 3）截7米长2根，2米长0根。余1米废料。设用第截法，用去钢材根（j=1，2，3）。则这批钢材截成7米长的钢梁为根，2米长的根，废料总长米.于是，得出问题的数学模型为：求一组变量,的值，使满足：（根数限制）（钢铁限制）（配套限制）并且使废料总长最少。 例11.1.3 （营养问题或配料问题）一个简化了的小鸡食物配方例。假定每天需要的混合司料质量是100斤，这分事物必须包含： 1） 至少0.8%但不超过1.2%的钙，2） 至少22%的蛋白质，3） 至少5%的纤维素。主要配料是：石灰石，谷物，大豆粉，其营养成分如下：表11.1.2配料每斤配料中的含量每斤成本钙蛋白质纤维石灰石0.3800.000.000.164谷物0.0010.090.020.463大豆粉0.0020.500.081.250问应如何处理配料，使在营养和物质条件均满足的情况 解：设生产100斤饲料，需用斤石灰石，斤谷物，斤大豆粉，于是可找出问题的模型：求 的值最小 满足条件：由以上几个例子，我们看到，所建立的数学模型其目标函数和约束条件均是关于未知变量的线形函数。目的是要求目标函数在约束下的极大或极小。我们称这样一类模型为线性规划模型。建立数学规划模型主要由以下三个步骤（隐含着三个要素）1确定决策变量，亦即选取适当的量为问题的待确定量，这是问题的基础。2建立适当的约束条件。3建立目标函数。下面我们再举一些例子说明如何建立线性规划模型：例11.1.4（装配成套）某产品的一个单件包括四个A个零和三个B零件。这两种零件由两种不同原料制成，而这两种原料可利用的数额分别为100个单位和200个单位。由三个车间按不同的方法制造。下面表格给出每个生产班的原料耗用量和每种零件的产量。目标是确定每个生产班数使产品得配套数最大？表11.1.3车间每班进料（单位）每班产量（个数）原料1原料2零件1零件2186 752596933884解：设是第1，2，3车间的生产班数，则三个车间生产零件A的总数是生产零件B的总数是而原料1和原料2对应的约束条件分别是因为目标是要使产品总件数达到最大，而每件产品要4个零件A和3个零件B。所以产品的最大数额不能超过和中较小的一个，因此目标函数变成：求的最大值，这是一个非线性的目标函数，可以通过变换转换成线性规划模型：求：的最大，满足 整理即得：的最大值 例11.1.5 某厂准备在电视台做广告，根据电视台收费标准，播出时间有三种选择：时间（1）星期一至五18：3022：30热门时间，每半分钟收费300元；时间（2）星期六、日18：3022：30热门时间，每半分钟收费420元；时间（3）18：3022：30以外的时间，即平时，每半分钟收费180元。工厂希望每天播出一次半分钟时间的广告。而电视台希望放在时间（2）的播出次数不要超过在时间（1）的播出次数，工厂则希望不要在星期一至五热门时间播出，以便平时也能看到广告播出。因此规定在时间（1）的播出每月不超过15次。所以规定在时间（2）的播出每月不少于4次。工厂估计，认为在时间（1）观众为平时的三倍。在时间（2）观众则为平时的五倍。试列出一个线性规划模型，确定一个月内播送广告的方案。使（1）观众最多，（2）费用最少。解：题中需要确定的是在不同的时间内各播出几次。以一个月30天来考虑，假定星期六、日共9天。设为时间（1）播放次数，为时间（2）播放次数，为时间（3）播放次数，则(每月中每天一次）。电视台要求： 厂方要求：及 又一个月中: 。整理以上的约束条件得：11.2 线性规划的标准形式11.2.1标准形式我们由上面的实际例子已经看到,线性规划问题的模型是由一组线性等式或不等式表示的约束条件及一个线性目标参数组成的.即下面的一般形式: 求一组变量使满足并且使目标函数： 达到最大（或最小）为了便于求解线性规划，有必要找线性规划成一定形式，为下面的标准形式：求一组变量的值，是满足因为一般形式的线性规划问题都能化成标准形式（后面介绍），因此只要会求解标准形式的线性规划问题，就会求解一般形式的线性规划问题了。 下面介绍几种形式的标准线性规划SLP问题。（1）缩写形式矩阵形式其中 注：向量非负，代表向量的各分量非负（2）量形式设是A的n个列向量。即11.2.2 化线性规划问题为标准形式转换方法：第一是求目标函数的最小值。则可能转化为求目标参数的最大（小）值问题。第二若约束条件中出现线性不等式 则引进松弛变量，使上式等价于 若约束变量中出现不等式 则引进剩余变量，使上式等价于第三 若有约束条件的右端，则可用-1乘上式两边，得出等价式子。第四 若存在某些变量的约束条件这在物理或经济定义上均是合理的。但为了满足标准形式对变量的要求，可作如下变换：令用和代替这就可以在原问题中校区没有负限制的标量。下面根据这些方法来做几个实例：将下面的线性规划问题标准化：解：引进松弛变量，剩余变量及，令，则得标准线性规划如下11.3线性规划的基本性质11.3.1两个变量线性规划问题的图解法我们先对二维的简单线性规划问题利用图解法进行求解。从图解法的几何直观可以启发我们的思维，探寻线性规划的一些基本性质。例11.3.1：利用图解法求解下面线性规划问题：解：在平面上取一个直角坐标系，他的两个坐标是首先找出平面上满足约束条件的点。图11.3.1平面上满足约束条件的点为上图中的一个凸多边形。表明原线性规划问题的目标函数只能在这个凸多边形（含边界）上取值，那么求解线性规划问题就是如何从这个凸多边形上求出使目标函数达最大值的关系。为此，我们先看看目标函数在凸多边形上取值的变化性能。当目标函数取某一值h时，表示一条直线， 令h=0，得直线在此直线上的所有关对应的目标函数的值为0再令.得另外三条直线，其上点分别对应目标值2，6，7，因此把叫做目标函数的等值线。当参数h变化时，就得到一族平行直线，他们形象的描绘了目标函数的变化状态。当h由小（大）变大（小）时，我们来观察等值线在凸多边形上的变化情形。取等值线的（负）法向量，其方向指向目标参数值增大（减小）的方向。当h由小（大）变大（小）时，直线沿（负）法方向平行移动，目标参数值不断增大。这样就可以看到，对于凸多边形目标参数在07之间取值，且与凸多边形定点相交时，目标参数值达到最大值7，如果等值线继续沿法方向移动，将离开这个凸多边形。不满足约束条件。于是知这个线性规划的最优解为11.3.2 线性规划的基本性质若将上面例9改求目标参数的最小值，约束条件不变，那这整个问题就是：一个是在凸多边形，（包括边界）上求目标参数的极大，另一个则是在同一凸多边形上求同一目标参数的极小，由点面的分析知，目标参数在凸多边形顶点达到极大，根据同样的分析可知，这个目标参数也在凸多边形顶点达到极小。这个事实就是线性规划的一个基本性质，如果线性规划有最优解，必然在凸多边形（或凸多面体）的顶点上达到最优，下一章我们将证明这一性质。当求解线性规划问题时，图解法给人们提供了直观的思想，求解线性规划的单体形法是以解空间的凸多面体某一顶点开始进行替代，直到求出达到极值的顶点（如果问题有最优解）。下面在举几个例子说明怎样用图解法求线性规划问题的解。例11.3.2.求满足约束条件，使目标函数达到极小。解：画出由约束条件决定的4个半平面的交集K，这是一个无界的凸多边形。作目标函数的等值线让它沿着它的负法线图11.3.2等值线可以无限制的减小，也就是问题最优值是负无穷大，或者说函数最大化：目标函数等值线沿法向移动，最小化，沿负法向移动。例11.3.3求满足约束条件，。约束条件决定的图形是下图中凸多边形OBAC做等值直线束沿正法方向移动达到顶点时与线段重合。图11.3.3再移动就离开K了，所以线段AB上的点都使：解：如图所示：四个约束条件决定的半平面没有相交部分即问题没有可行解。综上可见：两个变量的线性规划问题可能有以下四种情形图11.3.4（1）. 有唯一最优解（2）. 有最优解，但不一（3）. 有可行解，但是没有最优解。（4）. 没有可行解。对于一般问题也有上述论述。习 题111.某汽车厂三种汽车：微型轿车、中级轿车和高级轿车。每种轿车需要的资源和销售的利润见表11.1.为达到经济规模，每种汽车的月产量必须达到一定数量时才可进行生产。工厂规定的经济规模为微型车1500辆，中级车1200辆，高级车1000辆，请构造一个整数规划模型使该厂的利润最大。表11.1微型车中级车高级车资源可用量钢材（吨）1.522.56000（吨）人工（小时）30405055000（小时）利润2342.某厂生产甲、乙、丙三种产品，都分别经A,B两道工序加工，A工序在设备或上完成，B工序在，三种设备上完成。已知产品甲可在A，B任何一种设备上加工；产品乙可在任何规格的A设备上加工，但完成B工序时，只能在设备上加工；产品丙只能在与设备上加工。加工单位产品所需要