9512.net
甜梦文库
当前位置:首页 >> 数学 >>

简单的线性规划整点最优解


y

——线性规划的简单应用 线性规划的简单应用

o

x

复习引入

1.已知二元一次不等式组 已知二元一次不等式组

{

x-y≥0 x+y-1≤0 y≥-1

(1)画出不等式组所表示的平面区域; )画出不等式组所表示的平面区域; (2)设z=2x+y,则式中变量x,y满足的二元一 ) x+y=1 次不等式组叫做x,y的 线性约束条件 ;

y

x-y=0 1 x 1
(2,-1)

z=2x+y 叫做

线性目标函数 ;

都叫做可行解 满足 线性约束条件 的解(x,y)都叫做可行解; 都叫做可行解; 取得最大值 使z=2x+y取得最大值的可行解为 (2,-1) 取得最大值的可行解为 且最大值为 3 ; ,

0
(-1,-1)

y=-1
2x+y=0

取得最小值 使z=2x+y取得最小值的可行解 (-1,-1) , 取得最小值的可行解 且最小值为

-3


返回

最值都叫做问题的 这两个最值 这两个最值都叫做问题的 最优解 。

例题分析
某工厂生产甲、乙两种产品.已知生产 种产品1t需消 已知生产甲 例1:某工厂生产甲、乙两种产品 已知生产甲种产品 需消 种矿石10t、 种矿石 种矿石5t、 耗 A种矿石 、 B种矿石 、 煤 4t;生产 乙 种产品 吨需消 种矿石 ; 生产乙 种产品1吨需消 种矿石4t、 种矿石 种矿石4t、 甲种产品的利润是600 耗A种矿石 、B种矿石 、煤9t.每1t甲种产品的利润是 种矿石 每 甲种产品的利润是 元,每1t乙种产品的利润是 每 乙种产品的利润是1000元.工厂在生产这两种产品的 元 工厂在生产这两种产品的 乙种产品的利润是 计划中要求消耗A种矿石不超过 种矿石不超过300t、消耗 种矿石不超过 计划中要求消耗 种矿石不超过 、消耗B种矿石不超过 200t、消耗煤不超过 、消耗煤不超过360t.甲、乙两种产品应各生产多少 精 甲 乙两种产品应各生产多少(精 确到0.1t),能使利润总额达到最大 能使利润总额达到最大? 确到 能使利润总额达到最大
分别为x 利润总额为z元 列表:设生产甲、乙两种产品.分别为 、 利润总额为 列表 设生产甲、乙两种产品 分别为 t、yt,利润总额为 元
消耗量 产品 资源

甲产品 (1t) )

乙产品 (1t) )

资源限额 (t) )

A种矿石(t) 种矿石( ) 种矿石 B种矿石(t) 种矿石( ) 种矿石 煤(t) ) 利润(元) 利润(

10 5 4 600

4 4 9 1000

300 200 360

例题分析
列表: 列表 资源

消耗量 产品

甲产品 xt (1t) )

乙产品 (1t) )

yt

资源限额 (t) )

