9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 工学 >>

第二章2[1].2.1 线性规划问题的图解法_图文

第二章2[1].2.1  线性规划问题的图解法_图文

一、 线性规划的图解法

---解的几何表示

1.什麽是图解法?
线性规划的图解法就是用几何作图 的方法分析并求出其最优解的过程。 求解的思路是:先将约束条件加以 图解,求得满足约束条件和非负条件的 解的集合(即可行域),然后结合目标 函数的要求从可行域中找出最优解。

2. 图解法举例 例2-1 max Z ? 2 x1 ? 3x2 ? x1 ? 2 x2 ≤ 8 ?4 x ≤ 16 ? 1 ? ?4 x2 ≤ 12 ? x1 , x2 ≥ 0 ? 实施图解法,以求出最优生产计 划(最优解), 给出最优值。

由于线性规划模型中只有两个决策 变量,因此只需建立平面直角坐标系就 可以进行图解了。
第一步:建立平面直角坐标系 标出坐标原点, 坐标轴的指向和单位 长度。用x1轴表示产品A的产量,用x2 轴表示产品B的产量。 第二步:对约束条件加以图解。 第三步:画出目标函数等值线,结合目标函数 的要求求出最优解:最优生产方案。

第四步:最优解带入目标函数,得出最优值。

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

?

怎麽确定 半平面

以第一个约束条件: x1 ? 2 x2 ≤ 8 为例, 说明图解过程。

x1 ? 2 x2 ≤ 8 代表一个半平面
其边界: x1+2 x2 =8
x2

x1+2 x2 =8 及x1,x2 ≥0 △ AOB 点A、B 连线AB △A0B

B
Q4

3 2 1

x1 ? 2x2 ? 8
A
1 2 x1

0

3

4

5

6

7

8

经济含义 ?

点A(8,0):
全部的设备都用来生产Ⅰ产品而不生产Ⅱ 产品,那么Ⅰ产品的最大可能产量为8台,计 算过程为: x1+2×0?8 ?x1?8

连接AB:
设备全部占用所生产 Ⅰ、Ⅱ数量对应的点 的集合。
x
2
Q4

B
x1 ? 2x2 ? 8

3 2 1

△A0 B:
设备没有全部占用所 生产Ⅰ、Ⅱ数量对应 的点的集合。

A
1 2 3 4 5 6 7 8

x
1

0

另两个约束条件的 边界直线CD、EF: 4x1≤16,4 x2 ≤12

x2

B
E

4x1 ? 16
F
C

3 2 1

4 x2 ? 12

x1 ? 2x2 ? 8
D

A

x1

约束条件及 0 1 2 3 4 5 6 7 8 非负条件x1,x2 ?0 代表的公共部分--图中阴影区,就是满足所 有约束条件和非负条件的点的集合,即可行域。 在这个区域中的每一个点都对应着一个可行的 生产方案。

令 Z=2x1+3x2=c, 其中c为任选的一个常 数,在图 中画出直线 2x1+3x2=c, 即对应着 一个可行的生产结果,即使两种产品的总利润 达到c。 这样的直线有无数条,且相互平行,称 这样的直线为目标函数等值线。只要画两条 目标函数等值线,如令 x2
B

4x1 ? 16
C

c=0和c=6,可看出目
3

E F

标函数值变化的方向,
2

4 x2 ? 12 最优点

即虚线 l1和l2,箭头为产 品的总利润递增的方向。

x1 ? 2x2 ? 8
D

1

A
5 6 7 8

x1

0

1

2

3

4

x2
3 2 1

B
E F

4x1 ? 16
C

4 x2 ? 12 最优点

x1 ? 2x2 ? 8
D

A
5 6 7 8

x1

0

1

2

3

4

? 沿着箭头方向平移目标函数等值线,达到可 行域中的最远点E, E点就是最优点;

? 对应坐标x1=4, x2=2 是最佳的产品组合, [4,2]T 就是线性规划模型的最优解
? 使产品的总利润达到最大值 maxZ=2?4+3?2=14就是目标函数最优值。

尽管最优点的对应坐标可以直接从图中 给出,但是在大多数情况下,对实际问题精 确地看出一个解答是比较困难的。所以,通 常总是用解联立方程的方法求出最优解的精 确值。 比如C点对应的坐标值我们可以通过求 解下面的联立方程,即求直线AB和CD的交 点来求得。 直线AB: x1+2x2=8 直线CD: 4x1=16

max Z ? 2 x1 ? 3x2
? x1 ? 2 x2 ≤ 8 ?4 x ≤ 16 ? 1 ? ?4 x2 ≤ 12 ? x1 , x2 ≥ 0 ?
x2

B
E F

4x1 ? 16

3

4 x2 ? 12
C

最优点

2

x1 ? 2x2 ? 8
D

1

A
5 6 7 8

x1

0

1

2

3

4

结果
有唯一最优解 可行域是一个非空有界区域

讨论

可行域有几种可能 ? 解有几种可能 ?

用图解法求解线性规划的各种可能的结果

唯一最优解
例2-3 将例2-1中目标要求改为极小化,
目标函数和约束条件均不变,则可行域与 例1-1相同,目标函数等值线也完全相同,

只是在求最优解时,应沿着与箭头相反的
方向平移目标函数等值线,求得的结果是 有唯一最优解x1=4,x2=2,对应着图2-6中 的坐标原点。

无穷多个最优解
max Z ? 2 x1 ? 3x2
x2

{c1,c2}

max Z ? x1 ? 2 x 2

? x1 ? 2 x2 ≤ 8 ?4 x ≤ 16 ? 1 ? ?4 x2 ≤ 12 ? x1 , x2 ≥ 0 ?

B
3

A
2 1

x1 ? 2 x2 ? 8
x1

0

1

2

3

4

5

6

7

8

沿着箭头的方向平移目标函数等值线, 发现平移的最终结果是目标函数等值线将 与可行域的一条边界线段AB重合。

结果表明,该线性规划有 无穷多个

最优解--线段AB上的所有点都是最优
点,它们都使目标函数取得相同的最大值 Zmax=14。

无界解
max Z ? x1 ? x2
??2 x1 ? x2 ≤ 4 ? ? x1 ? x2 ≤ 2 ?x , x ≥ 0 ? 1 2
x2

6

4

2

x1

0

1

2

3

4

5

如图中可行域是一个无界区域,如阴影区所示。 虚线为目表函数等值线,沿着箭头指的方向平移可 以使目标函数值无限制地增大,但是找不到最优解。 这种情况通常称为无“有限最优解” 或“最优

解无界”。
如果一个实际问题抽象成像例1-4这样的线性规 划模型,比如是一个生产计划问题,其经济含义就是 某些资源是无限的,产品的产量可以无限大。此时应 重新检查和修改模型,否则就没有实际意义。 注意,对于无界可行域的情况,也可能有唯一 最优解或无穷多个最优解。


网站首页 | 网站地图 | 学霸百科
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com