Chapter 4 Linear Programming: Formulation and applications 线性规划:建模与应用 Data Model and decisions 数据、模型与决策 第四章 Linear Programming Formulation and Applications 线性规划:建模与应用 RuC Information School, Ye Xiang 2007
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 线性规划:建模与应用 本章内容( Topics)P91 Introduction the Key Categories of Lp problems 介绍线性规划问题的三种主要类型(取决于函数约束): 资源分配问题( resource-allocation,≤) 成本收益平衡问题(cost- benefit-trade-o,≥) RuC Information School, Ye Xiang 2007
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 线性规划:建模与应用 Case Study: Super Grain Corp. Advertising-Mix Problem 41案例研究:超级食品公司的广告组合问题P92 超级食品公司如何才能大规模地进入已有许多供应商 的早餐谷物食品市场。 委托了一家一流的广告公司来帮助设计全国性的促销 活动,以使“脆始”( Crunchy Start)取得尽可能多 的消费者的认可。 费用情况:最多可以给广告商的酬金100万和400万的 广告费 ·广告公司确定了这一产品最有效的三种广告媒介: 口媒介1:星期六上午儿童节目的电视广告。 口媒介2:食品与家庭导向的杂志上的广告。 口媒介3:主要报纸星期天增刊上的广告。 RuC Information School, Ye Xiang 2007
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 线性规划:建模与应用 数据P93 成本(美元 成本分类 每次电视广告 每份杂志广告 每份星期天增刊广告 广告预算 $300000 $150,000 $100,000 策划预算 90.000 30.000 40.000 广告受众期望值 1,300,000 600.000 500,000 RuC Information School, Ye Xiang 2007
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
Exce模型P95 Chapter 4 Linear Programming: Formulation and applications 线性规划:建模与应用 P92超级谷物公司的广告组合问题 Super Grain Corp. Advertising- Mix Problem) 电视广告TV 杂志广告M屋期天增刊广告SS 每次广告受众数量1300 600 500 (千人次) 每次广告成本(千美元) 使用资金可用预算 广告预算 300 150 100 4000<=4000 策划预算 40 1,000<= 1,000 电视广告TV杂志广告M星期天增刊广告Ss 广告受众总量 广告数量 0 20 10 17.000 < 最多电视时段 注意P96-97: 结果是否符合实际情况:不做电视广告? 模型准确性评价P96:数学模型是否真的体现实际情况 RuC Information School, Ye Xiang 2007
Chapter 4 Linear Programming: Formulation and Applications 线性规划:建模与应用 RUC Information School ,Ye Xiang ,2007 Excel模型P95 注意P96-97： • 结果是否符合实际情况：不做电视广告？ • 模型准确性评价P96：数学模型是否真的体现实际情况 P92超级谷物公司的广告组合问题(Super Grain Corp. Advertising-Mix Problem) 电视广告T V 杂志广告M 星期天增刊广告S S 每次广告受众数量 1,300 600 500 (千人次) 使用资金 可用预算 广告预算 300 150 100 4,000 < = 4,000 策划预算 90 30 40 1,000 < = 1,000 电视广告T V 杂志广告M 星期天增刊广告S S 广告受众总量 广告数量 0 20 10 17,000 < = 最多电视时段 5 每次广告成本（千美元）
Chapter 4 Linear Programming: Formulation and applications 数学模型P96 线性规划:建模与应用 决策变量: TV一电视上的广告时段数目 M一杂志上的广告数目 ss一星期天增刊上的广告数目 目标函数:广告受众总量最大化 Max z=1300TV+600M+500SS 约束条件: 广告费用:300TV+150M+100SS≤4000 策划成本:90TV+30M+40SS≤1000 电视广告时段:Tv 5 且 非负: TVM.SS≥0 RuC Information School, Ye Xiang 2007
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 问题类型 线性规划:建模与应用 Resource-allocation problem 4,2资源分配问题P99 资源分配( resource- allocation)问题是将有限的瓷源 分配到各种活动中去的线性规划问题。这一类问题的 共性是在线性规划模型中每一个函数限制均为资源限 制 (resource constraint),并且每一种有限资源都可以表 现为如下的形式: 使用的资源数量≤可用的资源数量 RuC Information School, Ye Xiang 2007
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 线性规划:建模与应用 Datum Gathering 收集数据P100 对任何资源分配问题,有三种数据必须收集: 1、每种资源的可供量(可用量) 2、每一种活动所需要的各种资源的数量,对于每一种资 源与活动的组合,单位活动所消耗的资源量必须首先估 计出来(单位资源使用量) 3、每一种活动对总的绩效测度的单位贡献(单位利润) RuC Information School, Ye Xiang 2007
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 实际举例 线性规划:建模与应用 Think-Big development co 梦大发展公司资金预算问题P101 梦大( Think-Big)发展公司是商务房地产开发项目的主 要投资商。 目前,该公司有机会在三个建设项目中投资 口建造高层办公楼 Construct a high- -rise office building 口建造宾馆 Construct a hote 口建造购物中心 Construct a shopping center 每个项目都要求投资者在四个不同的时期投资:在当前 预付定金,以及一年、二年、三年后分别追加投资。 可以按比例投资项目 RuC Information School, Ye Xiang 2007
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 线性规划:建模与应用 梦大发展公司部分投资项目的财务数据P101 所需投资资金(百万美元) Year 办公楼项目宾馆项目购物中心项目 现在可用资金 0(当前) 80 90 2500万美元, 年后又有2000 60 80 50 万美元, 90 80 20 两年后又有2000 万美元 10 70 60 三年后再有1500 净现值NPV 45 70 50 万美元 (Net Present Value) RuC Information School, Ye Xiang 2007
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 万美元