第八章 线性规划.ppt

1、第八章线性规划，前言，优化问题包括一个目标函数和一个或多个约束。线性规划是一种用于解决一组特殊的带有约束的优化问题的方法，其中目标函数是线性的并且具有一个或多个线性约束。1.线性假设：线性规划问题中所有重要的关系都必须是线性的，通常包括生产、总成本、总收入和利润函数。这些函数是线性的假设也意味着规模收益、产品价格(不管产出有多大)和投入要素价格(不管投入要素购买了多少)被假设为常数。规模报酬不变和投入要素价格不变的结合意味着单位产出的生产成本是一个常数。不变的单位成本和不变的产品价格的结合将使单位产品的利润保持不变。(1)建筑问题假设一个企业生产两种产品，需要三台不同的机器。在生产期间，每台机

2、器的可用工作小时数是有限的。假设每个产品的单位利润在相关的产出范围内是一个常数。企业面临的问题是在可用机器工作时间有限的情况下，确定能使利润最大化的甲乙双方的质量保证和质量保证量。质量保证和质量保证被称为决策变量。第二，在利润最大化的约束条件下，为了解决这个问题，管理者需要找到一种函数形式来表达这个目标，即建立一个目标函数。在这个例子中，目标函数是：其中质量保证和质量保证是决策变量和总利润；a和b分别是生产一个单位a和b的利润。单位产品的资源(机器工作时间)需求和总的可用机器工作时间2。约束条件下的利润最大化。线性规划问题可以表示为：寻求最大值：满足要求：机器X的约束条件和机器Y的约束条件是非

3、负约束。一般来说，非零决策变量的数量不会大于资源约束的数量(即排除非负约束的约束的数量)，2。约束条件下的利润最大化，(2)可行域下一步是确定不违反约束条件的质量保证和质量保证产出，即可行域。可行域包括同时满足所有约束的所有决策变量的所有值。在其边界上或边界内的任何点上的生产都可以满足约束条件。2.约束条件下的利润最大化；2.约束条件下的利润最大化；和3。以图形方式计算分配给每个产品的机器工作小时数。严格和非严格约束概念的意义在于确定有限资源的机会成本。紧密性意味着这种资源的利用有机会成本。最佳解决方案总是在某个角落。解决线性规划问题的方法是随机取一个角，在这一点上评估目标函数。然后转移到其他

4、可以提供更高利润的角落，一个接一个，直到他们不能获得更高的利润。目标函数的斜率在决定哪个角是最好的方面起着决定性的作用。(4)代数角点是约束的交集，可以通过找出哪些约束是组合的，然后求解这两个约束的方程，并找出交集处决策变量之和的值来确定。决策变量的值和每个角点的利润；3.约束条件下的成本最小化：(1)建设问题、成本最小化问题的基础数据、成本最小化问题的约束条件和可行域；3.约束条件下的成本最小化：(2)代数方法中决策变量的值和每个角点的代价；3.约束条件下的成本最小化，无论目标是目标函数最大化。首先，约束条件确定可行域。其次，确定可行域每个角的决策变量的值。然后，评估这些组合中的每一个的目标

5、函数，并选择能够使目标函数最优(即最大或最小)的组合。(2)敏感性分析如果你知道原来的问题和答案，只需改变问题中的一个或几个参数，再次求解，然后比较原来的和新的答案。这是敏感性分析的本质。灵敏度分析的方法是解决线性规划问题；然后改变问题的一个或几个组成部分；然后解决问题并比较两个答案。目标函数的系数、约束条件的系数和/或约束条件右侧的资源数量可以改变。此外，可以从问题中添加或删除决策变量或约束。线性规划中的一些特殊问题(1)多解如果目标函数的斜率与约束条件的斜率相同，将会有无数个决策变量的最优组合。四。线性规划中的一些特殊问题：最大值：=10x15x2: X1 2X260(约束A) 2X1 X

6、260(约束B) X127(约束B) X10，X20在这个问题中，目标函数和约束B的斜率都是-2。线性规划中的一些特殊问题(2)冗余约束有时，一个或几个约束是不必要的。示例：a: x1 2x250(约束a) b: x1 x240(约束b) c: 5x1 6x2300(约束C) X10，X20由于约束C不紧，此约束所代表的资源机会成本为零。线性规划中的一些特殊问题(3)无可行解如果没有同时满足所有约束条件的决策变量的值，问题就很难解决。2X1 3X2120(约束A) 1x240(约束B)只有1X2=40的下点满足约束B，2X1 3X2=120的上点满足约束A，但是没有一个点可以同时满足这些条件。

7、在没有可行解的情况下，必须修改一个或多个约束条件以获得可行解。四、线性规划中的一些特殊问题，五、对偶问题，如果资源约束比较紧，这类资源就会有机会成本。对偶线性规划是一种估计与每个约束相关的资源机会成本的方法。每一个线性规划问题，称为原始问题，都有一个相关的问题，称为对偶问题。如果原问题的目标需要最大目标函数，那么对偶问题的目标就是最小化相关的目标函数。反之亦然。对偶问题和原始问题是对称的，因为一个问题的解也是另一个问题的解。(1)构造对偶问题对偶问题是根据原问题中的系数序列建立的。5.对偶性问题，假设三个新变量Cx、Cy和Cz分别代表机器X、Y和Z的工作时间机会成本。对偶问题的目标函数是：求m

8、in: c=90cx80cy60cz，即目标是使稀缺资源(机器工作时间)的机会成本最小化。5.对偶问题，对偶问题中第一个约束条件的系数是原问题中的第一列，即QA: 1Cx 2Cy 2Cz 3的系数。第二个约束条件是根据原问题中第二列的系数确定的。因此：3Cx 2Cy 0Cz 1因为产品b不需要在z机上加工，所以该机器没有成本。与原问题一样，对偶问题也有非负条件，即Cx，Cy，Cz 0。最后，因为有三个决策变量但只有两个资源约束，所以最多有两个非零值的决策变量。(2)解决对偶问题的方法与上述方法完全相同，即定义可行域，确定每个角决策变量的值，用每个组的值来评估目标函数，并选择能够最小化目标函数值的组的值。因为原问题中的约束X不紧，所以机器X的工时机会成本为零(即Cx=0)。因此，问题可以简化为：发现min: c=80cy60cz满足2cy2cz32cy1的要求；Cy，Cz0: Cz=1，Cy=0.5，然后C=100。五、二元性问题，在资源最优配置的情况下，利润等于机会成本或用于产生