运筹学--线性规划问题最优解的确定与改进.pdf
线性规划问题最优解确实定与改良线性规划问题最优解确实定与改良线性规划是运筹学的一个重要分支。自 1947 年丹捷格G.B.Dantzig提出了一般线性规划问题求解的方法单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划最优解求解问题，在运筹学本科版给出了图解法和单纯形法。一般线性规划问题的标准型为：max z cjxji1n(14)aijxjbi,i1,2j1xj0,j1,2, nnm(1 5)(1 6)满足约束条件1-5式、 1-6式的解X (x1,x2,xn)T，称为线性规划问题的可行解，其中使目标函数到达最大值的可行解称为最优解。2009 年中国科教创新导刊，第三十期李高秀写的线性规划中最优解的准确确定中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。图解法过程：图解法过程：1 线性目标函数最值的分析对于线性目标函数Z=ax+by ，假设b0 时，目标函数可变为y azx，则是直线bbazy x在 y 轴上的截距。bbaz (1)b0 时，随着直线y x的平移，直线在与可行域有公共点的条件下，它在 y 轴上的bbzz截距最大时 z 最大；当最小时 z 最小。bbaz (2)b0 时，随着直线y x的平移，直线在与可行域有公共点的条件下，它在 y 轴上的bbzz截距最大时 z 最小；当最小时 z 最大。bb由以上两点可知，要求线性目标函数 z=ax+by 的最大最小值要注意 y 的系数 b 的正负和平移直线在 y 轴上的截距。2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解确实凿位置。斜率比较大小的目的是直观形象的比较两直线的方向和倾斜程度。具体的做法是：(1)假设目标函数的斜率是正(或负)的，只需要与斜率为正(或负)的直线进行比较， 即与斜率同号的比较。(2)比较斜率的绝对值，绝对值越大所对应的直线的倾斜程度越大，从直观来看直线越陡。根据上述的 1 和 2，可准确确实定最优解的位置单纯形法：单纯形法：单纯形法的一般解题步骤可归纳如下： 线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 假设基本可行解不存在，即约束条件有矛盾，则问题无解。 假设基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。 按步骤 3 进行迭代,直到对应检验数满足最优性条件这时目标函数值不能再改善 ，即得到问题的最优解。 假设迭代过程中发现问题的目标函数值无界，则终止迭代。2006 年甘肃联合大学学报(自然科学版)第三期，在熊洪斌发表的论文线性规划最优解的进一步研究 中研究了线性规划最优解的参数表示， 通过对某一最优解引入参数向量， 得到新的 LPP 模型 通过求解 LPP 模型便可得到 LP 最优解的参数表达式。人们在求解 LP 问题时常用单纯形方法求出一组最优解便终止这样的思想和方法有时是不可取的因为方案的单一性不便于决策者在短期内根据条件的变化进行灵活调整，从而使原有期望不变用参数向量表示最优解，便可实现这一目的。LLPLLP 方法介绍如下：方法介绍如下：1 1 定义与引理定义与引理定义 1 区间向量：假设一向量的每个分量均为一区间数，则称该向量为区间向量普通向量也是区间向量的一种特殊形式。引理 1 假设 LP 问题mincx.s. t Ax b，x 0有最优解x*。则x*为原 LP 问题最优解的充要条件是：c0，A x 0，x* 0，其中c (c1,c2,cn)x (x1,x2,bm)T，,xn)T，,0)T，m1x* (x*1,x*2,x*n)T，A (aij)mn，b (b1,b2,0 (0,0, (1,2,n)T。2 LPP2 LPP 模型的建立模型的建立考虑标准型 LP 问题：mincx.s. t Ax b，x 0。设其某一最优解x，则有与之对应的LPP 模型：*mincx 0, A 0, x* 0。由引理 1 和 LP 理论有以下定理：定理 1 设N为 LP 问题非基变量的判别数集(N 为非基变量下标集)则(1)j N,j 0 为零向量问题有惟一最优解(2)j N,j 0 为区间向量LP 有无穷组最优解。含义：为零向量，说明决策者选择方案惟一。为区间向量，说明决策者可随时根据条件变化调整既定方案，使原有期望不变。3 ILPP3 ILPP 模型的建立模型的建立考虑 ILP 问题：mincx.s. t Ax b，xZ，x 0(z 为整数)，则与之对应的ILPP 模型为minc0，s. t A.0，x* 0，Z。对 ILPP 模型，有以下定理：定理 2：(1j N,j 0 为零向量lLP 问题有惟一最优解(2)j N,j 0 为区间向量lLP 有多重最优解4 4 数值求解数值求解问题：现有一投资商对 A、B 两项产品投资，其投资利润及相关条件如下表：利润机器人员A 产品1 千元/件24B 产品1 千元/件15数量62情况变化12 台故障0 人请假情况变化21 台故障1 人请假问：该投资商在正常情况下如何安排生产，利润最大?条件变化又该如何安排生产(A、B 产品数量需整数)?解 根据题意，可得以下模型：max z x1 x2 (x1，x2分别是 A、B 的生产数量) 2x1 x2 6;(ILP)s. t4x15x2 20;x 0,i 1,2.i本文用割平面法解上述(ILP)，则上述(ILP)问题对应的 LP 松驰问题为：maxz x1 x2. 2x1 x2 x3 6;(LP)s. t4x15x2 x4 20;x 0,i 1,2,3,4.iLP 单纯性表如下：表一x1x2x3x4min(z)基01100 x3x4表二62024151001对表一单纯选得最优表二x10 x20 x3-1/6x4-1/6s10-13/5min(z)基5/38/3-2/31000102/3-2/3-1/3-1/61/3-1/3001x3x4s1由表二中的x1为源行，可得割平面方程：s1 对表二对偶单纯选代得最优表三表三-4211x3x4，将s1置于尾行并作为基。333x30 x10 x20 x40s1-1/2min(z)基2221000105/6-11001-1/21-3x3x4s1于是得 ILP 的一组最优解x1 2，x2 2，maxz 4。为了考察情况变化是否直接影响投资者利益，我们有必要考虑如下模型ILPP：min(12) 0.2123 0;s.t.41 524 0; 2, 2, 0, 0;2341,i Z ,i 1, 2,3, 4.(2 1,21,1,31),12,0,1Z.通过求解 ILPP 问题， 可得 ILP 的最优解可表示为：由 ILP 最优解的参数表达式可知：在正常状况下，投资者有三种方案可供选择，分别为：方案一1 0,x1 2,x2 2.方案二1 1,x11,x2 3.方案三1 2,x1 0,x2 4.根据情况变化(1)，投资者只可选择方案三；根据情况变化(2)，投资者只可选择方案二。通过LP和ILP模型的转换求出其最优解集， 可让决策者更好地对其可利用资源进行更合理的分配，获得最正确利润，而不像单纯性表法只有一组最优解，一次LP 和 ILP 模型有其优越性，可以用于解决最优化问题。【参考文献】 ：1薛声家，刘 惠一般形式线性规划最优解集确实定M广州：暨南大学出版社，2001.22 熊洪斌. 线性规划最优解的进一步研究M. 甘肃：甘肃联合大学学报编辑部，2006.63李高秀. 线性规划中最优解的准确确定M.北京：中国科学技术信息研究所ISTIC 科学技术文献出版社，2009
