tceic.com
学霸学习网 这下你爽了
当前位置:首页 >> 数学 >>

3.5.2《简单线性规划》2_图文

Dingchangwen

一.复习 想一想:
线性约 5x+4y ≤ 束条件

已知实数 x,y满足下列条件: 转化 20
可行域

三个转化

y

Z的最大值为44
6. . 5 4. 3. 2. 1 . 最优解

2x+3y 线性目 标函数 x ≥0 Z=Ax+By

≤12转化
转化

? Z y?? x? ? B

线性约束 条件 一组平行线

12 20 M( , ) 7 7
可行域 .. .. . .. 1 2 3 4 5 6

y≥0

最优解

寻找平行线组 的纵截距 求z=9x+10y的最大值 . ?最值9x+10y=0
?
线性目标函数

x

四个步骤:
1、画 2、移 3、求 4、答

0

2x+3y=12 5x+4y=20

代数问题
(线性约束条件)

图解法

想一想(结论): 三个转化
线性约束条件

转化 转化

可行域

线性目标函数 Z=Ax+By

? Z y?? x? ? B

一组平行线

图 解 法

最优解

转化

四个步骤:

? 寻找平行线组的 最大(小)纵截距 ?

1。画(画可行域) 2。移(平移直线L 。寻找使纵截距取得最值时的点) 3。求(求出点的坐标,并转化为最优解) 4。答

例1:已知x、y满足

x -4y≤-3 3x+5y≤25 x≥1

,设z=ax+y (a>0), 若z

取得最大值时,对应点有无数个,求a 的值。

解:当直线 l :y =-ax+ z 与
直线重合时,有无数个点,使 函数值取得最大值,此时有: k l =kAC

y
3x+5y=25 x-4y=-3
C



4.4 ? 2 3 ? ? kAC= 1 ? 5 5

k l = -a ∴ -a
=?
3 5

3 5

A B



a=

o

x

x=1

3x +2y≤10 例2:满足线性约束条件 多少个整数解。

x+4y≤11 的可行域中共有 x>0 y>0
y
5
4 3 2 1

解:由题意得可行域如图:

由图知满足约束条件的 可行域中的整点为(1,1)、 (1,2)、(2,1)、(2,2)

故有四个整点可行解.

x +4y=11

0

1

2

3

3x +2y=10

4

5

x

实际应用
给定一定量的 人力.物力, 资金等资源
精打细算 最优方案 统筹安排

完成的任务量最大 经济效益最高
所耗的人力. 物力资源最小 获取最大的利润

给定一项任务
最佳方案

降低成本
六个步骤: 1、设
2、列 3、画

4、移

5、求

6、答

例4.某工厂现有两种大小不同规格的钢板可截成A、B、C三种规 格,每张钢板可同时截得三种规格的小钢板的块数如下表所示 :
钢板类型 规格类型

A规格
2
1

B规格
1 2

C规格
1 3

第一种钢板 x张

第二种钢板 y张

某顾客需要A,B,C三种规格的成品分别为15,18,27块,若你是经理, 问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。 解:设需截第一种钢板x张,第二种钢板y张,钢板总张数为Z,则

分 析 问 题 :

2x+y≥15, x+2y≥18, x+3y≥27, x≥0 y≥0
x, y ? N

求目标函数: z=x+y取最小值时的x,y

约束条件 : 15, 2x+y≥ x+2y≥18, x+3y≥27, x≥0, y≥0 (x, y ? N)

