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

第1.2节 线性规划问题的图解法_图文

第1.2节 线性规划问题的图解法_图文

第1讲
1

线性规划:基本概念

第1.1节 ? 第1.2节 ? 第1.3节 ? 第1.4节
?

线性规划问题的基本概念 两变量线性规划问题的图解法 线性规划问题的EXCEL求解法 从更广泛的视角看线性规划问题

2

第1.2节 两变量线性规划问题的图解法
图解法的求解过程 ? 2 规划问题求解的几种可能结果 ? 3 由图解法得到的启示 ? 4 图解法总结
?1

3

1 图解法的求解过程
? 图解法简单直观,有助于了解线性规划问题

求解的基本原理,尤其适用于只含有两个决 策变量的线性规划问题。

4

【例】花瓶问题
一家公司生产带有花样图案的彩色玻璃花瓶。每一个 花瓶经过艺术玻璃吹风机从液态加工而成,然后进入 储藏室冷却至室温,花瓶有大和小两种尺寸,但是生 产过程几乎相当,而且使用同一种材料。 ? 不论尺寸,每一个花瓶都需要20分钟的艺术加工,每 周艺术加工工作时间为40小时; ? 大小花瓶每个各需彩色玻璃2 盎司和1盎司,每周可用 的玻璃为160盎司。 ? 一个小花瓶占用2个单位储存空间,大花瓶占用3个单 位储存空间,一共有260个单位储存空间。 ? 大小花瓶的利润贡献率分别为12元/个和10元/个。 ? 问题:应该怎样安排生产,才能使利润值最大?
?

5

【例】花瓶问题
表1 花瓶生产的材料、工时、存储空间和利润清单

工序 花瓶种类 大花瓶 小花瓶 每周可用能力

占用材料 (盎司) 2 1 160

艺术加工 (小时) 1/3 1/3 40

储存空间 (一单位) 3 2 260

利润值 (元) 12 10 —
6

〔数学建模〕:如果用 x1表示每周生产的大花 瓶数量, x2表示每周生产的小花瓶数量,那么:
max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? ? x1 ? x2 ? 40 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0
工序 花瓶种类 占用材料 (盎司) 艺术加工 (小时) 储存空间 (一单位) 利润值 (元)

大花瓶
小花瓶 每周可用能力

2
1 160

1/3
1/3 40

3
2 260

12
10 —
7

【例】花瓶问题
? 〔图解法求解〕:如果用

x1表示每周生产的 大花瓶数量, x2表示每周生产的小花瓶数量, 那么:
max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? ? x1 ? x2 ? 40 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0

x1 ? 20 * x 2 ? 100
* * z ? 1240

8

1 图解法的求解过程
? (1)画出平面直角坐标系。以一个变量作为

横坐标轴,另一个变量作为纵坐标轴,画出 平面直角坐标系,并适当选取单位坐标长度。 由于变量是非负的,所以画出坐标系的第一 象限即可。
max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? x ? x2 ? 40 ? 1 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0

9

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0
160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

x1
10

图解法的基本步骤:
? (2)找出可行域。作出各约束条件在坐标系

中所对应的直线,找出可行域(常用阴影区 域标识)。

max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? x ? x2 ? 40 ? 1 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0

11

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160

x1
12

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160

1/3x1+1/3x2=40

x1
13

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160

(40,80)

1/3x1+1/3x2=40

x1
14

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260

(40,80)

1/3x1+1/3x2=40

x1
15

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
16

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

三个约束条件所对应的直线以及两条坐标轴所围成的 公共区域称为可行域(Feasible Region)。可行域中 包含的点均为问题的可行解(Feasible Solutions)。
x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160 3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)
17

x1

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10

18

图解法的基本步骤:
? (3)作出目标函数。由于

z 是一个待求的目 标函数值,所以目标函数常用一组平行虚线表 示,离坐标原点越远的虚线表示的目标函数值 越大。
max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? x ? x2 ? 40 ? 1 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0

19

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
20

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

?

分析目标函数 12 x1 ? 10 x2 ? z , 在 x1 ? x 2 坐标平面上, 它可

6 表示为以 z 为参数、 ? 为斜率的一族平行线(在图中用虚 5
线表示) :

6 z x2 ? ? x1 ? 5 10
? 位于同一直线上的点,具有相同的目标函数值,因而称它为 “等值线” 。当 z 值由小变大时,直线 x2 ? ? ? 6 5? x1 ? z 10 沿着其法线方向向右上方移动。即,离原点越远的直线

x2 ? ? ? 6 5? x1 ? z 10 所对应的 z 值越大。因此,可通过沿
目标函数法线方向移动目标函数直线的方法寻找最优解。
21

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
22

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

图解法的基本步骤:
? (4)确定最优解。最优解是可行域中使目标

函数值达到最优的点,当目标函数直线由原点 开始沿法线方向向右上方移动时,z 值开始增 大,一直移到目标函数直线与可行域相切时为 止,切点即为最优解。
max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? x ? x2 ? 40 ? 1 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0

23

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
24

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

1 图解法的求解过程
? 图解法的基本步骤:
?(1)画出平面直角坐标系。 ?(2)找出可行域。 ?(3)作出目标函数。 ?(4)确定最优解。

25

?2
? ? ? ?

