2022年运筹学--线性规划问题最优解的确定与改进.docx
精选学习资料 - - - - - - - - - 线性规划问题最优解的确定与改良线性规划是运筹学的一个重要分支；自1947 年丹捷格 G.B.Dantzig提出了一般线性规划问题求解的方法单纯形法之后,线性规划在理论上趋向成熟,在有用中日益广泛与深化；线性规划最优解求解问题,在运筹学本科版给出了图解法和单纯形法；一般线性规划问题的标准型为：满意约束条件maxznc x jj1,2m,xnT14i11 5na x i j jb i,ij1n1 6xj0,j1,2,1-5 式、1-6 式的解Xx x 2,称为线性规划问题的可行解,其中使目标函数到达最大值的可行解称为最优解；2022 年中国科教创新导刊,第三十期李高秀写的线性规划中最优解的精确确定中具体介绍了图解法的过程,图解法适合于二元线性规划问题,对于多元线性规划问题图解法相对较难；图解法过程：1 线性目标函数最值的分析对于线性目标函数Z=ax+by ,假设b 0 时,目标函数可变为yaxz,就是直线bbyaxz在 y 轴上的截距；bby 轴上的 1b>0时,随着直线yaxz的平移,直线在与可行域有公共点的条件下,它在bb截距z b最大时 z 最大；当z b最小时 z 最小；y 轴上的 2b<0时,随着直线yaxz的平移,直线在与可行域有公共点的条件下,它在bb截距z 最大时 z 最小；当z 最小时 z 最大；b b由以上两点可知,要求线性目标函数 z=ax+by 的最大最小值要留意在 y 轴上的截距；y 的系数 b 的正负和平移直线2 在图上分别作出约束函数和目标函数,平移目标函数线到可行域的交点时,要把目标函数的斜 率与相交于这一点的直线的斜率进行比较名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - - - - - - 上述的最值分析是确定平移目标函数的大致方向,而这次是确定最优解的确凿位置；斜率比较大小的目的是直观形象的比较两直线的方向和倾斜程度；具体的做法是：1 假设目标函数的斜率是正 或负 的,只需要与斜率为正 或负 的直线进行比较,即与斜率同号的比较；2 比较斜率的肯定值,肯定值越大所对应的直线的倾斜程度越大,从直观来看直线越陡；依据上述的 1 和 2,可精确的确定最优解的位置单纯形法：单纯形法的一般解题步骤可归纳如下： 线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解； 假设基本可行解不存在,即约束条件有冲突,就问题无解； 假设基本可行解存在,从初始基本可行解作为起点,依据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解；按步骤3 进行迭代 , 直到对应检验数满意最优性条件这时目标函数值不能再改善,即得到问题的最优解； 假设迭代过程中发觉问题的目标函数值无界,就终止迭代；2006 年甘肃联合高校学报 自然科学版 第三期,在熊洪斌发表的论文线性规划最优解的进一步讨论中讨论了线性规划最优解的参数表示,通过对某一最优解引入参数向量,得到新的 LPP模型通过求解 LPP模型便可得到 LP 最优解的参数表达式；人们在求解 LP 问题经常用单纯形方法求出一组最优解便终止这样的思想和方法有时是不行取的由于方案的单一性不便于决策者在短期内依据条件的变化进行敏捷调整,从而使原有期望不变用参数向量表示最优解,便可实现这一目的；LLP方法介绍如下：1 定义与引理定义 1 区间向量：假设一向量的每个重量均为一区间数,就称该向量为区间向量一般向量也是区间向量的一种特别形式；引理 1 假设 LP 问题 mincxst Axb,x0有最优解*x ；就*xx为原 LP 问题最优解的充要条件是：c0,A x0,x*0,其中cc c 2,c nx x2,x nT,x*x*1,x*2,x*nT,Aa ijm n,bb b 2,b mT,00,0,0T1,m1,2,nT；2 LPP 模型的建立考虑标准型LP 问题： mincx st Axb ,x0；设其某一最优解*x ,就有与之对应的LPP模型：mincx0,A0,x*0；由引理 1 和 LP 理论有以下定理：名师归纳总结 定理 1 设N为 LP 问题非基变量的判别数集N 为非基变量下标集 就第 2 页,共 5 页1 jN,j0为零向量问题有惟一最优解- - - - - - -精选学习资料 - - - - - - - - - 2 jN,j0为区间向量LP有无穷组最优解；含义：为零向量,说明决策者挑选方案惟一；为区间向量,说明决策者可随时依据条件变化调整既定方案,使原有期望不变；3 ILPP 模型的建立考虑ILP0问题： mincxst Axb , xZ ,x0z为整数 ,就与之对应的ILPP 模型为minc, . st A .0,x*0,Z ；对 ILPP 模型,有以下定理：定理 2：1jjN,jj00为零向量lLP 问题有惟一最优解2 N为区间向量lLP 有多重最优解4 数值求解问题：现有一投资商对 A、B 两项产品投资,其投资利润及相关条件如下表：A 产品 B 产品 数量 情形变化 情形变化12利润 1 千元 / 件 1 千元 / 件机器 2 1 6 2 台故障 1 台故障人员 4 5 2 0 人请假 1 人请假问：该投资商在正常情形下如何支配生产,利润最大 .条件变化又该如何支配生产 A、B 产品数量需整数 . 解 依据题意,可得以下模型：max z x 1 x 1x ,x 分别是 A、B 的生产数量 2 x 1 x 2 6; ILP st 4 x 1 5 x 2 20;x i 0, i 1,2.本文用割平面法解上述 ILP ,就上述 ILP 问题对应的 LP 松驰问题为：max z x 1 x 2 .2 x 1 x 2 x 3 6; LP s t 4 x 1 5 x 2 x 4 20;x i 0, i 1,2,3,4.LP单纯性表如下：表一1xx2x34x名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - minz 0 1 1 0 0 基3x6 2 1 1 0 4x20 4 5 0 1 对表一单纯选得最优表二表二minz -13/5 1xx23xx41s0 0 -1/6 -1/6 0 基3x5/3 1 0 212/3 x ,将-1/6 0 4x8/3 0 1 -2/3 1/3 0 1s-2/3 0 0 -1/3 -1/3 1 由表二中的1x 为源行,可得割平面方程：s 1x 31 31s 置于尾行并作为基；33对表二对偶单纯选代得最优表三表三minz -4 1xx23xx41s0 0 0 0 -1/2 基名师归纳总结 3x2 1 0 5/6 0 ILPP ：-1/2 第 4 页,共 5 页4x2 0 1 -1 0 1 1s2 0 0 1 1 -3 于是得 ILP 的一组最优解x 12,x 22, maxz4；为了考察情形变化是否直接影响投资者利益,我们有必要考虑如下模型- - - - - - -精选学习资料 - - - - - - - - - min120.21230;141,0; 2,0,1Z.0;s t . .4152412,22,30,iZ i1, 2,3, 4.1, 31通过求解 ILPP 问题,可得 ILP 的最优解可表示为：21,2由 ILP 最优解的参数表达式可知：在正常状况下,投资者有三种方案可供挑选,分别为：方案一10,x 12,x22.方案二11,x 11,x 23.方案三12,x 10,x 24.依据情形变化 1 ,投资者只可挑选方案三；依据情形变化 2 ,投资者只可挑选方案二；通过 LP和 ILP 模型的转换求出其最优解集,可让决策者更好地对其可利用资源进行更合理的安排,获得最正确利润,而不像单纯性表法只有一组最优解,一次 LP 和 ILP 模型有其优越性,可以用于解决最优化问题；【参考文献】 ：名师归纳总结 1 薛声家,刘惠一般形式线性规划最优解集的确定M 广州：暨南高校出版社,2001.2 第 5 页,共 5 页2熊洪斌 . 线性规划最优解的进一步讨论M. 甘肃：甘肃联合高校学报编辑部,2006.6 3 李高秀 . 线性规划中最优解的精确确定M. 北京：中国科学技术信息讨论所ISTIC 科学技术文献出版社,2022- - - - - - -
