线性规划问题概述演示文稿

线性规划问题概述演示文稿目前一页\总数四十四页\编于十八点（优选）线性规划问题概述目前二页\总数四十四页\编于十八点（4）课后安排适量作业，巩固所学内容，要求按时完成。（5）对部分有能力的同学，引导他们通过计算机实习，编制程序解题。三、教学计划与内容提纲：1教学内容与学时匹配，见教学日历。2教学内容大纲：第一章线性规划问题概述

1花一节课时间介绍线性规划的发展历史和发展动态以及在经济分析等实际工作中的应用，调动同学们的学习兴趣。

2建模部分着重讲一些实际问题的线性规划模型建立过程；突出模型的三要素：目标方程，决策变量，约束方程。

3线形规划的几何解法，主要是在平面上用图形如何解二维的规划问题，注意从中得出结论，最优解在解这一领域的顶点达到。目前三页\总数四十四页\编于十八点

1交代清楚基本概念。

2基本定理2.2.2是重点讲解内容，其证明过程的推导过程要详细讲解。由此定理，强调一个结论，若一个线性规划问题有最优解，则必有最优基本可行解。也就是说最优解必可在可行解域的极点上达到。这是后面单纯形法的基本启发思想。

3极射向和可行解表示定理，这部分内容比较偏重理论推导过程，要求同学们对定理特别清楚的了解，这是后面判一个问题设有最优解的基本理论，也是单纯形法的一个终止原则。至于可行解的表示定理，纯属理论证明之用，故此讲解时，注意把证明的思想将清楚。第二章线性规划的基本概念和基本定理目前四页\总数四十四页\编于十八点第三章单纯形法本章是线性规划的一个核心内容，要重点介绍一下。

1单纯形法的概念部分主要讲述三个内容：（1）极轴的运算（2）判别数定义（3）最优判别定理2对单纯形法分两种方式介绍：（1）数值迭代公式方法，这里要注意推导极轴运算过程，证出迭代公式。（2）表上作业法两种方法都重要，前者便于计算机运算，后者便于手工计算。在介绍他们时都要注意以下问题：<A>极轴元的选择方式，过程。<B>数值迭代或表变换过程，步骤。<C>终止准则（有或无最优解）。<D>收敛性定理。目前五页\总数四十四页\编于十八点5Bland先行循环的方法，粗略介绍。6

修正单纯形法，主要用于计算机运算，请同学们自学7求最优基本可行解，每个最优基本可行解对于实际工作的决策者来说，就是一种最优决策方案，因此能够求出最优基本可行解，就能为决策者提供可用方案。3人工变量方法，为了寻找单纯形法的新始基可行解，引进人工变量，介绍两阶段方法求解过程；增加内容：大M方法产生新始基可行解。4退化与循环问题，讲情楚Beale的例子，说明线性规划中在退化情性下可能出现循环现象，着重介绍-摄动法先行循环；注意从理论上完备S-摄动法即定理3.4.2的结论及其的证明过程要交代清楚，着重讲解。目前六页\总数四十四页\编于十八点第四章线形规划的对偶定理及应用1注意从实际问题中引出对偶规划的概念。

2重点介绍对称形式对规划及对偶定理。对定理，，，全面地描述了一对偶规划的解之间的关系，注意把这三个定理串联起来对对偶规划综合分析。

对偶定理，注意说明由此引出的松紧概念。

3非对称对偶规划。与对称对偶规划的四个对偶定理对比研究，启发同学们对对偶单纯形法基本思想的初步认识。目前七页\总数四十四页\编于十八点

4混合形对偶规划，要举出几个实例证明如何由一个问题，写出另一个对偶问题的方法，强调解题过程，第一要对问题形式规范化，第二要掌握对偶表，根据对偶表写出对偶问题。5对偶单纯形法，与第三章的单纯形法对比研究，哪些不同，哪些相同，迭代公式，表格形式，迭代过程。6对偶单纯形法的经济意义，举一个实际例子，证明由一个对偶单纯形最终表，一个决策者可以得到什么信息目前八页\总数四十四页\编于十八点第五章灵敏度分析

