文档介绍：运筹学
Operations Research
Chapter 1 线性规划
Linear Programming
LP的数学模型 Mathematical Model of LP
图解法 Graphical Method
标准型 Standard form of LP
基本概念 Basic Concepts
单纯形法 Simplex Method
7/20/2017
数学模型
Mathematical Model
7/20/2017
线性规划的数学模型 Mathematical Model of LP
线性规划(Linear Programming,缩写为LP)通常研究资源的最优利用、设备最佳运行等问题。例如,当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)。
7/20/2017
【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定,每件产品甲需要消耗材料A 2公斤,消耗材料B 1公斤,每件产品乙需要消耗材料A 1公斤,消耗材料B 。已知在计划期内可供材料分别为40、30公斤;每生产一件甲、乙两产品,企业可获得利润分别为300、400元,如表1-1所示。假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大。
线性规划的数学模型 Mathematical Model of LP
应用模型举例
7/20/2017
【解】设x1、x2分别为甲、乙产品的产量,数学模型为:
线性规划的数学模型 Mathematical Model of LP
产品
资源
甲
乙
现有资源
材料A
2
1
40
材料B
1
30
利润(元/件)
300
400
表1-1
7/20/2017
线性规划的数学模型由
决策变量 Decision variables
目标函数Objective function
及约束条件Constraints
构成。称为三个要素。
其特征是:
线性函数,通常是求最大值或最小值;
的线性不等式或等式。
怎样辨别一个模型是线性规划模型?
线性规划的数学模型 Mathematical Model of LP
7/20/2017
【例1-2】某超市决定:营业员每周连续工作5天后连续休息2天,轮流休息。根据统计,超市每天需要的营业员如表1-2所示。
表1-2 营业员需要量统计表
超市人力资源部应如何安排每天的上班人数,使超市总的营业员最少。
星期
需要人数
星期
需要人数
一
300
五
480
二
300
六
600
三
350
日
550
四
400
线性规划的数学模型 Mathematical Model of LP
7/20/2017
【解】设xj (j=1,2,…,7)为休息2天后星期一到星期日开始上班的营业员,则这个问题的线性规划模型为
线性规划的数学模型 Mathematical Model of LP
星期
需要人数
星期
需要人数
一
300
五
480
二
300
六
600
三
350
日
550
四
400
7/20/2017
1
X1
0
C1
404
>=
300
104
2
X2
67
C2
301
>=
300
1
3
X3
146
C3
350
>=
350
0
4
X4
170
C4
400
>=
400
0
5
X5
97
C5
480
>=
480
0
6
X6
120
C6
600
>=
600
0
7
X7
17
C7
550
>=
550
0
最优解:
Z=617(人)
线性规划的数学模型 Mathematical Model of LP
注:表中是取整数后的结果!整数规划将在第3章讲解。
7/20/2017
【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根,,1,(m),这些轴需要用同一种圆钢来做,圆钢长度为4 m。现在要制造1000辆汽车,最少要用多少圆钢来生产这些轴?
【解】这是一个条材下料问题,设切口宽度为零。