线性规划问题概述课件.ppt

《线性规划问题概述课件.ppt》由会员分享，可在线阅读，更多相关《线性规划问题概述课件.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、线性规划问题概述第1页，此课件共46页哦线性规划 教学大纲 一、本课程教学目的是使同学们从理论上，应用上掌握运筹学的一个 基本分枝-线性规划。二、基本要求：（1）通过学习，熟悉线性规划的基本概念；能熟练的运用线性规划解决实际问题，包括建立模型。求解和解后的经济分析基本方法。（2）从数学理论上完善的了解线性规划基本原理，以及该课题新近的发展动态。（3）强调掌握对偶单纯形法及灵敏度的分析的经济意义。第2页，此课件共46页哦（4）课后安排适量作业，巩固所学内容，要求按时完成。（5）对部分有能力的同学，引导他们通过计算机实习，编制程序解题。三、教学计划与内容提纲：1 教学内容与学时匹配，见教学日历。2

2、 教学内容大纲：第一章 线性规划问题概述 1 花一节课时间介绍线性规划的发展历史和发展动态以及在经济分析等实际工作中的应用，调动同学们的学习兴趣。2 建模部分着重讲一些实际问题的线性规划模型建立过程；突出模型的三要素：目标方程，决策变量，约束方程。3 线形规划的几何解法，主要是在平面上用图形如何解二维的规划问题，注意从中得出结论，最优解在解这一领域的顶点达到。第3页，此课件共46页哦 1 交代清楚基本概念。2 基本定理2.2.2 是重点讲解内容，其证明过程的推导过程要详细讲解。由此定理，强调一个结论，若一个线性规划问题有最优解，则必有最优基本可行解。也就是说最优解必可在可行解域的极点上达到。这

3、是后面单纯形法的基本启发思想。3 极射向和可行解表示定理，这部分内容比较偏重理论推导过程，要求同学们对定理2.3.2特别清楚的了解，这是后面判一个问题设有最优解的基本理论，也是单纯形法的一个终止原则。至于可行解的表示定理，纯属理论证明之用，故此讲解时，注意把证明的思想将清楚。第二章 线性规划的基本概念和基本定理第4页，此课件共46页哦第 三章 单纯形法 本章是线性规划的一个核心内容，要重点介绍一下。1 单纯 形法的概念部分主要讲述三个内容：（1）极轴的运算（2）判别数定义 （3）最优判别定理2 对单纯形法分两种方式介绍：（1）数值迭代公式方法，这里要注意推导极轴运算过程，证出迭代公式。（2）表

4、上作业法 两种方法都重要，前者便于计算机运算，后者便于手工计算。在介绍他们时都要注意以下问题：极轴元的选择方式，过程。数值迭代或表变换过程，步骤。终止准则（有或无最优解）。收敛性定理。第5页，此课件共46页哦5 Bland先行循环的方法，粗略介绍。6 修正单纯形法，主要用于计算机运算，请同学们自学7 求最优基本可行解，每个最优基本可行解对于实际工作的决策者来说，就是一种最优决策方案，因此能够求出最优基本可行解，就能为决策者提供可用方案。3 人工变量方法，为了寻找单纯形法的新始基可行解，引进人工变量，介绍两阶段方法求解过程；增加内容：大M 方法产生新始基可行解。4 退化与循环问题，讲情楚Beal

5、e的例子，说明线性规划中在退化情性下可能出现循环现象，着重介绍 -摄动法先行循环；注意从理论上完备S-摄动法即定理3.4.2的结论及其的证明过程要交代清楚，着重讲解。第6页，此课件共46页哦第四章第四章 线形规划的对偶定理及应用线形规划的对偶定理及应用1 注意从实际问题中引出对偶规划的概念。2 重点介绍对称形式对 规划及对偶定理。对 定理4.1.1，4.1.2，4.1.3，全面地描述了一对偶规划 的解之间的关系，注意把这三个定理串联起来对对偶 规划综合分析。对偶定理4.1.4，注意说明由此引出的松紧概念。3 非对称对偶规划。与对称对偶规划的四个对偶定理 对比研究，启发同学们对对偶单纯形法基本思

6、想的初 步认识。第7页，此课件共46页哦 4 混合形对偶规划，要举出几个实例证明如何由一个问 题，写出另一个对偶问题的方法，强调解题过程，第一要对问题形式规范化，第二要掌握对偶表，根据对偶表写出对偶问题。5 对偶单纯形法，与第三章的单纯形法对比研究，哪些不同，哪些相同，迭代公式，表格形式，迭代过程。6 对偶单纯形法的经济意义，举一个实际例子，证明由一个对偶单纯形最终表，一个决策者可以得到什么信息第8页，此课件共46页哦第五章第五章 灵敏度分析灵敏度分析 1 为什么要对线性规划问题进行灵敏度分析，主要从经济分析方面回答。2 本章各节均与第四章内容紧密联系，因此讲授时，一要提醒同学们复习，二要简明

