上海海事大学 2005项目管理工程硕士课程——系统工程

killl

系统优化
2005.11.6
上海海事大学 经济管理学院
上海海事大学 2005项目管理工程硕士课程——系统工程
大纲
线性规划简介
线性规划研究的主要问题
线性规划的基本概念
线性规划模型及标准形式
线性规划数学模型的建立
线性规划图解法
线性规划解的概念及性质
单纯形法
线性规划简介
线性规划( Linear Programming,LP )是运筹学中最重要的一个分支,也是其他运筹学分支的基础.
线性规划最典型的应用背景是限资源的优化配置问题,它是由于受到30年代关于线性经济模型讨论的影响和列昂惕夫(W.Leontief )的投入产出模型的促进,以吸取在第二次世界大战时期盟军后勤工作的实际经验总结而发展起来的.
自1947年,美国数学家丹惕格(G.B.Dantzig)提出了求解线性规划问题的方法——单纯形法之后,线性规划在理论上就趋于成熟.目前,随着计算机的普及,它已成为一种强有力的定量分析工具,广泛地应用于军事,科学研究,工程技术,经济和管理等几乎所有领域,并在不断提高国民经济的计划,管理水平和企事业单位的经营管理决策水平方面起着越来越重要的作用.
线性规划简介
线性规划的发展
1939年,前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题
1947年,Dantzig提出求解线性规划的单纯形法
1950-1956年,主要研究线性规划的对偶理论
1958年,发表整数规划的割平面法
1960年,Dantzig和Wolfe研究成功分解算法,奠定了大规模线性规划问题理论和算法的基础.
1979年,Khachiyan,1984年,Karmarkaa研究成功线性规划的多项式算法.
线性规划研究的主要问题
一类是已有一定数量的资源(人力,物质,时间等),研究如何充分合理地使用它们,才能使完成的任务量为最大.
—— 实际上,上述两类问题是一个问题的两个不同的方面,都是求问题的最优解( max 或 min ).
另一类是当一项任务确定以后,研究如何统筹安排,才能使完成任务所耗费的资源量为最少.
例1 某厂生产两种产品,下表给
出了单位产品所需资源及单位产品
利润
问:应如何安排生产计划,才能使
总利润最大
解:
1.决策变量:设产品I,II的产量分
别为 x1,x2
2.目标函数:设总利润为z,则有:
max z = 2 x1 + 3 x2
3.约束条件:
x1 + 2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12