2022年运筹学--线性规划问题最优解的确定与改进 .pdf

《2022年运筹学--线性规划问题最优解的确定与改进 .pdf》由会员分享，可在线阅读，更多相关《2022年运筹学--线性规划问题最优解的确定与改进 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划问题最优解确实定与改良线性规划是运筹学的一个重要分支。自1947 年丹捷格 G.B.Dantzig提出了一般线性规划问题求解的方法单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划最优解求解问题，在运筹学本科版给出了图解法和单纯形法。一般线性规划问题的标准型为：1max(14)njjizc x1,1,2(1 5)0,1,2,(1 6)ni jjijja xbimxjn满足约束条件1-5 式、 1-6 式的解12(,)TnXx xx，称为线性规划问题的可行解，其中使目标函数到达最大值的可行解称为最优解。2009 年中国科教创新导刊，第三十期李高秀写的线性规划中最优解

2、的准确确定中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。图解法过程：1 线性目标函数最值的分析对于线性目标函数Z=ax+by ，假设b 0 时，目标函数可变为azyxbb，则是直线azyxbb在 y 轴上的截距。 (1)b0时，随着直线azyxbb的平移，直线在与可行域有公共点的条件下，它在y 轴上的截距zb最大时 z 最大；当zb最小时 z 最小。 (2)b0时，随着直线azyxbb的平移，直线在与可行域有公共点的条件下，它在y 轴上的截距zb最大时 z 最小；当zb最小时 z 最大。由以上两点可知，要求线性目标函数z=ax+by 的最大最小值要

3、注意y 的系数 b 的正负和平移直线在 y 轴上的截距。2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 5 页上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解确实凿位置。斜率比较大小的目的是直观形象的比较两直线的方向和倾斜程度。具体的做法是：(1) 假设目标函数的斜率是正( 或负 ) 的，只需要与斜率为正( 或负 ) 的直线进行比较，即与斜率同号的比较。(2) 比较斜率的绝对值，绝对值越大所对应的直线的

4、倾斜程度越大，从直观来看直线越陡。根据上述的 1 和 2，可准确确实定最优解的位置单纯形法：单纯形法的一般解题步骤可归纳如下：线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。假设基本可行解不存在，即约束条件有矛盾，则问题无解。假设基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3 进行迭代 , 直到对应检验数满足最优性条件这时目标函数值不能再改善，即得到问题的最优解。假设迭代过程中发现问题的目标函数值无界，则终止迭代。2006 年甘肃联合大学学报( 自然科学版 ) 第三期，

5、在熊洪斌发表的论文线性规划最优解的进一步研究中研究了线性规划最优解的参数表示，通过对某一最优解引入参数向量，得到新的 LPP模型通过求解 LPP模型便可得到LP 最优解的参数表达式。人们在求解LP 问题时常用单纯形方法求出一组最优解便终止这样的思想和方法有时是不可取的因为方案的单一性不便于决策者在短期内根据条件的变化进行灵活调整，从而使原有期望不变用参数向量表示最优解，便可实现这一目的。LLP方法介绍如下：1 定义与引理定义 1 区间向量：假设一向量的每个分量均为一区间数，则称该向量为区间向量普通向量也是区间向量的一种特殊形式。引理 1 假设 LP 问题min. .cxst Axb，0 x有最

6、优解*x。则*x为原 LP 问题最优解的充要条件是：0c，0A x，*0 x，其中12(,)ncc cc12(,)Tnxx xx，*12(,)Tnxxxx，()ijm nAa，12(,)Tmbb bb，10(0,0,0)Tm，12(,)Tn。2 LPP 模型的建立考虑标准型LP问题：min. .cxst Axb，0 x。设其某一最优解*x，则有与之对应的LPP模型：*min0,0,0cxAx。由引理 1 和 LP理论有以下定理：定理 1 设N为 LP问题非基变量的判别数集(N 为非基变量下标集) 则(1) ,0jjN为零向量问题有惟一最优解精选学习资料 - - - - - - - - - 名师

7、归纳总结 - - - - - - -第 2 页，共 5 页(2) ,0jjN为区间向量LP有无穷组最优解。含义：为零向量，说明决策者选择方案惟一。为区间向量，说明决策者可随时根据条件变化调整既定方案，使原有期望不变。3 ILPP 模型的建立考虑ILP问题：min. .cxst Axb，xZ，0 x(z为整数 ) ，则与之对应的ILPP 模型为min0c，.0st A，*0 x，Z。对 ILPP 模型，有以下定理：定理 2：(1,0jjN为零向量lLP 问题有惟一最优解(2) ,0jjN为区间向量lLP 有多重最优解4 数值求解问题：现有一投资商对A、B两项产品投资，其投资利润及相关条件如下表：

8、A产品B产品数量情况变化1情况变化2利润1 千元 / 件1千元 / 件机器2 1 6 2 台故障1 台故障人员4 5 2 0 人请假1 人请假问：该投资商在正常情况下如何安排生产，利润最大?条件变化又该如何安排生产(A、B产品数量需整数 )? 解 根据题意，可得以下模型：12max zxx (1x，2x分别是 A、B的生产数量 ) 121226;() .4520;0,1,2.ixxILP stxxxi本文用割平面法解上述(ILP) ，则上述 (ILP) 问题对应的LP松驰问题为：12123124max.26;() .4520;0,1,2,3,4.izxxxxxLP stxxxxiLP单纯性表如

9、下：表一1x2x3x4x精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 5 页min()z基0 1 1 0 0 3x6 2 1 1 0 4x20 4 5 0 1 对表一单纯选得最优表二表二1x2x3x4x1smin()z基-13/5 0 0 -1/6 -1/6 0 3x5/3 1 0 2/3 -1/6 0 4x8/3 0 1 -2/3 1/3 0 1s-2/3 0 0 -1/3 -1/3 1 由表二中的1x为源行，可得割平面方程：134211333sxx，将1s置于尾行并作为基。对表二对偶单纯选代得最优表三表三1x2x3x4x1smin

10、()z基-4 0 0 0 0 -1/2 3x2 1 0 5/6 0 -1/2 4x2 0 1 -1 0 1 1s2 0 0 1 1 -3 于是得 ILP 的一组最优解12x，22x，max4z。为了考察情况变化是否直接影响投资者利益，我们有必要考虑如下模型ILPP：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 5 页121231241234min()0.20;. .450;2,2,0,0;,1, 2,3, 4.s tiZ i通过求解ILPP 问题，可得 ILP 的最优解可表示为：111111(2,2, 3), 2,0,.Z由 ILP

11、最优解的参数表达式可知：在正常状况下，投资者有三种方案可供选择，分别为：方案一1120,2,2.xx方案二1121,1,3.xx方案三1122,0,4.xx根据情况变化 (1) ，投资者只可选择方案三；根据情况变化 (2) ，投资者只可选择方案二。通过 LP和 ILP 模型的转换求出其最优解集，可让决策者更好地对其可利用资源进行更合理的分配，获得最正确利润，而不像单纯性表法只有一组最优解，一次LP和 ILP 模型有其优越性，可以用于解决最优化问题。【参考文献】 ：1 薛声家，刘惠一般形式线性规划最优解集确实定M 广州：暨南大学出版社，2001.2 2熊洪斌 . 线性规划最优解的进一步研究M. 甘肃：甘肃联合大学学报编辑部，2006.6 3 李高秀 . 线性规划中最优解的准确确定M. 北京：中国科学技术信息研究所ISTIC 科学技术文献出版社，2009精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 5 页