运筹学与最优化方法第4章.ppt

第四章
线性规划
本章内容
线性规划问题及其数学模型
线性规划的图解法
线性规划解的基本性质
单纯形算法
初始基本可行解求法
对偶性及对偶单纯形方法
线性规划灵敏度分析
线性规划的建模实例
用数学软件求解线性规划模型介绍
运筹学
线性规划
线性规划研究的主要问题
一类是已有一定数量的资源(人力、物质、时间等),研究如何充分合理地使用它们,才能使完成的任务量为最大。
另一类是当一项任务确定以后,研究如何统筹安排,才能使完成任务所耗费的资源量为最少。
——实际上,上述两类问题是一个问题的两个不同的方面,都是求问题的最优解( max 或 min )。
线性规划(Linear Programming)创始人:(Dantzing)
1951年提出单纯形算法(Simpler method)
线性规划
运筹学
一、线性规划问题的提出(资源分配问题):某工厂生产门窗两种产品,已知的条件如表所示,试制订总利润最大的生产计划。
§ 线性规划问题及数学模型
问题分析
运筹学
线性规划
模型
运筹学
线性规划
用Excel软件求解:
产品门生产2件
产品窗生产6件
最大利润3600(元)
:某公司有100万元资金要投资(要求全部用完)。该公司有六个投资项目可选,已知的条件如表所示,该公司希望投资风险最小,,最低平均增长率为12%,最低平均信用度为7。试解该问题。
运筹学
线性规划
模型
用Excel软件求解:
项目1投资25万元
项目2投资0万元


项目5投资0万元
项目6投资0万元
%
:
运筹学
线性规划
B1
B2
…
Bn
A1
A2
…
A3
c11
c21
…
cm1
c12
c22
…
cm2
…
…
…
…
c1n
c2n
…
cmn
单位运价表(cij)
B1
B2
B3
B4
产量
A1
A2
…
A3
x11
X21
…
xm1
x12
X22
…
xm2
…
…
…
…
x1n
X2n
…
xmn
a1
a2
…
am
销量
b1
b2
…
bn
产销平衡表(决策变量xij=0或1)