A种矿石(t) 种矿石( ) 种矿石 B种矿石(t) 种矿石( ) 种矿石 煤(t) ) 利润( 利润(元)

10 5 4 600

4 4 9 1000

300 200 360

把题中限制条件进行转化: 把题中限制条件进行转化: 转化
? 10x+4y≤300 ? 5x+4y≤200 ? ? ? 4x+9y≤360 ? x≥0 ? ? y ≥0 ?

设生产甲、乙两种产品.分别为 t、yt,利润总额为 元 分别为x 利润总额为z元 设生产甲、乙两种产品 分别为 、 利润总额为

约束条件

目标函数: 目标函数:

z=600x+1000y.

例题分析
设生产甲、 分别为x 解:设生产甲、乙两种产品 分别为 设生产甲 乙两种产品.分别为 10x+4y≤300 那么 5x+4y≤200 4x+9y≤360 x≥0 y ≥0 t、yt,利润总额为z=600x+1000y. 元, 、 利润总额为

{

75

y
50 40

z=600x+1000y.
作出以上不等式组所表示的可行域
l l

作 出 一 组 平 行 直 线

M (12.4,34.4) 4x+9y=360

600x+1000y=t, ,
经过可行域上的点M时 目标函数 经过可行域上的点 时,目标函数 轴上截距最大. 在y轴上截距最大 轴上截距最大
10 10 20 30

此时z=600x+1000y取得最大值 0 取得最大值. 此时 取得最大值 5x+4y=200 由 4x+9y=360 解得交点M的坐标为 的坐标为(12.4,34.4) 解得交点 的坐标为

{

40 5x+4y=200

90

x

10x+4y=300 600x+1000y=0

应生产甲产品约12.4吨,乙产品 答:应生产甲产品约 应生产甲产品约 吨 乙产品34.4吨,能使利润总额达到最大。 吨 能使利润总额达到最大。

例题分析
要将两种大小不同规格的钢板截成A、 、 三种规格 三种规格, 例2 要将两种大小不同规格的钢板截成 、B、C三种规格, 每张钢板可同时截得三种规格的小钢板的块数如下表所示 :
规格类型 钢板类型

A规格 规格 2 1

B规格 规格 1 2

C规格 规格 1 3

第一种钢板 X张 张
张 第二种钢板 y张

今需要A,B,C三种规格的成品分别为 ,18,27块,问 三种规格的成品分别为15, , 块 今需要 三种规格的成品分别为 各截这两种钢板多少张可得所需三种规格成品, 各截这两种钢板多少张可得所需三种规格成品,且使所 用钢板张数最少。 用钢板张数最少。 设需截第一种钢板x张 第一种钢板y张 解:设需截第一种钢板 张,第一种钢板 张,则

{

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

目标函数为 z=x+y
作出可行域(如图) 作出可行域(如图)

例题分析

{

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

12

2x+y=15

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

18

x 27
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),它们是最优解 经过的整点是 直线 经过的整点是 和 ,它们是最优解.

答(略)

例题分析

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

{

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

打网格线法

目标函数t = x+y

9

A(18/5,39/5)

x+y =0

2 1 0 12

x 78
2x+y=15

18

27

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

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

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

巩固练习1: 巩固练习
不等式组

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



)个

1

0

1

2

3

4

x

4x+3y=12

在可行域内找出最优解、线性规划整数 在可行域内找出最优解、 解问题的一般方法是: 解问题的一般方法是:
1.若区域“顶点”处恰好为整点,那么它就是最优解; 若区域“ 若区域 顶点”处恰好为整点,那么它就是最优解;
(在包括边界的情况下) 在包括边界的情况下) 2.若区域“顶点”不是整点或不包括边界时,应先求出 若区域“顶点”不是整点或不包括边界时, 若区域 该点坐标,并计算目标函数值Z, 该点坐标,并计算目标函数值Z,然后在可行域内适当 放缩目标函数值,使它为整数,且与Z最接近 最接近, 放缩目标函数值,使它为整数,且与 最接近,在这条 对应的直线中,取可行域内整点,如果没有整点, 对应的直线中,取可行域内整点,如果没有整点,继续 放缩,直至取到整点为止。 放缩,直至取到整点为止。 3.在可行域内找整数解,一般采用平移找解法,即打网 在可行域内找整数解, 在可行域内找整数解 一般采用平移找解法, 找整点、平移直线、 络、找整点、平移直线、找出整数最优解

解线性规划应用问题的一般步骤: 解线性规划应用问题的一般步骤
1)理清题意,列出表格: )理清题意,列出表格: 2)设好变元并列出不等式组和目标函数 ) 3)由二元一次不等式表示的平面区域做出可行域; )由二元一次不等式表示的平面区域做出可行域; 4)在可行域内求目标函数的最优解 ) 5)还原成实际问题 (准确作图,准确计算 还原成实际问题 准确作图,准确计算)

