2线性规划图解法.ppt

1、，2.0线性规划简介，第二章线性规划及其图式法(LP)章节结合了五个概念，线性规划是运筹学中较早、广泛、快速发展、方法比较成熟的重要分支，是帮助人们进行科学管理的数学方法。(莎士比亚、北极谱(美国电视剧)、线性规划、线性规划、线性规划、线性规划、线性规划、线性规划)将LP缩写为研究线性目标函数在线性约束下的极值问题的数学理论和方法。LP是运筹学的重要领域，广泛应用于军事行动、经济分析、经营管理、工程技术等领域。为合理利用有限的人力、物力、财力等资源的最佳决策提供科学依据。1832年和1911年法国数学家J. B.J .傅里叶和c .瓦莱普森分别独立提出了线性规划的想法，但没有引起注意。1939

2、年，原苏联数学家康托洛维奇通过对线性规划模型的研究，提高了组织和生产力问题。1947年，Dantzig提出了解决线性规划的单纯形方法1950-1956年。主要研究了线性规划的对偶理论，1951年美国经济学家T.C .库普曼斯将线性规划应用于经济领域，并与康托洛维奇一起应用。1958年发表整数规划的切面法1960年，Dantzig和Wolfe研究成功分解了算法，为大规模线性规划问题理论和算法奠定了基础。第一，线性规划开发概述，线性规划的研究结果直接推进其他数学规划问题，包括整数规划、随机规划和非线性规划的算法研究。数字电子计算机的发展导致了许多线性编程软件(如MPSX、OPHEIE、UMPIRE

3、等)的出现，从而可以轻松解决数千个变量的线性规划问题。1979年，Khachiyan，1984年，Karmarkaa研究了成功线性规划的多项式算法。用卡马卡方法求解线性规划问题。变量数为5000时，只需要单纯形方法所需时间的1/50。2，线性规划研究中解决的主要问题，事实上，这两类问题是一个问题的两个不同方面，都是问题的最佳解决方案(最大或分钟)。另一种是研究任务确定后如何协调才能最大限度地减少完成任务所消耗的资源量。(莎士比亚、温斯顿、工作)，一种已经有一定数量的资源(人力、物质、时间等)，可以研究如何充分合理使用它们，最大限度地提高完成的任务量。线性计划可用于解决人力资源分配问题、生产计划

4、问题、材料、投资问题(请参阅第4章)、运输问题(请参阅第7章)等问题。事实上，比这些具体问题要多得多。但是，一般意义上解决的问题有两种类型。即3，LP解决问题的一般思维，5，模型解决和解决的协调。(获得最佳方案的一组决策变量的值。)，1，对问题进行系统分析，确定决策是什么，确定决策层目标是什么？2、决定影响决定目标(大小变化)的因素(人为控制、决定变量)、决定变量对目标(函数)的影响系数以及与目标函数是否具有线性关系。3，资源约束(或需求约束)条件，用于限制目标(最大或最小)。决策变量对这些资源(或需求)的单位冲减(单位产量)是多少？也就是说，可以获得总资源和总I/o系数。4，建立线性规划数学

5、模型。6、方案实施和曹征。，2.1 LP问题提出和数学模型，1，提出叶诗文问题，示例2.1-1某工厂分配在计划期间生产两种产品，生产所需的资源限制和单位产品原料消耗根据下表，利润50 100如下：为了最大化总利润，应该如何制定生产计划？求解：确定决策变量：将产品甲分别设置为x1，x2，2。设定目标函数。将总利润设置为z。此示例为max z=50 x1 100 x2，3。考虑约束：目标函数：1.决策变量：设置产品I，II的产量分别为x1，x2，2。目标函数：设定利润为z，最大z=2x1 3x2，3。限制：例如2.1-3工厂生产三种药品，下表列出了原料可以提取的药品数量(有效单位数)。生产a种药品

6、至少需要160个单位。b种药品精确到200个单位，C种药品不超过180个单位，将原料的总成本降至最低。解决方案：1。决策变量：将四种原料的使用情况分别设置为x1、x2、x3和x4，2。目标函数：如果将总成本设置为z，则min z=5x16x27x38x4，X1 2x2 x3 x4 160 2x1 4x 3 2x4 160 3x1 x2 x3 2x4 180 X1，x2，x3，x40，决定变数：x=(x1 2)。目标函数：max=c1x1c2 x2 . cnxn，set，LP模型特性，1，全部确定变量集X=(x1，x2，xn)T表示方案，满足以上三个条件的数学模型为线性编程数学模型或LLP模型，

7、3，有一组约束，可以表示为决策变量的线性等式或线性不等式。LP模型的其他表示，简单格式，矩阵格式，确定变量，常数，系数矩阵，值系数，其中，4，线性规划数学模型的建立，(1)建模条件，1优化条件：问题需要实现的目标可以使用线型函数，2合格，3选择标准：决策者有多种选择以找到最佳方案。(2)确定LP建模阶段，1确定确定变量并收集相关参数。也就是说，需要决策或选择的数量。一般来说，不管题目问什么，把什么设定为决定变量。2查找所有资格条件：即决策变量接收的所有资源和需求等约束条件。3写目标函数：也就是说，清楚地知道问题应达到的目标，最大还是最小。(3)建模实例，实例2.1-4如果一家工厂生产A、B两种

