文档介绍：简单的线性规划<br****题课
x
y
o
使z=2x+y取得最大值的可行解为,
且最大值为;
复****引入
{
x-y≥0
x+y-1≤0
y≥-1
(1)画出不等式组所表示的平面区域;
满足的解(x,y)都叫做可行解;
z=2x+y 叫做;
(2)设z=2x+y,则式中变量x,y满足的二元一次不等式组叫做x,y的;
y=-1
x-y=0
x+y=1
2x+y=0
(-1,-1)
(2,-1)
使z=2x+y取得最小值的可行解,
且最小值为;
这两个最值都叫做问题的。
线性约束条件
线性目标函数
线性约束条件
(2,-1)
(-1,-1)
3
-3
最优解
x
y
0
1
1
例题分析
例1:某工厂生产甲、、B种矿石5t、煤4t;生产乙种产品1吨需消耗A种矿石4t、B种矿石4t、,、消耗B种矿石不超过200t、、乙两种产品应各生产多少(),能使利润总额达到最大?
甲产品
(1t)
乙产品
(1t)
资源限额
(t)
A种矿石(t)
B种矿石(t)
煤(t)
利润(元)
产品
消耗量
资源
列表:
5
10
4
600
4
4
9
1000
300
200
360
设生产甲、 t、yt,利润总额为z元
例题分析
甲产品
(1t)
乙产品
(1t)
资源限额
(t)
A种矿石(t)
B种矿石(t)
煤(t)
利润(元)
产品
消耗量
资源
列表:
5
10
4
600
4
4
9
1000
300
200
360
把题中限制条件进行转化:
约束条件
10x+4y≤300
5x+4y≤200
4x+9y≤360
x≥0
y ≥0
z=600x+1000y.
目标函数:
设生产甲、 t、yt,利润总额为z元
xt
yt
例题分析
解:设生产甲、 t、yt,利润总额为z=600x+1000y. 元,那么
{
10x+4y≤300
5x+4y≤200
4x+9y≤360
x≥0
y ≥0
z=600x+1000y.
作出以上不等式组所表示的可行域
作出一组平行直线 600x+1000y=t,
解得交点M的坐标为(,)
5x+4y=200
{
4x+9y=360
由
10x+4y=300
5x+4y=200
4x+9y=360
600x+1000y=0
M
答:,,能使利润总额达到最大。
(,)
经过可行域上的点M时,目标函数在y轴上截距最大.
90
30
0
x
y
10
20
10
75
40
50
40
此时z=600x+1000y取得最大值.
例题分析
例2 要将两种大小不同规格的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示:
解:设需截第一种钢板x张,第一种钢板y张,则
规格类型
钢板类型
第一种钢板
第二种钢板
A规格
B规格
C规格
2
1
2
1
3
1
2x+y≥15,
{
x+2y≥18,
x+3y≥27,
x≥0
y≥0
作出可行域(如图)
目标函数为 z=x+y
今需要A,B,C三种规格的成品分别为15,18,27块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少。
x张
y张
例题分析
x
0
y
2x+y=15
x+3y=27
x+2y=18
x+y =0
2x+y≥15,
{
x+2y≥18,
x+3y≥27,
x≥0, x∈N
y≥0 y∈N
直线x+y=12经过的整点是B(3,9)和C(4,8),它们是最优解.
作出一组平行直线z=x+y,
目标函数z= x+y
B(3,9)
C(4,8)
A(18/5,39/5)
当直线经过点A时z=x+y=,
x+y=12
解得交点B,C的坐标B(3,9)和C(4,8)
调整优值法
2
4
6
18
12
8
27
2
4
6
8
10
15
但它不是最优整数解.
作直线x+y=12
答(略)
例题分析
x
0
y
2x+y=15
x+