运筹学 第2版 课件 1-2线性规划图解法与基本解的几何意义

PART02线性规划问题的图解法与解的性质线性规划问题的图解法（解的几何表示）1．什么是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解思路是：先将约束条件加以图解，求得满足约束条件的解的几何区域（可行域），然后结合目标函数的要求从可行域中找出最优解。

线性规划问题的图解法（解的几何表示）1．图解法举例

实施图解法，以求出最优生产计划（最优解）。线性规划问题的图解法（解的几何表示）由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解了

线性规划问题的图解法（解的几何表示）约束条件的图解：

每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。

?

怎么画边界

怎么确定半平面线性规划问题的图解法（解的几何表示）如果全部的劳动工时都用来生产A产品而不生产B产品，那么A产品的最大可能产量为3吨，计算过程为：

这个结果对应着右图中的点A(3,0)，同样我们可以找到B产品最大可能生产量对应的点B(0,3)。连接A、B两点得到约束：

所代表的半平面的边界:

即直线AB。线性规划问题的图解法（解的几何表示）第二个约束条件的边界---直线CD:

线性规划问题的图解法（解的几何表示）

线性规划问题的图解法（解的几何表示）

线性规划问题的图解法（解的几何表示）

线性规划问题的图解法（解的几何表示）0123456789x1

54321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

线性规划问题的图解法0123456789x1

321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

无穷多个最优解线性规划问题的图解法0123456789x1

321x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）

无穷多个最优解线性规划问题的图解法

唯一最优解0123456789x1x2x1（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）线性规划问题的图解法例1-3：无界解

线性规划问题的图解法本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解。这种情况通常称为无“有限最优解”或“最优解无界”。如果一个实际问题抽象成像例4这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。无界解

线性规划问题的图解法无界解和无可行解统称为无最优解产生无界解的原因是遗漏了约束条件。改变目标函数可能会使一个无界问题变成一个有界问题。(缺乏必要的约束条件)无可行解同目标函数无关，是因为约束条件太苛刻。（矛盾的约束条件）注释：线性规划问题的图解法综上，用图解法求解线性规划时，各种求解结果与各种类型的可行域之间的对应关系可以用下图加以描述：解的类型可行域类型唯一最优解非空有界无穷多最优解最优解无界（无“有限最优解”）无界无解（不存在可行域）空集线性规划问题的图解法注释线性规划问题的可行域非空时，它是有界或无界凸多变形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到。若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即无穷多最优解。线性规划问题的图解法

线性规划问题的图解法

线性规划问题的图解法图解法小结使用条件：仅有两个至多不超过三个决策变量的线性规划。基本步骤：第一步---建立平面直角坐标系；第二步---根据约束条件和非负条件画出可行域。第三步---作出目标函数等值线（至少两条），结合目标函数优化要求，平移目标函数等值线求出最优解。图解法的优缺点：简单、直观但有局限性。图解法求解线性规划图解法的局限性(1)图解法的优点:简单、直观;(2)局限性:对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法，大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解;(3)对含有三个以及三个以上决策变量的线性规划则应考虑使用更加有效的通用算法——单纯形法来进行求解。

线性规划问题的图解法用图解法求解以下的线性规划问题：课堂练习按小组分工完成：①画约束条件1,2；②画约束条件3并标明可行域；③画目标函数等值线；④说明如何得到最优解,算出相应的目标函数最优值。其他小组进行讲评。线性规划问题的图解法课堂练习(2,2)

12345x1X2

543210

C=2C=10线性规划问题的图解法

12345x1X2543210(2,2)

C=2C=10I(4,0)E(0,-2)H(6,4)G(0,4)F(-2,0)2.1基本可行解的几何意义1、讨论课堂练习

（1）如何求得基本解？

（2）观察图解法求解图，其中点I、H、G均在第一象限，它们是基本解，但不是基本可行解，这与基本可行解非负性有无矛盾？

基本可行解的几何意义

基本可行解的几何意义求解结果：H(6,4,-6,0,0)T,C(3,1,0,3,0)T,

B(2,2,0,0,2)T,D(2,0,2,4,0)T,

F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,

E(0,-2,6,6,0)T,A(0,1,3,0,3)T,

G(0,4,0,-8,6)T,O(0,0,4,2,2)T;基本可行解的几何意义2、结论：

(1)基本解对应所有可行域边界及其延长线、坐标轴之间的交点；

(2)基本可行解对应可行域的顶点。线性规划解的性质

线性规划解的性质

线性规划解的性质2、线性规划问题解的性质定理：

线性规划解的性质

X是D的一个顶点<=>X的正分量所对应的系数列向量线性无关线性规划解的性质

线性规划解的性质（2）定理1-2（反证法）

线性规划解的性质

线性规划解的性质（2）定理1-2（反证法）

线性规划解的性质定理1-3若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。

线性规划解的性质

线性规划解的性质

线性规划解的性质

线性规划解的性质课后讨论：（1）读懂证明，理清思路，写出从最罗嗦的证明过渡到最简洁的证明过程（加上边注——段落大意）线性规划解的性质

LP