文档介绍：运筹学
Operations Research
Chapter 1 线性规划
Linear Programming
LP的数学模型 Mathematical Model of LP
图解法 Graphical Method
标准型 Standard form of LP
基本概念 Basic Concepts
单纯形法 Simplex Method
11/12/2017
数学模型
Mathematical Model
11/12/2017
线性规划的数学模型 Mathematical Model of LP
线性规划通常研究资源的最优利用、设备最佳运行等问题。例如,当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)。
线性规划(Linear Programming,缩写为LP)是运筹学的重要分支之一,在实际中应用得较广泛,其方法也较成熟,借助计算机,使得计算更方便,应用领域更广泛和深入。
11/12/2017
【】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工,需要消耗材料C、D,按工艺资料规定,。已知在计划期内设备的加工能力各为200台时,可供材料分别为360、300公斤;每生产一件甲、乙、丙三种产品,企业可获得利润分别为40、30、50元,假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大?
线性规划的数学模型 Mathematical Model of LP
应用模型举例
11/12/2017
产品
资源
甲
乙
丙
现有资源
设备A
3
1
2
200
设备B
2
2
4
200
材料C
4
5
1
360
材料D
2
3
5
300
利润(元/件)
40
30
50
产品资源消耗
线性规划的数学模型 Mathematical Model of LP
11/12/2017
【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型为:
线性规划的数学模型 Mathematical Model of LP
产品
资源
甲
乙
丙
现有资源
设备A
3
1
2
200
设备B
2
2
4
200
材料C
4
5
1
360
材料D
2
3
5
300
利润(元/件)
40
30
50
最优解X=(50,30,10);Z=3400
11/12/2017
线性规划的数学模型由
决策变量 Decision variables
目标函数Objective function
及约束条件Constraints
构成。称为三个要素。
其特征是:
线性函数,通常是求最大值或最小值;
的线性不等式或等式。
怎样辨别一个模型是线性规划模型?
线性规划的数学模型 Mathematical Model of LP
11/12/2017
【】某商场决定:营业员每周连续工作5天后连续休息2天,轮流休息。根据统计,。
营业员需要量统计表
商场人力资源部应如何安排每天的上班人数,使商场总的营业员最少。
星期
需要人数
星期
需要人数
一
300
五
480
二
300
六
600
三
350
日
550
四
400
线性规划的数学模型 Mathematical Model of LP
11/12/2017
【解】设xj(j=1,2,…,7)为休息2天后星期一到星期日开始上班的营业员,则这个问题的线性规划模型为
线性规划的数学模型 Mathematical Model of LP
星期
需要人数
星期
需要人数
一
300
五
480
二
300
六
600
三
350
日
550
四
400
11/12/2017
1
X1
0
C1
404
>=
300
104
2
X2
67
C2
301
>=
300
1
3
X3
146
C3
350
>=
350
0
4
X4
1