线性规划优秀文档

第三节线性规划——建模与应用应用线性规划问题解决实际问题，最重要的一个步骤就是首先要建立实际问题的线性规划问题的数学模型。建模是一项技巧性很强的创造性的工作，既要求对实际问题有深入的了解，又要求对线性规划模型的结构特点有很好的把握。本节内容3.1资源分配问题3.2成本收益平衡问题3.3网络配送问题教学目标熟悉线性规划问题的类型；理解线性规划问题的基本建模程序；能洞察这些问题产生的背景中；学习如何用线性规划描述与分析管理问题；3.1资源分配问题资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数约束均为资源约束,并且每一种资源都可以表现为如下的形式：使用的资源数量可用的资源数量问题的目标：最有效地利用各种资源，使获利最大解：这是一个资源分配问题资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。确定需求约束的形式如下：表3－1显示了四个时期每个项目所需资金（百万元）。工厂1运送到顾客2的产品为2个设司机和乘务人员分别在各时间段一开始时上班，并(1)每种收益的最低可接受水平（管理决策）某公司是商务房地产开发项目的主要投资商能洞察这些问题产生的背景中；研究如何规划每个轮班人员才能以最小的成本提供令人满意的服务。项目3：建造购物中心。既能满足工作需要，又配备最少司机和乘务人员?解:本问题是一个平衡运输问题项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；数学模型（线性规划模型）对资源分配问题，必须收集三种数据：（1）每种资源的可供量；（2）每一种活动所需要的各种资源的数量,对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来；（3）每一种活动对总的绩效测度（如总利润）的单位贡献（如单位利润）。

某公司是商务房地产开发项目的主要投资商该公司有机会在三个建设项目中投资： 项目1：建造高层办公楼； 项目2：建造宾馆； 项目3：建造购物中心。每个项目都要求投资者在四个不同的时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资。表3－1显示了四个时期每个项目所需资金（百万元）。投资者可以按一定的比例进行投资和获得相应比例的收益。年份办公楼项目宾馆项目购物中心项目0（现在）408090160805029080203107060净现值457050公司目前有2500万元资金可供投资，预计一年后，又可获得2000万元，两年后获得另外的2000万元，三年后还有1500万元以供投资。那么，该公司要在每个项目中投资多少比例，才能使其投资组合获得最大的总净现值？解：这是一个资源分配问题(1)决策变量

设：x1，x2，x3分别为在办公楼项目、宾馆项目、购物中心项目中的投资比例(2)目标函数

本问题的目标是总净现值最大。(3)约束条件：

公司在各期可获得的资金限制（资源约束）注意：前一期尚未使用的资金，可以在下一期使用（为了简化，不考虑资金可获得的利息）每一时点的资金限制就表现为累计的资金。年份办公楼项目宾馆项目购物中心项目可用资金0（现在）40809025110016014045219024016065320031022080净现值457050数学模型（线性规划模型）电子表格模型资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。使用的资源数量可用的资源数量该公司有机会在三个建设项目中投资：（i＝F1,F2;j=C1,C2,C3)购物中心项目的投资比例为13.项目1：建造高层办公楼；(3)每种活动的单位成本成本收益平衡问题需要的三种数据：成本收益平衡问题与资源分配问题的形式完全不同，这种差异主要是由问题的管理目标不同而造成的。应用线性规划问题解决实际问题，最重要的一个步骤就是首先要建立实际问题的线性规划问题的数学模型。表3－1显示了四个时期每个项目所需资金（百万元）。工厂2运送到顾客3的产品为9个该公司有机会在三个建设项目中投资：规划求解结果为：不投资办公楼项目宾馆项目的投资比例为16.5％购物中心项目的投资比例为13.11％此时获得的总利润最大，为1811万元。3.2成本收益平衡问题成本收益平衡问题与资源分配问题的形式完全不同，这种差异主要是由问题的管理目标不同而造成的。对于成本收益平衡问题，管理层采取更为主动的姿态，他们指明哪些收益必须实现（不管如何使用资源），并且要以最低的成本实现所指明的收益。管理层期望获得成本和收益之间的适度平衡。问题的目标：通过选择各种活动水平的组合，以最小的成本来实现最低可接受的各种收益水平成本收益平衡问题的共性是所有的函数约束均为收益约束，并具有如下的形式：

