任务二图解法求解线性规划问题.pdf

任务二图解法求解线性规划问题

情境导入：

我们上一个任务成功的将一个实际问题转化为数学语言，用数学模型表达了出来，但

是该问题到底该怎么解决呢？我们又该如何对该数学模型进行求解呢？

任务：掌握图解法求解两个决策变量的线性规划问题的思路，了解线性规划问题解的性质

任务引入：

现在我们要想办法求解例1的数学模型

MaxZ=2x+3x

12

x2x8

12

s.t.4x116

4x12

2

xx0

12

一、任务分析

图解法是指求解仅含两个变量的线性规划问题的一种方法。是求解线性规划的一种几

何解法。只含两个变量的线性规划问题，由约束条件确定的可行域可以在二维平面上表示

出来，按照一定规则，在可行域上移动目标函数的等值线，从而得到线性规划问题的最优

解。这里的可行域是凸区域，最优解必在可行域的某个顶点上达到。[1]

图解法仅适用于仅含有两个变量的线性规划问题的求解，因而图解法的实际用途并不

广泛。针对线性规划几何解还有一些重要的性质，这里不加证明叙述如下：

1.若线性规划可行域非空，则可行域必定是一个凸集，即集合中任意两点连线上的一

切点仍然在该集合巾，这样的凸集表现为一个凸多边形，在空间上为一个凸几何体。

2.若线性规划优解存在，则最优解或最优解之一肯定能够在可行域（凸集）的某个极

点找到。

3.线性规划的可行域若有界，则一定有最优解。

4.线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无有限最优解、无可

行解。

以上结论是非常有用的，特别是结论2非常明确地告诉我们，线性规划的最优解不可能

在可行域的内点取得，而只能在凸集的某一个顶点(特殊情况为在凸集的某一条边界上)上

达到。因此，求解线性规划问题可转化为如何在可行域的顶点上求出使目标函数值达到最

优的点的问题。由于可行域的顶点个数是有限的，因此在求解线性规划模型的最优解时，

只要在可行域的有限个顶点范围内一一寻找即可，这样就极大地降低了线性规划问题的复

杂程度，将减少大量的工作。

通过图解法直观的画图表现形式，也能让我们对线性规划解的进行更加理解。

二、基本理论

（一）解的基本概念

通过上面的描述，我们对线性规划问题的解有如下理解，从线性代数角度来说，接分

为可行解和最优解。

可行解：凡满足约束条件和非负条件的决策变量的取值x(x,x,,x)T称为线性

12n

规划可行解。所有可行解的集合称为线性规划的可行域。

最优解：使目标函数达到最优值的可行解称为线性规划的最优解

****T

X(x,x,,x)。

12n

（二）图解法基本步骤

在