第一章线性规划与单纯形法.ppt

第一章，线性编程的发展，法国数学家J.-B.-J .傅里叶和c .芭蕾-福建分别在1832年和1911年提出了独立线性编程的想法。1939年苏联数学家。科托洛维奇在生产组织与计划中的数学方法中提出了线性编程问题。1947年，美国数学家g. B. Dan zick提出了线性规划的一般数学模型和解决线性规划问题的一般方法单纯形法。1947年，美国数学家J.von neumann提出了对偶理论，开拓了线性编程的许多新研究领域，扩大了其应用范围和解决问题的能力。1951年，由于美国经济学家t.c .库普曼斯在经济领域应用线性编程，他与康托洛维奇一起获得了1975年诺贝尔经济学奖。线性编程的发展，50年代以来线性编程的很多理论研究。例如，1954年c .罗琳提出了双单纯形法，1954年s .天然气和t .萨迪等解决了线性编程的灵敏度分析及参数规划问题，1956年a .塔克提出了互补松弛定理，1960年g.b .坦奇克和p .沃尔夫提出了分解算法等。此外，线性规划的结果直接影响其他数学规划问题，如整数规划、随机规划、非线性规划的算法研究。线性规划的发展，1979年苏联数学家L.G.Khachian提出了求解线性规划问题的椭球算法，并证明了它是多项式时间算法。1984年，n .卡马卡提出了一种求解线性规划问题的新的多项式时间算法。使用此方法解决线性编程问题。如果变量数为5000，则仅需单纯形法的1/50。形成了线性规划多项式算法理论。第一节线性编程问题及其数学模型，第一节，线性编程问题的建议在生产管理和运营活动中，经常提出如何合理利用有限的人员、物力、财力等资源，获得最佳经济效果的问题。第一节线性编程问题和数学模型，实例1:工厂计划期间生产准备，两种产品，生产单位产品所需的设备表和a，b两种原材料的消耗(如表1-1所示：x1，x2，第一节线性编程问题和数学模型，问：计划，工厂最多解决问题的思路：用以下数学模型说明，x1，x2分别表示计划期间产品，的生产。设备有效平台为8，是限制产量的条件，因此，在确定产品，产量时，要考虑设备不超过有效时间，可以将不等式表示为：第一节线性规划问题及其数学模型，第一节线性规划问题及其数学模型，概括地说，规划问题可以用以下数学模型表示：第一节线性编程问题和数学模型，实例2:河上有两个化工厂，通过第一化工厂的河流流量为每天500万立方米，两个工厂之间每天有1个流量为200万立方米，第一化工厂每天排放包含一种有害物质的产业污水2万立方米，第二化工厂每天排放这些污水1万4000立方米，第一节线性规划问题及其数学模型来自第一化工厂的产业污水根据环境保护要求，河流工业废水含量不得超过0.2%。两个工厂都要分别处理工业污水的一部分。一级化工厂处理工业污水的成本为1000元/万立方米，二级化工厂处理工业污水的成本为800元/万立方米。符合环保要求的话，每个工厂要处理多少工业污水，这两个工厂的工业污水处理总费用要降到最低。线性编程问题和数学模型，解决问题的想法：用数学模型说明。制药：建立第一化工厂，每天将工业污水处理为x万立方米，第二化工厂每天将工业污水处理为x2万立方米，从第一化工厂到第二化工厂，确保河流工业污水的含量不超过0.2%。这可以得到近似关系(2-x1)/500通过第二化工厂后，河流的产业污水也没有超过0.2%，大致有关系0.8(2-x1)(1.4-x2)/(500 200)x21.4目标函数：查找用于处理工业废水的两个工厂的总成本(z=1000 x1 800 x2)。第一节线性规划问题及其数学模型，概括地说，数学模型如下：目标函数minz=1000 x1 800 x2受约束(2-x1)/500资源和设备能力的消费定额和单位产品的收益见表1-1。只有询问生产调度方法，才能得到工厂最多的利益。例如，生产计划问题的数据表，x1，x2，因此总利润f=2x12最大值，解决方案：问题中表明：假定加工时间和利润与产品生产是线性关系，则a，b这两种产品的生产是负值，即x1，x2练习，生产计划问题(资源利用问题)胜利家具工厂生产桌子和椅子两户。桌子售价为50元/狗，椅子售价为30元/狗，桌椅生产需要木工和画家两种。生产一张桌子需要4小时木工，画家需要2小时。生产一把椅子需要3小时木工，画家需要1小时。这家工厂每月可使用120小时，油漆工人50小时的木工时间。问这个工厂如何组织生产才能最大限度地提高每月销售收入。练习，工厂生产a，b产品。据悉，生产1吨a种产品需要10吨a种矿石，5吨b种矿石，4吨煤。生产1吨b产品需要4吨a矿石，4吨b矿石，9吨煤。每吨甲方产品的利润为600元，每吨乙方产品的利润为1000元。工厂在生产这两种产品的计划中，要求a种矿石不超过300吨，b种矿石不超过200吨，煤不超过360吨。甲，乙两种产品各生产几吨(达0.1吨)，总利润才能最大化？练习，如合理的下料问题，钢筋的工厂，活动原材料是10米长的钢筋(直径相同)，90条3米长的钢筋，60捆4米长的钢筋。问如何才能满足需求，将原材料制成最低限度。解法：根据问题的意义，用以下三种方法剪下1) 3米的3个。请切成2) 3米2，4米1。3)切成4米的两块。材料(10m) x1，x2，x3根，表格1-7:范例：合理的空白问题，空白方法表格，minf=x1 x2 x3，空白方法，x1，x2，x3，object共同特征：1，每个问题都有一系列决定变量(x1，x2，xn)，其中这些确定变量的值通常表示具有非负连续值的特定方案。2、构成具有相关数据且与决策变量不冲突的约束条件的这些约束条件可以表示为线性等式或线性不等式组。3，都有要求实现的目标，可以用由决策变量和相关价值系数组成的线性函数来表示。根据问题，应最大化或最小化目标函数。第一节线性规划问题及其数学模型，满足上述三个条件的数学模型称为线性规划的数学模型。一般形式是：价值系数、目标函数、技术系数、限制系数、约束、变量的非负约束、1.2图形方法、示例1的图形解决。，4x1=16，4x2=12，x12x2=8，Q1，Q2，Q3，Q4，可执行域，1.2图形，4x1=16，4x1、等值线、x1、x2，1.2图形方法，上述示例中解决的问题的最佳解决方案是唯一的，但是对于一般线性编程问题，解决结果可能是以下几种情况：1，无限多最优解(多最优解)示例1中的目标函数更改为maxz=2x1 4x2时，目标函数中参数z的此族与约束x1 2 x2 z值从较小的值增大时，与段Q2Q3匹配。如果让分段Q2Q3的所有点都具有相同的z最大值，就有了这个线性规划问题的无限数的最优解(多重最优解)。1.2图形方法，1，无限最佳解决方案(多最佳解决方案)，(4，2)，(4，0)，(0，0)，16 (2) 4x2 12 (3) x1，X20(4)，无限最佳解决方案，注意：产生多个解决方案的原因是目标，(1)，(3)，(8)2 (2) x1，x2 0 (3)，(2，0)，(0，4)，(0，0)，“无限解决方案(没有可行的解决方案)这取决于目标函数的情况。在此问题中，如果将目标函数x1的系数从原始1更改为-3/2，则问题具有最佳解z (0，4)=4。1.2图形方法，3，无可行解决方案maxz=2 x1x 28(1)4 x116(2)4 x212(3)-2 x24(2如果在两个顶点同时获得最佳解决方案，则该连接的所有点都是最佳解决方案，即无限多个最佳解决方案。1.3线性规划问题的标准形式：在标准形式中指定每个约束的右端bi0。否则，方程式的两端将乘以-1 。1.3线性程序设计问题的标准形式，向量和矩阵符号表示：1.3线性程序设计问题的标准形式，实际上遇到各种线性程序设计问题的数学模型，需要转换为标准样式后解决。1.3线性编程问题的标准形式，转换为标准形式的方法问题。标准型的特征：1，目标函数求最大值2，约束方程都是方程3，变量都不是负数。4，约束右端的常数数bi 0 (I=1，2，m)，1.3线性规划问题的标准形式，标准形式的一般步骤1，目标函数最小化“最大化”2，约束的右端项bi0“0”3，约束不等式 4，值不受约束(自由) 获得Maxz=-CX时，上述两个问题的最优解相同，但最优解的目标函数值是minz=-maxz=CX，1.3线性编程问题的标准形式，注意：目标函数值是符号，1.3线性编程问题的标准形式，(2)约束方程是不等式的问题约束方程是“ 如果约束方程是“”不等式，则从“”不等式的左端减去一个非负变量。1.3线性编程问题的标准形式，示例3:1的数学转换为标准示例1的数学模型：松弛变量，添加的松弛变量表示未使用的资源。当然也没有利润。在目标函数中，系数必须为零。，1.3线性规划问题的标准形式，3，无变量符号限制问题xk限制的情况下，xk=xk-xk ，xk 0，将以下线性规划问题更改为标准形式，将1.3线性规划问题的标准形式更改为(1) x3为x3-x 其中x3，x 30；(2)在第一约束不等式编号的左端添加松弛变量x4。(3)从第二个约束不等式号的左端减去剩余变量X5。(4)如果创建z=-z并将minz更改为maxz ，则该问题的标准型、标准型、1.3线性编程问题的标准型、4、bi为负数，则将约束等式的两侧相乘(-1)。1.3线性编程问题的标准形式，因为1，x3不受约束，所以2，第一个约束条件是“”号，所以将缓和变量x4添加到“左侧”。3，第二个约束条件是“”编号，因此从“”编号的左侧减去其馀变量X5。4，第三个约束条件为“编号”，常数为负数，因此在“编号左侧添加松弛变量X6，两边乘以“-1”。5，因为目标函数是最小值，所以z=-z，maxz=-CX，即Z达到最小值时，Z 达到最大值。1.3线性规划问题的标准形式，1.3线性规划问题的标准形式，5，变量XJa，b，即aXJb，0XJ-a；b-a命令xj=xj-a0的xj xn 1=b-a和XJ 88050，1.3线性编程问题的标准形式，例如，标准化下一个问题，1.3线性编程问题解决方案：x2无限制，x2=x2-x2，x20是x30，因此x3=-0是标准。注意：必须重新导入原始问题，1.3线性编程问题的标准形式。范例4:将下列线性程式设计问题变更为标准形式，x3=x4-x5，其中x4、x50，z=-z 变更为minz。1.4线性程式设计疑难排解的概念，可能的解决方案：以限制(1-5)为基础，1.4线性规划问题解决的概念：如果a的子矩阵B是可逆矩阵|B|0，则方形B称为LP问题的基础。b的所有列都成为LP问题的一个基本向量(共m个)。与基础向量相对应的变量是基础变量。a的其他列矢量称为基准b的非基本矢量(总n-m)。与非基本向量相对应的变量是非基本变量。基本向量，1.4线性编程故障诊断的概念，a=(P1 pm pm 1 pn)=(b n)基本向量非基本向量，x=(x1 XM xm1).xn)