7、提出一些重要内容课堂复习。3 对三个灵敏度分析专题：新增变量，新增约束，系数 cj,bi,aij 变化。各举一到两个实例说明分析的方法和经济意义。第9页，此课件共46页哦第六章第六章 变量有界限制的线性规划问题变量有界限制的线性规划问题 1 问题的标准形式及其基本概念，重点讲解最优判别定理7.1.1。2 问题的算法，主要介绍第一阶段算法的最优准则算法思想和算法过程，及第二阶段中心枢纽运算过程寻找新的基矩阵。3 迭代收敛性定理7.4.1重点讲解。它证明了上面建立的算法是有限终止的。4 花一课时间深细讲一个例子，说明算法步骤及其中诸深细细节问题。第10页，此课件共46页哦 线性规划线性规划 Lin

8、ear Programming 前言 一一 线性规划的发展史线性规划的发展史参考书目参考书目：北京理工大学出版社，许万蓉，线性规划。山东科学技术出版社 线性规划。29.183GMG 管梅谷，郑汉鼎。研究线性规划最早的是苏联的.（康脱洛维奇），1939年，他发表了生产组织与计划中的数学方法一书。主要讨论了机床、负荷、下料运输等问题。但他提出的问题在当时并未引起人们的注意。他自己也未能提出一个统一的求解方法。第11页，此课件共46页哦 在第二次世界大战期间，由于军事运输的需要，提出线性问题的解法，美国的经济学家柯普曼（Koupman）也研究了运输问题。直到1947年，美国的G.B.Dantzig提

9、出了求解线性规划的单纯形法，才使线性规划这门学科在理论上趋于成熟，并成功地运用到了工业、交通、农业、军事等各个领域内，使线性规划的理论与方法成为管理科学的重要内容。在当今电子技术高度发展的信息社会中，线性规划给人类在经济管理、生产管理、人才事务管理等方面发挥了巨大作用。现在对于成千上万个约束条件、成千上万个变量的线性规划问题在计算上已没有任何问题。据20世纪80年代末美国一个杂志对全美500家大公司的调查，线性规划的应用范围名列前茅，有85%的公司频繁使用线性规划。第12页，此课件共46页哦二 线性规划问题的特点线性规划问题的特点 由于是管理科学的重要分支，也是它的最成熟，最完整的分支。而管理

10、科学的特点是利用数学模型为管理人员提供方针，以便在现有信息的情况下作出有效的决策，或现有信息不足作出决策时，而去搜索更多的信息。这里我们要抓住以下几个要素：第一 管理科学的核心是建立模型。即运用数学的抽象，住所要探讨对策问题最重要的特征。模型是现实的简化表示。笫二 通过模型设计，给管理工作提供方便.笫三 进行有效决策所需信息的多少，决策所要探讨问题的复杂程度，而不决定于研究过程所用的工具。模型要求过多的信息就不是好模型。线性规划也是这样通过模型，求解，分析综合，为决策者提供科学决策依据。第13页，此课件共46页哦三三 线性规划的主要应用线性规划的主要应用 线性规划主要应用在以下几个方面：（1）

11、在某一企业内部，如何配合产品的销售时间，在各部门的原料，产品的存储，分配的数量等最为合理。（2）在某一企业生产的产品数量（或产值），如何使现有的设备，人力，原料等条件限制下，合理组织生产，使经济效益最高。（3）在某地的交通网中，如何合理组织运输，使运费最小。（4）在市场上产品的（或原料）价格变动时，对于 这些变动，企业如何做出最优决策。（5）合理下料问题，即利用某种原料下料时，如何 达到既满足要求，又使原料最少。第14页，此课件共46页哦 （6）配料问题，即生产由各种原料生产的的产品时（如混合饲料等）时，如何既满足规定的质量的标准，又使产品的成本最低。（7）库存问题，在仓库的容量及其他条件的限

12、制下，确定库存物资的品种，数量，期限，使库存的效益最高。（8）在投入产出问题中，引进某一目标函数，制定最优的企业（或地区）经济计划。当前，我国正在进行以城市为重点的整个经济体制的改革，企业的自主权在扩大。一个企业要适应国内，国际的市场竞争，就必须改善经营管理，提高经济效益，制定最优的生产计划，并对瞬息万变的市场信息作出反映，应用现代数学方法，特别是线性规划方法，对于提高企业管理水平和企业活力，将会起着极大的作用。第15页，此课件共46页哦 第一章第一章 线性规划问题概述线性规划问题概述 1.1 线性规划问题举例及数学模型 例1（生产安排问题）某厂生产A,B两种产品。生产一吨A需用煤九吨，电力4

