Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第二章
Linear Programming,Basic Concepts
线性规划,基本概念
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
本章内容（ Topics）
2.1Three ClassicApplicationsofLP
三个经典的线性规划应用
2.2CaseStudy,WyndorGlassCo.Product-MixProblem
案例研究：伟恩德玻璃制品公司产品组合问题
2.4伟恩德玻璃制品公司产品组合问题的数学模型
2.5The GraphicalMethodforSolvingLP
线性规划的图解法 （ 两变量 ）
2.3,2.6UsingMicrosoftExcelSolverfor Solving LP
用微软 Excel求解线性规划问题
2.7一个最小化的例子 ---利博公司广告组合问题
2.8 ModelingfromManagerialPerspective
管理视角的建模
2.9Summary小结
案例 2.1自动装配
案例 2.2降低咖啡屋的成本
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
线性规划基本概念（ P19)
任何一个组织的管理通常都必须对如何向不同的活动分配资源的问题做出决策,以最好地达到组织的目标 。 线性规划是帮助管理这些决策的一个功能强大的问题解决工具 。
向活动进行分配的 资源 可以是比如 钱,不同的 人员 以及不同的 机器和设备 。 在许多情况下,大量不同的生产活动 （ 如生产不同产品 ）,营销活动 （ 如在不同媒体做广告 ）,金融活动 （ 如进行资金投资 ） 或其他一些活动 。 所有这些类型的活动 （ 以及其他 ） 就会导致一些问题的产生,因为他们 争夺同一资源 。
线性规划是应用数学模型对所研究的问题进行表述 。 线性 （
Linear） 是指一次关系 。 规划 （ Programming） 不是程序,而本质是计划 （ Planning） 。
所谓,线性,规划,是指如果目标函数是关于决策变量的线性函数,而且约束条件也都是决策变量的线性等式或线性不等式,则相应的规划问题就称为线性规划问题 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.1 Three Classical Applications of LP
三个经典的线性规划应用（ P20-22)
确定潘德罗索工业公司的产品组合
联合航空公司的员工排程 （ 排班 ）
Citgo石油公司的供应,配送和营销规划
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
公司经验
Ponderosa Industrial
潘德罗索工业公司 P20
潘德罗索应用成功的因素：
以 自然语言 为用户界面的财务计划系统,使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果,使得做决策的管理者能够很容易看懂整个过程 。
最优化系统是 互动的 （ interactive）,管理者在从一个版本的模型中获得一组最优解之后,可以提出一系列的 what-if问题,并能立即得到回应 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
公司经验
Personnel Scheduling at UA.
联合航空公司人员排程 P20-21
联合航空公司利用线性规划,来为其在主要的机场和订票点的上万个工作人员安排每周的工作时间表 。 目标是为了能够在满足客户的服务需要的同时,将一周内每天每半个小时的人员成本最小化 。 联合航空公司一些地点的规划模型却包括 20,000个决策变量 。
应用成功最主要的因素是 因为得到了运营经理以及其它员工的大力支持 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
公司经验
Citgo Petroleum Corporation
Citgo石油集团 P21-22
Citgo石油集团运用管理科学的技术,特别是线性规划,建立供应,配送与营销的建模系统将公司主要产品的供应,配送与营销通过公司庞大的销售与配送网络得到很好的协调 。 在 90年代中期创造了大量的财富 。
公司每种主要产品的模型都含有大约 1,500个决策变量以及 3，
000个确定需求的约束最重要的成功因素是高层管理者所给予的无限支持,并且设立运作协调副总裁,来负责评价与协调这一跨组织边界的模型所提供的建议 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.2 Case Study:Wyndor Glass Co,Product-Mix Problem
案例研究：伟恩德玻璃制品公司产品组合问题 P22
要生产两种新产品：
8英尺的铝框玻璃门 （ Door）
4英尺 × 6英尺的双把木框窗 （ Window）
背景资料 （ 由于某些产品销售量的下降,高层管理部门决定调整公司的产品线 ）,
伟恩德玻璃制品公司有三个工厂：
工厂 1：生产铝框和五金件
工厂 2：生产木框
工厂 3：生产玻璃和组装窗与门
生产两种新产品所需的工厂生产能力：
8英尺的铝框玻璃门 Door：需要工厂 1和工厂 3,不需要工厂 2
4英尺 × 6英尺的双把木框窗 Window：需要工厂 2和工厂 3
现在管理部门要考虑下列两个问题：
公司是否应该生产这两个新产品？
如果生产,两个新产品的产品生产组合如何？ 每周分别生产多少数量？
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
伟恩德玻璃制品公司产品组合问题 P25-26
（将实际问题转化为运筹学的线性规划问题）
问题,两种新产品的生产率 （ 每周生产数量 ） 的哪种组合能最大化两种产品的总利润？ 即如何安排生产,使两种产品的总利润最大 。
需收集 （ 或估计 ） 的信息 （ 数据 ）,
每家工厂的可得生产能力 （ 生产能力的限制 ）
生产每一产品各需要每家工厂多少生产能力 （ 单位消耗 ）
每一产品的单位利润 （ 用于目标函数 ）
现在收集到 (估计 )的数据 工厂单位产品的生产时间 每周可得时间门 D 窗 W
1 1小时 0 4小时
2 0 2小时 12小时
3 3小时 2小时 18小时单位利润 ($) $300 $500
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.4 伟恩德玻璃制品公司产品组合问题的数学模型（运筹学的线性规划模型） P31
决策变量,D-每周新门的生产数量
W-每周新窗的生产数量目标函数,总利润最大化
Max P=300D+500W
约束条件,
（资源约束－函数约束 )：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W?18
且
D,W? 0 （非负约束）
为了最大化利润或最小化成本的目的，需要对一些稀缺资源进行配置
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Components of the Model
模型的组成部分
Decisionvariables决策变量
Objectivefunction 目标函数
Constraints约束条件附,P33 线性规划模型的一些术语决策变量、目标函数、目标函数值、非负约束、
函数约束、参数、解、可行解、最优解注意：线性规划的几种可能解：无解、多个最优解、唯一最优解
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Assumptions of Linear Programming
线性规划的假设
Linearity 线性
Divisibility 可分性
Certainty 确定性
Nonnegativity 非负性
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Why Use Linear Programming?
为什么要使用线性规划
线性规划很容易而有效率地被求解
如果存在最优解,则肯定能够找到
功能强 大的敏感性分析 （ sensitivity
analysis）
许多实际问题本质上是线性的
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
线性规划要确定决策变量 x1,x2,…,xn 使得
M a x i m i z e Z? c
1
x
1
c
n
x
n
Objective Function
s ubj e c t t o
a
11
x
1
a
1 n
x
n
b
1
a
21
x
1
a
2 n
x
n
b
2
a
m 1
x
1
a
mn
x
n
b
m
Functional Constraints
a nd
x
1
0,?,x
n
0? Nonnegativity Constraints
已知参数 c1,…,cn ; a11,…,amn ; b1,…,bm。
Mathematical Statement of LP Problem
线性规划的数学描述
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Steps in Formulating LP Problem
线性规划问题建模步骤
需要做哪些决策？ 决策变量是什么？
问题的目标是什么？ 写出目标函数 （ 与决策变量有关,
是决策变量的 线性函数 ）
资源和需求之间的情况如何？ 写出约束条件 （ 也与决策变量有关,是决策变量的 线性函数 ）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.5 The Graphical Method for Solving LP
线性规划的图解法（两变量）的步骤 P33
画出每个函数约束的约束边界线
找出由所有约束条件都同时满足所决定的可行域
确定一条目标函数线的斜率,所有其他目标函数线具有与之相同的斜率
用这一斜率在可行域内向目标函数值增加的方向移动
,直到在可行域的一个点时停止,此时为最优目标函数线
最优目标函数线上的可行点就是一个最优解
在光盘的 Interactive Management Science文件夹下
,有互动模型 LP,可以帮助我们理解图解法
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
(0,0)
(4,0)
(0,6)
P r odu c t i on ra t e
fo r w i ndo w s
P r odu c t i on ra t e for do ors
P r ofi t = $3,000
(2,6)
P r ofi t = $3,600
P r ofi t = $2,700
P r ofi t = $1,200
F e a s i bl e
re gi on
32
1
(4,3)
P r ofi t = 0
D
W
The Simplex Method for Solving LP
线性规划的 单纯形法
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Using Excel Solver for Solving LP
用微软 Excel的规划求解
规划求解不是典型安装,要加载宏,在工具菜单中 加载宏
,选,规划求解,(需要 Office安装盘或在安装时已经全部安装 ) 或 直 接 拷 贝 （ C:\Program Files\Microsoft
Office\OFFICE11\Library文件夹下 ） SOLVER文件夹下的两个文件并直接双击运行 Solver.xla加载宏也可 。 当然最好将 Excel全部安装 。
利用规划求解 （ 在,工具,菜单中选,规划求解,）
目标单元格,目标函数 （ 所在单 元格 地址,最大或最小或某值 ）
可变单元格：决策变量 （ 所在单 元格 地 址 ）
约束条件：函数约束 （ 所在单 元格 地 址 和约束值 ）
选项
采用线性模型
假定非负 （ 非负约束 ）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
在 Excel的 帮助 中，输入“规划求解”，可以查到,规划求解”算法与方法? Microsoft Excel 的,规划求解,工具取自德克萨斯大学奥斯汀分校的
Leon Lasdon 和克里夫兰州立大学的 Allan Waren 共同开发的
GeneralizedReducedGradient(GRG2)非线性最优化代码 。
线性和整数规划问题取自 Frontline Systems 公司的 John Watson 和
Dan Fylstra 提供的有界变量 单纯形法 和 分支边界法 （ 分支定界法 ） 。
有关,规划求解,使用的内部求解过程的详细信息,请与下列地址联系：
FrontlineSystems,Inc.
P.O.Box4288
InclineVillage,NV89450-4288
(775)831-0300
网站,http://www.frontsys.com
电子邮件,info@frontsys.com
Microsoft Excel Solver 程序代码的部分为 Frontline Systems,Inc 1990
,1991,1992 和 1995 年版权所有,部分为 Optimal Methods,Inc 公司
1989年版权所有 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.3 Building Wyndor Co,Problem Model in Excel
在电子表格上建立伟恩德公司问题的模型 P26
在用 Excel为问题建立数学模型 （ 这里是一个线性规划模型 ） 的过程中,有三个问题需要得到回答：
要做出的决策 （ decisions)是什么？ － 决策变量
在做出这些决策上有哪些约束条件 （ constraints）?－ 约束条件
这些决策的全部绩效测度 （ measure of performance)是什么
？ － 目标函数
在 Excel中,伟恩德公司模型的三个问题具体如下：
要做出的决策是两种新产品的生产率 （ productionrates)
对决策上的约束条件是两种新产品在相应工厂里每周生产时间不能超过每个工厂的可得生产时间
这些决策的全部绩效测度是这两种新产品的总利润 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.3 Building Wyndor Co,Problem Model in Excel
在电子表格上建立伟恩德公司问题的模型 P29
伟恩德公司模型的三个问题 （ 决策变量,函数约束,
目标函数 ）,具体在 Excel的实现 （ 单元格和公式,
用不同底色的单元格表示 ）,
P 43 伟恩德玻璃制品公司产品组合问题
Wyndor Glass Co,Product-Mix Problem
门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
使用时数 每周可得时数工厂 1 1 0 2 <= 4
工厂 2 0 2 12 <= 12
工厂 3 3 2 18 <= 18
门 D o o r s 窗 W i n d o w s 总利润每周生产数量 2 6 $ 3,6 0 0
每个产品所需生产时数
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.3 Building Wyndor Co,Problem Model in Excel
在电子表格上建立伟恩德公司问题的模型 P26-31
（四类单元格）
伟恩德公司模型的三个问题 （ 决策变量,函数约束,目标函数 ）,
具体在 Excel的实现 （ 单元格的位置和公式 ）,
将收集到 (估计 )的数据以直观的形式输入到 Excel中 （ 当然也要根据需要确定位置－－ 数据单元格 DataCells）
确定决策变量 （ 可变单元格 Changing Cells） 位置：每周生产数量
C12:D12
给单元格或区域 Range命名：插入 -->名称 -->定义 （ 或指定 ）
确定函数约束 （ 三个工厂生产时间限制,注意：与决策变量有关,是决策变量的线性函数 ） 位置和公式－－ 输出单元格 OutputCells：
E7=C7*C12+D7*D12＝ SUMPRODUCT(C7:D7,每周生产数量 )
E8=C8*C12+D8*D12＝ SUMPRODUCT(C8:D8,每周生产数量 )
E9=C9*C12+D9*D12＝ SUMPRODUCT(C9:D9,每周生产数量 )
确定目标函数 （ 与决策变量有关,是决策变量的线性函数 ） 位置和公式
,目标单元格 TargetCellG12(总利润 )=SUMPRODUCT(单位利润,每周生产数量 )
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.6 Using Excel for Solving LP
应用 Excel求解线性规划问题 P41-44
Excel中,工具－ >规划求解,在对话框中：
目标单元格,目标函数 （ 所在单元格地址,最大或最小或某值 ）
可变单元格,决策变量 （ 所在单 元格 地址 ）
约束条件,函数约束 （ 所在单 元格 地址和约束值 ）
选项
采用 线性 模型
假定 非负
单击,求解,按钮,进入,求解结果,对话框,即可知道求解结果 （ 找到一个最优解或找不到可行解 ）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.7 一个最小化的例子利博公司广告组合问题 P44
利博公司生产家用的清洁产品,管理层决定集中在下列三种主要产品上实行一个大规模的新的广告运动：
一种喷雾去污剂
一种新的液体洗涤剂
一种成熟的洗衣粉
这一广告运动采用 电视 （ 只做液体洗涤剂广告 ） 和 印刷媒体 （
做所有三种产品的促销广告,有优惠券 ）,达到的目标如下 （
其他收集到的数据见下页 ）,
喷雾去污剂 必须再增加 3%的市场份额
新的 液体洗涤剂 必须在洗涤剂市场中获得 18%的份额
洗衣粉 占洗涤剂市场的份额必须增加 4%
管理部门的目标是决定以最低的总成本达到市场份额的目标,
此时要在每种媒体上做多少钱的广告 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
利博公司广告组合问题的数据和数学模型（运筹学的线性规划模型） P44-47
决策变量,TV-电视广告的数量
PM-印刷媒体的数量目标函数,总成本最小化
Min C=1TV+2PM
约束条件：
（收益约束－函数约束）：
去污剂,1%PM? 3%
液体洗涤剂,3%TV+2%PM? 18%
洗衣粉,-1%TV+4%PM? 4%
且
TV,PM? 0 （非负约束）
产品每单位广告增加的市场份额需要最小的增加量电视 TV 印刷媒体 PM
去污剂 0% 1% 3%
液体洗涤剂 3% 2% 18%
洗衣粉 -1% 4% 4%
单位成本
(百万美元 ) 1 2
用 Excel的规划求解
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
利博公司广告组合问题的电子表格模型 P46
P 46 利博公司广告组合问题
P r o f i t & G a m b i t A d v e r t i s i n g - M i x P r o b l e m
电视 TV 印刷媒体 PM
单位成本 1 2
实际增加量 最小增加量去污剂 0% 1% 3% >= 3%
液体洗涤剂 3% 2% 18% >= 18%
洗衣粉 - 1 % 4% 8% >= 4%
电视 TV 印刷媒体 PM 总成本广告数量 4 3 10
每单位广告增加的市场份额
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
LP from Managerial Perspective
2.8 管理视角的线性规划 P48
线性规划对于辅助全世界各类公司的管理决策制定是无价的,功能强大的电子表格软件包的出现更进一步扩展了这一技术的应用 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.9 Summary 小结 P49
线性规划是对某几类问题的辅助管理决策制定的功能强大的技术 。 它的基本方法是建立一个称为线性规划模型的数学模型来表述问题,然后对这个模型进行分析 。
任何一个线性规划模型包含有：
表示要做决策的 决策变量
表述对这些决策变量的可行值限制的 约束条件
一个表示问题完全绩效测度的 目标函数
电子表格 Excel提供了一种对线性规划问题进行建模并且进行求解的灵活且直观的方式 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.1自动装配 P60
用 Excel的规划求解不同点：
多一个产量限制
参数的变化（如何保存问题）
F a m i l y
T hri l l s e e ke r(F )
Cl a s s y
Crui s e r(C )
单位利润 $3,600 $5,400
使用资源 资源限制工时 6 10.5 48000 <= 48000
车门 4 2 20000 <= 20000
F a m i l y
T hri l l s e e ke r(F )
Cl a s s y
Crui s e r(C ) 总利润每月产量 3800 2400 $ 2 6,6 4 0,0 0 0
<=
C 产量限制 3500
每辆汽车生产所需资源代数模型（数学模型）
决策变量,
假设每月生产 F辆 Family Thrillseeker，
C辆 Classy Cruiser
目标函数,总利润最大化
Max P=3600F+5400C
约束条件 （ (资源限制,Classy Cruiser产量限制，非负）：
工时,6F+10.5C? 48000
车门,4F+2C? 20000
C产量限制,C? 3500
非负,F,C? 0
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.1 自动装配
a.用 Excel的规划求解,得 F=3800,C＝ 2400,P=$26,640,000
b,在 a得到结果中,改变 Classy Cruiser的产量限制 （ 3500->3500*(1+20%)=4200),
重新运行规划求解,比较 a和 b利润变化,看是否超过广告费用,再作决策
c.将 a的工时限制改为 48000*(1+25%)=60000,重新运行规划求解
d.比较 a和 c利润变化,利润变化为最大加班费用
e.f,在 b基础上,工时限制改为 48000*(1+25%)=60000,重新运行规划求解,比较 a和 e
利润变化,以及广告和加班成本,再作决策
g,将 a的 FamilyThrillseeker(F)利润由 3600改为 2800,重新运行规划求解
h.将 a的 FamilyThrillseeker(F)工时由 6改为 7.5,重新运行规划求解
i,将 a的 Classy Cruiser(C)产量定为 3500,重新运行规划求解 (注意 C不变,仅 F变 )，
比较 a和 i利润变化,以及可以接受的利润降低额,再作决策
j,将 a中 F的利润 3600->2800(g),F工时 6->7.5(h)新情况,重新运行规划求解,得
F=1500,C＝ 3500,P=$23,100,000；是否进行广告活动：将 j的 Classy
Cruiser的产量限制改为 3500*(1+20%)＝ 4200,重新运行规划求解,与 j比较利润变化,以及广告成本,再作决策 。 是否加班：将 j的工时限制改为
48000*(1+25%)=60000,重新运行规划求解,与 j比较利润变化,以及加班成本
,再作决策 。 还有同时考虑广告活动和加班情况 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.2 降低咖啡屋的成本 P61原表（单位不统一）
含量 单位 含量 单位蛋白质 1.5 克/ 1 0 0 克 5.67 克/ 1 0 盎司铁 0.3 毫克/ 1 0 0 克 3.402 毫克/ 1 0 盎司维生素C 12 毫克/ 1 0 0 克 28.35 毫克/ 1 0 盎司成本 0.4 美元/ 磅 1 美元/ 磅土豆 绿豆单位换算表
1 磅 454 克
1 克 1000 毫克
1 盎司 28.35 克
1 公斤 1000 克单位统一换算成（ 1000 克和毫克,即,1000g 和 mg ）
土豆 T 绿豆 L
成本($/ kg) $0.881 $2.203
蛋白质 (g / kg ) 15 20
铁 (m g / kg ) 3 12
维生素C(m g/k g) 120 100
每 kg 土豆 T 和绿豆 L 所含的营养成分
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.2 P61
代数模型（数学模型）
决策变量,假设用土豆 T千克，绿豆 L千克目标函数,总成本最小化
Min C=0.881T+2.203L
约束条件 (营养要求，土豆和绿豆的总量比，总重? 10公斤）：
蛋白质,15T+20L? 180
铁,3T+12L? 80
维生素 C,120T+100L? 1050
总量比 T:L? 6:5,5T? 6L
总重 T+L,T+L? 10
非负,T,L? 0
不同点：
单位不统一
多口味和重量的限制单位统一换算成（ 1000 克和毫克,即,1000g 和 mg ）
土豆 T 绿豆 L
成本($/kg) $0.881 $2.203
所含营养 营养需求蛋白质 (g / kg ) 15 20 1 9 4,9 >= 180
铁 (m g / kg ) 3 12 8 0,0 >= 80
维生素C(mg/kg) 120 100 1 2 5 1,3 >= 1050
土豆 T 绿豆 L 总成本数量 (k g ) 6.15 5.13 $ 1 6,7 2
口味要求 5T > = 6L 30.8 >= 30.8
重量要求 T + L > = 10 11.3 >= 10
每 kg 土豆 T 和绿豆 L 所含的营养成分
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.2 降低咖啡屋的成本
a,用 Excel 的规划求解,得 T=6.15Kg,L＝ 5.13Kg，
C=$16.72
b,将 a的土豆和绿豆的总量比 (T/L? 6/5 -> 1/2,即 2T? L),重新运行规划求解
c,将 a的铁的营养要求 (80->65),重新运行规划求解
d,将 c的绿豆成本 (1->0.5$/磅 ),重新运行规划求解
e,将 c的绿豆改为利马豆 (蛋白质,铁,VC,成本 ),重新运行规划求解
f,比较 c和 e的成本,如果 e的成本比 c低,则满意
g,将 e的铁营养要求改为 120,VC营养要求改为 500,重新运行规划求解
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P52 习题 2.4,2.5,2,11,2.30,2.
35 (30克的 脂肪 改为 30克的 蛋白质 ） 或
2.45(将 VC的营养需求 600改为 60,否则无解 ）
作业要求 （ 只要下面三个 ）,
画出数据表格 （ 类似 P26的表 2.1,上机,在
Excel中实现即可 ）
写出数学模型 （ 手写作业,均要写明意义
）
决策变量
目标函数
约束条件
用 Excel求解得到的答案 （ 上机,在 Excel中实现即可 ）
特别提醒：
作业中的 数学模型 要求手写，每人每章交一次作业，老师抽查改，根据平时作业情况给平时成绩（ 10分
）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例
（第一问的数学模型也要交）
案例 2.1 自动装配 P60（ 前面学号 1-28）
案例 2.2 降低咖啡屋的成本 P61
（ 后面学号 29-56）
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第二章
Linear Programming,Basic Concepts
线性规划,基本概念
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
本章内容（ Topics）
2.1Three ClassicApplicationsofLP
三个经典的线性规划应用
2.2CaseStudy,WyndorGlassCo.Product-MixProblem
案例研究：伟恩德玻璃制品公司产品组合问题
2.4伟恩德玻璃制品公司产品组合问题的数学模型
2.5The GraphicalMethodforSolvingLP
线性规划的图解法 （ 两变量 ）
2.3,2.6UsingMicrosoftExcelSolverfor Solving LP
用微软 Excel求解线性规划问题
2.7一个最小化的例子 ---利博公司广告组合问题
2.8 ModelingfromManagerialPerspective
管理视角的建模
2.9Summary小结
案例 2.1自动装配
案例 2.2降低咖啡屋的成本
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
线性规划基本概念（ P19)
任何一个组织的管理通常都必须对如何向不同的活动分配资源的问题做出决策,以最好地达到组织的目标 。 线性规划是帮助管理这些决策的一个功能强大的问题解决工具 。
向活动进行分配的 资源 可以是比如 钱,不同的 人员 以及不同的 机器和设备 。 在许多情况下,大量不同的生产活动 （ 如生产不同产品 ）,营销活动 （ 如在不同媒体做广告 ）,金融活动 （ 如进行资金投资 ） 或其他一些活动 。 所有这些类型的活动 （ 以及其他 ） 就会导致一些问题的产生,因为他们 争夺同一资源 。
线性规划是应用数学模型对所研究的问题进行表述 。 线性 （
Linear） 是指一次关系 。 规划 （ Programming） 不是程序,而本质是计划 （ Planning） 。
所谓,线性,规划,是指如果目标函数是关于决策变量的线性函数,而且约束条件也都是决策变量的线性等式或线性不等式,则相应的规划问题就称为线性规划问题 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.1 Three Classical Applications of LP
三个经典的线性规划应用（ P20-22)
确定潘德罗索工业公司的产品组合
联合航空公司的员工排程 （ 排班 ）
Citgo石油公司的供应,配送和营销规划
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
公司经验
Ponderosa Industrial
潘德罗索工业公司 P20
潘德罗索应用成功的因素：
以 自然语言 为用户界面的财务计划系统,使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果,使得做决策的管理者能够很容易看懂整个过程 。
最优化系统是 互动的 （ interactive）,管理者在从一个版本的模型中获得一组最优解之后,可以提出一系列的 what-if问题,并能立即得到回应 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
公司经验
Personnel Scheduling at UA.
联合航空公司人员排程 P20-21
联合航空公司利用线性规划,来为其在主要的机场和订票点的上万个工作人员安排每周的工作时间表 。 目标是为了能够在满足客户的服务需要的同时,将一周内每天每半个小时的人员成本最小化 。 联合航空公司一些地点的规划模型却包括 20,000个决策变量 。
应用成功最主要的因素是 因为得到了运营经理以及其它员工的大力支持 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
公司经验
Citgo Petroleum Corporation
Citgo石油集团 P21-22
Citgo石油集团运用管理科学的技术,特别是线性规划,建立供应,配送与营销的建模系统将公司主要产品的供应,配送与营销通过公司庞大的销售与配送网络得到很好的协调 。 在 90年代中期创造了大量的财富 。
公司每种主要产品的模型都含有大约 1,500个决策变量以及 3，
000个确定需求的约束最重要的成功因素是高层管理者所给予的无限支持,并且设立运作协调副总裁,来负责评价与协调这一跨组织边界的模型所提供的建议 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.2 Case Study:Wyndor Glass Co,Product-Mix Problem
案例研究：伟恩德玻璃制品公司产品组合问题 P22
要生产两种新产品：
8英尺的铝框玻璃门 （ Door）
4英尺 × 6英尺的双把木框窗 （ Window）
背景资料 （ 由于某些产品销售量的下降,高层管理部门决定调整公司的产品线 ）,
伟恩德玻璃制品公司有三个工厂：
工厂 1：生产铝框和五金件
工厂 2：生产木框
工厂 3：生产玻璃和组装窗与门
生产两种新产品所需的工厂生产能力：
8英尺的铝框玻璃门 Door：需要工厂 1和工厂 3,不需要工厂 2
4英尺 × 6英尺的双把木框窗 Window：需要工厂 2和工厂 3
现在管理部门要考虑下列两个问题：
公司是否应该生产这两个新产品？
如果生产,两个新产品的产品生产组合如何？ 每周分别生产多少数量？
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
伟恩德玻璃制品公司产品组合问题 P25-26
（将实际问题转化为运筹学的线性规划问题）
问题,两种新产品的生产率 （ 每周生产数量 ） 的哪种组合能最大化两种产品的总利润？ 即如何安排生产,使两种产品的总利润最大 。
需收集 （ 或估计 ） 的信息 （ 数据 ）,
每家工厂的可得生产能力 （ 生产能力的限制 ）
生产每一产品各需要每家工厂多少生产能力 （ 单位消耗 ）
每一产品的单位利润 （ 用于目标函数 ）
现在收集到 (估计 )的数据 工厂单位产品的生产时间 每周可得时间门 D 窗 W
1 1小时 0 4小时
2 0 2小时 12小时
3 3小时 2小时 18小时单位利润 ($) $300 $500
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.4 伟恩德玻璃制品公司产品组合问题的数学模型（运筹学的线性规划模型） P31
决策变量,D-每周新门的生产数量
W-每周新窗的生产数量目标函数,总利润最大化
Max P=300D+500W
约束条件,
（资源约束－函数约束 )：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W?18
且
D,W? 0 （非负约束）
为了最大化利润或最小化成本的目的，需要对一些稀缺资源进行配置
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Components of the Model
模型的组成部分
Decisionvariables决策变量
Objectivefunction 目标函数
Constraints约束条件附,P33 线性规划模型的一些术语决策变量、目标函数、目标函数值、非负约束、
函数约束、参数、解、可行解、最优解注意：线性规划的几种可能解：无解、多个最优解、唯一最优解
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Assumptions of Linear Programming
线性规划的假设
Linearity 线性
Divisibility 可分性
Certainty 确定性
Nonnegativity 非负性
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Why Use Linear Programming?
为什么要使用线性规划
线性规划很容易而有效率地被求解
如果存在最优解,则肯定能够找到
功能强 大的敏感性分析 （ sensitivity
analysis）
许多实际问题本质上是线性的
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
线性规划要确定决策变量 x1,x2,…,xn 使得
M a x i m i z e Z? c
1
x
1
c
n
x
n
Objective Function
s ubj e c t t o
a
11
x
1
a
1 n
x
n
b
1
a
21
x
1
a
2 n
x
n
b
2
a
m 1
x
1
a
mn
x
n
b
m
Functional Constraints
a nd
x
1
0,?,x
n
0? Nonnegativity Constraints
已知参数 c1,…,cn ; a11,…,amn ; b1,…,bm。
Mathematical Statement of LP Problem
线性规划的数学描述
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Steps in Formulating LP Problem
线性规划问题建模步骤
需要做哪些决策？ 决策变量是什么？
问题的目标是什么？ 写出目标函数 （ 与决策变量有关,
是决策变量的 线性函数 ）
资源和需求之间的情况如何？ 写出约束条件 （ 也与决策变量有关,是决策变量的 线性函数 ）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.5 The Graphical Method for Solving LP
线性规划的图解法（两变量）的步骤 P33
画出每个函数约束的约束边界线
找出由所有约束条件都同时满足所决定的可行域
确定一条目标函数线的斜率,所有其他目标函数线具有与之相同的斜率
用这一斜率在可行域内向目标函数值增加的方向移动
,直到在可行域的一个点时停止,此时为最优目标函数线
最优目标函数线上的可行点就是一个最优解
在光盘的 Interactive Management Science文件夹下
,有互动模型 LP,可以帮助我们理解图解法
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
(0,0)
(4,0)
(0,6)
P r odu c t i on ra t e
fo r w i ndo w s
P r odu c t i on ra t e for do ors
P r ofi t = $3,000
(2,6)
P r ofi t = $3,600
P r ofi t = $2,700
P r ofi t = $1,200
F e a s i bl e
re gi on
32
1
(4,3)
P r ofi t = 0
D
W
The Simplex Method for Solving LP
线性规划的 单纯形法
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Using Excel Solver for Solving LP
用微软 Excel的规划求解
规划求解不是典型安装,要加载宏,在工具菜单中 加载宏
,选,规划求解,(需要 Office安装盘或在安装时已经全部安装 ) 或 直 接 拷 贝 （ C:\Program Files\Microsoft
Office\OFFICE11\Library文件夹下 ） SOLVER文件夹下的两个文件并直接双击运行 Solver.xla加载宏也可 。 当然最好将 Excel全部安装 。
利用规划求解 （ 在,工具,菜单中选,规划求解,）
目标单元格,目标函数 （ 所在单 元格 地址,最大或最小或某值 ）
可变单元格：决策变量 （ 所在单 元格 地 址 ）
约束条件：函数约束 （ 所在单 元格 地 址 和约束值 ）
选项
采用线性模型
假定非负 （ 非负约束 ）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
在 Excel的 帮助 中，输入“规划求解”，可以查到,规划求解”算法与方法? Microsoft Excel 的,规划求解,工具取自德克萨斯大学奥斯汀分校的
Leon Lasdon 和克里夫兰州立大学的 Allan Waren 共同开发的
GeneralizedReducedGradient(GRG2)非线性最优化代码 。
线性和整数规划问题取自 Frontline Systems 公司的 John Watson 和
Dan Fylstra 提供的有界变量 单纯形法 和 分支边界法 （ 分支定界法 ） 。
有关,规划求解,使用的内部求解过程的详细信息,请与下列地址联系：
FrontlineSystems,Inc.
P.O.Box4288
InclineVillage,NV89450-4288
(775)831-0300
网站,http://www.frontsys.com
电子邮件,info@frontsys.com
Microsoft Excel Solver 程序代码的部分为 Frontline Systems,Inc 1990
,1991,1992 和 1995 年版权所有,部分为 Optimal Methods,Inc 公司
1989年版权所有 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.3 Building Wyndor Co,Problem Model in Excel
在电子表格上建立伟恩德公司问题的模型 P26
在用 Excel为问题建立数学模型 （ 这里是一个线性规划模型 ） 的过程中,有三个问题需要得到回答：
要做出的决策 （ decisions)是什么？ － 决策变量
在做出这些决策上有哪些约束条件 （ constraints）?－ 约束条件
这些决策的全部绩效测度 （ measure of performance)是什么
？ － 目标函数
在 Excel中,伟恩德公司模型的三个问题具体如下：
要做出的决策是两种新产品的生产率 （ productionrates)
对决策上的约束条件是两种新产品在相应工厂里每周生产时间不能超过每个工厂的可得生产时间
这些决策的全部绩效测度是这两种新产品的总利润 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.3 Building Wyndor Co,Problem Model in Excel
在电子表格上建立伟恩德公司问题的模型 P29
伟恩德公司模型的三个问题 （ 决策变量,函数约束,
目标函数 ）,具体在 Excel的实现 （ 单元格和公式,
用不同底色的单元格表示 ）,
P 43 伟恩德玻璃制品公司产品组合问题
Wyndor Glass Co,Product-Mix Problem
门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
使用时数 每周可得时数工厂 1 1 0 2 <= 4
工厂 2 0 2 12 <= 12
工厂 3 3 2 18 <= 18
门 D o o r s 窗 W i n d o w s 总利润每周生产数量 2 6 $ 3,6 0 0
每个产品所需生产时数
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.3 Building Wyndor Co,Problem Model in Excel
在电子表格上建立伟恩德公司问题的模型 P26-31
（四类单元格）
伟恩德公司模型的三个问题 （ 决策变量,函数约束,目标函数 ）,
具体在 Excel的实现 （ 单元格的位置和公式 ）,
将收集到 (估计 )的数据以直观的形式输入到 Excel中 （ 当然也要根据需要确定位置－－ 数据单元格 DataCells）
确定决策变量 （ 可变单元格 Changing Cells） 位置：每周生产数量
C12:D12
给单元格或区域 Range命名：插入 -->名称 -->定义 （ 或指定 ）
确定函数约束 （ 三个工厂生产时间限制,注意：与决策变量有关,是决策变量的线性函数 ） 位置和公式－－ 输出单元格 OutputCells：
E7=C7*C12+D7*D12＝ SUMPRODUCT(C7:D7,每周生产数量 )
E8=C8*C12+D8*D12＝ SUMPRODUCT(C8:D8,每周生产数量 )
E9=C9*C12+D9*D12＝ SUMPRODUCT(C9:D9,每周生产数量 )
确定目标函数 （ 与决策变量有关,是决策变量的线性函数 ） 位置和公式
,目标单元格 TargetCellG12(总利润 )=SUMPRODUCT(单位利润,每周生产数量 )
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.6 Using Excel for Solving LP
应用 Excel求解线性规划问题 P41-44
Excel中,工具－ >规划求解,在对话框中：
目标单元格,目标函数 （ 所在单元格地址,最大或最小或某值 ）
可变单元格,决策变量 （ 所在单 元格 地址 ）
约束条件,函数约束 （ 所在单 元格 地址和约束值 ）
选项
采用 线性 模型
假定 非负
单击,求解,按钮,进入,求解结果,对话框,即可知道求解结果 （ 找到一个最优解或找不到可行解 ）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.7 一个最小化的例子利博公司广告组合问题 P44
利博公司生产家用的清洁产品,管理层决定集中在下列三种主要产品上实行一个大规模的新的广告运动：
一种喷雾去污剂
一种新的液体洗涤剂
一种成熟的洗衣粉
这一广告运动采用 电视 （ 只做液体洗涤剂广告 ） 和 印刷媒体 （
做所有三种产品的促销广告,有优惠券 ）,达到的目标如下 （
其他收集到的数据见下页 ）,
喷雾去污剂 必须再增加 3%的市场份额
新的 液体洗涤剂 必须在洗涤剂市场中获得 18%的份额
洗衣粉 占洗涤剂市场的份额必须增加 4%
管理部门的目标是决定以最低的总成本达到市场份额的目标,
此时要在每种媒体上做多少钱的广告 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
利博公司广告组合问题的数据和数学模型（运筹学的线性规划模型） P44-47
决策变量,TV-电视广告的数量
PM-印刷媒体的数量目标函数,总成本最小化
Min C=1TV+2PM
约束条件：
（收益约束－函数约束）：
去污剂,1%PM? 3%
液体洗涤剂,3%TV+2%PM? 18%
洗衣粉,-1%TV+4%PM? 4%
且
TV,PM? 0 （非负约束）
产品每单位广告增加的市场份额需要最小的增加量电视 TV 印刷媒体 PM
去污剂 0% 1% 3%
液体洗涤剂 3% 2% 18%
洗衣粉 -1% 4% 4%
单位成本
(百万美元 ) 1 2
用 Excel的规划求解
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
利博公司广告组合问题的电子表格模型 P46
P 46 利博公司广告组合问题
P r o f i t & G a m b i t A d v e r t i s i n g - M i x P r o b l e m
电视 TV 印刷媒体 PM
单位成本 1 2
实际增加量 最小增加量去污剂 0% 1% 3% >= 3%
液体洗涤剂 3% 2% 18% >= 18%
洗衣粉 - 1 % 4% 8% >= 4%
电视 TV 印刷媒体 PM 总成本广告数量 4 3 10
每单位广告增加的市场份额
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
LP from Managerial Perspective
2.8 管理视角的线性规划 P48
线性规划对于辅助全世界各类公司的管理决策制定是无价的,功能强大的电子表格软件包的出现更进一步扩展了这一技术的应用 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
2.9 Summary 小结 P49
线性规划是对某几类问题的辅助管理决策制定的功能强大的技术 。 它的基本方法是建立一个称为线性规划模型的数学模型来表述问题,然后对这个模型进行分析 。
任何一个线性规划模型包含有：
表示要做决策的 决策变量
表述对这些决策变量的可行值限制的 约束条件
一个表示问题完全绩效测度的 目标函数
电子表格 Excel提供了一种对线性规划问题进行建模并且进行求解的灵活且直观的方式 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.1自动装配 P60
用 Excel的规划求解不同点：
多一个产量限制
参数的变化（如何保存问题）
F a m i l y
T hri l l s e e ke r(F )
Cl a s s y
Crui s e r(C )
单位利润 $3,600 $5,400
使用资源 资源限制工时 6 10.5 48000 <= 48000
车门 4 2 20000 <= 20000
F a m i l y
T hri l l s e e ke r(F )
Cl a s s y
Crui s e r(C ) 总利润每月产量 3800 2400 $ 2 6,6 4 0,0 0 0
<=
C 产量限制 3500
每辆汽车生产所需资源代数模型（数学模型）
决策变量,
假设每月生产 F辆 Family Thrillseeker，
C辆 Classy Cruiser
目标函数,总利润最大化
Max P=3600F+5400C
约束条件 （ (资源限制,Classy Cruiser产量限制，非负）：
工时,6F+10.5C? 48000
车门,4F+2C? 20000
C产量限制,C? 3500
非负,F,C? 0
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.1 自动装配
a.用 Excel的规划求解,得 F=3800,C＝ 2400,P=$26,640,000
b,在 a得到结果中,改变 Classy Cruiser的产量限制 （ 3500->3500*(1+20%)=4200),
重新运行规划求解,比较 a和 b利润变化,看是否超过广告费用,再作决策
c.将 a的工时限制改为 48000*(1+25%)=60000,重新运行规划求解
d.比较 a和 c利润变化,利润变化为最大加班费用
e.f,在 b基础上,工时限制改为 48000*(1+25%)=60000,重新运行规划求解,比较 a和 e
利润变化,以及广告和加班成本,再作决策
g,将 a的 FamilyThrillseeker(F)利润由 3600改为 2800,重新运行规划求解
h.将 a的 FamilyThrillseeker(F)工时由 6改为 7.5,重新运行规划求解
i,将 a的 Classy Cruiser(C)产量定为 3500,重新运行规划求解 (注意 C不变,仅 F变 )，
比较 a和 i利润变化,以及可以接受的利润降低额,再作决策
j,将 a中 F的利润 3600->2800(g),F工时 6->7.5(h)新情况,重新运行规划求解,得
F=1500,C＝ 3500,P=$23,100,000；是否进行广告活动：将 j的 Classy
Cruiser的产量限制改为 3500*(1+20%)＝ 4200,重新运行规划求解,与 j比较利润变化,以及广告成本,再作决策 。 是否加班：将 j的工时限制改为
48000*(1+25%)=60000,重新运行规划求解,与 j比较利润变化,以及加班成本
,再作决策 。 还有同时考虑广告活动和加班情况 。
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.2 降低咖啡屋的成本 P61原表（单位不统一）
含量 单位 含量 单位蛋白质 1.5 克/ 1 0 0 克 5.67 克/ 1 0 盎司铁 0.3 毫克/ 1 0 0 克 3.402 毫克/ 1 0 盎司维生素C 12 毫克/ 1 0 0 克 28.35 毫克/ 1 0 盎司成本 0.4 美元/ 磅 1 美元/ 磅土豆 绿豆单位换算表
1 磅 454 克
1 克 1000 毫克
1 盎司 28.35 克
1 公斤 1000 克单位统一换算成（ 1000 克和毫克,即,1000g 和 mg ）
土豆 T 绿豆 L
成本($/ kg) $0.881 $2.203
蛋白质 (g / kg ) 15 20
铁 (m g / kg ) 3 12
维生素C(m g/k g) 120 100
每 kg 土豆 T 和绿豆 L 所含的营养成分
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.2 P61
代数模型（数学模型）
决策变量,假设用土豆 T千克，绿豆 L千克目标函数,总成本最小化
Min C=0.881T+2.203L
约束条件 (营养要求，土豆和绿豆的总量比，总重? 10公斤）：
蛋白质,15T+20L? 180
铁,3T+12L? 80
维生素 C,120T+100L? 1050
总量比 T:L? 6:5,5T? 6L
总重 T+L,T+L? 10
非负,T,L? 0
不同点：
单位不统一
多口味和重量的限制单位统一换算成（ 1000 克和毫克,即,1000g 和 mg ）
土豆 T 绿豆 L
成本($/kg) $0.881 $2.203
所含营养 营养需求蛋白质 (g / kg ) 15 20 1 9 4,9 >= 180
铁 (m g / kg ) 3 12 8 0,0 >= 80
维生素C(mg/kg) 120 100 1 2 5 1,3 >= 1050
土豆 T 绿豆 L 总成本数量 (k g ) 6.15 5.13 $ 1 6,7 2
口味要求 5T > = 6L 30.8 >= 30.8
重量要求 T + L > = 10 11.3 >= 10
每 kg 土豆 T 和绿豆 L 所含的营养成分
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例 2.2 降低咖啡屋的成本
a,用 Excel 的规划求解,得 T=6.15Kg,L＝ 5.13Kg，
C=$16.72
b,将 a的土豆和绿豆的总量比 (T/L? 6/5 -> 1/2,即 2T? L),重新运行规划求解
c,将 a的铁的营养要求 (80->65),重新运行规划求解
d,将 c的绿豆成本 (1->0.5$/磅 ),重新运行规划求解
e,将 c的绿豆改为利马豆 (蛋白质,铁,VC,成本 ),重新运行规划求解
f,比较 c和 e的成本,如果 e的成本比 c低,则满意
g,将 e的铁营养要求改为 120,VC营养要求改为 500,重新运行规划求解
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P52 习题 2.4,2.5,2,11,2.30,2.
35 (30克的 脂肪 改为 30克的 蛋白质 ） 或
2.45(将 VC的营养需求 600改为 60,否则无解 ）
作业要求 （ 只要下面三个 ）,
画出数据表格 （ 类似 P26的表 2.1,上机,在
Excel中实现即可 ）
写出数学模型 （ 手写作业,均要写明意义
）
决策变量
目标函数
约束条件
用 Excel求解得到的答案 （ 上机,在 Excel中实现即可 ）
特别提醒：
作业中的 数学模型 要求手写，每人每章交一次作业，老师抽查改，根据平时作业情况给平时成绩（ 10分
）
Chapter 2
Linear Programming:Basic Concepts
线性规划,基本概念
RUC Information School,Ye Xiang,2007
案例
（第一问的数学模型也要交）
案例 2.1 自动装配 P60（ 前面学号 1-28）
案例 2.2 降低咖啡屋的成本 P61
（ 后面学号 29-56）
