Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第四章
Linear Programming,
Formulation and Applications
线性规划：建模与应用
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
本章内容（ Topics） P91
Introduction the Key Categories of LP Problems
介绍线性规划问题的三种主要类型（取决于函数约束）：
资源分配问题（ resource-allocation,?）
成本收益平衡问题 （ cost-benefit-trade-off,?）
网络配送问题（ distribution-network,=）
混合问题（ mixed Problem）－两种或三种类型的混合
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Case Study:Super Grain Corp,Advertising-Mix Problem
4.1 案例研究：超级食品公司的广告组合问题 P92
超级食品公司如何才能大规模地进入已有许多供应商的早餐谷物食品市场。
委托了一家一流的广告公司来帮助设计全国性的促销活动，以使,脆始,（ Crunchy Start）取得尽可能多的消费者的认可。
费用情况：最多可以给广告商的酬金 100万和 400万的广告费
广告公司确定了这一产品最有效的三种广告媒介：
媒介 1：星期六上午儿童节目的电视广告。
媒介 2：食品与家庭导向的杂志上的广告。
媒介 3：主要报纸星期天增刊上的广告。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数据 P93
成本（美元）
成本分类 每次电视广告 每份杂志广告 每份星期天增刊广告广告预算 $300,000 $150,000 $100,000
策划预算 90,000 30,000 40,000
广告受众期望值 1,300,000 600,000 500,000
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Excel模型 P95
注意 P96-97：
结果是否符合实际情况：不做电视广告？
模型准确性评价 P96：数学模型是否真的体现实际情况
P 9 2 超级谷物公司的广告组合问题 ( S u p e r G r a i n C o r p,A d v e r t i s i n g - M i x P r o b l e m )
电视广告 TV 杂志广告 M 星期天增刊广告 SS
每次广告受众数量 1,3 0 0 600 500
( 千人次 )
使用资金 可用预算广告预算 300 150 100 4,0 0 0 <= 4,0 0 0
策划预算 90 30 40 1,0 0 0 <= 1,0 0 0
电视广告 TV 杂志广告 M 星期天增刊广告 SS 广告受众总量广告数量 0 20 10 1 7,0 0 0
<=
最多电视时段 5
每次广告成本（千美元）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数学模型 P96
决策变量：
TV－电视上的广告时段数目
M －杂志上的广告数目
SS－星期天增刊上的广告数目目标函数,广告受众总量 最大化
Max z=1300TV+600M+500SS
约束条件：
广告费用,300TV+150M+100SS? 4000
策划成本,90TV+ 30M+ 40SS? 1000
电视广告时段,TV? 5
且非负,TV,M,SS? 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型
Resource-allocation Problem
4.2 资源分配问题 P99
资源分配（ resource-allocation） 问题 是将有限的资源分配到各种活动中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数限制均为 资源限制 (resource constraint),并且每一种有限资源都可以表现为如下的形式：
使用的资源数量?可用的资源数量
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Datum Gathering
收集数据 P100
对任何资源分配问题，有三种数据必须收集：
1,每种资源的可供量（可用量）
2、每一种活动所需要的各种资源的数量,对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来（ 单位资源使用量 ）
3、每一种活动对总的绩效测度的单位贡献（ 单位利润 ）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例
Think-Big Development Co.
梦大发展公司资金预算问题 P101
梦大 (Think-Big)发展公司是商务房地产开发项目的主要投资商。
目前，该公司有机会在三个建设项目中投资：
建造高层办公楼 Construct a high-rise office building
建造宾馆 Construct a hotel
建造购物中心 Construct a shopping center
每个项目都要求投资者在四个不同的时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资。
可以 按比例 投资项目
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
梦大发展公司部分投资项目的财务数据 P101
所需投资资金（百万美元）
Year 办公楼项目 宾馆项目 购物中心项目
0（当前） 40 80 90
1 60 80 50
2 90 80 20
3 10 70 60
净现值 NPV
(Net Present Value) 45 70 50
现在可用资金
2500万美元，
一年后又有 2000
万美元，
两年后又有 2000
万美元，
三年后再有 1500
万美元
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Excel模型 P104
注意 P102-103：
由于 前一期尚未使用的资金，可以在下一期使用,所以每一时点的资源限制都必须表现为累计的资金
想求每一个项目的 投资比例办公楼项目 宾馆项目 购物中心项目单位净现值 45 70 50 单位：百万美元使用的累计资金额可获得的累计资金额现在 40 80 90 25 <= 25
一年后 100 160 140 4 4,7 6 <= 45
二年后 190 240 160 6 0,5 8 <= 65
三年后 200 310 220 80 <= 80
办公楼项目 宾馆项目 购物中心项目 总净现值投资比例 0,0 0 % 1 6,5 0 % 1 3,1 1 % 1 8,1 1
单位累计资金需求量
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数学模型 P105
决策变量,OB - 办公楼项目中的投资比例
H - 宾馆项目中的投资比例
SC - 购物中心项目中的投资比例目标函数,总净现值 最大化
Max NPV = 45OB + 70H + 50SC
约束条件：
现在的总投资,40OB + 80H + 90SC? 25 ($million)
1年后的总投资,100OB + 160H + 140SC? 45 ($million)
2年后的总投资,190OB + 240H + 160SC? 65 ($million)
3年后的总投资,200OB + 310H + 220SC? 80 ($million)
且非负,OB,H,SC? 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
方法 2
1,用第三章 P65现金流管理的方法
2,前一期尚未使用的资金，可以在下一期使用
3,增加：实际每期所需投资资金、可用资金、资金余额、每年资金等详细信息。
P 1 0 4 梦大发展公司资金预算问题 T h i n k - B i g D e v e l o p m e n t C o,C a p i t a l B u d g e t i n g P r o b l e m
办公楼项目 宾馆项目 购物中心项目单位净现值 45 70 50
办公楼项目 宾馆项目 购物中心项目 办公楼项目 宾馆项目 购物中心项目 总投资额 可用资金 资金余额 每年资金现在 40 80 90 0,0 0 1 3,2 0 1 1,8 0 25 <= 25 0 25
一年后 60 80 50 0,0 0 1 3,2 0 6,5 5 20 <= 20 0 20
二年后 90 80 20 0,0 0 1 3,2 0 2,6 2 16 <= 20 4 20
三年后 10 70 60 0,0 0 1 1,5 5 7,8 6 19 <= 19 0 15
办公楼项目 宾馆项目 购物中心项目 总净现值投资比例 0,0 0 % 1 6,5 0 % 1 3,1 1 % 1 8,1 1
单位所需投资资金单位：百万美元实际每期所需投资资金
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
方法 2的数学模型 (补充 )
决策变量,OB - 办公楼项目中的投资比例
H - 宾馆项目中的投资比例
SC - 购物中心项目中的投资比例
R0,R1,R2,R3为各年的资金余额目标函数,总净现值 最大化
Max NPV = 45OB + 70H + 50SC
约束条件：
现在的投资,40OB + 80H + 90SC ＋ R0＝ 25 ($million)
1年后的投资,60OB + 80H + 50SC ＋ R1＝ 20 ＋ R0 ($million)
2年后的投资,90OB + 80H + 20SC ＋ R2＝ 20＋ R1($million)
3年后的投资,10OB + 70H + 60SC ＋ R3＝ 15 ＋ R2($million)
且非负,OB,H,SC? 0,Ri? 0（ i＝ 0,1,2,3）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型
Cost-benefit-trade-off Problem
4.3 成本收益平衡问题 P106
成本收益平衡问题（ Cost-benefit-trade-off Problem ）
是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以 最小的成本 来实现最低可接受的各种收益水平。这类问题的共性是，所有的函数约束均为 收益约束,并具有如下的形式：
完成的水平? 最低可接受的水平
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
成本收益平衡问题需要的三种数据 P107
1、每种收益的 最低可接受水平 （管理决策）
2、每一种活动对每一种收益的贡献（ 单位活动的贡献 ）
3、每种活动的 单位成本
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例
P108 联邦航空公司人员排班问题
Union Airways Personnel Scheduling Problem
请看书 P108-112和第 4章相应的 Excel文件
Excel模型 P110
早 6 点 班 早 8 点班 中午班 下午 4 点班 晚 10 点班单位成本 $170 $160 $175 $180 $195
时段 在岗人数 所需的最少人数
6 a m - 8 a m 1 48 >= 48
8 a m - 1 0 a m 1 1 79 >= 79
1 0 a m - 1 2 p m 1 1 79 >= 65
1 2 p m - 2 p m 1 1 1 118 >= 87
2 p m - 4 p m 1 1 70 >= 64
4 p m - 6 p m 1 1 82 >= 73
6 p m - 8 p m 1 1 82 >= 82
8 p m - 1 0 p m 1 43 >= 43
1 0 p m - 1 2 a m 1 1 58 >= 52
1 2 a m - 6 a m 1 15 >= 15
早 6 点 班 早 8 点班 中午班 下午 4 点班 晚 10 点班 总人数 总成本每班人数 48 31 39 43 15 176 $ 3 0,6 1 0
是否在岗 S h i f t W o r k s T i m e P e r i o d? ( 1 = y e s,0 = n o )
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
P108 联邦航空公司人员排班问题（续）
代数模型 P111
决策变量,设 Si 为轮班 i的人数 (i = 1,2,3,4,5)
目标函数,总成本 最小化
Min C = $170S1 + $160S2 + $175S3 + $180S4 + $195S5
约束条件：
6AM–8AM,S1? 48
8AM–10AM,S1 + S2? 79
10AM–12PM,S1 + S2? 65
12PM–2PM,S1 + S2 + S3? 87
2PM–4PM,S2 + S3? 64
4PM–6PM,S3 + S4? 73
6PM–8PM,S3 + S4? 82
8PM–10PM,S4? 43
10PM–12AM,S4 + S5? 52
12AM–6AM,S5? 15
且非负,Si? 0 (i = 1,2,3,4,5)
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型
Distribution-network Problem
4.4 网络配送问题 P113
网络配送问题 （ distribution network）能以最小的成本完成货物的配送，所以称之为网络配送问题并具有如下的确定性约束形式：
提供的数量＝需求的数量
（平衡运输问题：总供应＝总需求）
确定需求的约束
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例
P113 大 M公司网络配送问题
(Big M Company Distribution Problem)
请看书 P113-117
和第 4章相应的
Excel文件
代数模型 P116和
Excel模型 P116
右图为配送网络图
F 1
C 2
C 3
C 1
F 2
1 2 l a t h e
p r o d u c e d
1 5 l a t h e s
p r o d u c e d
1 0 l a t h e s
n e e d e d
8 l a t h e s
n e e d e d
9 l a t h e s
n e e d e d
$700 / l a t he
$900 / l a t he
$800 / l a t he
$800 / l a t he $900 / l a t he
$700 / l a t he
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
P113 大 M公司网络配送问题（续）
Excel模型 P116（平衡运输问题：总供应＝总需求 ）
单位运输成本 顾客 1 顾客 2 顾客 3
工厂 1 $700 $900 $800
工厂 2 $800 $900 $700
运输量 顾客 1 顾客 2 顾客 3 实际运出 可运出工厂 1 10 2 0 12 = 12
工厂 2 0 6 9 15 = 15
运往顾客 10 8 9
= = = 总成本订货量 10 8 9 $ 2 0,5 0 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
P113 大 M公司网络配送问题（续）
代数模型 P116 （平衡运输问题：总供应＝总需求 ）
决策变量,设 Sij 为从工厂 i 运输到顾客 j的车床数量 (i = F1,F2; j = C1,C2,C3)
目标函数,总成本 最小化
Min C = $700SF1-C1 + $900SF1-C2 + $800SF1-C3
+ $800SF2-C1 + $900SF2-C2 + $700SF2-C3
约束条件,
工厂 1,SF1-C1 + SF1-C2 + SF1-C3 = 12
工厂 2,SF2-C1 + SF2-C2 + SF2-C3 = 15
顾客 1,SF1-C1 + SF2-C1 = 10
顾客 2,SF1-C2 + SF2-C2 = 8
顾客 3,SF1-C3 + SF2-C3 = 9
且 非负,Sij? 0 (i = F1,F2; j = C1,C2,C3)
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Continuing the Super Grain Case Study
4.5 超级食品公司案例的再研究 P117
原问题（ 4.1节）为资源分配问题（?）
现在增加两个目标（?）：
目标 1：必须至少有 500万儿童看到该广告
目标 2：必须至少有 500万儿童的家长看到该广告
将剩余的优惠券预算 1,490,000美元全部用完（ =）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
4.5 超级食品公司案例的再研究 （续）
电视广告 TV 杂志广告 M 星期天增刊广告 SS
广告受众期望值 1,3 0 0 600 500
( 千人次 )
实际使用 可用预算广告预算 300 150 100 3,7 7 5 <= 4,0 0 0
策划预算 90 30 40 1,0 0 0 <= 1,0 0 0
实际人次 最低可接受水平儿童 1,2 0,1 0 5 >= 5
儿童家长 0,5 0,2 0,2 5,8 5 >= 5
电视广告 TV 杂志广告 M 星期天增刊广告 SS 实际数量 需求数量优惠券 0 40 120 1,4 9 0 = 1,4 9 0
电视广告 TV 杂志广告 M 星期天增刊广告 SS 广告受众总量广告数量 3 14 7,7 5 1 6,1 7 5
<=
最多电视时段 5
每次广告能达到各目标群的数量（百万 )
每次广告成本（千美元）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
4.5 超级食品公司案例的再研究 （续）
决策变量,TV－ 电视上的广告时段数目
M － 杂志上的广告数目
SS － 星期天增刊上的广告数目目标函数,广告受众总量 最大化
Max z= 1300TV + 600M + 500SS
约束条件：
广告预算,300TV + 150M + 100SS? 4,000 ($thousand)
策划预算,90TV + 30M + 30SS? 1,000 ($thousand)
电视广告时段,TV? 5
儿童,1.2TV + 0.1M? 5 (millions)
儿童家长,0.5TV + 0.2M + 0.2SS? 5 (millions)
优惠券,40M + 120SS = 1,490 ($thousand)
且 非负,TV,M,SS? 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型 Mixed Problem
4.6 混合问题 P121
资源分配问题,成本收益平衡问题 以及 网络配送问题,都以一类约束条件为特色的 。 实际上,纯资源分配问题的共性是它所有的函数约束均为 资源约束,
而成本收益平衡问题的共性是它所有的函数约束均为 收益约束,网络配送问题中,主要的函数约束为一特定类型的 确定需求的约束 。
混合问题是第四类线性规划问题，这一类型包括了以上两类或三类约束函数
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
类型总结类型 形式 解释 主要用于资源约束 LHS? RHS 对于特定的资源使用的数量?可获得的数量资源分配问题混合问题收益约束 LHS? RHS 对于特定的收益达到的水平?最低可接受水平成本收益平衡问题混合问题确定需求约束
LHS = RHS 对于一些数量提供的数量＝ 需求的数量网络配送问题混合问题
Summary of LP Types
线性规划问题总结 P122
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例 Save-It Company
塞维特公司 (回收固体废弃物 ) P122
塞维特公司经营一个回收中心，专门从事四种固体废弃物（材料 1、
2,3,4）的回收，并将回收物处理、混合成为可销售的三种产品。
三种不同等级的产品,A,B,C，它们取决于四种材料的混合成分等级 规格说明 每磅混合成本 每磅的售价
A
材料 1,不超过总量的 30%
材料 2,不少于总量的 40%
材料 3,不超过总量的 50%
材料 4,总量的 20%
$3.00 $8.50
B
材料 1,不超过总量的 50%
材料 2,不少于总量的 10%
材料 4,总量的 10%
2.50 7.00
C 材料 1,不超过总量的 70% 2.00 5.50
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
回收固体废弃物 P122（续）
塞维特公司固体废弃物的有关数据材料每周可获得的数量 (磅 )
每磅处理成本
($) 附加约束
1 3,000 $3.00 1、对于每种材料，每周必须至少收集并处理一半以上数量
2,每周有 $30,000可用于处理这些材料（要求用完：＝）
2 2,000 6.00
3 4,000 4.00
4 1,000 5.00
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Excel模型 P124
P 1 2 4 塞维特公司 ( 回收固体废弃物 ) S a v e - I t C o m p a n y R e c l a m a t i o n P r o b l e m
等级A 等级B 等级C
单位混合成本 $ 3,0 0 $ 2,5 0 $ 2,0 0 总处理成本 $ 3 0,0 0 0
单位售价 $ 8,5 0 $ 7,0 0 $ 5,5 0 =
单位利润 $ 5,5 0 $ 4,5 0 $ 3,5 0 可获得的捐款 $ 3 0,0 0 0
单位处理 最少处理 实际处理 可获得的等级A 等级B 等级C 成本 的材料量 的材料量 材料量材料 1 6 4 4,7 2,3 5 5,3 0 $3 1,5 0 0 <= 3,0 0 0 <= 3,0 0 0
材料 2 8 5 9,6 5 1 7,5 0 $6 1,0 0 0 <= 1,3 7 7 <= 2,0 0 0
材料 3 2 1 4,9 1,7 8 5,1 0 $4 2,0 0 0 <= 2,0 0 0 <= 4,0 0 0
材料 4 4 2 9,8 5 1 7,5 0 $5 500 <= 947 <= 1,0 0 0
产品总量 2,1 4 9,1 5,1 7 5,4 0
混合说明 M i x t u r e S p e c i f i c a t i o n s 混合比例等级 A,材料 1 6 4 4,7 <= 6 4 4,7 30% 等级 A
总利润 $ 3 5,1 1 0 等级 A,材料 2 8 5 9,6 >= 8 5 9,6 40% 等级 A
等级 A,材料 3 2 1 4,9 <= 1,0 7 4,6 50% 等级 A
等级 A,材料 4 4 2 9,8 = 4 2 9,8 20% 等级 A
等级 B,材料 1 2,3 5 5,3 <= 2,5 8 7,7 50% 等级 B
等级 B,材料 2 5 1 7,5 >= 5 1 7,5 10% 等级 B
等级 B,材料 4 5 1 7,5 = 5 1 7,5 10% 等级 B
等级 C,材料 1 0,0 <= 0,0 70% 等级 C
材料分配 M a t e r i a l A l l o c a t i o n
每种等级产品所需的材料数量 ( 磅 )
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数学模型 P126
决策变量,xij =每周分配给 i等产品的材料 j的数量 (磅 ) (i = A,B,C; j = 1,2,3,4)
目标函数,总利润最大化
Max P = 5.5(xA1 + xA2 + xA3 + xA4) + 4.5(xB1 + xB2 + xB3 + xB4) + 3.5(xC1 + xC2 + xC3 + xC4)
约束条件：
混合规格,xA1? 0.3 (xA1 + xA2 + xA3 + xA4)
xA2? 0.4 (xA1 + xA2 + xA3 + xA4)
xA3? 0.5 (xA1 + xA2 + xA3 + xA4)
xA4 = 0.2 (xA1 + xA2 + xA3 + xA4)
xB1? 0.5 (xB1 + xB2 + xB3 + xB4)
xB2? 0.1 (xB1 + xB2 + xB3 + xB4)
xB4 = 0.1 (xB1 + xB2 + xB3 + xB4)
xC1? 0.7 (xC1 + xC2 + xC3 + xC4)
可获得的材料限制,xA1 + xB1 + xC1? 3,000
xA2 + xB2 + xC2? 2,000
xA3 + xB3 + xC3? 4,000
xA4 + xB4 + xC4? 1,000
最少要求处理限制,xA1 + xB1 + xC1? 1,500
xA2 + xB2 + xC2? 1,000
xA3 + xB3 + xC3? 2,000
xA4 + xB4 + xC4? 500
处理成本限制,3(xA1 + xB1 + xC1) + 6(xA2 + xB2 + xC2)
+ 4(xA3 + xB3 + xC3) + 5(xA4 + xB4 + xC4) = 30,000
且 非负,xij? 0 (i = A,B,C; j = 1,2,3,4)
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
思考题 1：
问题,四种材料（固体废弃物），在每周可获得的数量限制和要求处理一半以上，且捐款全部用完时，是否可以用销售利润的一部分作为处理成本？且总利润还增加。
回答可以,此时总利润＝等级产品 ABC的利润＋可获得的捐款 30,000-总处理成本，而将,处理成本＝可获得的捐款,的 确定需求约束 改为,处理成本?可获得的捐款,
的 收益 约束,即可获得的捐款全部用完 。
结果,等级产品 ABC的利润＝ $36,250
总处理成本＝ $31,000 > $30,000
总利润＝ $35,250 > 原来的 $35,110
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
思考题 2：
问题,四种材料（固体废弃物），要求每周可获得的数量全部处理完
，且捐款全部用完时，此时获利最大 (总利润最大 )。
回答可以：
此时总利润＝等级产品 ABC的利润＋可获得的捐款 30,000-总处理成本，而
1,将,处理成本＝可获得的捐款,的 确定需求约束 改为,处理成本?可获得的捐款,的 收益 约束,即可获得的捐款全部用完
2,去掉 要求处理一半以上的收益约束
3,改,实际处理的材料量?可获得的材料量,为,实际处理的材料量 =可获得的材料量,。
结果,等级产品 ABC的利润＝ $45,000
总处理成本＝ $42,000 > $30,000
总利润＝ $33,000 < 原来的 $35,110
虽然总利润有所下降，但固体废弃物全部处理完（取得社会效益）。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Modeling from Managerial Perspective
4.7 管理视角的建模 P127
总绩效测度必须是管理层想获得的现实目标
准确细致地描述资源约束、收益约束、确定需求约束
管理科学小组与管理层的有效沟通
模型往往要不断地修改和扩展
要进行 what-if分析
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Classical Applications of LP
4.8 线性规划经典应用回顾 P129
应用回顾
为潘德罗索工业公司选择产品组合
联合航空公司工作人员排程
Citgo石油集团供应、配送与营销的规划
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Ponderosa Industrial
潘德罗索工业公司 P129
公司经验潘德罗索应用成功的因素：
以 自然语言 为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整个过程。
最优化系统是 互动的（ interactive）,管理者在从一个版本的模型中获得一组最优解之后，可以提出一系列的
what-if问题，并能立即得到回应。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Personnel Scheduling at UA.
联合航空公司人员排程 P130
公司经验联合航空公司利用线性规划，来为其在主要的机场和订票点的上万个工作人员安排每周的工作时间表。目标是为了能够在满足客户的服务需要的同时，将一周内每天每半个小时的人员成本最小化。联合航空公司一些地点的规划模型却包括
20,000个决策变量。
应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Citgo Petroleum Corporation
Citgo石油集团 P130
公司经验
Citgo石油集团运用管理科学的技术，特别是线性规划，建立供应、配送与营销的建模系统将公司主要产品的供应、配送与营销通过公司庞大的销售与配送网络得到很好的协调。在 90年代中期创造了大量的财富。
公司每种主要产品的模型都含有大约 1,500个决策量以及
3,000个确定需求的约束最重要的 成功因素 是高层管理者所给予的 无限制 的支持，
并且设立运作协调副总裁，来负责评价与协调这一跨组织边界的模型所提供的建议
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
4.9 Summary 小结 P131
以?符号表示的函数约束称为 资源约束,这些限制要求使用的资源必须小于等于所能提供的资源的数量 。 资源分配问题的共性就是它们的函数约束全部为资源约束 。
以?符号表示的函数约束为 收益约束,形式为收益取得的水平必须大于等于最低可接受水平 。 收益约束反映了管理层所规定的目标 。 如果所有约束均为收益约束,这一问题为成本收益平衡问题 。
以 ＝ 符号表示的函数约束称为 确定需求的约束,它们表示了一定数量的确定的需求,提供的数量等于要求的数量 。 网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束 。
不能归于这三类的任何线性规划的问题称为 混合问题 。
在实际的应用当中,管理科学小组经常建立和分析大型的线性规划模型以指导管理决策,这些工作需要管理层足够强大的管理上的投入与支持
,才能达到管理层实际的要求 。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 4.2 新的边界 P140
地区 1 8 ~ 2 5 2 6 ~ 4 0 4 1 ~ 5 0 51 以上硅谷 $ 4,7 5 $ 6,5 0 $ 6,5 0 $ 5,0 0
大城市 $ 5,2 5 $ 5,7 5 $ 6,2 5 $ 6,2 5
小城镇 $ 6,5 0 $ 7,5 0 $ 7,5 0 $ 7,2 5
决策变量：X i j 为地区i 年龄组j 的被调研人数地区 1 8 ~ 2 5 2 6 ~ 4 0 4 1 ~ 5 0 51 以上求和 ( 每个地区的总人数 )
每个地区所需的最少人数 比例要求硅谷 600 0 0 300 900 >= 300 15%
大城市 150 550 0 0 700 >= 700 35%
小城镇 100 0 300 0 400 >= 400 20%
求和 ( 每个年龄段的总人数 )
850 550 300 300
>= >= >= >= 总的调查人数 2000
每个年龄段所需的最少人数
400 550 300 300 =
比例要求 20% 2 7,5 % 15% 15% 需要调查人数 2000
总成本 C $ 1 1,2 0 0
边际收益 15%
投标 B i d $ 1 2,8 8 0
每人的调研费用 C i j
每个地区不同年龄组的被调研人数 X i j
12个决策变量 Xij:地区 i年龄段 j的被调研人数
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 4.2 新的边界（续）
ab.决策变量 Xij:地区 i年龄段 j的被调研人数 （ i=1,2,3 j=1,2,3,4）
来自硅谷地区的人数,X11+X12+X13+X14?15%*2000 其余地区类似
第一年龄段的人数,(X11+X21+X31)? 20%*2000 其余年龄段类似
要求调查总人数,X11+X12+X13+X14 + X21+X22+X23+X24+ X31+X32+X33+X34 ＝ 2000
总成本 最小化
Min C=4.75 X11+6.50X12+6.50X13+5.00X14+5.25X21+5.75X22+6.25X23+6.25X24
+6.50X31+7.50X32+7.50X33+7.25X34
投标 Bid=总成本 *(1+15%)
c.在 a上,增加 Xij? 50,重新运行规划求解
d.在 c上,增加 18～ 25岁总人数?600,硅谷地区总人数? 650,重新运行
e.在 d上,改 18～ 25岁的调研成本,重新运行规划求解
f.在 e上,修改比例 （ 确定需求约束 ）,重新运行规划求解
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P132习题 4.1,4.5（ 资源约束 ）,
4,14（ 收益约束 ）,4,18（ 需求约束 ）,4.22（ 混合 ）
作业要求 （ 只要下面三个 ）,
1,画出数据表格 （ 上机,在 Excel中实现即可 ）
2,写出数学模型 （ 手写作业,均要写明意义 ）
决策变量
目标函数
约束条件
3,用 Excel求解得到的答案 （ 上机,在 Excel中实现即可 ）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 4.1（ 前面学号）
案例 4.1 秋季流行服饰与衣料的准备 P139（ 注意：共 3次时装展,所以时装展总费用 =3*$2,700,000）
改,1,P139(右下角 ) 采购材料,“开司米 28000码,改为,醋酸纤维 28000码
,开司米 9000码,
2,P139 (右上角 ),剪裁考究的 衬衫,改为,剪裁考究的 裙子 Skirt”,
2800件
3,P139 (f.问题 ),10000码的 醋酸 纤维衣料订单,
提示,1,7种衣料 生产 11种服装 （ 6种职业装＋ 5种休闲装 ）
2,多余边料约束,丝绸女背心?丝绸上衣,棉迷你裙?棉汗衫
3,(g,问题 )在 b上,需要 增加 11月份的 11种服装的生产量作为新的决策变量 （ 第 11章的可分离规划 ）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 2.3（后面学号）
案例 2.3 为呼叫中心配备工作人员 P62
注意：
1,全职员工 （ 工作 8小时 ） 有 4种上班方式 （ 7AM,9AM,11AM、
1PM开始上班 ） 且有 2种工作方式 （ 从接听电话开始或从做文书工作开始 ）,共 8种组合 （ 英语和西班牙语各 8种 ）
2,英语兼职员工 （ 工作 4小时 ） 有 2种上班方式 （ 3PM,5PM开始上班
）,西班牙语没有兼职员工结果,10（ 西班牙语 ） ＋ 30（ 英语 ） ＝ 40人,Min C＝ $1,640
提示,1,abc要分两个规划求解去解,否则可能会死机
2,最低可接受水平可以是 电话量,也可以是 人员 （ 向上取整 ）
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第四章
Linear Programming,
Formulation and Applications
线性规划：建模与应用
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
本章内容（ Topics） P91
Introduction the Key Categories of LP Problems
介绍线性规划问题的三种主要类型（取决于函数约束）：
资源分配问题（ resource-allocation,?）
成本收益平衡问题 （ cost-benefit-trade-off,?）
网络配送问题（ distribution-network,=）
混合问题（ mixed Problem）－两种或三种类型的混合
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Case Study:Super Grain Corp,Advertising-Mix Problem
4.1 案例研究：超级食品公司的广告组合问题 P92
超级食品公司如何才能大规模地进入已有许多供应商的早餐谷物食品市场。
委托了一家一流的广告公司来帮助设计全国性的促销活动，以使,脆始,（ Crunchy Start）取得尽可能多的消费者的认可。
费用情况：最多可以给广告商的酬金 100万和 400万的广告费
广告公司确定了这一产品最有效的三种广告媒介：
媒介 1：星期六上午儿童节目的电视广告。
媒介 2：食品与家庭导向的杂志上的广告。
媒介 3：主要报纸星期天增刊上的广告。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数据 P93
成本（美元）
成本分类 每次电视广告 每份杂志广告 每份星期天增刊广告广告预算 $300,000 $150,000 $100,000
策划预算 90,000 30,000 40,000
广告受众期望值 1,300,000 600,000 500,000
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Excel模型 P95
注意 P96-97：
结果是否符合实际情况：不做电视广告？
模型准确性评价 P96：数学模型是否真的体现实际情况
P 9 2 超级谷物公司的广告组合问题 ( S u p e r G r a i n C o r p,A d v e r t i s i n g - M i x P r o b l e m )
电视广告 TV 杂志广告 M 星期天增刊广告 SS
每次广告受众数量 1,3 0 0 600 500
( 千人次 )
使用资金 可用预算广告预算 300 150 100 4,0 0 0 <= 4,0 0 0
策划预算 90 30 40 1,0 0 0 <= 1,0 0 0
电视广告 TV 杂志广告 M 星期天增刊广告 SS 广告受众总量广告数量 0 20 10 1 7,0 0 0
<=
最多电视时段 5
每次广告成本（千美元）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数学模型 P96
决策变量：
TV－电视上的广告时段数目
M －杂志上的广告数目
SS－星期天增刊上的广告数目目标函数,广告受众总量 最大化
Max z=1300TV+600M+500SS
约束条件：
广告费用,300TV+150M+100SS? 4000
策划成本,90TV+ 30M+ 40SS? 1000
电视广告时段,TV? 5
且非负,TV,M,SS? 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型
Resource-allocation Problem
4.2 资源分配问题 P99
资源分配（ resource-allocation） 问题 是将有限的资源分配到各种活动中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数限制均为 资源限制 (resource constraint),并且每一种有限资源都可以表现为如下的形式：
使用的资源数量?可用的资源数量
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Datum Gathering
收集数据 P100
对任何资源分配问题，有三种数据必须收集：
1,每种资源的可供量（可用量）
2、每一种活动所需要的各种资源的数量,对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来（ 单位资源使用量 ）
3、每一种活动对总的绩效测度的单位贡献（ 单位利润 ）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例
Think-Big Development Co.
梦大发展公司资金预算问题 P101
梦大 (Think-Big)发展公司是商务房地产开发项目的主要投资商。
目前，该公司有机会在三个建设项目中投资：
建造高层办公楼 Construct a high-rise office building
建造宾馆 Construct a hotel
建造购物中心 Construct a shopping center
每个项目都要求投资者在四个不同的时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资。
可以 按比例 投资项目
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
梦大发展公司部分投资项目的财务数据 P101
所需投资资金（百万美元）
Year 办公楼项目 宾馆项目 购物中心项目
0（当前） 40 80 90
1 60 80 50
2 90 80 20
3 10 70 60
净现值 NPV
(Net Present Value) 45 70 50
现在可用资金
2500万美元，
一年后又有 2000
万美元，
两年后又有 2000
万美元，
三年后再有 1500
万美元
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Excel模型 P104
注意 P102-103：
由于 前一期尚未使用的资金，可以在下一期使用,所以每一时点的资源限制都必须表现为累计的资金
想求每一个项目的 投资比例办公楼项目 宾馆项目 购物中心项目单位净现值 45 70 50 单位：百万美元使用的累计资金额可获得的累计资金额现在 40 80 90 25 <= 25
一年后 100 160 140 4 4,7 6 <= 45
二年后 190 240 160 6 0,5 8 <= 65
三年后 200 310 220 80 <= 80
办公楼项目 宾馆项目 购物中心项目 总净现值投资比例 0,0 0 % 1 6,5 0 % 1 3,1 1 % 1 8,1 1
单位累计资金需求量
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数学模型 P105
决策变量,OB - 办公楼项目中的投资比例
H - 宾馆项目中的投资比例
SC - 购物中心项目中的投资比例目标函数,总净现值 最大化
Max NPV = 45OB + 70H + 50SC
约束条件：
现在的总投资,40OB + 80H + 90SC? 25 ($million)
1年后的总投资,100OB + 160H + 140SC? 45 ($million)
2年后的总投资,190OB + 240H + 160SC? 65 ($million)
3年后的总投资,200OB + 310H + 220SC? 80 ($million)
且非负,OB,H,SC? 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
方法 2
1,用第三章 P65现金流管理的方法
2,前一期尚未使用的资金，可以在下一期使用
3,增加：实际每期所需投资资金、可用资金、资金余额、每年资金等详细信息。
P 1 0 4 梦大发展公司资金预算问题 T h i n k - B i g D e v e l o p m e n t C o,C a p i t a l B u d g e t i n g P r o b l e m
办公楼项目 宾馆项目 购物中心项目单位净现值 45 70 50
办公楼项目 宾馆项目 购物中心项目 办公楼项目 宾馆项目 购物中心项目 总投资额 可用资金 资金余额 每年资金现在 40 80 90 0,0 0 1 3,2 0 1 1,8 0 25 <= 25 0 25
一年后 60 80 50 0,0 0 1 3,2 0 6,5 5 20 <= 20 0 20
二年后 90 80 20 0,0 0 1 3,2 0 2,6 2 16 <= 20 4 20
三年后 10 70 60 0,0 0 1 1,5 5 7,8 6 19 <= 19 0 15
办公楼项目 宾馆项目 购物中心项目 总净现值投资比例 0,0 0 % 1 6,5 0 % 1 3,1 1 % 1 8,1 1
单位所需投资资金单位：百万美元实际每期所需投资资金
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
方法 2的数学模型 (补充 )
决策变量,OB - 办公楼项目中的投资比例
H - 宾馆项目中的投资比例
SC - 购物中心项目中的投资比例
R0,R1,R2,R3为各年的资金余额目标函数,总净现值 最大化
Max NPV = 45OB + 70H + 50SC
约束条件：
现在的投资,40OB + 80H + 90SC ＋ R0＝ 25 ($million)
1年后的投资,60OB + 80H + 50SC ＋ R1＝ 20 ＋ R0 ($million)
2年后的投资,90OB + 80H + 20SC ＋ R2＝ 20＋ R1($million)
3年后的投资,10OB + 70H + 60SC ＋ R3＝ 15 ＋ R2($million)
且非负,OB,H,SC? 0,Ri? 0（ i＝ 0,1,2,3）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型
Cost-benefit-trade-off Problem
4.3 成本收益平衡问题 P106
成本收益平衡问题（ Cost-benefit-trade-off Problem ）
是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以 最小的成本 来实现最低可接受的各种收益水平。这类问题的共性是，所有的函数约束均为 收益约束,并具有如下的形式：
完成的水平? 最低可接受的水平
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
成本收益平衡问题需要的三种数据 P107
1、每种收益的 最低可接受水平 （管理决策）
2、每一种活动对每一种收益的贡献（ 单位活动的贡献 ）
3、每种活动的 单位成本
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例
P108 联邦航空公司人员排班问题
Union Airways Personnel Scheduling Problem
请看书 P108-112和第 4章相应的 Excel文件
Excel模型 P110
早 6 点 班 早 8 点班 中午班 下午 4 点班 晚 10 点班单位成本 $170 $160 $175 $180 $195
时段 在岗人数 所需的最少人数
6 a m - 8 a m 1 48 >= 48
8 a m - 1 0 a m 1 1 79 >= 79
1 0 a m - 1 2 p m 1 1 79 >= 65
1 2 p m - 2 p m 1 1 1 118 >= 87
2 p m - 4 p m 1 1 70 >= 64
4 p m - 6 p m 1 1 82 >= 73
6 p m - 8 p m 1 1 82 >= 82
8 p m - 1 0 p m 1 43 >= 43
1 0 p m - 1 2 a m 1 1 58 >= 52
1 2 a m - 6 a m 1 15 >= 15
早 6 点 班 早 8 点班 中午班 下午 4 点班 晚 10 点班 总人数 总成本每班人数 48 31 39 43 15 176 $ 3 0,6 1 0
是否在岗 S h i f t W o r k s T i m e P e r i o d? ( 1 = y e s,0 = n o )
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
P108 联邦航空公司人员排班问题（续）
代数模型 P111
决策变量,设 Si 为轮班 i的人数 (i = 1,2,3,4,5)
目标函数,总成本 最小化
Min C = $170S1 + $160S2 + $175S3 + $180S4 + $195S5
约束条件：
6AM–8AM,S1? 48
8AM–10AM,S1 + S2? 79
10AM–12PM,S1 + S2? 65
12PM–2PM,S1 + S2 + S3? 87
2PM–4PM,S2 + S3? 64
4PM–6PM,S3 + S4? 73
6PM–8PM,S3 + S4? 82
8PM–10PM,S4? 43
10PM–12AM,S4 + S5? 52
12AM–6AM,S5? 15
且非负,Si? 0 (i = 1,2,3,4,5)
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型
Distribution-network Problem
4.4 网络配送问题 P113
网络配送问题 （ distribution network）能以最小的成本完成货物的配送，所以称之为网络配送问题并具有如下的确定性约束形式：
提供的数量＝需求的数量
（平衡运输问题：总供应＝总需求）
确定需求的约束
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例
P113 大 M公司网络配送问题
(Big M Company Distribution Problem)
请看书 P113-117
和第 4章相应的
Excel文件
代数模型 P116和
Excel模型 P116
右图为配送网络图
F 1
C 2
C 3
C 1
F 2
1 2 l a t h e
p r o d u c e d
1 5 l a t h e s
p r o d u c e d
1 0 l a t h e s
n e e d e d
8 l a t h e s
n e e d e d
9 l a t h e s
n e e d e d
$700 / l a t he
$900 / l a t he
$800 / l a t he
$800 / l a t he $900 / l a t he
$700 / l a t he
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
P113 大 M公司网络配送问题（续）
Excel模型 P116（平衡运输问题：总供应＝总需求 ）
单位运输成本 顾客 1 顾客 2 顾客 3
工厂 1 $700 $900 $800
工厂 2 $800 $900 $700
运输量 顾客 1 顾客 2 顾客 3 实际运出 可运出工厂 1 10 2 0 12 = 12
工厂 2 0 6 9 15 = 15
运往顾客 10 8 9
= = = 总成本订货量 10 8 9 $ 2 0,5 0 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
P113 大 M公司网络配送问题（续）
代数模型 P116 （平衡运输问题：总供应＝总需求 ）
决策变量,设 Sij 为从工厂 i 运输到顾客 j的车床数量 (i = F1,F2; j = C1,C2,C3)
目标函数,总成本 最小化
Min C = $700SF1-C1 + $900SF1-C2 + $800SF1-C3
+ $800SF2-C1 + $900SF2-C2 + $700SF2-C3
约束条件,
工厂 1,SF1-C1 + SF1-C2 + SF1-C3 = 12
工厂 2,SF2-C1 + SF2-C2 + SF2-C3 = 15
顾客 1,SF1-C1 + SF2-C1 = 10
顾客 2,SF1-C2 + SF2-C2 = 8
顾客 3,SF1-C3 + SF2-C3 = 9
且 非负,Sij? 0 (i = F1,F2; j = C1,C2,C3)
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Continuing the Super Grain Case Study
4.5 超级食品公司案例的再研究 P117
原问题（ 4.1节）为资源分配问题（?）
现在增加两个目标（?）：
目标 1：必须至少有 500万儿童看到该广告
目标 2：必须至少有 500万儿童的家长看到该广告
将剩余的优惠券预算 1,490,000美元全部用完（ =）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
4.5 超级食品公司案例的再研究 （续）
电视广告 TV 杂志广告 M 星期天增刊广告 SS
广告受众期望值 1,3 0 0 600 500
( 千人次 )
实际使用 可用预算广告预算 300 150 100 3,7 7 5 <= 4,0 0 0
策划预算 90 30 40 1,0 0 0 <= 1,0 0 0
实际人次 最低可接受水平儿童 1,2 0,1 0 5 >= 5
儿童家长 0,5 0,2 0,2 5,8 5 >= 5
电视广告 TV 杂志广告 M 星期天增刊广告 SS 实际数量 需求数量优惠券 0 40 120 1,4 9 0 = 1,4 9 0
电视广告 TV 杂志广告 M 星期天增刊广告 SS 广告受众总量广告数量 3 14 7,7 5 1 6,1 7 5
<=
最多电视时段 5
每次广告能达到各目标群的数量（百万 )
每次广告成本（千美元）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
4.5 超级食品公司案例的再研究 （续）
决策变量,TV－ 电视上的广告时段数目
M － 杂志上的广告数目
SS － 星期天增刊上的广告数目目标函数,广告受众总量 最大化
Max z= 1300TV + 600M + 500SS
约束条件：
广告预算,300TV + 150M + 100SS? 4,000 ($thousand)
策划预算,90TV + 30M + 30SS? 1,000 ($thousand)
电视广告时段,TV? 5
儿童,1.2TV + 0.1M? 5 (millions)
儿童家长,0.5TV + 0.2M + 0.2SS? 5 (millions)
优惠券,40M + 120SS = 1,490 ($thousand)
且 非负,TV,M,SS? 0
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
问题类型 Mixed Problem
4.6 混合问题 P121
资源分配问题,成本收益平衡问题 以及 网络配送问题,都以一类约束条件为特色的 。 实际上,纯资源分配问题的共性是它所有的函数约束均为 资源约束,
而成本收益平衡问题的共性是它所有的函数约束均为 收益约束,网络配送问题中,主要的函数约束为一特定类型的 确定需求的约束 。
混合问题是第四类线性规划问题，这一类型包括了以上两类或三类约束函数
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
类型总结类型 形式 解释 主要用于资源约束 LHS? RHS 对于特定的资源使用的数量?可获得的数量资源分配问题混合问题收益约束 LHS? RHS 对于特定的收益达到的水平?最低可接受水平成本收益平衡问题混合问题确定需求约束
LHS = RHS 对于一些数量提供的数量＝ 需求的数量网络配送问题混合问题
Summary of LP Types
线性规划问题总结 P122
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
实际举例 Save-It Company
塞维特公司 (回收固体废弃物 ) P122
塞维特公司经营一个回收中心，专门从事四种固体废弃物（材料 1、
2,3,4）的回收，并将回收物处理、混合成为可销售的三种产品。
三种不同等级的产品,A,B,C，它们取决于四种材料的混合成分等级 规格说明 每磅混合成本 每磅的售价
A
材料 1,不超过总量的 30%
材料 2,不少于总量的 40%
材料 3,不超过总量的 50%
材料 4,总量的 20%
$3.00 $8.50
B
材料 1,不超过总量的 50%
材料 2,不少于总量的 10%
材料 4,总量的 10%
2.50 7.00
C 材料 1,不超过总量的 70% 2.00 5.50
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
回收固体废弃物 P122（续）
塞维特公司固体废弃物的有关数据材料每周可获得的数量 (磅 )
每磅处理成本
($) 附加约束
1 3,000 $3.00 1、对于每种材料，每周必须至少收集并处理一半以上数量
2,每周有 $30,000可用于处理这些材料（要求用完：＝）
2 2,000 6.00
3 4,000 4.00
4 1,000 5.00
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Excel模型 P124
P 1 2 4 塞维特公司 ( 回收固体废弃物 ) S a v e - I t C o m p a n y R e c l a m a t i o n P r o b l e m
等级A 等级B 等级C
单位混合成本 $ 3,0 0 $ 2,5 0 $ 2,0 0 总处理成本 $ 3 0,0 0 0
单位售价 $ 8,5 0 $ 7,0 0 $ 5,5 0 =
单位利润 $ 5,5 0 $ 4,5 0 $ 3,5 0 可获得的捐款 $ 3 0,0 0 0
单位处理 最少处理 实际处理 可获得的等级A 等级B 等级C 成本 的材料量 的材料量 材料量材料 1 6 4 4,7 2,3 5 5,3 0 $3 1,5 0 0 <= 3,0 0 0 <= 3,0 0 0
材料 2 8 5 9,6 5 1 7,5 0 $6 1,0 0 0 <= 1,3 7 7 <= 2,0 0 0
材料 3 2 1 4,9 1,7 8 5,1 0 $4 2,0 0 0 <= 2,0 0 0 <= 4,0 0 0
材料 4 4 2 9,8 5 1 7,5 0 $5 500 <= 947 <= 1,0 0 0
产品总量 2,1 4 9,1 5,1 7 5,4 0
混合说明 M i x t u r e S p e c i f i c a t i o n s 混合比例等级 A,材料 1 6 4 4,7 <= 6 4 4,7 30% 等级 A
总利润 $ 3 5,1 1 0 等级 A,材料 2 8 5 9,6 >= 8 5 9,6 40% 等级 A
等级 A,材料 3 2 1 4,9 <= 1,0 7 4,6 50% 等级 A
等级 A,材料 4 4 2 9,8 = 4 2 9,8 20% 等级 A
等级 B,材料 1 2,3 5 5,3 <= 2,5 8 7,7 50% 等级 B
等级 B,材料 2 5 1 7,5 >= 5 1 7,5 10% 等级 B
等级 B,材料 4 5 1 7,5 = 5 1 7,5 10% 等级 B
等级 C,材料 1 0,0 <= 0,0 70% 等级 C
材料分配 M a t e r i a l A l l o c a t i o n
每种等级产品所需的材料数量 ( 磅 )
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
数学模型 P126
决策变量,xij =每周分配给 i等产品的材料 j的数量 (磅 ) (i = A,B,C; j = 1,2,3,4)
目标函数,总利润最大化
Max P = 5.5(xA1 + xA2 + xA3 + xA4) + 4.5(xB1 + xB2 + xB3 + xB4) + 3.5(xC1 + xC2 + xC3 + xC4)
约束条件：
混合规格,xA1? 0.3 (xA1 + xA2 + xA3 + xA4)
xA2? 0.4 (xA1 + xA2 + xA3 + xA4)
xA3? 0.5 (xA1 + xA2 + xA3 + xA4)
xA4 = 0.2 (xA1 + xA2 + xA3 + xA4)
xB1? 0.5 (xB1 + xB2 + xB3 + xB4)
xB2? 0.1 (xB1 + xB2 + xB3 + xB4)
xB4 = 0.1 (xB1 + xB2 + xB3 + xB4)
xC1? 0.7 (xC1 + xC2 + xC3 + xC4)
可获得的材料限制,xA1 + xB1 + xC1? 3,000
xA2 + xB2 + xC2? 2,000
xA3 + xB3 + xC3? 4,000
xA4 + xB4 + xC4? 1,000
最少要求处理限制,xA1 + xB1 + xC1? 1,500
xA2 + xB2 + xC2? 1,000
xA3 + xB3 + xC3? 2,000
xA4 + xB4 + xC4? 500
处理成本限制,3(xA1 + xB1 + xC1) + 6(xA2 + xB2 + xC2)
+ 4(xA3 + xB3 + xC3) + 5(xA4 + xB4 + xC4) = 30,000
且 非负,xij? 0 (i = A,B,C; j = 1,2,3,4)
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
思考题 1：
问题,四种材料（固体废弃物），在每周可获得的数量限制和要求处理一半以上，且捐款全部用完时，是否可以用销售利润的一部分作为处理成本？且总利润还增加。
回答可以,此时总利润＝等级产品 ABC的利润＋可获得的捐款 30,000-总处理成本，而将,处理成本＝可获得的捐款,的 确定需求约束 改为,处理成本?可获得的捐款,
的 收益 约束,即可获得的捐款全部用完 。
结果,等级产品 ABC的利润＝ $36,250
总处理成本＝ $31,000 > $30,000
总利润＝ $35,250 > 原来的 $35,110
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
思考题 2：
问题,四种材料（固体废弃物），要求每周可获得的数量全部处理完
，且捐款全部用完时，此时获利最大 (总利润最大 )。
回答可以：
此时总利润＝等级产品 ABC的利润＋可获得的捐款 30,000-总处理成本，而
1,将,处理成本＝可获得的捐款,的 确定需求约束 改为,处理成本?可获得的捐款,的 收益 约束,即可获得的捐款全部用完
2,去掉 要求处理一半以上的收益约束
3,改,实际处理的材料量?可获得的材料量,为,实际处理的材料量 =可获得的材料量,。
结果,等级产品 ABC的利润＝ $45,000
总处理成本＝ $42,000 > $30,000
总利润＝ $33,000 < 原来的 $35,110
虽然总利润有所下降，但固体废弃物全部处理完（取得社会效益）。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Modeling from Managerial Perspective
4.7 管理视角的建模 P127
总绩效测度必须是管理层想获得的现实目标
准确细致地描述资源约束、收益约束、确定需求约束
管理科学小组与管理层的有效沟通
模型往往要不断地修改和扩展
要进行 what-if分析
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Classical Applications of LP
4.8 线性规划经典应用回顾 P129
应用回顾
为潘德罗索工业公司选择产品组合
联合航空公司工作人员排程
Citgo石油集团供应、配送与营销的规划
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Ponderosa Industrial
潘德罗索工业公司 P129
公司经验潘德罗索应用成功的因素：
以 自然语言 为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整个过程。
最优化系统是 互动的（ interactive）,管理者在从一个版本的模型中获得一组最优解之后，可以提出一系列的
what-if问题，并能立即得到回应。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Personnel Scheduling at UA.
联合航空公司人员排程 P130
公司经验联合航空公司利用线性规划，来为其在主要的机场和订票点的上万个工作人员安排每周的工作时间表。目标是为了能够在满足客户的服务需要的同时，将一周内每天每半个小时的人员成本最小化。联合航空公司一些地点的规划模型却包括
20,000个决策变量。
应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Citgo Petroleum Corporation
Citgo石油集团 P130
公司经验
Citgo石油集团运用管理科学的技术，特别是线性规划，建立供应、配送与营销的建模系统将公司主要产品的供应、配送与营销通过公司庞大的销售与配送网络得到很好的协调。在 90年代中期创造了大量的财富。
公司每种主要产品的模型都含有大约 1,500个决策量以及
3,000个确定需求的约束最重要的 成功因素 是高层管理者所给予的 无限制 的支持，
并且设立运作协调副总裁，来负责评价与协调这一跨组织边界的模型所提供的建议
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
4.9 Summary 小结 P131
以?符号表示的函数约束称为 资源约束,这些限制要求使用的资源必须小于等于所能提供的资源的数量 。 资源分配问题的共性就是它们的函数约束全部为资源约束 。
以?符号表示的函数约束为 收益约束,形式为收益取得的水平必须大于等于最低可接受水平 。 收益约束反映了管理层所规定的目标 。 如果所有约束均为收益约束,这一问题为成本收益平衡问题 。
以 ＝ 符号表示的函数约束称为 确定需求的约束,它们表示了一定数量的确定的需求,提供的数量等于要求的数量 。 网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束 。
不能归于这三类的任何线性规划的问题称为 混合问题 。
在实际的应用当中,管理科学小组经常建立和分析大型的线性规划模型以指导管理决策,这些工作需要管理层足够强大的管理上的投入与支持
,才能达到管理层实际的要求 。
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 4.2 新的边界 P140
地区 1 8 ~ 2 5 2 6 ~ 4 0 4 1 ~ 5 0 51 以上硅谷 $ 4,7 5 $ 6,5 0 $ 6,5 0 $ 5,0 0
大城市 $ 5,2 5 $ 5,7 5 $ 6,2 5 $ 6,2 5
小城镇 $ 6,5 0 $ 7,5 0 $ 7,5 0 $ 7,2 5
决策变量：X i j 为地区i 年龄组j 的被调研人数地区 1 8 ~ 2 5 2 6 ~ 4 0 4 1 ~ 5 0 51 以上求和 ( 每个地区的总人数 )
每个地区所需的最少人数 比例要求硅谷 600 0 0 300 900 >= 300 15%
大城市 150 550 0 0 700 >= 700 35%
小城镇 100 0 300 0 400 >= 400 20%
求和 ( 每个年龄段的总人数 )
850 550 300 300
>= >= >= >= 总的调查人数 2000
每个年龄段所需的最少人数
400 550 300 300 =
比例要求 20% 2 7,5 % 15% 15% 需要调查人数 2000
总成本 C $ 1 1,2 0 0
边际收益 15%
投标 B i d $ 1 2,8 8 0
每人的调研费用 C i j
每个地区不同年龄组的被调研人数 X i j
12个决策变量 Xij:地区 i年龄段 j的被调研人数
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 4.2 新的边界（续）
ab.决策变量 Xij:地区 i年龄段 j的被调研人数 （ i=1,2,3 j=1,2,3,4）
来自硅谷地区的人数,X11+X12+X13+X14?15%*2000 其余地区类似
第一年龄段的人数,(X11+X21+X31)? 20%*2000 其余年龄段类似
要求调查总人数,X11+X12+X13+X14 + X21+X22+X23+X24+ X31+X32+X33+X34 ＝ 2000
总成本 最小化
Min C=4.75 X11+6.50X12+6.50X13+5.00X14+5.25X21+5.75X22+6.25X23+6.25X24
+6.50X31+7.50X32+7.50X33+7.25X34
投标 Bid=总成本 *(1+15%)
c.在 a上,增加 Xij? 50,重新运行规划求解
d.在 c上,增加 18～ 25岁总人数?600,硅谷地区总人数? 650,重新运行
e.在 d上,改 18～ 25岁的调研成本,重新运行规划求解
f.在 e上,修改比例 （ 确定需求约束 ）,重新运行规划求解
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P132习题 4.1,4.5（ 资源约束 ）,
4,14（ 收益约束 ）,4,18（ 需求约束 ）,4.22（ 混合 ）
作业要求 （ 只要下面三个 ）,
1,画出数据表格 （ 上机,在 Excel中实现即可 ）
2,写出数学模型 （ 手写作业,均要写明意义 ）
决策变量
目标函数
约束条件
3,用 Excel求解得到的答案 （ 上机,在 Excel中实现即可 ）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 4.1（ 前面学号）
案例 4.1 秋季流行服饰与衣料的准备 P139（ 注意：共 3次时装展,所以时装展总费用 =3*$2,700,000）
改,1,P139(右下角 ) 采购材料,“开司米 28000码,改为,醋酸纤维 28000码
,开司米 9000码,
2,P139 (右上角 ),剪裁考究的 衬衫,改为,剪裁考究的 裙子 Skirt”,
2800件
3,P139 (f.问题 ),10000码的 醋酸 纤维衣料订单,
提示,1,7种衣料 生产 11种服装 （ 6种职业装＋ 5种休闲装 ）
2,多余边料约束,丝绸女背心?丝绸上衣,棉迷你裙?棉汗衫
3,(g,问题 )在 b上,需要 增加 11月份的 11种服装的生产量作为新的决策变量 （ 第 11章的可分离规划 ）
Chapter 4
Linear Programming,Formulation and Applications
线性规划,建模与应用
RUC Information School,Ye Xiang,2007
案例 2.3（后面学号）
案例 2.3 为呼叫中心配备工作人员 P62
注意：
1,全职员工 （ 工作 8小时 ） 有 4种上班方式 （ 7AM,9AM,11AM、
1PM开始上班 ） 且有 2种工作方式 （ 从接听电话开始或从做文书工作开始 ）,共 8种组合 （ 英语和西班牙语各 8种 ）
2,英语兼职员工 （ 工作 4小时 ） 有 2种上班方式 （ 3PM,5PM开始上班
）,西班牙语没有兼职员工结果,10（ 西班牙语 ） ＋ 30（ 英语 ） ＝ 40人,Min C＝ $1,640
提示,1,abc要分两个规划求解去解,否则可能会死机
2,最低可接受水平可以是 电话量,也可以是 人员 （ 向上取整 ）