13、千瓦，劳动力三个（以劳动日计算）；生产一吨B需用煤3吨，电力五千瓦，劳动力10个。已知一吨A可获利C1元，一吨B可获利C2元。该厂现有煤360吨，电力200千瓦，劳动力300个，问：生产A、B各多少吨获利最大？试建立这一问题的数学模型。第16页，此课件共46页哦 煤耗：9x1+4 x2360 电耗：4x1+5 x2200 解：首先列出数据表：第17页，此课件共46页哦 劳动力耗：3 x1+10 x2300 生产数量：x1 0 x20 注意：约束条件两边单位要一致。从而此问题的数学模型为：求一组变量x1，x2值，使满足：第18页，此课件共46页哦 例2设有钢材150根，长15米，需轧成配套钢料。

14、每套由7根2米长与2根7米长的钢梁组成，问如何下料使钢材废料最少（设不计下料损耗）？解：依题意，每根钢材的下料有三种可能情形：1）截7米长0根，2米的7根，余1米废料。2）截7米长1根，2米长4根，无废料。3）截7米长2根，2米长0根。余1米废料。设用第j截法，用去钢材xj根（j=1，2，3）。则这批钢材截成7米长的钢梁为x2+2x3根，2米长的7x1+4x2根，废料总长x1+x3米.于是，得出问题的数学模型为：求一组变量x1,x2,x3,的值，使满足：第19页，此课件共46页哦第20页，此课件共46页哦主要配料是：石灰石，谷物，大豆粉，其营养成分如下：问应如何处理配料，使在营养和物质条件均满

15、足的情况 解：设生产100斤饲料，需用x1斤石灰石，x2斤谷物，x3斤 大豆粉，于是可找出问题的模型：第21页，此课件共46页哦第22页，此课件共46页哦由以上几个例子，我们看到，所建立的数学模型其目标函数和约束条件均是关于未知变量的线形函数。目的是要求目标函数在约束下的极大或极小。我们称这样一类模型为线性规划模型。建立数学规划模型主要由以下三个步骤三个步骤（隐含着三个要素三个要素）1确定决策变量确定决策变量，亦即选取适当的量为问题的待确定量，这是问题的基础。2建立适当的约束条件建立适当的约束条件。3建立目标函数建立目标函数。下面我们再举一些例子说明如何建立线性规划模型：例例四四：（装配成套）

16、某产品的一个单件包括四个A个零和三个B零件。这两种零件由两种不同原料制成，而这两种原料可利用的数额分别为100个单位和200个单位。由三个车间按不同的方法制造。下面表格给出每个生产班的原料耗用量和每种零件的产量。目标是确定每个生产班数使产品得配套数最大？第23页，此课件共46页哦17 5，2解：设,x1,x2,x3是第1.23车间的生产班数，则三个车间生产零件A的总数是x+6x+8x生产零件B的总数是x+9x+4x1233第24页，此课件共46页哦而原料1和原料2对应的约束条件分别是因为目标是要使产品总件数达到最大，而每件产品要4个零件A和3个零件B。所以产品的最大数额不能超过第25页，此课件

17、共46页哦这是一个非线性的目标函数，可以通过变换转换成线性规划模型：求：第26页，此课件共46页哦例例6 某厂准备在电视台做广告，根据电视台收费标准，播出时间有三种选择：时间（1）星期一至五18：3022：30热门时间，每半分钟收费300元；时间（2）星期六、日18：3022：30热门时间，每半分钟收费420元；时间（3）18：3022：30以外的时间，即平时，每半分钟收费180元。工厂希望每天播出一次半分钟时间的广告。而电视台希望放在时间（2）的播出次数不S.t.整理即得：求f=y的最大值第27页，此课件共46页哦要超过在时间（1）的播出次数，工厂则希望不要在星期一至五热门时间播出，以便平时

