文档介绍：第一章线性规划 (Linear Programming )
运筹学的一个重要分枝
研究较早
发展较快
理论较成熟
应用极为广泛
简记为LP
典型的线性规划的在经济管理上的应用举例:
1、合理利用线材问题:
现有一批长度一定的钢管,由于生产的需要,
要求截出不同规格的钢管若干。试问应如何
下料,既满足了生产的需要,又使得使用的
原材料钢管的数量最少。
2、配料问题:
用若干种不同价格不同成分含量的原料,
用不同的配比混合调配出一些不同价格不同
规格的产品。在原料供应量的限制和保证产
品成分的含量的前提下,如何获取最大的利润。
3、投资问题:
从不同的投资项目中选出一个投资方案,使投
资的回报最大。
4、产品生产计划:
合理充分利用厂里现有的人力、物力、才力,
作出最优的产品生产计划,使得工厂获利最大。
5、劳动力安排:
某单位由于工作需要,在不同时间段需要不同
数量的劳动力,在每个劳动力工作日连续工作
8小时的规定下,如何安排劳动力,才能用最少
的劳动力来满足工作的需要。
6、运输问题:
一个公司有若干个生产单位与销售单位,根据
各生产单位的产量及销售单位的情况,如何制定
调运方案,将产品运到各销售单位而总的运费最少。
线性规划研究的问题:
1、在现有的人、财、物等资源的条件下,
研究如何合理地计划、安排,可使得
某一目标达到最大,
寻求在一定约束条件下使某个指标达到最优
如产量、利润等。
2、在任务确定后,如何计划、安排,使
用最少的人、财、物等资源,去实现
该任务,
如使生产成本、费用最少等。
§ 线性规划的基本概念
线性规划模型
一、线性规划问题举例
例1 (生产安排问题)假定某工厂生产甲、乙、丙三种产品,每种产品都要经过三种不同的工序加工。每一件产品所需要的加工时间(分钟)和每天对各道工序的加工能力(每天多少分钟)以及销售各种产品的单位利润如下表所示:
假定所生产的三种产品都能全部售出,问这三种产品每天要各生产多少件才能使得获得的利润最大?
设:
决策变量
目标函数
对第三道工序,有
对第二道工序,有
对第一道工序,有
约束条件
非负性约束条件
问题归结为:
目标函数:
线性
例2 (营养搭配问题) 如果有甲、乙、丙、丁四种食品,都含有不同成分的维生素,其含量和单价如下表所示
现在我们希望每天得到的维生素不少于所规定的最低需要量,问应该如何搭配各种食品才能使所花的费用最少?
解:
约束条件:
决策变量:
问题归结为:
线性
二、线性规划模型的建立
1、建模的一般步骤:
步骤一:确定决策变量
即用变量取不同的值来表示可供选择的各种不同方案
步骤二:建立目标函数
即找到目标值与决策变量的数量关系
步骤三:确定约束条件
即决策变量所受到的外界条件的制约。
约束条件一般为决策变量的等式或不等式
要求:目标函数与约束条件均是线性的,
且目标函数只能是一个。