第三章 线性规划.ppt

文档介绍：第三章线性规划
线性规划(Linear Programming,简称LP)是运筹学
的一个重要分支,
线性规划的发展列为20世纪中期最重要的科学进步之一。
1939年,苏联数学家康脱洛维奇研究并发表了《生产组织
与计划的数学方法》一书,首次提出了线性规划问题,
1947年美国数学家丹捷格提出求解线性规划的一般方法
—
随着计算机技术的迅速发展,大型线性规划问题的迅速
求解成为可能,从而使线性规划的应用范围日益广泛.
目前,线性规划已广泛应用于工业、农业、商业、交通
运输、经济管理和国防等部门的计划管理与决策分析,
成为现代管理的有力工具之一.
本章主要内容
LP问题的提出及其数学模型
LP问题的解及其性质
单纯形法
大M法与两阶段法
第一节问题的提出及数学模型
线性规划问题的提出
线性规划问题的数学模型

线性规划模型的标准化
一、线性规划问题的提出
现实生活中,我们经常面临这种情况,有许多活动
要完成,同时存在为完成这些活动可供选择的多种方法。
但是,由于有时某些资源有限,这就有一个稀少资源的

:一类是给定了一
定数量的人力、物力、财力资源,研究如何运用这些资
源使完成的任务最多;另一类是给定了一项任务,研究
如何统筹安排,才能以最少的人力、物力、财力等资源
来完成该项任务.
例1 生产计划问题
某工厂生产甲、乙两种产品,这两种产品都需要在A、B、C三
、乙产品在不同的设备上加工所需的台
时数,它们销售后所能获得的利润值以及这三种加工设备在计划期
内能提供的有限台时数列于表3-:如何安排生产计划,即
甲、乙两种产品各生产多少吨,方可使该厂所得利润最大?
表 3-1
解:设在计划期内甲、乙两种产品的产量分别为、
吨
目标函数

约束条件
例2、营养配餐问题
有A、B两种食品,含有每天必须的营养成分C和D,

和B的成分和单价如表3-
使费用最省?
表 3-2
解:设每天购买食品A、B分别为, 个单位

目标函数
约束条件
例3、合理下料问题
有一批某种型号的圆钢长8m,
坯100根,,问怎样选择下料方式,才
能既满足需要,又使总的用料最少?(各种可能的搭配
方案如表3-3所示).
表 3-3