线性规划新.ppt

简单的线性规划

总结归纳:
直线定界,特殊点定域
使z=2x+y取得最大值的可行解,
且最大值为;
复习引入

x-y≥0
(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)
3
x
y
0
使z=2x+y取得最小值的可行解,
且最小值为;
这两个可行解都叫做问题的。
变式1:求的最大值和最小值.
变式2:求的最大值和最小值.
总结:在约束条件下,求目标函数的最大值和最小值.
引申:
总结:
(1)求最优解的一般过程:
依题意,画区域,再把直线来平移,寻找最优在哪里
(2)最优解的位置:
一般在区域的边缘点或在边缘线上取得
X
y
0
8
4
x=8
y=4
7
6
5
4
3
2
1
3
2
1
x+y=10
4x+5y=30
320x+504y=0
,该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车,有10名驾驶员;每辆卡车每天往返的次数为A型卡车4次,B型卡车3次,每辆卡车每天往返的成本费A型卡车为320元,B型卡车为504元,问如何安排车辆才能使该公司所花的成本费最低,最低为多少元?(要求每型卡车至少安排一辆)
解:设每天调出的A型车x辆,B型车y辆,公司所花的费用为z元,则
x≤8
{
y≤4
x+y≤10
x,y∈N*
24x+5y≥30
Z=320x+504y
作出可行域中的整点,
可行域中的整点(5,2)使Z=320x+504y取得最小值,且Zmin=2608元
答(略)
作出可行域
返回
例题分析
例2 要将两种大小不同规格的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示:
规格类型
钢板类型
第一种钢板
第二种钢板
A规格
B规格
C规格
2
1
2
1
3
1
今需要A,B,C三种规格的成品分别为15,18,27块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少。
返回
例题分析
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
经过可行域内的整点B(3,9)和C(4,8)且和原点距离最近的直线是x+y=12,它们是最优解.
答:(略)
作出一组平行直线t = x+y,
目标函数t = x+y
返回
B(3,9)
C(4,8)
A(18/5,39/5)
打网格线法
在可行域内打出网格线,
当直线经过点A时t=x+y=11.,但它不是最优整数解,
将直线x+y=,
解:设需截第一种钢板x张,第一种钢板y张,则
x+y=12
例题分析
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),它们是最优解. 答(略)
作出一组平行直线t = x+y,
目标函数t = x+y
返回
B(3,9)
C(4,8)
A(18/5,39/5)
当直线经过点A时t=x+y=,+y=12
x+y=12
解得交点B,C的坐标B(3,9)和C(4,8)
调整优值法