咖啡馆配制两种饮料.甲种饮料每杯含奶粉 咖啡4g、 咖啡馆配制两种饮料.甲种饮料每杯含奶粉9g 、咖啡 、 乙种饮料每杯含奶粉4g 咖啡5g、 糖3g,乙种饮料每杯含奶粉 、咖啡 、糖10g.已知每天 乙种饮料每杯含奶粉 . 原料的使用限额为奶粉3600g ,咖啡 咖啡2000g 糖3000g,如果 原料的使用限额为奶粉 如果 甲种饮料每杯能获利0.7元 乙种饮料每杯能获利1.2元 甲种饮料每杯能获利 元,乙种饮料每杯能获利 元,每 天在原料的使用限额内饮料能全部售出, 天在原料的使用限额内饮料能全部售出,每天应配制两种 饮料各多少杯能获利最大? 饮料各多少杯能获利最大 将已知数据列为下表: 解:将已知数据列为下表:
甲产品 消耗量 产品 (1 杯) 资源 奶粉( 奶粉(g) 咖啡(g) 咖啡(g) 糖(g) 利润( 利润(元) 乙产品(1 乙产品 杯) 资源限额( ) 资源限额(g)

9 4 3 0.7

4 5 10 1.2

3600 2000 3000

设每天应配制甲种饮料x 设每天应配制甲种饮料x杯,乙种饮料y杯,则 乙种饮料y

作出可行域: 作出可行域: 目标函数为: 目标函数为:z =0.7x +1.2y 作直线l x+1 y=0 作直线l:0.7x+1.2y=0, 把直线l向右上方平移至l 把直线 l 向右上方平移至 l1 的位置 时, 直线经过可行域上的点C 直线经过可行域上的点C,且与原 点距离最大, 点距离最大, 此时z 此时z =0.7x +1.2y取最大值 解方程组

?9 x + 4 y ≤ 3600 ?4 x + 5 y ≤ 2000 ? ? ?3x + 10 y ≤ 3000 ?x ≥ 0 ? ?y ≥ 0 ?

y _ 9 _00

4 _00 3 _00 7 _ x + 12 y = 0 0 _ _00 4 _ ( 200 , 240 ) C _ x + 10 y = 3000 3
_ 0

1 500 _000 _ _ x + 5 y = 2000 4

_ x

? 4 x + 5 y = 2000 , ? ? 3 x + 10 y = 3000 ,

9 x + 4 y = 3600 _

得点C的坐标为(200,240) 得点C的坐标为(200,240)

二元一次不等式 表示平面区域

直线定界, 直线定界, 特殊点定域 约束条件 目标函数

应 用

简单的线性规划

可行解 可行域

求解方法: 求解方法:画、 移、求、答

最优解

练习巩固
1.某家具厂有方木材 某家具厂有方木材90m3 , 木工板 木工板600m3 , 准备加工成 某家具厂有方木材 书桌和书橱出售, 已知生产每张书桌需要方木料0.1m3 、 书桌和书橱出售 , 已知生产每张书桌需要方木料 木工板2m 生产每个书橱需要方木料0.2m3 , 木工板 木工板 3 ; 生产每个书橱需要方木料 1m3 , 出售一张书桌可以获利 元 , 出售一张书橱可以 出售一张书桌可以获利80元 获利120元; 获利 元 (1)怎样安排生产可以获利最大? )怎样安排生产可以获利最大? (2)若只生产书桌可以获利多少? )若只生产书桌可以获利多少? (3)若只生产书橱可以获利多少? )若只生产书橱可以获利多少?

分析: 分析:
产品 资源 方木料 m
3

书桌(张) 0.1 2 80

书橱(张) 0.2 1 120

资源限额 m3 90 600

木工板 m3 利润 (元)

由上表可知: (1)只生产书桌,用完木工板了,可生产书桌 600÷2=300张, 可获利润:80×300=24000元,但木料没有用完 (2)只生产书橱,用完方木料,可生产书橱90÷0.2=450 张,可 获利润120×450=54000元,但木工板没有用完

1.某家具厂有方木材 3,木工板 某家具厂有方木材90m 木工板600m3,准备加工成书桌和书橱出售, 准备加工成书桌和书橱出售,
已知生产每张书桌需要方木料0.1m3、木工板 3;生产每个书橱需要方木 木工板2m 已知生产每张书桌需要方木料 木工板1m 出售一张书桌可以获利80元 料0.2m3,木工板 3,出售一张书桌可以获利 元,出售一张书橱可以获 利120元; 元 (1)怎样安排生产可以获利最大? )怎样安排生产可以获利最大? (2)若只生产书桌可以获利多少? )若只生产书桌可以获利多少? y 求解: 求解: (3)若只生产书橱可以获利多少? )若只生产书橱可以获利多少? (1)设生产书桌 张,书橱 张,利 )设生产书桌x张 书橱y张 润为z元 润为 元, 则约束条件为

600 450

A(100,400)

{

0.1x+0.2y≤90 x+0 y≤90 x+y≤600 2x+y≤600 x,y∈N*

x+2y-900=0 x
300 900

Z=80x+120y Z=80x+120y 80x+120 0 作出不等式表示的平面区域, 作出不等式表示的平面区域, 将直线z=80x+120y平移可知: 平移可知: 将直线 平移可知 当生产100张书桌 , 400张书橱时利润最大为 张书桌, 当生产 张书桌 张书橱时利润最大为 z=80×100+120×400=56000元 × × 元

2x+y-600=0

(2)若只生产书桌可以生产 )若只生产书桌可以生产300张,用完木工板,可获利 24000元; 张 用完木工板, 元 (3)若只生产书橱可以生产 )若只生产书橱可以生产450张,用完方木料,可获利 张 用完方木料,可获利54000元。 元

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

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

y

4x+5y=30

x+y=10

x=8 y=4

