文档介绍：简单的线性规划
简单的线性规划
(第三课时)
5x+4y=20
2x+3y=12
线性目标函数
Z的最大值为44
已知实数x,y满足下列条件:
5x+4y ≤ 20
2x+3y ≤12
x ≥0
y≥0
求z=9x+10y的最大值.
最优解
可行域
9x+10y=0
想一想:
线性约束条件
.
.
.
.
.
.
.
.
.
.
.
.
.
0
1
2
3
4
5
6
1
2
3
4
5
6
x
y
代数问题
(线性约束条件)
图解法
转化
线性约
束条件
可行域
转化
线性目
标函数
Z=Ax+By
一组平行线
转化
最优解
图解法的步骤:
1。画可行域;
4。求出最优解作答.
3。平移直线L0找最优解;
2。作Z=0时的直线L0.
三个转化
平行线在y轴上
的截距最值
某工厂生产甲、
耗A种矿石10t、B种矿石5t、煤4t;生产乙种产品1t需
消耗A种矿石4t、B种矿石4t、煤9t. 每1t甲种产品的利润
是600元,
种产品的计划中要求消耗A种矿石不超过300t、消耗B种
矿石不超过200t、
两种产品的产量(),才能使利润总额达到最大?
探索问题一:
某工厂生产甲、、B种矿石5t、煤4t;生产乙种产品1t需消耗A种矿石4t、B种矿石4t、,、消耗B种矿石不超过200t、消耗煤不超过360t. 你应如何安排甲乙两种产品的产量(),才能使利润总额达到最大?
分
析
问
题:
?
?
?
?
?
原材
料
每吨产品消耗的原材料
A种矿石
B种矿石
煤
甲产品(t)
乙产品(t)
10
5
4
4
4
9
原材料
限额
300
200
360
利润
600
1000
xt
yt
10x+4y≤300
5x+4y≤200
4x+9y≤360
x≥0
y ≥0
z=600x+1000y.
目标函数:
设生产甲、乙两种产品的产量分别为x t、yt,利润总额为z元
解:设生产甲、 t、yt,利润总额为z元,那么
10x+4y≤300
5x+4y≤200
4x+9y≤360
x≥0
y ≥0
z=600x+1000y.
画出以上不等式组所表示的可行域
作出直线L 600x+1000y=0.
解得交点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取得最大值.
把直线L向右上方平移
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,
y≥0
在可行域内直线x+y=12经过的整点是B(3,9)和C(4,8),它们是最优解.
作出直线L:x+y=0,
目标函数:z= x+y
B(3,9)
C(4,8)
A(,)
当直线L经过点A时z=x+y=,
x+y=12
2
4
6
18
12
8
27
2
4
6
8
10
15
但它不是最优整数解.
作直线x+y=12
答(略)
约束条件:
画可行域
平移L找交点
及交点坐标
继续平移L找最优整数解
调整Z的值,
X+y=
A
调整优值法
即先求非整数条件下的最优解,调整Z的值使不定方程Ax+By=Z存在最大(小)的整点值,最后筛选出整点最优解.
即先打网格,描出可行域内的整点,平移直线,最先经过(或最后)经过的整点坐标即为最优整解.
线性规划