1为什么要对线性规划问题进行灵敏度分析，主要从经济分析方面回答。

2本章各节均与第四章内容紧密联系，因此讲授时，一要提醒同学们复习，二要简明提出一些重要内容课堂复习。

3对三个灵敏度分析专题：新增变量，新增约束，系数cj,bi,aij

变化。各举一到两个实例说明分析的方法和经济意义。目前九页\总数四十四页\编于十八点第六章变量有界限制的线性规划问题

1

问题的标准形式及其基本概念，重点讲解最优判别定理。

2

问题的算法，主要介绍第一阶段算法的最优准则算法思想和算法过程，及第二阶段中心枢纽运算过程寻找新的基矩阵。

3迭代收敛性定理重点讲解。它证明了上面建立的算法是有限终止的。

4花一课时间深细讲一个例子，说明算法步骤及其中诸深细细节问题。目前十页\总数四十四页\编于十八点

线性规划

LinearProgramming

前言

一线性规划的发展史参考书目：北京理工大学出版社，

许万蓉，《线性规划》。山东科学技术出版社

《线性规划》。29.183GMG

管梅谷，郑汉鼎。研究线性规划最早的是苏联的П.В.канторович（康脱洛维奇），1939年，他发表了《生产组织与计划中的数学方法》一书。主要讨论了机床、负荷、下料运输等问题。但他提出的问题在当时并未引起人们的注意。他自己也未能提出一个统一的求解方法。目前十一页\总数四十四页\编于十八点在第二次世界大战期间，由于军事运输的需要，提出线性问题的解法，美国的经济学家柯普曼（Koupman）也研究了运输问题。直到1947年，美国的提出了求解线性规划的单纯形法，才使线性规划这门学科在理论上趋于成熟，并成功地运用到了工业、交通、农业、军事等各个领域内，使线性规划的理论与方法成为管理科学的重要内容。在当今电子技术高度发展的信息社会中，线性规划给人类在经济管理、生产管理、人才事务管理等方面发挥了巨大作用。现在对于成千上万个约束条件、成千上万个变量的线性规划问题在计算上已没有任何问题。据20世纪80年代末美国一个杂志对全美500家大公司的调查，线性规划的应用范围名列前茅，有85%的公司频繁使用线性规划。目前十二页\总数四十四页\编于十八点二线性规划问题的特点由于是管理科学的重要分支，也是它的最成熟，最完整的分支。而管理科学的特点是利用数学模型为管理人员提供方针，以便在现有信息的情况下作出有效的决策，或现有信息不足作出决策时，而去搜索更多的信息。这里我们要抓住以下几个要素：第一管理科学的核心是建立模型。即运用数学的抽象，住所要探讨对策问题最重要的特征。模型是现实的简化表示。

笫二通过模型设计，给管理工作提供方便.

笫三进行有效决策所需信息的多少，决策所要探讨问题的复杂程度，而不决定于研究过程所用的工具。模型要求过多的信息就不是好模型。线性规划也是这样通过模型，求解，分析综合，为决策者提供科学决策依据。目前十三页\总数四十四页\编于十八点三线性规划的主要应用线性规划主要应用在以下几个方面：（1）在某一企业内部，如何配合产品的销售时间，在各部门的原料，产品的存储，分配的数量等最为合理。（2）在某一企业生产的产品数量（或产值），如何使现有的设备，人力，原料等条件限制下，合理组织生产，使经济效益最高。（3）在某地的交通网中，如何合理组织运输，使运费最小。（4）在市场上产品的（或原料）价格变动时，对于这些变动，企业如何做出最优决策。（5）合理下料问题，即利用某种原料下料时，如何达到既满足要求，又使原料最少。目前十四页\总数四十四页\编于十八点（6）配料问题，即生产由各种原料生产的的产品时（如混合饲料等）时，如何既满足规定的质量的标准，又使产品的成本最低。（7）库存问题，在仓库的容量及其他条件的限制下，确定库存物资的品种，数量，期限，使库存的效益最高。（8）在投入产出问题中，引进某一目标函数，制定最优的企业（或地区）经济计划。当前，我国正在进行以城市为重点的整个经济体制的改革，企业的自主权在扩大。一个企业要适应国内，国际的市场竞争，就必须改善经营管理，提高经济效益，制定最优的生产计划，并对瞬息万变的市场信息作出反映，应用现代数学方法，特别是线性规划方法，对于提高企业管理水平和企业活力，将会起着极大的作用。目前十五页\总数四十四页\编于十八点第一章线性规划问题概述

