浅谈解简单线性规划问题的图解法.docx

浅谈解简单线性规划问题的图解法 摘要：线性规划是运筹学中应用最广泛的方法之一，也是运筹学的最基本的方法之一。它是解决稀缺资源最优安排的有效方法，使付出的费用最小或获得的收益最大。最近十多年来，线性规划无论是在深度还是在广度方面又都取得了重大进展。简洁线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简洁线性规划问题求解的几种可能状况及解简洁线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简洁线性规划问题的图解法作一些探讨。 关键词：图解法；可行域；最优解 中图分类号：G642.4 文献标记码：A 文章编号：1674-932439-0101-02 线性规划问题探讨的是在一组线性约束条件下一个线性函数最优问题。简洁线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简洁线性规划问题求解的几种可能状况及解简洁线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简洁线性规划问题的图解法作一些探讨。简洁线性规划问题求解的几种可能状况：无可行解；无界；最优解。简洁线性规划问题我们可以直观了解可行区域的结构，同时还可利用目标函数与可行区域的关系利用图解法求解该问题。图解法的步骤为：画出直角坐标系；依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；任取一目标函数值作一条目标函数线，依据目标函数类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。 一、无界 例1 用图解法解线性规划。 min z=-2x1+x2 s.t.x +x 1 x -3x -3 x 0，x 0 解：该问题的可行区域如图1所示。 目标函数z=-2x1+x2沿着它的负法线方向T移动，由于可行域D无界，因此，移动可以无限制下去，而目标函数值始终减小，所以该线性规划问题无有限最优解，即该问题无界。 二、唯一最优解 例2 求解线性规划。 min z=x1-x2 s.t.2x -x -2 x -2x 2 x +x 5 x 0，x 0 解：可行区域如图2所示。在区域0A1A2A3A40的内部及边界上的每一个点都是可行点，目标函数z=-x1+x2的等直线沿着它的负梯度方向T移动，函数值会减小，当移动到点A2=T时，再接着移动就离开区域D了。于是点A2就是最优解，而最优值为z=1-4=-3。 可以看出，点0、A1、A2、A3、A4都是该线性规划问题可行域的顶点。 三、无穷多最优解 例3 假如将例2中的目标函数改为minz=4x1-2x2，可行区域不变，用图解法求解的过程如图3所示。 由于目标函数z=4x1-2x2的等值线与直线A1A2平行，当目标函数的等值线与直线A1A2重合时，目标函数达z=4x1-2x2到最小值-4，于是，线段A1A2上的每一个点均为该问题的最优解。特殊地，线段A1A2的两个端点，即可行区域D的两个顶点A1=T，A2=T均是该线性规划问题的最优解。此时，最优解不唯一。 从图解法的几何直观简单得到下面几个重要结论： 1.线性规划的可行区域是若干个半平面的交集，它形成了一个多面凸集。 2.对于给定的线性规划问题，假如它有最优解，最优解总可以在可行域的某个顶点上达到。在这种状况下还包含两种状况：有唯一解和有无穷多解。若有两个最优解，则其连线上的点都是最优解。 3.假如可行域无界，线性规划问题的目标函数可能有无界的状况。 参考文献： 1石卫东，王媛.例谈目标函数新视角J.语数外学习，2022，. 2兑松杰.构造向量巧解线性规划问题J.中学数学中学版，2022，. 3孙殿武.别样的线性规划问题更精彩J.河北理科教学探讨，2022，. 4张香云.线性规划M.浙江：浙江高校出版社，2022. 第5页 共5页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页