清华大学运筹学课件(完整课件).ppt

第一章 线性规划与单纯形法
§1 线性规划问题及其数学模型
问题的提出
[] 生产计划问题
问:产品Ⅰ、Ⅱ各生产多少件,
使利润最大?
Ⅰ
Ⅱ
限制
设备台时
1
2
8台时
材料A
4
0
16kg
材料B
0
4
12kg
利润
2
3
分析:
设:产品Ⅰ生产x1件,
产品Ⅱ生产x2件。
这里z为利润函数,
max z:表示求z的最大值。
目标函数: max z = 2x1 + 3x2
约束条件: 1x1 + 2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
x1,x2 ≥ 0
毗磁昂始涂蛆名***逢群驰唤乞都署烯恰染竟祖缴陕题啄沁毋笑亏隧旬衬甚清华大学运筹学课件(完整课件)清华大学运筹学课件(完整课件)
1
[]污水处理问题
环保要求河水含污低于2‰,河水可自身净化20%。
问:化工厂1、2每天各处理多少污水,使总费用最少?
分析:
化工厂1处理污水x1万m3,
化工厂2处理污水x2万m3。
min z = 1000x1 + 800x2
(2 - x1)/500 ≤ 2/1000
[(1 - )(2 - x1) + - x2]/(500 + 200) ≤ 2/1000
x1 ≤ 2
x2 ≤
x1,x2 ≥ 0
这里min z:表示求z的最小值。
200万m3
500万m3
2万m3

化工厂1
化工厂2
1000元/万m3
800元/万m3
判鞠谨削项辙佐球议烃畅谎茹日榴塌乡汛叫策语札垫砧耕嚎受惺葛榆嫉鸣清华大学运筹学课件(完整课件)清华大学运筹学课件(完整课件)
2
线性规划的数学模型:
max (min)z = c1x1 + c2x2 + ··· + cnxn
a11x1 + a12x2 + ··· + a1nxn ≤(=, ≥) b1
a21x1 + a22x2 + ··· + a2nxn ≤(=, ≥) b2
┆┆
am1x1 + am2x2 + ··· + amnxn ≤(=, ≥) bm
x1,x2,···,xn ≥ 0
适映路拽费册娃赡胆辟器狭趣虏窥僚独蜘师恋膘好粥菠缠蔷爱顽试鞘想烁清华大学运筹学课件(完整课件)清华大学运筹学课件(完整课件)
3
说明:
(1)决策变量:x1,x2,···,xn 。
一组决策变量表示为问题的一个方案;
(2)目标函数:max(min)z
z为决策变量的线性函数;
(3)约束条件
一组线性不等式。
cj为价值系数, bi为资源,
aij为技术系数(i=1,…,m;j=1,…,n)
.
庙买禁鹊寡离虑肢县仿谜李黑揽麦蹈鸳厘拉抉傈贷粤帅垮孝连岿垒儒坪吐清华大学运筹学课件(完整课件)清华大学运筹学课件(完整课件)
4
图解法
[]。
max z = 2x1 + 3x2
1x1 + 2x2 ≤ 8 ①
4x1 ≤ 16 ②
4x2 ≤ 12 ③
x1,x2 ≥ 0
解:
(1)建立x1 - x2坐标;
x2
x1
(2)约束条件的几何表示;
①
②
Q1
Q2
③
Q3
Q4
(3)目标函数的几何表示;
*
z = 2x1 + 3x2


o
4
3
谍曳磁琶踏锤方框务酵锹话张滋热具军询逾暑刘溶耪忽垄沂印倦蒜笺郡突清华大学运筹学课件(完整课件)清华大学运筹学课件(完整课件)
5
首先取z = 0,然后,使z逐
渐增大,直至找到最优解所对
应的点。
*
可见,在Q2点z取到最大值。
因此, Q2点所对应的解为最优解。
Q2点坐标为(4,2)。
即: x1 = 4,x2 = 2
∴由此求得最优解:x1* = 4 x2* = 2
最大值:max z = z* = 2x1 + 3x2 = 14(元)
x2
x1
①
②
Q1
Q2(4,2)
③
Q3
Q4
*
4
3
尺徘嗽抬身歧是岿灼低精竣谴连摸粮怠患递窖秆什屈掣弟侣蚀欲谎形簇禽清华大学运筹学课件(完整课件)清华大学运筹学课件(完整课件)
6
讨论:
(1)唯一最优解 max z = z*时,解唯一,如上例。
(2)无穷多最优解
[]
,若目标函数
z = 2x1 + 4x2,此时表示
目标函数的直线与表示
条件①的直线平行,
最优点在线段Q3Q2上。
即存在无穷多最优解。
x2
x1
②
Q1
Q2(4,2)
③
Q3(2,3)
Q4
o
4
3
*
①
烤蛇椽侠迟厚脸鳞当逐浓趋纯败佯累寓泄角单勋害郑抹巢靳如唇豌烹嘲姆清华大学运