3
线性规划
【开篇案例】
二、生产计划的问题
明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工 和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自 行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问： 公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、 乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
则该问题的数学模型表示为
maxZ= 2x1 +3x2
2x1+2x2 ≤12 x1 +2x2 ≤8 设生产Ⅰ、Ⅱ产品为x1、x2件 4x1 ≤16 4x2 ≤12 问题：建立线性规划模型要考虑的关键要素？ x ≥0, x ≥0 1 2 10
线性规划
maxZ= 2x1 +3x2 2x1+2x2 ≤12 x1 +2x2 ≤8 4x1 ≤16 4x2 ≤12 x1 ≥0, x2 ≥0
产地
A1 A2 A3 销量
销地 B1
B2
B3
B4
产量
6 7 3 2
3 5 2 3
2 8 9 1
5 4 7 4
5 2 3
17
线性规划
销地
建立模型： A
1
产地
B1
B2
B3
x13
B4
x14 5
2
A2 A3 销量
x24 7 x21 5x22 8 x23 4
3 x31 2x32 9 x33 7 x34
线性规划是一种合理利用资源、合理调配资源的应用数学 方法。 其中：规划就是利用某种数学方法使得有效资源的运用最 优化；线性就是用来描述就是之间关系的函数是线性函数。
8
线性规划
在管理中一些典型的线性规划应用
在生产管理和经济活动中经常提出这样一类问题， 即如何 合理地利用有限的人力、物力、财力等资源，以便得到最好的 经济效果。 主要包括：
约束条件
任何问题都是限定在一定的条件下求解，把各种限制条件表示为 一组等式或不等式，称之为约束条件。如设备能力、原材料数量等 约束条件是决策方案可行的保障。 约束条件的基本类型：大于等于“≥”、等于“＝”、小于等于 11 “≤”
线性规划
二、线性规划模型的构建
线性规划建模步骤：
明确问题，确定目标，列出约束条件； 收集资料，确立模型；
9
问题：如何建立线性规划模型？
线性规划
§1.1 一般线性规划问题的数学模型
【引例】生产计划的问题
设备A 设备B 设备C 设备D 利润
产品1 2 1 4 0 2
产品2 2 2 0 4 3
资源量 12 8 16 12
某企业生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D 四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、4、0小时， 生产每件产品Ⅱ 需占用各设备为2、2、0、4小时，各设备用于生产这 两种产品的能力分别为12、8、16、12小时，又知生产一件产品Ⅰ获得2 元，生产Ⅱ 获得3元，问如何安排生产，使总的利润最大。
18
线性规划
【例3】营养问题
某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混 合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲 料中第 i 种营养成份的含量不能低于 bi ( i= 1,2, …, m）。已知 第 i 种营养成份在每单位的第 j 种配料中的含量为 aij , j = 1,2, …, n，每单位的第 j 种配料的价格为 cj 。现在要求在保证营养条件 的前提下，应采用何种配方，使混合饲料的成本最小.
maxZ= 3x1 +5 x2
≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 x1
15
目标函数
约束条件
线性规划
【引例】生产计划的问题
某企业生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、 C、D四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、 4、0小时，生产每件产品Ⅱ 需占用各设备为2、2、0、4小时，各 设备用于生产这两种产品的能力分别为12、8、16、12小时，又知 生产一件产品Ⅰ获得2元，生产Ⅱ 获得3元，问如何安排生产，使 maxZ= 2x1 +3x2 总的利润最大。 则该问题的数学模型表示为
配料
营养成份
B1
B2
…
Bn
含量 b1 b2 bm
19
A1 A2
…
a11 a21
a12 a22
… …
a1n a2n amn cn
Am 单价
am1 am2 … c1 c2 …
线性规划
配料 营养成份 A1 A2
…
B1 a11 a21 a12 a22
B2 … …
… a1n a2n amn cn
Bn
含量 b1 b2 bm
建立模型：
Am 价格
am1 am2 … c1 c2 …
设xj 表示在单位混合饲料中，第j 种配料的含量（ j =1,2,…,n） 则有如下的数学模型：
MinZ=c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … + a1nxn ≥ b1 a21x1 + a22x2 + … + a2nxn ≥ b2 …… am1x1 + am2x2 + … + amnxn ≥ bm
合理利用线材问题：如何下料使用材最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大
产品生产计划：合理利用人力、物力、财力等，使获利最大
劳动力安排：用最少的劳动力来满足工作的需要
运输问题：如何制定调运方案，使总运费最小
盈亏平衡问题：掌握企业盈亏界限，合理安排生产能力
班次 1 2 3 4 5 6 时间 6：00 —— 10：00 10：00 —— 14：00 14：00 —— 18：00 18：00 —— 22：00 22： —— 2：00 2：00 —— 6：00 所需人数 60 70 60 50 20 30
设司机分别在各时间段一开始时上班，并连续工作八小时， 问该公交线路怎样安排司机，既能满足工作需要，又配备最少 司机?
13
线性规划
产品 车间 A B C 单位产品获利 甲
工时单耗 乙 0 2 4 5 1 0 3 3
生产能力 8 12 36
建立模型：
(1) 决策变量
要决策的问题是甲、乙两种产品的产量，因此有两个决 策变量：设x1为甲产品产量，x2为乙产品产量。 (2) 约束条件 生产这两种产品受到现有生产能力的制约，用量不能突破。 生产单位甲产品的零部件需耗用A车间的生产能力1工时， 生产单位乙产品不需耗用A车间的生产能力，A车间的能力总量 限制为8工时，则A车间的能力约束条件表述为 x1 ≤8 同理，B和C车间能力约束条件为 2x2 ≤12 3x1 +4 x2 ≤36
(1)决策变量: 设从Ai到Bj的运输量为xij，
(2)目标函数: 则运费最小的目标函数为
2
3
1
4
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
(3) 约束条件: 产量之和等于销量之和,故要满足 供应平衡条件 x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3 销售平衡条件 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4 条件非负性约束 xij≥0 (i=1,2,3；j=1,2,3,4)
x1 ≥0, x2 ≥0 ,… , xn≥0
甲 5 6 3 3 5 2 3 23 乙 10 4 2 5 6 1 2 18 丙 7 8 2 4 -3 2 16 资源限制 8000 12000 10000
铸造工时(小时/件) 机加工工时(小时/件) 装配工时(小时/件) 自产铸件成本(元/件) 外协铸件成本(元/件) 机加工成本(元/件) 装配成本(元/件) 产品售价(元/件)
模型求解与检验
优化后的分析
其中：最为困难的是建模
12
线性规划
【例1】生产计划问题
某厂生产甲乙两种产品，各自的零部件分别在A、B车间 生产，最后都需在C车间装配，相关数据如表所示：
产品 车间 A B C 单位产品获利 工时单耗 甲 乙 1 0 3 3 0 2 4 5 生产能力 8 12 36
问如何安排甲、乙两产品的产量，使利润为最大。
项目 A B C D 风险指数（次/万元） 1 3 4 5.5
问：a.应如何确定这些项目的每年投资额，使得第五年年末拥有资 金的本利金额为最大？ b.应如何确定这些项目的每年投资额，使得第五年年末拥有资 6 金的本利在330万元的基础上使得其投资总的风险系数为最小？
线性规划
归纳上述研究的主要内容：
设生产Ⅰ、Ⅱ产品为x1、x2件
设备A 设备B 设备C 设备D 利润
产品1 2 1 4 0 2
产品2 2 2 0 4 3
资源量 12 8 16 12
2x1+2x2 ≤12 x1 +2x2 ≤8 4x1 ≤16 4x2 ≤12 x1 ≥0, x2 ≥0
16
线性规划
【例2】运输问题
某名牌饮料在国内有三个生产厂，分布在城市A1、A2, A3, 其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂 的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij， 为发挥集团优势，公司要统一筹划运销问题，求运费最小的调 运方案。