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

文香丹

摘要：线性规划是运筹学中应用最广泛的方法之一，也是运筹学的最基本的方法之一。它是解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。最近十多年来，线性规划无论是在深度还是在广度方面又都取得了重大进展。简单线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简单线性规划问题求解的几种可能情况及解简单线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简单线性规划问题的图解法作一些探讨。

关键词：图解法；可行域；最优解

中图分类号：G642.4 文献标志码：A 文章编号：1674-9324（2014）39-0100-02

线性规划问题研究的是在一组线性约束条件下一个线性函数最优问题。简单线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简单线性规划问题求解的几种可能情况及解简单线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简单线性规划问题的图解法作一些探讨。简单线性规划问题求解的几种可能情况：（1）无可行解（可行域是空集）；（2）无界（可行域不空集，但目标函数在可行域上无界）；（3）最优解（可行域不空集，且目标函数有有限的最优值）。简单线性规划问题我们可以直观了解可行区域的结构，同时还可利用目标函数与可行区域的关系利用图解法求解该问题。图解法的步骤为：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。

一、无界

例1 用图解法解线性规划。

min z=-2x1+x2

s.t.x

+x

≥1

x

-3x

≥-3

x

≥0，x

≥0

解：该问题的可行区域如图1所示。

目标函数z=-2x1+x2沿着它的负法线方向（2，-1）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的等直线沿着它的负梯度方向（1，-1）T移动，函数值会减小，当移动到点A2=（1，4）T时，再继续移动就离开区域D了。于是点A2就是最优解，而最优值为z=1-4=-3。

可以看出，点0、A1、A2、A3、A4都是该线性规划问题可行域的顶点。

三、无穷多最优解

例3 如果将例2中的目标函数改为minz=4x1-2x2，可行区域不变，用图解法求解的过程如图3所示。

由于目标函数z=4x1-2x2的等值线与直线A1A2平行，当目标函数的等值线与直线A1A2重合（此时z=-4）时，目标函数达z=4x1-2x2到最小值-4，于是，线段A1A2上的每一个点均为该问题的最优解。特别地，线段A1A2的两个端点，即可行区域D的两个顶点A1=（0，2）T，A2=（1，4）T均是该线性规划问题的最优解。此时，最优解不唯一。

从图解法的几何直观容易得到下面几个重要结论：

1.线性规划的可行区域是若干个半平面的交集，它形成了一个多面凸集（也可能是空集）。

2.对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。在这种情况下还包含两种情况：有唯一解和有无穷多解。若有两个最优解，则其连线上的点都是最优解。

3.如果可行域无界，线性规划问题的目标函数可能有无界的情况。

参考文献：

[1]石卫东，王媛.例谈目标函数新视角[J].语数外学习，2013，（8）.

[2]兑松杰.构造向量巧解线性规划问题[J].中学数学高中版，2012，（7）.

[3]孙殿武.别样的线性规划问题更精彩[J].河北理科教学研究，2012，（2）.

[4]张香云.线性规划[M].浙江：浙江大学出版社，2013.endprint

摘要：线性规划是运筹学中应用最广泛的方法之一，也是运筹学的最基本的方法之一。它是解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。最近十多年来，线性规划无论是在深度还是在广度方面又都取得了重大进展。简单线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简单线性规划问题求解的几种可能情况及解简单线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简单线性规划问题的图解法作一些探讨。

关键词：图解法；可行域；最优解

中图分类号：G642.4 文献标志码：A 文章编号：1674-9324（2014）39-0100-02

线性规划问题研究的是在一组线性约束条件下一个线性函数最优问题。简单线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简单线性规划问题求解的几种可能情况及解简单线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简单线性规划问题的图解法作一些探讨。简单线性规划问题求解的几种可能情况：（1）无可行解（可行域是空集）；（2）无界（可行域不空集，但目标函数在可行域上无界）；（3）最优解（可行域不空集，且目标函数有有限的最优值）。简单线性规划问题我们可以直观了解可行区域的结构，同时还可利用目标函数与可行区域的关系利用图解法求解该问题。图解法的步骤为：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。

一、无界

例1 用图解法解线性规划。

min z=-2x1+x2

s.t.x

+x

≥1

x

-3x

≥-3

x

≥0，x

≥0

解：该问题的可行区域如图1所示。

目标函数z=-2x1+x2沿着它的负法线方向（2，-1）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的等直线沿着它的负梯度方向（1，-1）T移动，函数值会减小，当移动到点A2=（1，4）T时，再继续移动就离开区域D了。于是点A2就是最优解，而最优值为z=1-4=-3。