8、产品，参数数据将询问如何组织生产才能最大限度地提高效果，如下表所示。设置：毛利为Z。产品A、B产量为x1、x2，产品C销售量为x3，报废数量为x4:max z=4 x1 10 x2 3 x3 2 x4，2.2线性计划图，1，故障排除步骤，4使用目标函数替换最佳解决方案以获得最佳值。1设置坐标系，在正交平面坐标系中绘制所有约束方程式，然后查找满足所有约束的公共部分。这称为可执行字段，可执行字段中的点称为可执行解决方案。2显示目标函数值改进的方向。3绘制目标函数素线。取得最大(较小)值后，目标函数等角线沿目标函数值增大(或减小)的方向平行移动，以找到与可执行栏位最后相交的点。这是最佳解决方案。下一

9、线性规划问题(范例1)，最佳解决方案：X*=(2，4)T最佳值：Z*=14，目标函数等角线Z=0，T最佳值在直角坐标系中，图形中任意点的坐标表示决策变量的值集，每个约束表示半平面。下图显示了：通过以图形方式解决以下线性规划问题，最佳目标值：1、凸面集为N维点集P的两点x(1)、x(2)，如果相应段仍在P内，则称为P。也就是说，x|x=x(1) (1-) x(2)、01、x(1)P、x(2)P P、P称为凸集)、2、极点x多边形的顶点都是极，且边坡、二、凸集、极值点的概念、三、线性规划解的性质、定理1线性规划的可行域R是凸集，具有有限极点。定理2 X是线性可规划域R顶点的充分条件下X线性规划的基

10、本可行解。如果清理3线性规划具有最佳解决方案，则必须存在预设最佳解决方案。定理4如果在可线性编程域的两个顶点上最佳，则在两个顶点的连接上也最佳。线性规划中的每个基本可行解对应于凸集的每个顶点。如果线性规划有最优解，则应在凸集的某些顶点处达到最优解。如果线性规划在两个或更多顶点上是最优的，则必须有无限数目的最优解。最优解必须是基本的可行解，但基本的可行解不一定是最优解。4，线性计划问题解决可能发生的情况，4，没有可行的解决方案。如果在示例3中添加另一个约束，3，无限解决方案。行域可以扩展到无穷大。目标函数值可以是无穷大或无穷大。2，如果最优解现在达到两极，就会有无穷数的最优解。1，如果LP具有最

11、优解，则应具有与该最优解相对应的可行域极；5，LP解决方案的相关概念和关系，1可行解决方案：满足线性规划约束的解决方案称为可行解决方案。(a)概念，2最佳解决方案：使线性规划目标函数最优的可行解决方案称为最佳解决方案。3基本解(基本解):基于线性编程约束方程的系数矩阵a中任意m行m列的mm完全排名子矩阵，与基本矩阵对应的变量称为基本变量，其馀变量称为非基本变量，将非基本变量设置为0可获得基本变量4基本可行解：满足非负约束的基本解为基本解，如果约束等式中有n个变量，m个约束，则基本解数，非基本变量X10，x2 0是X (0，0，3，1 )T，如果基本变量是x2，x3，则非基本变量是X1，这是基本

12、可行的解决方案吗？x1 2x2 x3 2x1 x2 x4 1x1，x2，x3，x40，解析：系数矩阵：设定预设变数x3，x4，非预设变数x1，x2，3) x (1/2，例如1可行解和最优解：最优解不一定是可行解，但可行解不一定是最优解。(b)线性规划解决方案之间的关系，基本解决方案不一定是可行的解决方案，可执行的解决方案不一定是基本解决方案。2可行的解决方案和基本解决方案：3可行的解决方案和基本可行的解决方案：基本可行的解决方案必须是可行的解决方案。但是，可行的解决方案不一定是基本解决方案。基本可行的解决方案不一定是基本解决方案，但基本解决方案不一定是基本可行的解决方案。4基本解决方案和基本可

13、行解决方案：5最佳解决方案和基本解决方案：最佳解决方案不一定是基本解决方案，基本解决方案不一定是最佳解决方案。问题：最佳解决方案和基本可行解决方案？不可行的解决方案、基本解决方案、6、线性编程模型的标准格式和标准化、(1)线性编程模型的标准格式特性、1目标最大化2约束是方程式。3决定变量不是负数。4右边的项目不是负数。，特性，最大z=c1x1c2x2cnxn，a11x1a 12 x2 a1 nxn=b1a 21 x1a 22 x2 a2 nxn=B2.如果am1x1am2x2amnxn=bmx1，x2目标函数为Min，则此最小化问题与下面的最大化问题具有相同的最佳解决方案，但是最佳解决方案的目

14、标函数值可以引入新变量，使其等于(2)线性编程模型标准化问题，1，目标函数最小化问题：(2)约束右和左之间的差值、等于或大于如果原始问题中有多个非等式约束，则转换为标准格式时，必须在每个约束中引入其他松弛变量或其他变量。在标准格式中，右侧项目的每个元件都不能为负。右端系数为负值(例如4 .在标准格式中，变量无符号问题要求每个变量具有非负约束。如果变量XJ没有非负约束，则可以创建XJ=xj- XJ 。其中xj0，XJ 0是两个非负变量的差异，表示无符号变量。当然，XJ的符号取决于XJ和XJ 的大小。简单地说，通过上述问题处理，可以将线性计划模型的一般格式转换为标准格式。标准化案例1、一般格式、标准格式、标准化案例2，2.3敏感度分析、敏感度分析是构建数学模型并求出最佳解决方案后，研究线性计划中一个或多个参数()变更时对最佳解决方案的影响。或者，这是当这些参数在一定范围内发生变化时，原始LP问题的最佳解决方案不变的问题。、C的敏感度分析是在目标函数中保持最佳解决方案不变的情况下该系数的值，1目标函数的系数“C”的敏感度分析，常规：、也就是说，代