规划问题求解的几种可能结果
1)唯一解 2)无穷多最优解 3)无界解 4)无解或者无可行解

26

2 规划问题求解的几种可能结果
? 1)唯一解

max z ? 12 x1 ? 10 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? ? x1 ? x2 ? 40 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0

x1 ? 20 * x 2 ? 100
* * z ? 1240

27

2 规划问题求解的几种可能结果
? 2)无穷多最优解

max z ? 12 x1 ? 8 x2 ? 2 x1 ? x2 ? 160 ?1 1 ? ? x1 ? x2 ? 40 3 ?3 ?3 x1 ? 2 x2 ? 260 ? ? ? x1 , x2 ? 0
28

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
29

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

2 规划问题求解的几种可能结果
? 3)无界解

?

可行域伸展到无穷,决策变量的取值没有限制, 产生无界解。
max z ? 12 x1 ? 8 x2 ? x2 ? a, 其中,a为常数 ? ? x1 , x2 ? 0

max z ? 12 x1 ? 8 x2 ? x1 ? a, 其中,a为常数 ? ? x1 , x2 ? 0

30

2 规划问题求解的几种可能结果
? 4)无解或者无可行解

?

可行域为空集,说明该问题无解。
max z ? 12 x1 ? 8 x2 ?2 x1 ? x2 ? 160 ?1 ? x1 ? 1 x2 ? 40 3 ?3 ?3 x ? 2 x ? 260 2 ? 1 ? x1 ? 13 ? ? x1 , x2 ? 0

31

3 由图解法得到的启示
?

求解含有两个决策变量的线性规划模型,用图解法 比较方便,但它不适用于含超过三个的多个决策变 量线性规划模型求解。

32

3 由图解法得到的启示
求解含有两个决策变量的线性规划模型,用图解法 比较方便,但它不适用于含超过三个的多个决策变 量线性规划模型求解。 ? 虽然如此,图解法的解题方法和几何意义对于求解 一般的线性规划问题仍有很大启发,使我们产生以 下推测:
?

33

3 由图解法得到的启示
?

虽然如此,图解法的解题方法和几何意义对于求解 一般的线性规划问题仍有很大启发,使我们产生以 下推测:
?

(1)线性规划问题解的情况可分以下四种,即:唯一最 优解、无穷多最优解、无界解和无可行解。

34

3 由图解法得到的启示
?

虽然如此,图解法的解题方法和几何意义对于求解 一般的线性规划问题仍有很大启发,使我们产生以 下推测:
?

(2)线性规划问题有解,那么可行域是凸集。〔当线性 规划问题的可行域非空时,它是有界或无界凸多边形。〕

35

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
36

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

3 由图解法得到的启示
?

虽然如此,图解法的解题方法和几何意义对于求解 一般的线性规划问题仍有很大启发,使我们产生以 下推测:
?

(3)如果线性规划问题存在最优解,那么唯一最优解一 定是可行域凸集的某个顶点,无穷多最优解一定是可行 域的某个边或某个面。〔若线性规划问题存在最优解, 它一定在有界可行域的某个顶点得到;若在两个顶点同 时得到最优解,则它们连线上的任意一点都是最优解, 即有无穷多最优解。〕

37

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
38

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

3 由图解法得到的启示
?

虽然如此,图解法的解题方法和几何意义对于求解 一般的线性规划问题仍有很大启发,使我们产生以 下推测:
?

(4)线性规划问题的一般求解思路:先找出凸集的任一 顶点,计算该点的目标函数值,对凸集所有顶点的目标 函数值进行比较,找出目标函数值最大的顶点即为问题 的最优解。

39

x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0

2x1+x2=160
3x1+2x2=260 (20,100) (40,80)

1/3x1+1/3x2=40 (60,40)

x1
40

160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法

3 由图解法得到的启示
?

虽然如此,图解法的解题方法和几何意义对于求解 一般的线性规划问题仍有很大启发,使我们产生以 下推测:
(1)线性规划问题解的情况可分以下四种,即:唯一最 优解、无穷多最优解、无界解和无可行解。 ? (2)线性规划问题有解,那么可行域是凸集。 ? (3)如果线性规划问题存在最优解,那么唯一最优解一 定是可行域凸集的某个顶点,无穷多最优解一定是可行 域的某个边或某个面。 ? (4)线性规划问题的一般求解思路:先找出凸集的任一 顶点,计算该点的目标函数值,对凸集所有顶点的目标 函数值进行比较,找出目标函数值最大的顶点即为问题 的最优解。
?

41

3 由图解法得到的启示
?

线性规划问题的一般求解思路:先找出凸集的任一 顶点,计算该点的目标函数值,对凸集所有顶点的 目标函数值进行比较,找出目标函数值最大的顶点 即为问题的最优解。

42

4 图解法总结










画出每个函数的约束边界线,用原点(或其它不在 约束边界线上的点)来确定直线的那一侧是约束条 件所允许的。 找出同时满足所有约束条件的可行域。 确定一条目标函数线的斜率,所有其他目标函数线 具有与之相同的斜率。 在可行域内向目标函数增加的方向移动直尺,在它 仍然穿过可行域的一个点时停止移动,这时直尺给 出的直线就是最优目标函数线。 最优目标函数线上的可行点是一个最优解。
43

44


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