线性规划系数矩阵变化的灵敏度分析

《线性规划系数矩阵变化的灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、莆田学院2001级本科数学与应用数学专业毕业论文编号莆田学院毕业论文课题名称线性规划系数矩阵变化的灵敏度分析学生姓名黄爱梅学号2001141126专业数学与应用数学班级01级数学本科指导教师王海明2005年6月5日10莆田学院2001级本科数学与应用数学专业毕业论文线性规划系数矩阵变化的灵敏度分析数学系01数本2001141126黄爱梅指导老师：林鸿熙摘要：本文利用分块矩阵法，讨论了线性规划模型中，系数矩阵的变化及变量增加时，LP问题最优解的变化，给出一般了一般处理方法,并在此理论基础上举出具体的例子来验证。关键词：线性规划；系数矩阵

2、；灵敏度分析；单纯形法0引言在线性规划的灵敏度分析中，一般给出使最优基保持不变时，某个消耗系数的变化范围。本文针对常用的追求最大利益的资源最优利用模型，讨论系数矩阵A中增加和减少约束条件及增加变量时对最优解的影响。(1)的分块矩阵形式为　　　…………………………………(1-1)若B为最优基，则对（1）施行单纯形法有：若（称为检验数），,最优解为表（1—2）称为LP问题（1）的最终表若LP问题（1）的约束条件有增减时相应地最优解也可能发生变化。下面分别加以讨论。1增加约束条件[1]10莆田学院2001级本科数学与应用数学专业毕业论文设L

3、P（1）增加一个不等式约束：其中为n维行向量增加一个约束条件，或使可行域减小，或使可行域保持不变，绝不可能使可行域增大，所以下面有两种情况：1.1若原问题（1）的最优解满足这个新约束条件，则它就是增加约束条件的新LP问题的最优解。1.2若原问题（1）的最优解不满足这个新约束条件，就需寻求新的最优基对新增加的约束条件，引入松弛变量后成为此时就得到一新LP问题。………………………（2）新基为　　，由此可知：新LP问题（2）的检验数为所以现行的基本解对偶可行。现行基本解为10莆田学院2001级本科数学与应用数学专业毕业论文因为，所以若，则现

4、行的对偶可行基本解是新问题（2）的最优解，即最优解为若，则在最终表（1-2）中第m+1行增加新约束的数据，通过初等变换，将（单位矩阵），再用对偶单纯形法求解。上述讨论需注意以下几点1.2.1上述讨论并未限制的正负，所以若约束式是，则可用-1乘不等式两端，变成，按（2）的讨论处理。1.2.2若加入的约束是等式，就需在新约束中加入人工变量，由于其相应的价值系数为-M，这时可将相应数据加入最终表中，用单纯形法求新的最优解。1.2.3上述讨论过程可推广到增加有限个约束条件的情形。2减少约束条件设在原问题（1）中去第i个约束条件：即,此时如果在

5、这个约束方程中加上一个非负的松弛变量和一个非负的剩余变量[2],即，实质上就取消了这个约束条件，所以，减少第i个约束条件后的LP问题实际上与下述新LP问题等价[1]。…………………………………………………(3)其中，10莆田学院2001级本科数学与应用数学专业毕业论文用单纯形法解LP３得由此可知，若，则最优解不变，若，则就要将加入最终表（1-2）中，用单纯形法继续换基，即可求得新的最优解。这样就求出了去掉一个约束条件后新LP问题的最优解。上述解决方法可以推广到去掉有限个约束条件的情形。3增加一个变量的分析增加一个变量在实际问题中反映为

6、增加一种新的产品,原问题变为下面的新LP问题。若最优解不变，若可通过换基，继续用单纯形法迭代计算找到最优。4实例说明例：美佳公司计划制造两种家电产品，已知各制造一件时分别占用的设备的台时，调试时间，调试工序每天可用于这两种家电的能力，各售出一件时的获利情况，。表1-1家电Ⅰ家电Ⅱ每天可用能力设备A（h）0515设备B（h）6224调试工序(h)115利润（元）2110莆田学院2001级本科数学与应用数学专业毕业论文问：(1)该公司制造这两种家电各多少件，使获取的利润最大。(2)设家电经调试后，还需要经过一道环境试验工序，家电Ⅰ每件须环

7、境试验3小时，家电Ⅱ每件须环境试验2小时，又环境试验工序每天生产能力为12小时，试分析增加工序后的美佳公司生产计划[3]。(3)设该公司引进新设备A，使得生产过程不受原先的限制，试分析美佳公司的最佳生产计划。(4)设该公司引进新设备B，使得生产过程不受原先的限制，试分析美佳公司的最佳生产计划。(5)设该公司又计划推出新型号的家电Ⅲ，生产所需设备及调试工序的时间分别为3小时，4小时，2小时，产品的预期盈利为3元/件，试分析种产品是否值得投产；如果投产，对公司的最优生产计划有何变化[4]。解：我们用上述理论来分别分析上述问题。(1)令分别

8、表示美佳公司家电Ⅰ、Ⅱ的数量，这时公司可获取的利润为元，令，得LP4：化为标准形式：用单纯形法求解表（4）为最终解表，最优解，，考虑到家电的数量为整数个，所以美佳公司新的最优生产计划应为每天生产家电Ⅰ4件，家电Ⅱ2件。其