Chapter 2 inear Programming: Basic Concepts 线性规划基本概念 Data Model and decisions 数据、模型与决策 第二章 Linear Programming: Basic Concepts 线性规划基本概念 RuC Information School, Ye Xiang 2007
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 本章内容( Topics 线性规划基本概念 2.1 Three Classic Applications of LP 个经典的线性规划应用 2.2 Case Study: Wyndor glass co Product-Mix Problem 案例研究:伟恩德玻璃制品公司产品组合问题 24伟恩德玻璃制品公司产品组合问题的数学模型 2.5 The graphical Method for Solving lp 线性规划的图解法(两变量) 2.3 2.6Using microsoft excel solver for solving lP 用微软 Excel求解线性规划问题 27一个最小化的例子一利博公司广告组合问题 2.8 Modeling from Managerial Perspective 管理视角的建模 29 Summary小结 案例21自动装配 案例22降低咖啡屋的成本 RuC Information School, Ye Xiang 2007
Chapter 2 Linear Programming:Basic Concepts 线性规划:基本概念 RUC Information School ,Ye Xiang ,2007 本章内容（Topics） ▪ 2.1 Three Classic Applications of LP 三个经典的线性规划应用 ▪ 2.2 Case Study: WyndorGlass Co. Product-MixProblem 案例研究：伟恩德玻璃制品公司产品组合问题 ▪ 2.4 伟恩德玻璃制品公司产品组合问题的数学模型 ▪ 2.5 The GraphicalMethod for SolvingLP 线性规划的图解法（两变量） ▪ 2.3、2.6Using MicrosoftExcel Solver for Solving LP 用微软Excel求解线性规划问题 ▪ 2.7 一个最小化的例子---利博公司广告组合问题 ▪ 2.8 Modeling from ManagerialPerspective 管理视角的建模 ▪ 2.9 Summary 小结 ▪ 案例2.1自动装配 ▪ 案例2.2降低咖啡屋的成本
Chapter 2 线性规划基本概念(l2 Programming: Basic Concept 线性规划:基本概念 任何一个组织的管理通常都必须对如何向不同的活动分配资源的 问题做出决策,以最好地达到组织的目标。线性规划是帮助管理 这些决策的一个功能强大的问题解决工具。 向活动进行分配的资源可以是比如钱、不同的人员以及不同的机 器和设备。在许多情况下,大量不同的生产活动(如生产不同 品)、营销活动(如在不同媒体做广告)、金融活动(如进行资 金投资)或其他一些活动。所有这些类型的活动(以及其他)就 会导致一些问题的产生,因为他们争夺同一资源。 线性规划是应用数学模型对所研究的问题进行表述。线性( Linear)是指一次关系。规划( Programming)不是程序,而本 质是计划( Planning)。 所谓“线性”规划,是指如果目标函数是关于决策变量的线性函 数,而且约束条件也都是决策变量的线性等式或线性不等式,则 相应的规划问题就称为线性规划问题。 RuC Information School, Ye Xiang 2007
Chapter 2 Linear Programming:Basic Concepts 线性规划:基本概念 RUC Information School ,Ye Xiang ,2007 线性规划基本概念（P19) ▪ 任何一个组织的管理通常都必须对如何向不同的活动分配资源的 问题做出决策，以最好地达到组织的目标。线性规划是帮助管理 这些决策的一个功能强大的问题解决工具。 ▪ 向活动进行分配的资源可以是比如钱、不同的人员以及不同的机 器和设备。在许多情况下，大量不同的生产活动（如生产不同产 品）、营销活动（如在不同媒体做广告）、金融活动（如进行资 金投资）或其他一些活动。所有这些类型的活动（以及其他）就 会导致一些问题的产生，因为他们争夺同一资源。 ▪ 线性规划是应用数学模型对所研究的问题进行表述。线性（ Linear）是指一次关系。规划（Programming）不是程序，而本 质是计划（Planning）。 ▪ 所谓“线性”规划，是指如果目标函数是关于决策变量的线性函 数，而且约束条件也都是决策变量的线性等式或线性不等式，则 相应的规划问题就称为线性规划问题
Chapter 2 Linear Programming: Basic Concepts 线性规划基本概念 2.1 Three Classical Applications of LP 三个经典的线性规划应用(P20-2) 确定潘德罗索工业公司的产品组合 联合航空公司的员工排程(排班) Citgo石油公司的供应、配送和营销规划 RuC Information School, Ye Xiang 2007
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 公司经验 线性规划基本概念 Ponderosa industrial 潘德罗索工业公司P20 潘德罗索应用成功的因素: 以自然语言为用户界面的财务计划系统,使用自然语 言而不是数学符号来显示线性规划模型各个组成部分 以及输出的结果,使得做决策的管理者能够很容易看 懂整个过程。 最优化系统是互动的( interactive),管理者在从 个版本的模型中获得一组最优解之后,可以提出一系 列的 what-if问题,并能立即得到回应。 RuC Information School, Ye Xiang 2007
Chapter 2 Linear Programming:Basic Concepts 线性规划:基本概念 RUC Information School ,Ye Xiang ,2007 公司经验 Ponderosa Industrial 潘德罗索工业公司 P20 潘德罗索应用成功的因素： 以自然语言为用户界面的财务计划系统，使用自然语 言而不是数学符号来显示线性规划模型各个组成部分 以及输出的结果，使得做决策的管理者能够很容易看 懂整个过程。 最优化系统是互动的（interactive），管理者在从一 个版本的模型中获得一组最优解之后，可以提出一系 列的what-if问题，并能立即得到回应
Chapter 2 Linear Programming: Basic Concepts 公司经验 线性规划基本概念 Personnel scheduling at Ua 联合航空公司人员排程P20-21 联合航空公司 利用线性规划,来为其在主要的机场和订票点的上万 个工作人员安排每周的工作时间表。目标是为了能够 在满足客户的服务需要的同时,将一周内每天每半个 小时的人员成本最小化。联合航空公司一些地点的规 划模型却包括20,000个决策变量。 应用成功最主要的因素是因为得到了运营经理以及其 它员工的大力支持。 RuC Information School, Ye Xiang 2007
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 公司经验 线性规划基本概念 Citgo Petroleum Corporation Citgo石油集团P2122 Citgo石油集团 运用管理科学的技术,特别是线性规划,建立供应、配送与营销 的建模系统将公司主要产品的供应、配送与营销通过公司庞大 的销售与配送网络得到很好的协调。在90年代中期创造了大量 的财富。 公司每种主要产品的模型都含有大约1,500个决策变量以及3, 000个确定需求的约束 最重要的成功因素是高层管理者所给予的无限支持,并且设立运 作协调副总裁,来负责评价与协调这一跨组织边界的模型所提 供的建议。 RuC Information School, Ye Xiang 2007
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 2.2 Case Study: Wyndor Glass Co Product-Mix Problenty 性规划:基本概念 案例研究:伟恩德玻璃制品公司产品组合问题P22 要生产两种新产品 8英尺的铝框玻璃门(Door) 4英尺×6英尺的双把木框窗( Window) 背景资料(由于某些产品销售量的下降,高层管理部门决定调整 公司的产品线): 伟恩德玻璃制品公司有三个工厂: 工厂1:生产铝框和五金件 工厂2:生产木框 工厂3:生产玻璃和组装窗与门 生产两种新产品所需的工厂生产能力: 寒尺的铝栋玻的把要工厂不瓶要3不需要2 现在管理部门要考虑下列两个问题 公司是否应该生产这两个新产品? 如果生产,两个新产品的产品生产组合如何?每周分别生产多少数量? RuC Information School, Ye Xiang 2007
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 伟恩德玻璃制品公司产品组合问题P25-26 线性规划基本概念 (将实际问题转化为运筹学的线性规划问题) 问题:两种新产品的生产率(每周生产数量)的哪种组合能最大化 两种产品的总利润?即如何安排生产,使两种产品的总利润最大 需收集(或估计)的信息(数据): 每家工厂的可得生产能力(生产能力的限制) 生产每一产品各需要每家工厂多少生产能力(单位消耗) 每一产品的单位利润(用于目标函数) 现在收集到估计的数据工厂单位产品的生产时间 每周可得时间 门D 窗W 1小时 0 4小时 2小时 12小时 3小时 2小时 18小时 单位利润(s)$300s00 RuC Information School, Ye Xiang 2007
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 inear Programming: Basic Concepts 线性规划基本概念 24伟恩德玻璃制品公司产品组合问题 的数学模型(运筹学的线性规划模型)P31 决策变量:D-每周新门的生产数量 W每周新窗的生产数量 目标函数:总利润最大化 为了最大化利润 Max P=300D+500w 或最小化成本的 约束条件 目的,需要对 (资源约束一函数约束) 工厂1:D≤4 些稀缺资源进行 工厂2:2W≤12 配置 工厂3:3D+2W≤18 且 D,W≥0(非负约東) RuC Information School, Ye Xiang 2007
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 （非负约束） 为了最大化利润 或最小化成本的 目的，需要对一 些稀缺资源进行 配置