§1.1线性规划问题举例及数学模型例1．（生产安排问题）某厂生产A,B两种产品。生产一吨A需用煤九吨，电力4千瓦，劳动力三个（以劳动日计算）；生产一吨B需用煤3吨，电力五千瓦，劳动力10个。已知一吨A可获利C1元，一吨B可获利C2元。该厂现有煤360吨，电力200千瓦，劳动力300个，问：生产A、B各多少吨获利最大？试建立这一问题的数学模型。目前十六页\总数四十四页\编于十八点煤耗：9x1+4x2≤360

电耗：4x1+5x2≤200解：首先列出数据表：目前十七页\总数四十四页\编于十八点劳动力耗：3x1+10x2≤300

生产数量：x1≥0x2≥0注意：约束条件两边单位要一致。从而此问题的数学模型为：求一组变量x1，x2值，使满足：目前十八页\总数四十四页\编于十八点例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截法，用去钢材xj根（j=1，2，3）。则这批钢材截成7米长的钢梁为x2+2x3根，2米长的7x1+4x2根，废料总长x1+x3米.于是，得出问题的数学模型为：求一组变量x1,x2,x3,的值，使满足：目前十九页\总数四十四页\编于十八点目前二十页\总数四十四页\编于十八点主要配料是：石灰石，谷物，大豆粉，其营养成分如下：问应如何处理配料，使在营养和物质条件均满足的情况解：设生产100斤饲料，需用x1斤石灰石，x2斤谷物，x3斤大豆粉，于是可找出问题的模型：目前二十一页\总数四十四页\编于十八点目前二十二页\总数四十四页\编于十八点由以上几个例子，我们看到，所建立的数学模型其目标函数和约束条件均是关于未知变量的线形函数。目的是要求目标函数在约束下的极大或极小。我们称这样一类模型为线性规划模型。建立数学规划模型主要由以下三个步骤（隐含着三个要素）1．确定决策变量，亦即选取适当的量为问题的待确定量，这是问题的基础。2．建立适当的约束条件。3．建立目标函数。下面我们再举一些例子说明如何建立线性规划模型：

例四：（装配成套）某产品的一个单件包括四个A个零和三个B零件。这两种零件由两种不同原料制成，而这两种原料可利用的数额分别为100个单位和200个单位。由三个车间按不同的方法制造。下面表格给出每个生产班的原料耗用量和每种零件的产量。目标是确定每个生产班数使产品得配套数最大？目前二十三页\总数四十四页\编于十八点17

5，，2解：设,x1,x2,x3是第1.23车间的生产班数，则三个车间生产零件A的总数是x+6x+8x生产零件B的总数是x+9x+4x1233目前二十四页\总数四十四页\编于十八点而原料1和原料2对应的约束条件分别是因为目标是要使产品总件数达到最大，而每件产品要4个零件A和3个零件B。所以产品的最大数额不能超过目前二十五页\总数四十四页\编于十八点这是一个非线性的目标函数，可以通过变换转换成线性规划模型：求：目前二十六页\总数四十四页\编于十八点例6