可以看出，点0、A1、A2、A3、A4都是该线性规划问题可行域的顶点。

三、无穷多最优解

例3 如果将例2中的目标函数改为minz=4x1-2x2，可行区域不变，用图解法求解的过程如图3所示。

由于目标函数z=4x1-2x2的等值线与直线A1A2平行，当目标函数的等值线与直线A1A2重合（此时z=-4）时，目标函数达z=4x1-2x2到最小值-4，于是，线段A1A2上的每一个点均为该问题的最优解。特别地，线段A1A2的两个端点，即可行区域D的两个顶点A1=（0，2）T，A2=（1，4）T均是该线性规划问题的最优解。此时，最优解不唯一。

从图解法的几何直观容易得到下面几个重要结论：

1.线性规划的可行区域是若干个半平面的交集，它形成了一个多面凸集（也可能是空集）。

2.对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。在这种情况下还包含两种情况：有唯一解和有无穷多解。若有两个最优解，则其连线上的点都是最优解。

3.如果可行域无界，线性规划问题的目标函数可能有无界的情况。

参考文献：

[1]石卫东，王媛.例谈目标函数新视角[J].语数外学习，2013，（8）.

[2]兑松杰.构造向量巧解线性规划问题[J].中学数学高中版，2012，（7）.

[3]孙殿武.别样的线性规划问题更精彩[J].河北理科教学研究，2012，（2）.

[4]张香云.线性规划[M].浙江：浙江大学出版社，2013.endprint

摘要：线性规划是运筹学中应用最广泛的方法之一，也是运筹学的最基本的方法之一。它是解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。最近十多年来，线性规划无论是在深度还是在广度方面又都取得了重大进展。简单线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简单线性规划问题求解的几种可能情况及解简单线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简单线性规划问题的图解法作一些探讨。

关键词：图解法；可行域；最优解

中图分类号：G642.4 文献标志码：A 文章编号：1674-9324（2014）39-0100-02

线性规划问题研究的是在一组线性约束条件下一个线性函数最优问题。简单线性规划指的是目标函数含两个变量的线性规划。本文主要介绍简单线性规划问题求解的几种可能情况及解简单线性规划问题的基本方法即图解法的基本思想和算法步骤，并通过例子对解简单线性规划问题的图解法作一些探讨。简单线性规划问题求解的几种可能情况：（1）无可行解（可行域是空集）；（2）无界（可行域不空集，但目标函数在可行域上无界）；（3）最优解（可行域不空集，且目标函数有有限的最优值）。简单线性规划问题我们可以直观了解可行区域的结构，同时还可利用目标函数与可行区域的关系利用图解法求解该问题。图解法的步骤为：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。

一、无界

例1 用图解法解线性规划。

min z=-2x1+x2

s.t.x

+x

≥1

x

-3x

≥-3

x

≥0，x

≥0

解：该问题的可行区域如图1所示。

目标函数z=-2x1+x2沿着它的负法线方向（2，-1）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的等直线沿着它的负梯度方向（1，-1）T移动，函数值会减小，当移动到点A2=（1，4）T时，再继续移动就离开区域D了。于是点A2就是最优解，而最优值为z=1-4=-3。

可以看出，点0、A1、A2、A3、A4都是该线性规划问题可行域的顶点。

三、无穷多最优解

例3 如果将例2中的目标函数改为minz=4x1-2x2，可行区域不变，用图解法求解的过程如图3所示。

由于目标函数z=4x1-2x2的等值线与直线A1A2平行，当目标函数的等值线与直线A1A2重合（此时z=-4）时，目标函数达z=4x1-2x2到最小值-4，于是，线段A1A2上的每一个点均为该问题的最优解。特别地，线段A1A2的两个端点，即可行区域D的两个顶点A1=（0，2）T，A2=（1，4）T均是该线性规划问题的最优解。此时，最优解不唯一。

从图解法的几何直观容易得到下面几个重要结论：

1.线性规划的可行区域是若干个半平面的交集，它形成了一个多面凸集（也可能是空集）。

2.对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。在这种情况下还包含两种情况：有唯一解和有无穷多解。若有两个最优解，则其连线上的点都是最优解。

3.如果可行域无界，线性规划问题的目标函数可能有无界的情况。

参考文献：

[1]石卫东，王媛.例谈目标函数新视角[J].语数外学习，2013，（8）.

[2]兑松杰.构造向量巧解线性规划问题[J].中学数学高中版，2012，（7）.

[3]孙殿武.别样的线性规划问题更精彩[J].河北理科教学研究，2012，（2）.

[4]张香云.线性规划[M].浙江：浙江大学出版社，2013.endprint