18、也能看到广告播出。因此规定在时间（1）的播出每月不超过15次。所以规定在时间（2）的播出每月不少于4次。工厂估计，认为在时间（1）观众为平时的三倍。在时间（2）观众则为平时的五倍。试列出一个线性规划模型，确定一个月内播送广告的方案。使（1）观众最多，（2）费用最少。解：题中需要确定的是在不同的时间内各播出几次。以一个月30天来考虑，假定星期六、日共9天。设x为时间（1）播放次数。y为时间（2）播放次数。z为时间（3）播放次数。则x+y+z=30 (每月中每天一次）第28页，此课件共46页哦电视台要求：yx厂方要求：x15及y4非负约束：x0，y0,z0.又一个月中:y9整理以上的约束条件得第2

19、9页，此课件共46页哦一 标准形式标准形式:我们由上面的实际例子已经看到,线性规划问题的模型是由一组线性等式或不等式表示的约束条件及一个线性目标参数组成的.即下面的一般形式:求一组变量1.2 线性规划的标准形式并且使目标函数：达到最大（或最小）Opt.第30页，此课件共46页哦为了便于求解线性规划，有必要化线性规划成一定形式，即为下面的标准形式：求一组变量第31页，此课件共46页哦 因为一般形式的线性规划问题都能化成标准形式标准形式（后面介绍），因此只要会求解标准形式的线性规划问题，就会求解一般形式的线性规划问题了。下面介绍几种形式的标准线性规划SLP问题。1.缩写形式：第32页，此课件共46

20、页哦矩阵形式：注：向量非负，代表向量的各分量非负第33页，此课件共46页哦3.向量形式：第34页，此课件共46页哦二二 化线性规划问题为标准形式化线性规划问题为标准形式：第二第二 若约束条件中出现线性不等式 则可能转化为求目标参数 转换方法：第一第一 若是求目标函数第35页，此课件共46页哦第四第四第36页，此课件共46页哦下面根据这些方法来做几个实例：例例8 8 将下面的线性规划问题标准化：第37页，此课件共46页哦1.3线性规划的基本性质一一 两个变量线性规划问题的图解法两个变量线性规划问题的图解法：我们先对二维的简单线性规划问题利用图解法进行求解。从图解法的几何直观可以启发我们的思维，探

21、寻线性规划的一些基本性质。例例9 9：利用图解法求解下面线性规划问题：第38页，此课件共46页哦解：在平面上取一个直角坐标系，他的两个坐标是首先找出平面上满足约束条件的点。第39页，此课件共46页哦 当目标函数取某一 值h时。令h=0，得直线 目标函数的值为0 再令h=2,6,7.得另外三条直线，其上点分别对应目标值2，6，7，因此把 叫做目标函数的等值线。当参数h变化时，就得到一族平行直线，他们形象的描绘了目标函数的变化状态。平面上满足约束条件的点为上图中的一个凸多边形。表明原线性规划问题的目标函数只能在这个凸多边形（含边界）上取值，那么求解线性规划问题就是如何从这个凸多边形上求出使目标函数

22、达最大值的关系。为此，我们先看看目标函数在凸多边形上取值的变化性能。第40页，此课件共46页哦 当h由小（大）变大（小）时，我们来观察等值线在凸多边形上的变化情形。取等值线的正（负）法向量，其方向指向目标参数值增大（减小）的方向等值线的正（负）法向量，其方向指向目标参数值增大（减小）的方向。当h由小（大）变大（小）时，直线 沿（负）法方向平行移动，目标参数值不断增大。这样就可以看到，对于凸多边形 目标参数在07之间取值，且：相交时，目标参数值达到最大值7，如果等值线继续沿法方向移动，将离开这个凸多边形。不满足约束条件。于是知这个线性规划的最优解为第41页，此课件共46页哦二 线性规划的基本性质

23、：若将上面例9改求目标参数约束条件不变，那这整个问题就是：一个是在凸多边形的极大，另一个则是在同一凸多边形上求同一目标参数的极小，由点面的分析知，目标参数在凸多边形顶点 这个事实就是线性规划的一个基本性质，如果线性规划有最优解，必然在凸多边形（或凸多面体）的顶点上达到最优，下一章我们将证明这一性质。当求解线性规划问题时，图解法给人们提供了直观的思想，求解线性规划的单体形法是以解空间的凸多面体某一顶点开始进行替代，直到求出达到极值的顶点（如果问题有最优解）。这个目标参数也在凸多边形顶点第42页，此课件共46页哦解：画出由约束条件决定的4个半平面的交集K，这是一个无界的凸多边形。作目标函数的等值线

24、方向等值线可以无限制的减小，也就是问题最优值是负无 下面在举几个例子说明怎样用图解法求线性规划问题的解。例例1010.求使目标函数 穷大，或者说函数 最大化：目标函数等值线沿法向移动，最小化，沿负法向移动。第43页，此课件共46页哦例例1111使约束条件决定的图形是图中凸多边形OBAC做等值直线束沿正法方向第44页，此课件共46页哦再移动就离开K了，所以线段AB上的点都使解：如图所示：四个约束条件决定的半平面没有相交部分即问题没有可行解。综上可见：两个变量的线性规划问题可能有以下四种情形第45页，此课件共46页哦1.1.有唯一最优解有唯一最优解2.2.有最优解，但不唯一有最优解，但不唯一3.3.有可行解，但是没有最优解。有可行解，但是没有最优解。4.4.没有可行解。没有可行解。对于一般问题也有上述论述。第46页，此课件共46页哦