第03章线性规划

《第03章线性规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第3章线性规划数学规划是系统工程中最重要的分析方法之一，是运筹学的主要分支。它包括线性规划、非线性规划、整数规划和动态规划等。30年代初出现的线性规划，1947年丹茨基（GeorgeB．Dantzig）发明单纯形法，理论上才得到完善。随着电子计算机的发展，成千上万个约束条件和变量的大型线性规划问题都可以求解。因此，无论从理论的成熟性看，还是从应用的广泛性看，线性规划都是运筹学的一个重要分支。它在工业、农业、交通运输、军事和计划管理等各方面都愈来愈得到广泛地应用。l线性规划问题及其数学模型在生产过程中，要想提高工作效率和经济

2、效益，一般有两条途径：一是进行技术改造，改进生产手段和条件。（比如增添设备、改进工艺、挖掘潜力等）二是在生产手段和条件都不变的情况下，改善生产的组织和计划管理，作出最优安排，使生产手段和条件得到充分的利用。线性规划方法就是解决后一类问题的工具。后一类问题又可分为两个方面：一是在一定限制条件下，使得工作成果尽可能大；二是为完成既定任务，使资源消耗尽可能小。例3一1资源利用问题。某工厂计划生产A、B两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有360t，电力有200kw，劳动日有300个，生产每千克

3、产品的资源消耗量和能获得的利润如表3—1所示。问该厂应生产A，B两种产品各多少千克才能使总利润最大？解设生产A，B两种产品各为x1，x2kg，则该问题可归结为，求一组变量xl，x2满足下列条件：使得总利润f=7x1+12x2取得最大值。例3－2下料问题。某工厂制造一种机床，每台机床需A、B、C三种不同长度的轴各一根，其毛坯长度；A为2.9m，B为2.1m，C为1.5m，它们用同一种圆钢来下料，每根圆钢长为7.4m。要造100台机床，问如何下料最好？试建立其数学模型（不考虑下料截口损耗）。”解将各种可能的下料方案排列如表3－

4、2。设所用圆钢总数为f根，第j种下料方案。所用圆钢数为xj根，则由题意,上述模型即为所求模型。通过分析表3—2，发现其中的方案3、5、7、8的料头过长，不经济，如果把它们舍弃，对剩下的4种方案进行搭配，仍然可以满足题意。为此可以将上述模型简化为下列模型（保持变量下标不变）。例3—3运输问题。设有甲、乙、丙三个仓库，存有某种货物分别为7t、4t和9t。现在要把这些货物分别送往A、B、C、D四个商店，其需要量分别为3t、6t、5t和6t，各仓库到各商店的每吨运费以及收、发总量如表3—3所示。现在要求确定一个运输方案：从哪一个仓

5、库运多少货到哪一个商店，使得各个商店都能得到货物需要量，各个仓库都能发完存货，而且总的运输费用最低？试建立其数学模型。解记总运费为Z，设xij为i仓库到j商店的货物量，其中i=1，2，3分别代表甲、乙、丙仓库，j=1，2，3，4分别代表A、B、C、D商店，则根据题意：上述各例，都是要求一组非负变量，在满足一组线性等式或线性不等式的前提下，使一个线性函数取得最大值或最小值，这一类问题就称为线性规划问题。将上述问题得出的数学表达式加以概括和抽象，就可得到线性规划问题的一般数学模型：求一组变量xj，j＝1，2，…，n，满足条件使

6、函数取得最大值或最小值。如果简写，则线性规划问题的数学模型可以表示为(3-1)(3-2)式（3—1）称为目标函数，式（3—2）称为约束条件。式中max（min）f—目标函数／取最大（最小）值；xj—决策变量，又称为生产活动或活动方式；cj—决策变量在目标函数中的系数，又称为利益系数、价值或效果系数；aij—决策变量在约束条件中的系数，又称为投入产出系数或技术系数；bi—资源限制量；n—决策变量的个数；m—约束条件（不包括非负约束条件）的个数。把满足约束条件式（3—2）的任意一组解称为线性规划问题的可行解，使得目标函数f取得

7、最优值的可行解称为线性规划问题的最优解。如何求得线性规划问题的最优解，就是本章所要讨论的中心问题。2线性规划问题的图解法在介绍线性规划问题的一般解法之前，我们先介绍只含有两个变量的线性规划问题的图解法。图解法不仅简单而且直观，有助于了解线性规划问题求解的基本原理。例3—4考虑下列线性规划问题解在该问题的约束条件中，共有五个不等式（包括两个非负约束条件）。在以xl，x2为坐标轴的直角坐标系中，每一个不等式的解的集合均为一个半平面。所以同时满足五个不等式的解的集合一定是五个半平面的交集，称为可行域，即凸五边形OABCD。如图3

8、—1所示。可行域的五个顶点坐标分别为O（0，0），A（0，2），B（l，4），C（4，1），D（2，0）。下面讨论如何在可行域上找到使目标函数取得最小值的点，即问题的最优解。对于目标函数f=-x1+x2，若令f=f0为一常数，则目标函数在坐标平面上表现为一条确定的直线，如果f0取不同的值时，那么目标函数