某厂准备在电视台做广告，根据电视台收费标准，播出时间有三种选择：时间（1）星期一至五18：30~22：30热门时间，每半分钟收费300元；时间（2）星期六、日18：30~22：30热门时间，每半分钟收费420元；时间（3）18：30~22：30以外的时间，即平时，每半分钟收费180元。工厂希望每天播出一次半分钟时间的广告。而电视台希望放在时间（2）的播出次数不S.t.整理即得：求f=y的最大值目前二十七页\总数四十四页\编于十八点要超过在时间（1）的播出次数，工厂则希望不要在星期一至五热门时间播出，以便平时也能看到广告播出。因此规定在时间（1）的播出每月不超过15次。所以规定在时间（2）的播出每月不少于4次。工厂估计，认为在时间（1）观众为平时的三倍。在时间（2）观众则为平时的五倍。试列出一个线性规划模型，确定一个月内播送广告的方案。使（1）观众最多，（2）费用最少。解：题中需要确定的是在不同的时间内各播出几次。以一个月30天来考虑，假定星期六、日共9天。设x为时间（1）播放次数。

y为时间（2）播放次数。

z为时间（3）播放次数。则x+y+z=30(每月中每天一次）目前二十八页\总数四十四页\编于十八点电视台要求：y≤x厂方要求：x≤15及y≥4非负约束：x≥0，y≥0,z≥0.又一个月中:y≤9整理以上的约束条件得目前二十九页\总数四十四页\编于十八点一

标准形式:

我们由上面的实际例子已经看到,线性规划问题的模型是由一组线性等式或不等式表示的约束条件及一个线性目标参数组成的.即下面的一般形式:

求一组变量§1.2线性规划的标准形式并且使目标函数：达到最大（或最小）Opt.目前三十页\总数四十四页\编于十八点为了便于求解线性规划，有必要化线性规划成一定形式，即为下面的标准形式：求一组变量目前三十一页\总数四十四页\编于十八点

因为一般形式的线性规划问题都能化成标准形式（后面介绍），因此只要会求解标准形式的线性规划问题，就会求解一般形式的线性规划问题了。下面介绍几种形式的标准线性规划[SLP]问题。1.缩写形式：目前三十二页\总数四十四页\编于十八点矩阵形式：注：向量非负，代表向量的各分量非负目前三十三页\总数四十四页\编于十八点3.向量形式：目前三十四页\总数四十四页\编于十八点二化线性规划问题为标准形式：

第二若约束条件中出现线性不等式则可能转化为求目标参数转换方法：

第一若是求目标函数目前三十五页\总数四十四页\编于十八点第四目前三十六页\总数四十四页\编于十八点下面根据这些方法来做几个实例：例8

将下面的线性规划问题标准化：目前三十七页\总数四十四页\编于十八点§1.3线性规划的基本性质一两个变量线性规划问题的图解法：我们先对二维的简单线性规划问题利用图解法进行求解。从图解法的几何直观可以启发我们的思维，探寻线性规划的一些基本性质。例9：利用图解法求解下面线性规划问题：目前三十八页\总数四十四页\编于十八点解：在平面上取一个直角坐标系，他的两个坐标是首先找出平面上满足约束条件的点。目前三十九页\总数四十四页\编于十八点当目标函数取某一值h时。令h=0，得直线目标函数的值为0

再令h=2,6,7.得另外三条直线，其上点分别对应目标值2，6，7，因此把叫做目标函数的等值线。当参数h变化时，就得到一族平行直线，他们形象的描绘了目标函数的变化状态。平面上满足约束条件的点为上图中的一个凸多边形。表明原线性规划问题的目标函数只能在这个凸多边形（含边界）上取值，那么求解线性规划问题就是如何从这个凸多边形上求出使目标函数达最大值的关系。为此，我们先看看目标函数在凸多边形上取值的变化性能。目前四十页\总数四十四页\编于十八点当h由小（大）变大（小）时，我们来观察等值线在凸多边形上的变化情形。取等值线的正（负）法