完成的水平最低可接受的水平成本收益平衡问题需要的三种数据：(1)每种收益的最低可接受水平（管理决策）(2)每一种活动对每一种收益的贡献(单位活动的贡献)(3)每种活动的单位成本排班问题是成本收益平衡问题研究的最重要的应用领域之一在该领域中，管理层意识到在向顾客提供令人满意的服务水平的同时必须进行成本控制，因此必须寻找成本和收益之间的平衡。研究如何规划每个轮班人员才能以最小的成本提供令人满意的服务。例

某航空公司正准备增加其中心机场的往来航班，因此需要雇佣更多的服务人员。排班1:6AM～2PM排班2:8AM～4PM

排班3:中午～8PM排班4:4PM～午夜排班5:10PM～6M时段排班1排班2排班3排班4排班5最少需要人数6AM～8AM√488AM～10AM√√7910AM～中午√√65中午～2PM√√√872PM～4PM√√644PM～6PM√√736PM～8PM√√828PM～10PM√4310PM～午夜√√52午夜～6PM√15每人每天工资(元)170160175180195解:这是一个纯成本收益平衡问题（1）决策变量本问题的决策是不同排班的人数。设：xi为排班i的人数(i＝1,2,,5)（2）目标函数本问题的目标是人员总费用(工资)最少（3）约束条件每个时段的在岗人数必须不少于最低可接受水平（最少需要人数）非负数学模型（线性规划模型）电子表格模型本问题的目标是人员总费用(工资)最少据测定每万元每次投资的风险指数如右表：应用线性规划问题解决实际问题，最重要的一个步骤就是首先要建立实际问题的线性规划问题的数学模型。(3)约束条件：

公司在各期可获得的资金限制（资源约束）本问题的目标是人员总费用(工资)最少表3－1显示了四个时期每个项目所需资金（百万元）。晚上10点班需要15人项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。设司机和乘务人员分别在各时间段一开始时上班，并某昼夜服务的公交线路每天各时间段内所需司机管理的目标：通过配送网络能以最小的成本完成货物的配送设：xi-j为从工厂i运输到顾客j的产品数量(2)每一种活动对每一种收益的贡献(单位活动的贡献)项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。投资者可以按一定的比例进行投资和获得相应比例的收益。此时获得的总利润最大，为1811万元。求解结果为：早6点班需要48人早8点班需要31人中午班需要39人下午4点班需要43人晚上10点班需要15人总费用（工资）最低，为每天30610元。3.3网络配送问题管理的目标：通过配送网络能以最小的成本完成货物的配送确定需求约束的形式如下：提供的数量＝需求的数量

某公司网络配送问题某公司在两个工厂生产某种产品。现在收到三个顾客的下个月定单要购买这种产品，这些产品会被单独运送。表3—4显示了运送成本、顾客的订货量、工厂的生产量现在公司的物流经理要决定从每个工厂运送多少个产品到每个顾客那里才能使总成本最小？

单位运输成本（元/个）产量（个）顾客1顾客2顾客3工厂170090080012工厂280090070015订货量(个)108927(产销平衡)解:本问题是一个平衡运输问题总产量=总订货量=27（1）决策变量设：xi-j为从工厂i运输到顾客j的产品数量（i＝F1,F2;j=C1,C2,C3)（2）目标函数本问题的目标是使得公司总运输成本最低（3）约束条件

①从工厂运送出去的产品数量等于其产量②顾客收到的产品数量等于其订货量③非负数学模型（线性规划模型电子表格模型求解结果为：工厂1运送到顾客1的产品为10个工厂1运送到顾客2的产品为2个工厂2运送到顾客2的产品为6个工厂2运送到顾客3的产品为9个工厂所花费的总运输成本最低,为20500元作业1：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?作业2：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年