{

y 15

调整优解法

目标函数:z= x+y

10 B(3,9) C(4,8) 8 画可行域 6 A(3.6,7.8) x+y =0 4 作出直线L:x+y=0, 2 0 2 4 6 8
平移L找交点及交点坐标

2x+y=15

12

x+y=12 x+2y=18

18

27

x

x+3y=27

当直线L经过点A时z=x+y=11.4, 但它不是最优整数解 . 作直线x+y=12 1.满足哪些条件的解才是最优解 ? 解得交点B,C的坐标B(3,9)和C(4,8)

2.目标函数经过A(3.6,7.8)时Z的值是多少?

直线x+y=12经过的整点是 B(3,9)和C(4,8),它们是最优解 . 答(略) 你能否猜测一下 Z的最小值可能是多少 ?

3.最优解的几何意义是什么 (最优解可以转化为什么几何意义)?

例题分析

{

2x+y≥15, x+2y≥18, x+3y≥27, x≥0, x∈N y≥0 y∈N

y
15

调整优值法

作出一组平行直线z=x+y,

10 B(3,9) C(4,8) 目标函数z= x+y 8 A(18/5,39/5) 6 x+y =0 4 2 0 2 4 6 8

2x+y=15

12

x+y=12 x+2y=18
作直线x+y=12

18

27

x

x+3y=27

当直线经过点A时z=x+y=11.4, 但它不是最优整数解.

解得交点B,C的坐标B(3,9)和C(4,8)
直线x+y=12经过的整点是B(3,9)和C(4,8),它们是最优解. 答(略)

例题分析
2x+y≥15, x+2y≥18, x+3y≥27, x≥0, x∈N* y≥0 y∈N*

y
15 9
B(3,9)
C(4,8)

{

打网格线法

1.平移找解法:

目标函数z = x+y

A(18/5,39/5)

x+y =0

2 1 0 12

78
2x+y=15

18

作出一组平行直线z = x+y, 当直线经过点A时z=x+y=11.4,但它不是最优整数解,

x+2y=18 x+3y=27

27

x

在可行域内打出网格线, 将直线x+y=11.4继续向上平移,
经过可行域内的整点B(3,9)和C(4,8)时,z=x+y=12是最优解. 答:(略)

2. 特值验证法: 法2(特值验证法): 由法1知目标函数取得最小值的整点应分布在 可行域的左下侧靠近边界的整点,依次取满足 条件的整点A0(0,15),A1(1,13),A2 (2,11),A3(3,9),A4(4,8),…,A27 (27,0),将这些点的坐标分别z=x+y,经检 验可知在整点A3(3,9),A4(4,8)处z最小。 其解题思路:找整点,验证算,选优解

3.调整优解法:

法3:根据非整点最优解 可知,当x, y都是整数时,z ? 12 . 令 x ? y ? 12 , 9 y ? 12 ? x ,代入约束条件整理可得: 3 ? x ? 2 所以 x ? 3 或 x ? 4 ,这样便知道了最优整点解.
这种寻求整点最优解的方法可简述为调整优值法, 即先求非整点最优解及最优值,再借助不定方程的 知识调整最优值,最后筛选出整点最优解.

39 57 18 , x ? 5 ,y ? 5 , z ? 5

结论
线性规划求最优整数解的一般方法: 1.平移找解法: 即先打网格,描出可行域内的
整点,平移直线,最先经过或最后经过的整点

坐标即为最优整解.

2. 特值验证法: 找整点,验证算,选优解 3.调整优解法: 即先求非整数条件下的最优解,
调整Z的值使不定方程Ax+By=Z存在最大(小)

的整点值,最后筛选出整点最优解.

巩固练习1:
不等式组

? x ? 0 表示的平面区域内的整数点共有 y ? ?y ? 0 4 ?4 x ? 3 y ? 12 ?
3 2



)个

1

0

1

2

3

4

x

4x+3y=12

练习2:求满足 | x | + | y | ≤4 的整点(横、 纵坐标为整数)的个数。
共有: 9+2(7+5+3+1)

= 41

?4 ? ?? ???? -4 ? ? ? ? ? ? ? ? ?o? ? ? ? ? ?? ???? ??? -4 ?

y

? ? ? 4 ? ? ? ? ? ?

x

3.某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物 资的任务,该公司有8辆载重量为6吨的A型卡车和4辆载重量为10 吨的B型卡车,有10名驾驶员;每辆卡车每天往返的次数为A型卡 车4次,B型卡车3次,每辆卡车每天往返的成本费A型卡车为320 元,B型卡车为504元,问如何安排车辆才能使该公司所花的成本 费最低,最低为多少元?(要求每型卡车至少安排一辆)

解:设每天调出的A型车x辆,
B型车y辆,公司所花的费用为 z元,则

y

4x+5y=30

x+y=10

x=8

{

x≤8 y≤4 x+y≤10 4x+5y≥30 x,y∈N* Z=320x+504y

4 3 2 1 0 1 2 3 4 5 6 7 8

y=4

X

画出可行域 作出可行域中的整点,

画直线l0:320x+504y=0,平移直线l0到l的位置,直线l过

可行域中的整点(8,0)时,Z=320x+504y取得最小值, 320x+504y=0 且Zmin=2608元

小结:
列表

实际问题
作 答

设出变量

寻找约束条件 建立目标函数

转化

线性规划问题
建模

最优解
调 整

四个步骤

图解法 目 标 函 数

三 个 转 化

平移找解法
常用方法

最优整数解

调整优值法

距离,斜率等

小结:

1。这节课,我们学习了把实际问题转化成线性 规划问题即建立数模的方法 , 以及求解整点最 优解的两种方法 .建模主要分清已知条件中 ,哪 些属于约束条件,哪些与目标函数有关. 2。求解整点最优解有两种方法: 平移求解法与调整优值法.前者主要依赖 作图后者主要依赖推理,但一般都应充 分利用非整点最优解及最优值.

课后练习:

1.在x,y的值都是不小于0的整数点(x,y)中,

15 满足x + y ≤ 4的点的个数为_______ 3 x ? 2 y ?10 2. 设变量x, y满足条件 x ? 4 y ?11
求S ? 5 x ? 4 y的 最 大 值 。

?

x , y?Z x ?0 , y ?0

3.深圳市福田区水泥制品厂生产两种水泥,已知生产甲种水 泥制品1吨,需矿石4吨,煤3吨;生产乙种水泥制品1吨,需 矿石5吨,煤10吨,每1吨甲种水泥制品的利润为7万元,每1 吨乙种水泥制品的利润是12万元,工厂在生产这两种水泥制 品的计划中,要求消耗的矿石不超过200吨,煤不超过300吨, 甲乙两种水泥制品应生产多少,能使利润达到最大值?

y

A(2,4)

【练习4】

B(-1,2)

如图1所示,已知△ABC中的三顶点 A(2,4) ,B(-1,2),C(1,0),点P(x,y) 0 C(0,1) 在△ABC内部及边界运动, 请你探究并讨论以下问题: (图1) ① z=x+y 在_____处有最大值___,在____处有最小值____; ② z=x-y 在___处有最大值____,在____处有最小值____; ③ 你能否设计一个目标函数,使得其取最优解的 情况有无穷多个? ④ 请你分别设计目标函数,使得最值点分别 在A处、B处、C处取得? ⑤ (课后思考题)若目标函数是 z=x2+y2 , 你知道其几何意义吗?你能否借助其几何意义求得

x

zmin和zmax

y ?1 2y ? 3 呢? 或z? ?如果是 z ? x x ?1

(如图2,①②问参考答案: ① z=x+y 在 在 点A 点C 处有最大值 6 ,在边界BC处有最小值 1 ;②z=x+y 处有最大值 1 ,在 点 B 处有最小值 -3)

y
B

A

(2 , 4)

y x ? y ? ?3 A
(?1, 2)

(2 , 4)

(?1, 2)

x? y ?6

B

x ? y ?1

0

C (1, 0)
x ? y ?1

x
( 图2 )

0

C

(1, 0)

x


网站首页 | 网站地图 | 学霸百科 | 新词新语
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com