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吨, 吨 甲乙两种水泥制品应生产多少,能使利润达到最大值? 甲乙两种水泥制品应生产多少,能使利润达到最大值?



更多相关文章:
简单线性规划整点最优解问题研究
简单线性规划整点最优解问题研究_理学_高等教育_教育专区。简单线性规划整点最优解问题研究黄建华 摘要: 本文主要介绍简单线性规划整点最优解的几种搜索方法,它们都...
也谈线性规划整点最优解的一种处理方法
也谈线性规划整点最优解的一种处理方法_高二数学_数学_高中教育_教育专区。...[3]中的方法,网格法和筛选法),那么有没有一种适用性广,且简单易于 理解的...
浅析简单的线性规划最优解问题
二是寻找最优整点解时可记住 “整点在整线上”(整线:形如 x=k 或 y=k,k∈Z).三、最后是解线性规划的题目简单线性规划问题就是求线性目标函数在线性约束...
简单的线性规划(重点)
简单的线性规划(重点) 适用学科 高中数学 适用区域 全国新课标 知识点 1.不...建立数学模型.把实际问题转化为线性规划问题; 2.寻找整点最优解的方法. 教学...
例析线性规划的整点最优解
例析线性规划的整点最优解浙江 徐志平 【大中小】【关闭】 在组织社会化生产、 经营管理活动 中, 我们经常会碰到最优决策的实际问 题。 而解决这类问题的...
线性规划整点问题的求解策略
所以使 P 取得 最大值的最优解是阴影内最靠近直线 518x+698y=4000 的整点...简单的线性规划整点最优... 19页 2下载券 线性规划中的整点问题求... 3...
线性规划的整点问题求解方法
线性规划整点最优解的求... 3页 1财富值 用线性规划方法求解运输问... 8页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...
谈一类简单线性规划问题最优解的发现
关键词:简单线性规划;整点最优解 作为新课标增加内容,高中数学教材对简单线性规划这一部分的叙述不够清晰,甚至 其描述有偏离,导致师生对它普遍缺乏认识,特别是对...
线性规划的整点问题求解方法
线性规划的整点问题求解方法宜昌市一中 祝海燕 线性规划是运筹学的一个重要...由于实际问 题中线性规划问题的最优解多为整数解,也是学生学习线性规划的难点,...
3.3.2 简单的线性规划问题(2)
3.3.2 简单的线性规划问题(2)【学习目标】 1.体会线性规划的基本思想,借助几何直 观解决一些简单的线性规划问题; 2.掌握寻找整点最优解的方法; 3.求解非...
更多相关标签:

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

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