毕业论文-参数线性规划的算法研究24820.doc

i 摘 要 参数线性规划是约束条件和目标函数中的价值系数、工艺系数、资源限量中含有 一个或多个参数的优化模型，是线性规划理论的重要组成部分，线性规划是运筹学的 一个重要分支，从解决技术问题的最优化设计，到工业、农业、商业、交通运输、军 事、经济等，在许多领域中都有着重要的应用。在生产过程中，由于工艺条件、资源 限量、市场需求、市场价格等因素都在不断的变化，因此，最优解也就带有一定程度 的不确定性。为了及时根据市场动态及数据资料的变化调整决策方案，运用参数线性 规划这一工具，建立参数线性规划模型，可以更好地指导实际工作，适应市场的变化 达到增加收益、降低成本的目的。 1947 年，dantzig 针对线性规划提出了单纯形法，为线性规划发展奠定了基础； 1954 年，c.莱姆基提出了对偶单纯形法；1954 年，s.加斯和 t.萨迪等人在对偶单纯形 法的基础上解决了线性规划的灵敏度分析和参数规划问题。 近年来，参数线性规划模型在单纯形法和对偶单纯形法的基础上，又产生了搜索 法、分块矩阵法、建立神经网络模型法等方法，随着计算机软件的发展，通过建立仿 真模型用计算机解决参数线性规划问题也成为一种重要的途径。 本文针对价格系数和右端资源数据中同时含有两个参数的复杂情形，对实际问题 建立了参数线性规划模型，并分析了最优解不变的情况下，参数的变化区间，找到了 最优目标函数的变化规律，并用 matlab 绘出了三维仿真图，为求解大型参数线性规划 问题提供了基础。 关键词：参数线性规划；最优解；区间；对偶；决策变量 ii abstract parametric linear programming is one kind of optimal modle with some constraint conditions,which there exist one or more parametrics in the objective function,technology factors,or limited resourses.it is widly applicated to many fields from technical problems to optimization design,such as industrial,agricalfural,transportation,military,economic and so on. in the producing process,the solution of the parametric linear programming often will be some uncertainties,due to the change of technology conditions,resources,market demands,material prices and other factons.so in order to adjust decision schem and meet with the market needs,data must be changed timely and immdiatly.parametric linear programming has play a important role in dealing with such problems.it has been a very useful tool for us to obtain decision plan and to increase value and reduce costs. in 1947, dantzig proposed a important method,simplex method, laying the foundation for solving linear programming; in 1954, c.lemke proposed dual simplex method; in 1954, s. gaston and t. saadi and others solved the parametric programming based on studing dual simplex method to the problem of the linear programming. in recent years, many new methods the parameters of linear programming model with the basis of simplex method and the dual simplex method, produced the search method, sub-block matrix method, the establishment of neural network models and other methods. with the development of computer software, linear programming problem with parameters can be solved by computer through the establishment of simulation computer model. in this paper, a mathematical model is created in accordance with the practical problem which has two parameters,one is in the price coefficients,anothisin the right resource data.the interval is obtained in the condition of analysis the optimal solution unchanged to provide the fundation to solve complicated parametric linear programming.by solving optimal solution,we have obtained the fuction with two parametrics.at last,the simulations have been given by matlab. keywords: parametric linear programming; the optimal solution; interval; dual; decision variation iii 目 录 第一章 绪论 1 1.1 参数线性规划的研究背景 .1 1.1.1 什么是线性规划 1 1.1.2 参数线性规划的内容 1 1.2 参数线性规划的研究现状 .2 1.3 参数线性规划研究的意义 .3 第二章 参数线性规划的理论 4 2.1 参数线性规划研究的常用方法 .4 2.1.1 目标函数的系数含有参数的线性规划问题 4 2.1.2 约束条件右端的常数项含有参数的线性规划问题 5 2.2 线性规划灵敏度分析 .7 2.2.1 什么是线性规划的灵敏度 7 2.2.2 价值系数的灵敏度分析 7 2.2.3 资源限量的灵敏度分析 .10 第三章 参数线性规划的数学建模 .14 3.1 实际问题的提出 14 3.2 实际问题的分析与解决 14 3.2.1 获利最大的生产计划模型 .14 3.2.2 a 产品的利润变化区间的确定方法 .16 3.2.3 关于开发新产品的决策研究 .16 3.2.4 购入原材料进行扩大再生产的必要性的理论分析 .17 3.2.5 影子价格的含义及分析 .18 第四章 两参数线性规划问题的解法 .20 4.1 两参数线性规划的定义 20 4.2 两参数线性规划问题的求解方法 20 4.3 两参数线性规划问题的分析与求解 22 第五章 结论 .27 参考文献 .28 iv 谢辞 .29 附录一 1 附录二 6 1 参数线性规划的算法研究 第一章 绪论 1.1 参数线性规划的研究背景 1.1.1 什么是线性规划 线性规划是运筹学的一个基本的，也是成熟的分支。为了解决二次世界大战中的 后勤供应问题，早在 20 世纪 30 年代末期康托洛维奇和希奇柯克等在生产的组织和运 输问题等方面就开始研究应用这一数学方法。10 多年后 dantzig 等人提出的单纯形方 法给线性规划这一数学方法的成熟与发展奠定了坚实的理论基础。随着时间的推移， 能用线性规划解决问题的类型在大量的增加。现在几乎所有的工业领域、商业领域、 军事领域及科学技术的研究领域都在不同程度地运用这一方法。正是由于它的应用， 全球每年各个领域节省了上亿万美元的资金，而各个生产部门也创造了大量的经济效 益。我国在建国初期就开始应用线性规划这一数学方法。 线性规划方法是一种重要的数学方法，线性规划方法是企业进行总产量计划时常 用的一种定量方法。线性规划是运筹学的一个最重要的分支，理论上最完善，实际应 用得最广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源作出最佳 方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益。 由于有成熟的计算机应用软件的支持，采用线性规划模型安排生产计划，并不是一件 困难的事情。在总体计划中，用线性规划模型解决问题的思路是，在有限的生产资源 和市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点是可以处理多 品种问题，可解决如运输问题、生产的组织与计划问题、合理下料问题、配料问题、 布局问题、分派问题等。 1.1.2 参数线性规划的内容 在线性规划的实际应用中，由于某种原因，有时线性规划问题的目标函数的系数 c 和约束条件的常数项 b 的数据不是固定的常数，而有所波动。例如在制订生产计划时， 一个工厂生产的各种产品的价格，由于原材料的供应价格有所波动，因而也有所波动。 这样，代表总利润的目标函数中的价格系数 c 便会随某个参数（即原材料的价格升降 百分数）而改变。又例如，在同样的问题中，由于供应原材料的单位的生产发生改变， 原材料的限制量产生波动时，那么约束条件右端的常数项 b 也将随某个参数（即原材 2 料生产增长的百分数）而有所改变。再比如，该工厂的工艺技术条件发生变化，那么 原线性规划问题约束条件的系数矩阵的系数就随之改变。这样的一些线性规划问题， 便是所谓的“参数线性规划” 。对于这种线性规划，我们所关心的时在参数的可能范围 内，求出问题的最优解，即可以用原来数学模型按实际出现的目标函数的系数或约束 条件右端的常数项来决策最优方案 【2】 。 在实际的生产或经济活动中，应用线性规划方法解决实际问题时，仅仅求出最优 解或最佳决策是不够的，还必须掌握参数变化对最优解或最佳决策的影响，即要做灵 敏性分析。依据变化了的情况，采取相应的措施，做好相应预案，争取更好的经济利 益。否则，如果事先对这方面的情况没有充分的了解和准确的估计，难免导致决策失 误，造成经济上的损失。 当线性规划中的工艺系数 、价值系数 、资源限量 中一个量或多个量变成确ijajcib 定或不确定区间里的一个参数时，这时线性规划模型就变成一个参数线性规划的模型。 当对参数线性规划模型模型里的参数赋予具体的值的时候，这时又变成了线性规划模 型。线性规划模型是研究参数线性规划的依据，所有的参数线性规划模型的建立于解 决都是建立在线性规划模型的基础上。但现实中市场瞬息万变，变化是绝对的，工艺 系数、新产品的加入、市场价格、资源需求等因素都在改变，原生产计划建立的线性 规划模型也就不适用于实际生产中去了，这时候就需要建立参数线性规划模型，所以 参数线性规划模型较线性规划模型在实际生产中更有实际意义。 1.2 参数线性规划的研究现状 线性规划作为运筹学的一个重要分支，从解决问题的最优化设计到工业、农业、 交通运输军事等许多领域都有着重要的应用。参数线性规划是线性规划的重要组陈部 分之一，几乎在 dantzig 的单纯形法出现后不久，就开始了对参数线性规划的研究。参 数线性规划的研究源于实际问题的需要，比如运输问题中的单位货物运价的变化（对 应目标函数的价值系数 的变化） ；资源利用数量的变化（对应约束条件右端的资源限jc 量 的变化） ；生产工艺改进（对应约束条件的工艺系数 的变化） ；甚至其中两者或ib ija 三者皆变，所以对参数线性规划的研究有其现实意义。所以在 1954 年 s.加斯和 t.萨 迪等人在 c.莱姆基提出对偶单纯形法的基础上解决了线性规划的灵敏度分析和参数规 划问题。 3 目前，处理参数线性规划的主要方法仍然是单纯形表上作业法，或是从对偶理论 出发建立对偶单纯形表进行求解。此类方法属于对参数线性规划求解的传统方法，如 当参数线性规划的决策变量和约束条件都比较多的时候，也就是所谓的规模比较大的 时候，单纯形表上作业法的缺点就十分突出，处理起来非常困难，甚至求解失败，得 不到最优决策。随着计算机软件功能的日渐增强，新的算法设计思想的日益活跃，给 计算工作带来了更多的便利。 经过许多科学家的努力，现在参数线性规划在以单纯形表法的基础上得到许多新 的算法。如当参数、约束条件、决策变量都比较多的时候，也就是大型参数线性规划 模型求解时，可以用搜索法确定参数变化区间，从而确定最优决策；分块矩阵方法求 解参数线性规划；利用进化策略和神经网络模型建立参数线性规划的数学模型，采用 精英保留策略的方法求的最优解。但是以上各种方法都存在局限性，局部使用，没有 完整的理论体系，所以参数线性规划的算法研究还有很地方需要改进和努力。 1.3 参数线性规划研究的意义 线性规划应用于工业、农业、商业、行政、军事、公用事业等各个领域，从各种 限制条件的组合中，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结 果。在实际生产、经营、管理等活动中会因各种因素的变化而导致最优决策而改变， 所以一般的线性规划模型为企业管理提供了理论基础，但该线性规划下建立的数学模 型不适合应用于实际生产活动中去，所以用一些不确定的参数来代表目标函数或约束 条件中的不确定因子，从而引出了参数线性规划的概念。参数线性规划，在实际工作 中有较广泛的应用价值，解决了参数连续变化时，最优解的变化规律，确定了最优解 发生变化的各个的取值，最终解决实际工作中的各类问题。 4 第二章 参数线性规划的理论 2.1 参数线性规划研究的常用方法 2.1.1 目标函数的系数含有参数的线性规划问题 一般地，假定线性规划问题的目标函数的系数向量 c 变成 ，其中* 2-1rccn，),(*2*1 这时，可行域一般不变化，故原问题的最优解还是新问题的基本可行解。但是，需要 修改目标行。新检验数为 ，* 1 jjjjbja 其中 ；新目标函数值为 。要使原问题的最优解还是新问题的*1*jjbj ca bcb1 最优解，则要求 。0j 若 ，则 等价于 ；*jj *j 若 ，则 等价于 。0*jj *j 令 ),21(0|max* njjjb， 2-2“b),21(0|in*njjj， 则要使 成立，便要 。0j“ b 与 分别称为 b 的下特征数和上特征数，而闭区间 称为 b 的最优区间。b“ “,b 因此对于 b 的最优区间中的每个 所对应的解 都是新问题的最优解，目标函b1 5 数的最大值为 ，其中 。即对于 b 的最优区间中每个 所对应*0ffbcfb1*0 的最优解是相同的，但目标函数的最大值为 的函数 【1】 。 现在考察对于最优区间外的 值，最优解的变化情况。 首先，当 （ 为一有限数）时，求解所给线性规划问题。“b 假设 j=s 时， ，则 。于是当 时，得 。这时，如果单纯*“s0*s “b0s 形表中 对应的列没有正数，则目标函数无上届，新问题无最优解，否则用单纯形方sx 法进行换基迭代,从而得到一个新的最优解。 其次，当 （ 为一有限数）时，求解所给线性规划问题。b 假设 j=t 时， ，则 。于是当 时，得 。同上面一样用单*t0*t b0 t 纯形方法进行换基迭代，从而得到一个新的最优解，或判明此问题无最优解。 2.1.2 约束条件右端的常数项含有参数的线性规划问题 假定线性规划问题的约束条件的右端常数项 b 变成 ，其中* b 。这时，只需修改右端一列，便可得到新问题的单纯形表，新rbbm),(*2*1 表右端一列为 2-3 1bbbcfb0 检验数均不改变，故仍然有 。要使原问题的最优基还是新问题的最优基，则要0j 求 2-40* iiib 如果 ，那么 等价于 ；0*ib0*iiib*i 如果 ，那么 等价于 。*i *iii *ib 6 令 ),21(0|max* mibiib， 2-5 ),(|n*“iiib， 那么要使 成立，便要0*iiib“ b 与 分别称为 b 的上特征数与下特征数，而闭区间 称为 b 的最优区间。“b “, 因此对于最优区间中的每个 所对应的解 2-6tmbbx),( *2*1 都是最优解，这时目标函数的最大值为 2-7*0ff 其中 2-81*0bbc 与前一种参数线性规划不同，这里，对于 b 的最优区间中每个 ，不但目标函数 的最大值是 的函数，而是最优解也是 的函数。 现在我们考察对于最优区间外的其他 值，最优解的变化情况。 首先，考察 的情形。假设 是在 时达到的，即“b“bri 2-9)0(*“rb 于是由 得*“rbb 2-100*rb 即 2-11rrx 这时如果单纯形表中第 r 行没有负数,则当 时，问题无最优解；如果有负数，则“b 用对偶单纯形方法进行换基迭代，从而可得 时的一个新的最优解。“ 7 其次，考察 的情形。假设 是在 时达到的，即bbti 2-12*tb)0(t 于是由 得*tbb 2-130*ttb 即 2-14tttx 这时再用对偶单纯形方法进行换基迭代，或判明无最优解。 2.2 线性规划灵敏度分析 2.2.1 什么是线性规划的灵敏度 当线性规划问题数据比较准确，约束条件比较完整时，得到的解对指导实际管理 的可靠性就大。事实上，在生产过程中，工艺条件、资源数量、市场需求、市场价格 等因素都在不断地变化，有些数据也是通过估计或预测得到的，带有不确定性，这时 得到的解也就带有一定程度的不准确性。有些数据在一定范围内变化时，最优解可能 改变也可能不变。例如，产品 a 市场价格为 6 元/ 件，一个月降到 5 元/件，这时产品 a 的生产量就有可能变化或者由于利润太低而不生产产品 a。又如，原材料供应量变 化或者改变工艺、增加新的产品等因素的变化，原决策方案就要随之改变。这些现象 都是客观存在的。做为企业决策者必须随时掌握市场动态及数据资料的变化情况，及 时调整决策方案，有效的利用线性规划这一工具，更好地指导实际工作，达到增加效 益、降低成本的目的。 线性规划的灵敏度分析（sensitive analysis）也称为敏感性分析，它是研究和分析 参数 的波动对最优解的影响程度，主要研究下面两个方面：),(ijjabc （1） 参数在什么范围内变化时，原最优解或最优基不变； （2） 模型发生变化（增减约束、变量，参数变化）时，最优解或最优基有何变 化。 当模型的参数发生变化后，可以不必对线性规划问题重新求解，直接在原线性规 划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可根据参数的变化 范围，及时对原决策做出正确的调整和修正。 8 2.2.2 价值系数的灵敏度分析 为使最优解不变，求 的变化范围。jc 设线性规划 max0zcxab 其中 线性规划存在最优解，设最优基矩阵为mna 2-151212(,),(,)miimib 检验数为 2-161,jjbccpjn 要使最优解不变，即当 变化为 后，检验数仍然是小于等于零，即jcjjj 2-1710jjbjc 这时分 是非基变量和基变量的系数两种情况讨论。jc （1） 是非基变量 的系数j jx110jjbjjjbjjjjjjccpccpc 即 ，当 时最优解不变，否则最优解就要改变。jjcjj （2） 是基变量 的系数ijx 因 ，当 变化为 后 后同时变化，令ibcciciicj 111_12_()(0,0)(,)jjbjj jjjbjjbj tjmjj iijjcpccaa 9 当 时有 ，当 时有 。 _0ija_jija_0ij_jiijca 令 2-18 _1_2max|0in|jijjjijj 要使得所有 ，有0j12ic 只要求出上限 及下限 就可以求出 的变化区间。因 ，故 ，21i 0j1 。具体计算 ， 时可以按 的符号分成两部分，分别求比值，然后在比值为201_ija 负号中取最大者就是 ，比值为正号取最小者就是 ，当出现 时， 可能无上2_0ijaic 界或无下界。 问题 1.已知线性规划 123123max405,zxx （1）求最优解 （2）分别求 ， ， 的变化范围，使得最优解不变1c23 解 （1）加入松弛变量 ， ， ，用单纯形法求解最优表如表 2-1 所示。4x56 表 2-1jc 1 1 3 0 0 0bbxx2x45x6b 10 0 1 3 4x13x0 1 0 -2 1 1 0 0 1 1 0 0 0 1 0 0 0 1 5 5 15j 0 -3 0 0 -1 -2 最优解为 ，最优值 z=50。(5,1)tx （2） 为非基变量， ， 为基变量，则2x1x323c 变化范围是 或2c22()4c(,4 对于 ：表 2-1 中 对应行的系数 只有一个负数 ，有两个正数 及11x_2ja_261a_21a ，则有 _25a521_62_23max,ax.1in1 的变化范围是 ， 或1c11cc03c0, 对于 ：表 2-1 中 对应行 ， 而 ，则有33x_321a_6_35a1_3262m,x,1 无上界，即有 ， 的变化范围是 或 。3c32c33c3, 对 的变化范围，也可以直接从表退出，将 写成 。分别计算非基3c 变量的检验数并令其小于等于零 11 12233 15536332(0,)10(,)0(0,)21bbccpcccc ，要使 ， 同时小于等于零，解不等式组 得 ，同理，51026 302c32 用此方法可求出 和 的变化区间。2c1 2.2.3 资源限量的灵敏度分析 为了使最优基 不变，求 的变化范围。设 的增量为 ， 的增量brbrbrb ,原线性规划的最优解为 x，基变量 。(0,0)trbb 10b 3-19 11()bxb 3-20 mrrmbbb 21211),( 3-210_22_1121_2_1 mrrmrrb bbx 既要满足 3-22 _0,12,irib 当 时有 ，当 时有 。令0ir_irbir_irb 12 3-23 _1_2max|0in|iriiirib 因而要使得所有 ， ，必须满足0ixrb12rb 这个公式与求 的上、下限的公式类似，比值的分子都小于等于零，分母是ic 中第 r 列的元素， 大于等于比值小于零的最大值，小于等于比值大于零的最小1brb 值。当某个 时， 可能无上界或无下界。0irr 问题 2.已知线性规划 123123max405,zxx 求 ， ， 分别在什么范围内变化时，原最优基不变。1b23 由表 2-1 知，最优基 ， ， 分别为b1bx1213413 3_12_321(,)0, 055,1bbpbxx 对于 ：比值的分母取 的第一列，这里只有 ，而 ，则1b1 12130_115maxb 13 无上界，即 ，因而 在 内变化时最优基不变。1b15b1b35, 对于 ：比值的分母去 的第二列， ， ，则2b1202_12_1225maxin5bb 即 在 上变化时最优基不变。2b15, 对于 ：比值的分母取 的第三列，有31b _123351,5,b 故有 ， 在 上变化时最优基不变31530, 上述 及 的最大允许变化范围是假定其他参数不变的前提下，单个参数的变化jcib 范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。 14 第三章 参数线性规划的数学建模 3.1 实际问题的提出 根据市场要求，某生产单位可生产 a、b、c 三种产品，其所需专业技人员，材料 等有关数据见表 3-1。 表 3-1 产 品 资 源 a b c 可用量 （单位） 技术力量 材料 6 3 5 3 4 5 45 30 产品利润（万元） 3 1 4 根据表 3-1 的资料，要求计算确定： 1）获得利润最大的产品生产计划； 2）产品 a 的利润在什么范围内变动，前面计算出的最优生产计划不发生变 化； 3）如果开发一种新产品 d，单位技术力量消耗是 8，材料消耗 2 单位，每 件新产品可获利 3 万元，如果从经济效益考虑，那么，这种新开发的产品是否值得生 产； 4)该生产单位的技术力量数量是固定不变的,但生产材料不足时可以从市场购买, 每单位购入价为 0.4 万元,那么,该单位要不要购入生产材料扩大生产,以购入多少最为 15 适宜？这是一个实际生产的决策问题，下面按要求分别计算最优解，获取量化的最优 决策。 3.2 实际问题的分析与解决 3.2.1 获利最大的生产计划模型 首先，根据表 3-1 的资料建立数学模型，设 a 产品生产 件1x b 产品生产 件2 c 产品生产 件3x 那么，最优生产计划的数学模型可以写成如下形式： 0,35436max2121xz 其次，将上述数学模型化为标准形式，以便利用单纯形法进行解算。加入松弛变 量，得到以下标准形式： 0, 354346max21321 xz 用单纯形法求出上述线性规划问题的最优解。见表 3-2 表 3-2jcbc 基 ib 31x1243x0405x 0 0 4x545 30 6 3 3 4 5 5 1 0 0 0 96minjjcz 3 1 4 0 0 16 0 4 4x315 6 335-140 1 1 0 -15min 10jjcz 0 0 4 3 4 1x35 3 1 0 3 1 0 1 3512jjczjj 0 0 -2 3d0 0 43d8 经过用单纯形法计算求得最优解,即能够获利润最大的生产计划: a 产品生产 5 件,b 产品不生产,c 产品生产 3 件。 这样，可以获得最大利润，最大利润为 maxz=35+43=27(万元) 3.2.2 a 产品的利润变化区间的确定方法 产品 a 的利润在什么范围内变化,使得前面求出的最优生产计划 (最大利润)不变呢? 设 a 产品的利润为 d，将 d 带入表 3-2 中，把 的系数换成 ，很显然，如果检1x 验数 ，则说明仍为最优解，换而言之，的变化区间求出来了，问题就解0jjcz 决了，仍利用原单纯形表重新计算检验数。见表 3-2 最下面一行。根据计算出的检验 数，有下列结果，如果 3045803dd 则最优解不变。解上式得 ,93412,558,3ddd 17 于是，得到这样的结论：第一临界值为 ，第二临界值为 ，产品 a 利润在125245 范围内变化时，不会对原最优生产计划产生影响。124,5 3.2.3 关于开发新产品的决策研究 按照前面的材料及要求，如果生产新产品 d，要消耗单位技术力量 8，材料消耗 2 单位，每件产品利润为 3 万元，从经济效益考虑是否值得生产？针对这种问题，可以 重新建立数学模型，求出最优解，与原最优解对比。以确定是否生产新产品。但实际 工作中，尤其是比较复杂的生产决策问题，如果用下面的方法处理，似更简单直观。 其原理和结果都是一样的。 设：增加新产品 d 生产 件，则 ， ，根据原最终表6x63c6(8,2)tp615 上式中的 是原最终表检验数的相反数。13()5166128345pb 据此，在原最终表上增加一列，继续迭代： 表 3-3jc 3 1 4 0 0 3b 基 ib1x23x45x6 3 4 1x35 3 1 0 1 0 1 5 132245jjcz 0 -2 0 3 4 6x352 5 410 6350 1 65141 0 18 jjcz105930 73100 根据上述计算结果,代入数学模型,得到以下结论:如果增加新产品 d (万元)1236max42.5zx 而增加产品 d 获得利润为 27.5 万元，大于原最大生产利润 0.5 万元（原最大利润 27 万元） ，从经济效益考虑，是值得生产的。 3.2.4 购入原材料进行扩大再生产的必要性的理论分析 由于问题提出的前提是技术力量不变，如果需要时可以增加购买原材料，单位价 格 0.4 万元，这一问题的实质是确定是否增加投入，购买原材料，扩大生产，那么购 买多少最适宜。仍利用原最终表，并将参数直接反映到最终表上，采用对偶单纯形法 计算见表 3-4。 表 3-4jcb 基 ib 31x1243x0405x 3 4 1x35 3 1 0 1 0 1 5 312jjzc 0 -2 0 （将参数直接反映到最终表） 3 4 1x3521 0 3 1 0 1 35 12jjzc 0 -2 0 0 4 5x31 9 -356130 1 -151 0 jjzc70 40 19 原最终表中最后一列检验数“ ”是影子价格，绝对值为 0.6 万元，而35 0.60.4（万元） ，故购入原材料是合算的。关于影子价格的含义在后面专门介绍。 经过上述计算，得到的结果是：材料市场价格低于影子价格，故可购入，用参数 规划计算，确定购 15 个单位最佳。 3.2.5 影子价格的含义及分析 关于影子价格，仍用前例来说明。在表中技术力量可用量为 45（单位） ，材料可用 量为 30（单位） 。从广义上理解，45 和 30 代表的是不同资源的拥有量，它的对偶变量 则代表对第 种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中iyi 产生贡献所作出的估价，它是生产单位的产品所存在的一种特殊的估计价格，在经济 学中称之为影子价格（shadowprice） 【3】 。 （1）资源的市场价格是已知数，相对而言，是比较稳定的，而影子价格直接受到 资源利用情况的影响，因此是未知数。从前面的例子可以知道，如果生产单位的生产 任务、产品结构等情况发生变化时，资源的影子价格也会随之改变。 （2）影子价格是一种边际价格。由对偶问题的性质可知，在利用单纯形法每步迭 代中，恒有 ，由于 ， ，故 。wz njjxc1miiybw1miiybz1 如果原问题中的 ， 都不发生变化，而 中只有 发生变化，可jcija),2(i k 以预见，若限定 在某一范围内变化时，原问题的最优基 b 可能保持不变，这里若把kb 最优解对应的目标函数值 ，看成是 的函数，则偏导数 miiybz1mb,1 3-1kyz 即为 增加一个单位时所引起的最优值的改变量。kb （3）资源的影子价格又是一种机会成本。仍以前例来说明，如果购买原材料，其 市场价格是 0.4 万元，而计算出的影子价格是 0.6 万元，当然买进时合算的。鉴此， 可以得出这样的结果：在生产决策中，资源的市场价格低于影子价格，即可买进，反 之又可以卖出这种资源。影子价格与市场价格保持同等水平，则处于平衡状态 【3】 。 20 （4）由于对偶问题的互补松弛性质中有“当 时， ，当 时njijibxa10iy1y 有 ”，这表明生产中若某种资源的拥有量 未得到充分利用时，该资源的影 njiibxa1 i 子价格为 0 时，表明该种资源在生产中以耗尽。 （5）影子价格的计算可以反映出产品的隐含成本， （生产单位产品消耗资源的影 子价格的总和即产品的隐含成本） 。当产品产值大于隐含成本时，表明生产该种产品有 利，反之，说明利用该资源生产其他产品会更有利。此即单纯形法中各个检验数的经 济意义。 （6）一般来说，对线性规划原问题求解是确定资源的最优配置，而对于对偶问题 的求解则是对资源的恰当估价，这种估价对合理利用资源，控制成本，计算最低利润 等都是实用有效的。 第四章 两参数线性规划问题的解法 4.1 两参数线性规划的定义 两参数线性规划定义为如下形式的线性规划（记为 ）),(21lp 4-1 其中 是给定的价值向量， 是给定的变化向量，),(21nc ),(21nc 是给定的右端系数向量， 是变化向量， ， 为tmbb tmbb 12 未知参数。显然，当 时， 变成 ，这就是通常的线性规划021),(21lp)0,(l 问题。 对于 ，如果改变参数 的值，将引起全体价值系数的变化，如果改变参),(21lp1 数 的，将约束方程右端系数同时发生变化。我们来讨论随着 ， 取值的变化，最2 12 优解将发生什么变化 【10】 。 0),()(min2211xbalpz 21 4.2 两参数线性规划问题的求解方法 首先需要用分块矩阵将 的单纯形法进行简化。 为如下的线性规划：)0,(lp)0,(lpcxzmin 4-20),(balp 设 ，则矩阵形式为：)(,)( dbdbcxba 4-30,)( mindbdbbxbz 若 是最优基，则单纯形法的实施步骤可简化如下b 4-4 11111_00bdbddbbbbibibczczczcb 其中 i 为单位阵， 为非基变量 的检验数，它是非负的。由d1 _dx 得最终表 4-4 可以看出，最优解 。)0,(lp bbcz11*min,0 下面我们来讨论 的求解方法。同前一样， 的单纯形法可简化),(21lp),(21lp 如下： 112 2 11 112 11 ()()0()()(bdbdbbdbbibbcczcczi zb 22 ， 4-5 112_ 1()0dbibbczc 其中 同前所述， 。dc_1b 下面我们分四种情况来讨论： 情形 当 ，且 时， 与 有相同的最优基， _10d0)(21b),(21lp)0,( 其最优解为： ， *bx,min_1bcz 。 12()bb 情形 当 ，且 ，用单纯形法继续换基 _ 1120()0dcbb且 0)(21bb 即可。具体步骤如下： 1）求 的最终表 4-5、最优基 及 。),(lp1 4-6 bbczdi1_0 2） 在 4-5 的末行添加 ，末列添加 得到一个新的分),(1dbc12b 块矩阵 4-7 1211_1 )(bbczcbi bdb 对此矩阵试行行的初等变换即得 4-7。 3）对 4-7 施行单纯形法，继续换基就可得最优解、最优值。 情形 当 且 时，用对偶单纯形法继续换基即可。 _10dc0)(21bb 情形 当 且 时，这就需要引进人工变量，用大 法求 m 解。 4.3 两参数线性规划问题的分析与求解 讨论当 ， 时，下列参数线性规划问题的最优解：0152 23 21121 )()(),(minxxz0,5212x 解 将上述模型化为标准型 )5,21(0)1()(),(min524123 21ix xzi 1）求 的最终表)0,(lp 301205120210)(501252 zzz 由 的最终表可得),(lp2212 22121 6510010bbcb 2）由 的最终表可得如下：)0,(lp 21 263012005z 24 。 )210)(321020 511 2z 3）a当 且 即 ， ，21 5212 ， 。tx)0,0,(22* )0)(3min21z b.当 ， 时， ，用对偶单纯形法求解，分两种情况讨152 论： 当 时， ，此时以 为主元进行换基运算如下：301 112125a )210)(3210201 2z 。 212111 803502301 z 此时，最优解为 ，tx),5,(22* 。118minz 当 时， ，以 为主元换基运算如下：2312123a )210)(321020 51 2z 。 21211 74503201 z 此时，最优解为 ，tx),5,315(2* 25 。21217450minz c.当 ， 时， ，这时以 为主元进行换基运算如下：21213a )12(10(2102051 2z 此时，最优解为 ，tx),35,(* 。)(min12z d.当 ， 时， ， ，用大 法求解如下：2152002m )210)(3210201 51 2z 02120 51 2m 212111 27450232001 z 21211