2000年 第3期 数学通报19
如何寻找《线性规划问题》的整点最优解
安培录 (山西省代县中学校 034200)
试验教材高二数学(上)增加了《简单的线性
规划》的内容,利用图解法解答线性规划的两类问题Ζ对此,大纲要求“会简单的应用”Ζ
学生对线性规划的基本概念,入手,,试验教(P76页例4),两个习题(P79页第3、4题),一个复习题(P107页第17题)Ζ针对学生从认知到应用这一过程存在的问题,笔者在教学实践中归纳整理了三种基本方法,现举例说明如下:
例1 (P79页习题第4题)某人有楼房一幢,室内面积共180m2,拟分隔成两类房间作为旅游客房Ζ大房间每间面积为18m2,可住游客5名,每名游客每天住宿费为40元;小房间每间面积为15m2,可住游客3名,每名游客每天住宿费为50元;装修大房间每间需1000元,装修小房间每间需600元Ζ如果他只能筹款8000元用于装修,且游客能住满客房,他应隔出大房间和小房间各多少间,能获得最大收益?
分析 这是线性规划的理论和方法的应用中的第一类问题Ζ即:在人力、物力、资金等资源一定的条件下,如何使用它们来完成最多的任务Ζ解题一般步骤为:
11设出所求的未知数;21列出约束条件;31
建立目标函数;41作出可行域;
51运用图解法求出最优解Ζ根据题中的已知条件,列表如下:
分类
每间标准占地面积(m2)装修费用(元)
大房间小房间总限额181000
15600
1808000
元,Ζ
小房间y间,,则180
1000x+600y≤8000x≥0y0
6x+5y≤605x+3y≤40Ζ
x≥0y≥0x、y是整数Ζ
目标函数 z=200x+150y.作出可行域如图1Ζ
l1
[1**********]435y=60
5x+3y=40
x
l-[1**********]
图1
作出一组平行的直线200x+150y=t.
当t=0时,即200x+150y=0也就是直线l0:4x+3y=0.
将直线l0向上平移至l1的位置时,直线l1经过可行域上的点A,且与原点的距离最大,此时z=200x+150yΖ
6x+5y=60
5x+3y=40x=
7
y=
7
游客住满客房,每间每天住宿费大房间为
202000年 第3期 数学通报
即点A的坐标为(
,)77
[1**********]y=543
21-20134712
由题意知,最优解中的x、y
必须是整数,而点A的坐标不是整数,故不是题中所求最优解,需先找出可行域内的所有整点,作直线x=1,2,…,8,y=1,2,…,13Ζ如图2,打出网格,这些网格在可行域内的交点即可行域内的整点Ζ
l1l2
B[1**********]0
x
图3
60
5x+3y=40
x
-[1**********]
图2
将直线l1向下平移至l2的位置时,直线l2最先经过可行域上的整点B(0,12)和C(3,8)且使z=200x+150y取得最大值,此时z最大=200×0+150×12=200×3+150×8=1800
所以应隔出小房间12间或大房间3间,小房间8间能获得最大收益Ζ
说明 这种寻找整点最优解的方法可简述为:平移找解法,即打网格,描整点,平移直线l0,找出整点最优解Ζ
解法二 由解法一知,直线l1经过点A(,
7
),横纵坐标都不是整数,不是所求的最优整7
点,用解法一的方法,打出网格描出可行域内的整点,由题意,取得目标函数最大值的整点应分布在可行域的右上侧,为此在可行域内右上侧靠近边界的整点依次取B(0,12),C(1,10),D(2,9),E(3,8),F(4,6),G(5,5),H(6,3),L(7,1),K(8,0),将这些点的坐标分别代入z=200x+150y
,求出z的各对应值,经验证可知,在整点B(0,12)和E(3,8)处,z取得最大值,如图3(以下略)Ζ
说明 这种寻找整点最优解的方法可简述为:代入验证法,即打网格,描整点,代入算,选优解Ζ
解法三 由解法一可知,点A的坐标(,
7
),不是整数,不是所求的最优点,虽然点A的7
坐标不是最优解,但可利用它帮助我们较快地找到最优解,其方法是:将点A的坐标代入4x+3y
=t中,所得t的值为t0=37,当t>t0时,直线
3
4x+3y=t在直线l1的右上方,将离开可行域;当0
当t=37时,即4x+3y=37,也就是y=(x∈[0,8]且x∈N),当x=0,3,5,6,83
时,y无整数解,当x=1,2,4,7时,y虽有整数解,但不在可行域内Ζ
当t=36时,即4x+3y=36,也就是y=(x∈[0,8]且x∈N),当x=0时,y=12;3
当x=3时,y=8;当x=1,2,4,5,7,8时y无整数解;当x=6时,y=4虽是整数解,但不在可行域内(如图3),故(0,12)与(3,8)为所求最优整点的坐标Ζ(以下略)
说明 这种寻找整点最优解的方法可简述为:调整优值法,即先求非整点最优解,再求非整点最优值,调整这个最优值,筛选整点最优解Ζ
例2 (P107页复习参考题A组第17题)某运输公司有7辆重量为6t的A型卡车与4辆载重量为10t的B型卡车,有9名驾驶员,在建筑某段高速公路中,此公司承包了每天至少搬运360t沥青的任务,已知每辆卡车每天往返的次数为A型车8次,B型车6次,每辆卡车每天往返的成本费为A型车160元,B型车252元,每天派出A型车与B型车各多少辆,公司所花的成本费最
2000年 第3期 数学通报21
x=7
低?
分析 这是线性规划的理论和方法的应用中的第二类问题,即:给定一项任务,如何合理安排和规划,能以最少的人力、物力、资金等资源来完成该项任务Λ
根据题中已知条件,列表如下:
车型
每车每天
驾驶员(tA型车B型车总限额18
y=
5
)Ζ由题知,最优解中5
的x,y必须是整数,而点A的纵坐标不是整数,
即点A的坐标为(7,
A型车x辆,B型车y辆,公司所花的成本费为z元,则x,y满足约束条件:
x≤7x≤7y≤4y≤4x+y≤9x+y≤9
Ζ
48x+60y≥3604x+5y≥30x≥0x≥0y≥0y≥0其中x,y是整数Ζ
目标函数:z=160x+252y作出可行域如图4:
作出一组平行的直线160x+252y=t,当t=0时,即160x+252y=0,也就是直线l0:40x+63y=0.
将直线l0向上平移至l1的位置时,直线l1经过可行域上的点A,且与原点的距离最小,此时,z=160x+252yΖ
x=7
4x+5y=30
故不是所求的最优解Ζ
,需先找出,1,2,…,7,y4,,这时网格在可行域Ζ
将直线l1向上平移到l2的位置时,直线l2最先经过可行域内的整点B(5,2),且使z=160x+252y取最小值,此时
z最小=160×5+252×2=1304.
所以每天派出A型车5辆,B型车2辆,公司所花的成本费最低Ζ
解法二 代入验证法
由解法一知,l1经过点A(7,),因为不是
55
整数,所以点A不是所求的最优整点,用解法一的方法打出网格,描出可行域内的整点Ζ由题意可知,所求最优整点分布在可行域的左下侧,在可行域内靠近左下侧的整点依次为B(3,4),C(4,3),D(5,2),E(6,2),F(7,1),将这些点的坐标分别代入z=160x+252y,求出z的各对应值,经验证可知,在整点D(5,2)处,z取得最小值,如图5(以下略)Ζ
解法三 调整优值法
由解法一可知,点A坐标(7,)的纵坐标不
5
是整点最优解,但它为我们提供了一条较快地找到最优解的途径,其方法是:将点A的坐标代入
40x+63y=t中,所得t的值为t0=305
,若取t
5
=340,直线40x+63y=304在直线l1的左下方,将离开可行域;当t=306,方程40x+63y=306在可行域内无整数解,逐步调整t的取值,使t的值依次增大,当t=326时,即40x+63y=326,也
就是y=如图5,在可行域内,x的整数
63
值为3,4,5,6,7,当x=3,4,6,7时,y没有整数解;当x=5时,y=2,故(5,2)是所求最优整点的坐标(以下略)Ζ
2000年 第3期 数学通报19
如何寻找《线性规划问题》的整点最优解
安培录 (山西省代县中学校 034200)
试验教材高二数学(上)增加了《简单的线性
规划》的内容,利用图解法解答线性规划的两类问题Ζ对此,大纲要求“会简单的应用”Ζ
学生对线性规划的基本概念,入手,,试验教(P76页例4),两个习题(P79页第3、4题),一个复习题(P107页第17题)Ζ针对学生从认知到应用这一过程存在的问题,笔者在教学实践中归纳整理了三种基本方法,现举例说明如下:
例1 (P79页习题第4题)某人有楼房一幢,室内面积共180m2,拟分隔成两类房间作为旅游客房Ζ大房间每间面积为18m2,可住游客5名,每名游客每天住宿费为40元;小房间每间面积为15m2,可住游客3名,每名游客每天住宿费为50元;装修大房间每间需1000元,装修小房间每间需600元Ζ如果他只能筹款8000元用于装修,且游客能住满客房,他应隔出大房间和小房间各多少间,能获得最大收益?
分析 这是线性规划的理论和方法的应用中的第一类问题Ζ即:在人力、物力、资金等资源一定的条件下,如何使用它们来完成最多的任务Ζ解题一般步骤为:
11设出所求的未知数;21列出约束条件;31
建立目标函数;41作出可行域;
51运用图解法求出最优解Ζ根据题中的已知条件,列表如下:
分类
每间标准占地面积(m2)装修费用(元)
大房间小房间总限额181000
15600
1808000
元,Ζ
小房间y间,,则180
1000x+600y≤8000x≥0y0
6x+5y≤605x+3y≤40Ζ
x≥0y≥0x、y是整数Ζ
目标函数 z=200x+150y.作出可行域如图1Ζ
l1
[1**********]435y=60
5x+3y=40
x
l-[1**********]
图1
作出一组平行的直线200x+150y=t.
当t=0时,即200x+150y=0也就是直线l0:4x+3y=0.
将直线l0向上平移至l1的位置时,直线l1经过可行域上的点A,且与原点的距离最大,此时z=200x+150yΖ
6x+5y=60
5x+3y=40x=
7
y=
7
游客住满客房,每间每天住宿费大房间为
202000年 第3期 数学通报
即点A的坐标为(
,)77
[1**********]y=543
21-20134712
由题意知,最优解中的x、y
必须是整数,而点A的坐标不是整数,故不是题中所求最优解,需先找出可行域内的所有整点,作直线x=1,2,…,8,y=1,2,…,13Ζ如图2,打出网格,这些网格在可行域内的交点即可行域内的整点Ζ
l1l2
B[1**********]0
x
图3
60
5x+3y=40
x
-[1**********]
图2
将直线l1向下平移至l2的位置时,直线l2最先经过可行域上的整点B(0,12)和C(3,8)且使z=200x+150y取得最大值,此时z最大=200×0+150×12=200×3+150×8=1800
所以应隔出小房间12间或大房间3间,小房间8间能获得最大收益Ζ
说明 这种寻找整点最优解的方法可简述为:平移找解法,即打网格,描整点,平移直线l0,找出整点最优解Ζ
解法二 由解法一知,直线l1经过点A(,
7
),横纵坐标都不是整数,不是所求的最优整7
点,用解法一的方法,打出网格描出可行域内的整点,由题意,取得目标函数最大值的整点应分布在可行域的右上侧,为此在可行域内右上侧靠近边界的整点依次取B(0,12),C(1,10),D(2,9),E(3,8),F(4,6),G(5,5),H(6,3),L(7,1),K(8,0),将这些点的坐标分别代入z=200x+150y
,求出z的各对应值,经验证可知,在整点B(0,12)和E(3,8)处,z取得最大值,如图3(以下略)Ζ
说明 这种寻找整点最优解的方法可简述为:代入验证法,即打网格,描整点,代入算,选优解Ζ
解法三 由解法一可知,点A的坐标(,
7
),不是整数,不是所求的最优点,虽然点A的7
坐标不是最优解,但可利用它帮助我们较快地找到最优解,其方法是:将点A的坐标代入4x+3y
=t中,所得t的值为t0=37,当t>t0时,直线
3
4x+3y=t在直线l1的右上方,将离开可行域;当0
当t=37时,即4x+3y=37,也就是y=(x∈[0,8]且x∈N),当x=0,3,5,6,83
时,y无整数解,当x=1,2,4,7时,y虽有整数解,但不在可行域内Ζ
当t=36时,即4x+3y=36,也就是y=(x∈[0,8]且x∈N),当x=0时,y=12;3
当x=3时,y=8;当x=1,2,4,5,7,8时y无整数解;当x=6时,y=4虽是整数解,但不在可行域内(如图3),故(0,12)与(3,8)为所求最优整点的坐标Ζ(以下略)
说明 这种寻找整点最优解的方法可简述为:调整优值法,即先求非整点最优解,再求非整点最优值,调整这个最优值,筛选整点最优解Ζ
例2 (P107页复习参考题A组第17题)某运输公司有7辆重量为6t的A型卡车与4辆载重量为10t的B型卡车,有9名驾驶员,在建筑某段高速公路中,此公司承包了每天至少搬运360t沥青的任务,已知每辆卡车每天往返的次数为A型车8次,B型车6次,每辆卡车每天往返的成本费为A型车160元,B型车252元,每天派出A型车与B型车各多少辆,公司所花的成本费最
2000年 第3期 数学通报21
x=7
低?
分析 这是线性规划的理论和方法的应用中的第二类问题,即:给定一项任务,如何合理安排和规划,能以最少的人力、物力、资金等资源来完成该项任务Λ
根据题中已知条件,列表如下:
车型
每车每天
驾驶员(tA型车B型车总限额18
y=
5
)Ζ由题知,最优解中5
的x,y必须是整数,而点A的纵坐标不是整数,
即点A的坐标为(7,
A型车x辆,B型车y辆,公司所花的成本费为z元,则x,y满足约束条件:
x≤7x≤7y≤4y≤4x+y≤9x+y≤9
Ζ
48x+60y≥3604x+5y≥30x≥0x≥0y≥0y≥0其中x,y是整数Ζ
目标函数:z=160x+252y作出可行域如图4:
作出一组平行的直线160x+252y=t,当t=0时,即160x+252y=0,也就是直线l0:40x+63y=0.
将直线l0向上平移至l1的位置时,直线l1经过可行域上的点A,且与原点的距离最小,此时,z=160x+252yΖ
x=7
4x+5y=30
故不是所求的最优解Ζ
,需先找出,1,2,…,7,y4,,这时网格在可行域Ζ
将直线l1向上平移到l2的位置时,直线l2最先经过可行域内的整点B(5,2),且使z=160x+252y取最小值,此时
z最小=160×5+252×2=1304.
所以每天派出A型车5辆,B型车2辆,公司所花的成本费最低Ζ
解法二 代入验证法
由解法一知,l1经过点A(7,),因为不是
55
整数,所以点A不是所求的最优整点,用解法一的方法打出网格,描出可行域内的整点Ζ由题意可知,所求最优整点分布在可行域的左下侧,在可行域内靠近左下侧的整点依次为B(3,4),C(4,3),D(5,2),E(6,2),F(7,1),将这些点的坐标分别代入z=160x+252y,求出z的各对应值,经验证可知,在整点D(5,2)处,z取得最小值,如图5(以下略)Ζ
解法三 调整优值法
由解法一可知,点A坐标(7,)的纵坐标不
5
是整点最优解,但它为我们提供了一条较快地找到最优解的途径,其方法是:将点A的坐标代入
40x+63y=t中,所得t的值为t0=305
,若取t
5
=340,直线40x+63y=304在直线l1的左下方,将离开可行域;当t=306,方程40x+63y=306在可行域内无整数解,逐步调整t的取值,使t的值依次增大,当t=326时,即40x+63y=326,也
就是y=如图5,在可行域内,x的整数
63
值为3,4,5,6,7,当x=3,4,6,7时,y没有整数解;当x=5时,y=2,故(5,2)是所求最优整点的坐标(以下略)Ζ