{

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

X

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

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

320x+504y=0

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



更多相关文章:
简单的线性规划整点最优解_图文.ppt
简单的线性规划整点最优解 - y 线性规划的简单应用 o x 复习引入 1.
简单的线性规划(重点).doc
简单的线性规划(重点) 适用学科 高中数学 适用区域 全国新课标 知识点 1.不...建立数学模型.把实际问题转化为线性规划问题; 2.寻找整点最优解的方法. 教学...
教你如何做出最佳选择简单线性规划最优解.doc
教你如何做出最佳选择 简单的线性规划最优解在线性约束条件下,求线性目标...有实 际意义,而当可行域中的最优解不是整数解时,需作出可行域的整点作出...
简单的线性规划整点最优解_图文.ppt
简单的线性规划整点最优解 - 线性规划的简单应用 北城中学 例题分析 例1 要将
简单的线性规划整点最优解2014_图文.ppt
简单的线性规划整点最优解2014 - 线性规划的 y 简单应用 o x 复习引入
简单线性规划(整点解问题)_图文.ppt
简单线性规划(整点解问题) - 7.4简单的线型规划 7.4简单的线型规划(3) 整点解问题 怀化铁路第一中学 7.4简单的线型规划 一、朝花夕拾 图解法解简单...
简单线性规划整点最优解问题研究.doc
简单线性规划整点最优解问题研究宋永峰 随着中学数学教育的改革和发展, 简单线性规划问题已经逐渐成为中学数学 教学的一个基本内容。 简单线性规划问题与我们的日常...
简单的线性规划最优解.doc
简单的线性规划最优解 - 教你如何做出最佳选择 简单的线性规划最优解
也谈线性规划整点最优解的一种处理方法.doc
也谈线性规划整点最优解的一种处理方法 - 也谈线性规划整点最优解的一种处理方法 线性规划是解决现实生产、生活中遇到的资源利用、人力调配、生产安排等问题...
3.3.2简单的线性规划问题(整数最优解)_图文.ppt
小结:线性规划最优整数解的一般方法: 1.平移找解法: 即先打网格,描出可行域内的整点,平移直线,最先经过或最后经过的整点 坐标即为最优整解. 2.调整优...
简单线性规划整点最优解问题研究.doc
简单线性规划整点最优解问题研究 - 简单线性规划整点最优解问题研究 黄建华 摘要: 本文主要介绍简单线性规划整点最优解的几种搜索方法,它们都是 在图解平移法的...
简单的线性规划第一课时教案.doc
或最小值问题使目标函数达到最大值或最小 值的点的坐标,称为问题的最优解....小结:本题是整数线性规划问题,整数线性规划问题的可行域是由满足不等式组的整点...
高中数学 二简单的线性规划问题整点问题_图文.ppt
高中数学 二简单的线性规划问题整点问题 - 关于取整数解的问题 例1、一个化肥厂
3.3.2 简单的线性规划问题 课件_图文.ppt
3.3.2 简单的线性规划问题 课件_数学_高中教育_教育专区。3.3.2 简单的...再描整点,平移直线l, 最先经过或最后经过的整点坐标是整点最优解. ②检查...
线性规划最优整点解的三种求法_图文.pdf
( 湖北 省黄石 第二 十 中学 ,435000) 求最优整点解简单线性 规划这 一单元 中的学习难点 , 而教材 (人 教版高 中数学第二 册上)仅通过 一个例 题...
3.3.2.2简单线性规划-最优整数解_图文.ppt
3.3.2简单的线性规划-最优整数解 关于最优整数解的问题 例 要将两种大小不...(要求每型卡车至少安排一辆) 4 3 2 1 { 作出可行域 作出可行域中的整点,...
如何寻找线性规划问题的整点最优解_图文.pdf
如何寻找线性规划问题的整点最优解_数学_自然科学_专业资料。24 数学通讯 2O1 O年第11、1 2期(上半月) ? 辅教导学 ? 如何寻找线 性规划 问题 整...
谈一类简单线性规划问题最优解的发现.doc
谈一类简单线性规划问题最优解的发现 - 本文介绍了一种发现简单线性规划问题非负整数最优解的普适方法。它是在图解平移法基础上先对最优解在可行域中的位置进行...
线性规划中求整数最优解的五种方法_图文.pdf
线性规划中求整数最优解的五种方法 - 维普资讯 http://www.cqvip.com 10 数学通讯 200 4年第 24期 线性规划中求整数最优解的五种方...
简单的线性规划_图文.ppt
简单的线性规划_城乡/园林规划_工程科技_专业资料。珠海市金海岸中学 唐云辉 ? ...打网格,再描整点,平 移直线l,最先经过或最后经过的整点坐标是整点最优 解...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图