《线性规划：建模与应用.ppt》由会员分享，可在线阅读，更多相关《线性规划：建模与应用.ppt（67页珍藏版）》请在三一办公上搜索。
1、运筹学Operations Research,Operations Research,Chapter 4.Linear Programming:Formulation and Applications,第四章.线性规划：建模与应用,Operations Research,满足以下三个条件的模型称为线性规划模型每一个问题都用一组决策变量(通常非负)表示某一方案，这组决策变量的值就代表一个具体方案存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示都有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示，按照问题的不同，要求目标函数实现最大化或最小化,什么是线性规划模
2、型,线性规划模型的一般形式,什么是线性规划模型,资源分配问题(resource-allocation)：资源约束。伟恩德玻璃制品公司产品组合问题成本收益平衡问题(cost-benefit-trade-off)：收益约束。利博公司广告组合问题，大沼泽地金色年代公司的现金流问题网络配送问题(distribution-network)：确定需求约束。混合问题(mix)：多种约束。,线性规划问题的分类,Super Grain Corp.Advertising-Mix Problem(Section 4.1)(超级食品公司的广告组合问题)Resource Allocation Problems&Thin
3、k-Big Capital Budgeting(Section 4.2)(资源分配问题和梦大发展公司的资金预算问题)Cost-Benefit-Trade-Off Problems&Union Airways(Section 4.3)(成本收益平衡问题和联合航空公司问题)Distribution-Network Problems&Big M Co.(Section 4.4)(网络配送问题和大M公司),主要内容,Continuing the Super Grain Corp.Case Study(Section 4.5)(超级食品公司案例的再研究)Mixed Formulations&Save-I
4、t Solid Waste Reclamation(Section 4.6)(混合问题和赛维特公司固体废弃物回收问题),主要内容,Super Grain Corp.Advertising-Mix Problem,Goal:Design the promotional campaign for Crunchy Start.(目标：为早点谷类食品“脆始”设计出具有奖励性的商业计划)The three most effective advertising media for this product are(该产品三种最有效的广告媒介是)Television commercials on Satur
5、day morning programs for children.(星期六上午儿童节目的电视广告)Advertisements in food and family-oriented magazines.(食品与家庭导向的杂志上的广告),Advertisements in Sunday supplements of major newspapers.(主要报纸星期天增刊上的广告)The limited resources in the problem are(该问题的有限资源如下)Advertising budget($4 million).(广告预算400万美元做广告)Planning b
6、udget($1 million).(计划预算100万美元做广告设计)TV commercial spots available(5).(可获得的电视广告时段有5个单位),Super Grain Corp.Advertising-Mix Problem,Super Grain Corp.Advertising-Mix Problem,The objective will be measured in terms of the expected number of exposures.(广告受众的期望数量作为问题的总绩效测度),Question:At what level should they
7、 advertise Crunchy Start in each of the three media?,确定各种媒介的广告力度以获得最有效的广告组合？,Super Grain Corp.Advertising-Mix Problem,Algebraic Formulation(数学模型),Let(设定)TV=Number of commercials for separate spots on television(电视上的广告时段数目)M=Number of advertisements in magazines.(杂志上的广告数目)SS=Number of advertisements
8、in Sunday supplements.(星期天增刊上的广告数目)(最大化广告受众量)Maximize Exposure=1,300TV+600M+500SS,Subject to(约束)(广告总费用)Ad Spending:300TV+150M+100SS 4,000($thousand)(计划总成本)Planning Cost:90TV+30M+30SS 1,000($thousand)(电视广告的时段数目)Number of TV Spots:TV 5andTV 0,M 0,SS 0.,Algebraic Formulation(数学模型),Spreadsheet Formulati
9、on(电子表格模型),超级食品公司问题探讨,假设是否合理？数学模型是否和实际问题相吻合？可行域的小数问题正比的线性关系是否成立？不同媒介之间是否相关？目标函数的选取是否可行？市场细分的问题促销优惠券的问题模型需要不断完善！,资源分配问题,资源分配问题是将有限的资源分配到各种活动中去的线性规划问题。共性在于函数约束均可表现为：使用的资源数量可用的资源数量确定资源、资源可用量、活动、活动水平、活动消耗的资源数量以及活动对绩效测度的贡献等目标就是在满足资源限制的条件下使活动水平能够最大化所选择的绩效测度,决策变量是活动水平活动水平与绩效测度的贡献成正比活动水平与资源使用量成正比需要确定三类数据：资源
10、可用量、单位活动消耗的资源量和单位活动对绩效测度的贡献量,资源分配问题,Think-Big Capital Budgeting Problem,Think-Big Development Co.is a major investor in commercial real-estate development projects.(梦大发展公司是商务房地产开发项目的主要投资商)They are considering three large construction projects(他们正在考虑三个大型的建筑项目)Construct a high-rise office building.(建造
11、高层办公楼)Construct a hotel.(建造宾馆)Construct a shopping center.(建造购物中心),Each project requires each partner to make four investments:a down payment now,and additional capital after one,two,and three years.(每个项目都要求投资者在四个不同时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资)公司现有资金2500万美元，预计一年后可获得2000万美元，两年后可获得另外2000万美元，三年后可获得另外
12、1500万美元，这些新获得的资金可用于后续投资,Think-Big Capital Budgeting Problem,Financial Data for the Projects,Question:At what fraction should Think-Big invest in each of the three projects?,Think-Big Capital Budgeting Problem,Algebraic Formulation,Let(假定)OB=Participation share in the office building(办公楼项目中的投资比例),H=P
13、articipation share in the hotel(宾馆项目中的投资比例),SC=Participation share in the shopping center(购物中心项目中的投资比例).(最大化总投资净现值)Maximize NPV=45OB+70H+50SC,Subject to(约束)Total invested now(现期总投资):40OB+80H+90SC 25($million)Total invested within 1 year(一年后的总投资):100OB+160H+140SC 45($million)Total invested within 2 y
14、ears(一年后的总投资):190OB+240H+160SC 65($million)Total invested within 3 years(一年后的总投资):200OB+310H+220SC 80($million)andOB 0,H 0,SC 0.,Algebraic Formulation,Spreadsheet Formulation,Summary,Summary of Formulation Procedure for Resource-Allocation Problems(资源分配问题的建模步骤总结)：,Identify the activities for the pro
15、blem at hand.(确定当前问题的活动类型)Identify an appropriate overall measure of performance(commonly profit).(确定一个合适的总体绩效测度，通常为利润)For each activity,estimate the contribution per unit of the activity to the overall measure of performance.(估计每一种活动对于总绩效测度的单位贡献),Identify the resources that must be allocated.(明确分配给
16、各种活动的有限资源)For each resource,identify the amount available and then the amount used per unit of each activity.(对于每一种资源，确定可获得的数量以及各种活动的单位使用量)Enter the data in steps 3 and 5 into data cells.(把第3步和第5步中的数据录入数据单元格),Summary,Designate changing cells for displaying the decisions.(指定可变单元格来显示活动水平的决策变量)In the r
17、ow for each resource,use SUMPRODUCT to calculate the total amount used.Enter and the amount available in two adjacent cells.(在表示资源的每一行中，使用SUMPRODUCT函数计算总的资源使用量，在两个连续单元格中输入符号和可用资源量)Designate a target cell.Use SUMPRODUCT to calculate this measure of performance.(指定目标单元格，使用SUMPRODUCT函数计算绩效测度),Summary,U
18、nion Airways Personnel Scheduling,Union Airways is adding more flights to and from its hub airport and so needs to hire additional customer service agents.(联合航空公司正准备增加其中心机场的往来航班，因此需要雇用更多的客户服务代理商)The five authorized eight-hour shifts are(五个审定的8小时轮班如下)Shift 1:6:00 AM to 2:00 PM Shift 2:8:00 AM to 4:00
19、 PMShift 3:Noon to 8:00 PMShift 4:4:00 PM to midnightShift 5:10:00 PM to 6:00 AM,Schedule Data(排程数据),Union Airways Personnel Scheduling,Question:How many agents should be assigned to each shift?,每个轮班需要安排多少人才能在满足顾客需求的前提下降低成本？,Algebraic Formulation,Let(假定)Si=Number working shift i(for i=1 to 5),Minimi
20、ze(最小化)Cost=$170S1+$160S2+$175S3+$180S4+$195S5Subject to(约束)Total agents 6AM8AM:S1 48Total agents 8AM10AM:S1+S2 79Total agents 10AM12PM:S1+S2 65Total agents 12PM2PM:S1+S2+S3 87Total agents 2PM4PM:S2+S3 64Total agents 4PM6PM:S3+S4 73,Subject to(约束)Total agents 4PM6PM:S3+S4 73Total agents 6PM8PM:S3+S4
21、 82Total agents 8PM10PM:S4 43Total agents 10PM12AM:S4+S5 52Total agents 12AM6AM:S5 15and Si 0(for i=1 to 5),Algebraic Formulation,Spreadsheet Formulation,成本收益平衡问题,成本收益问题是通过选择各种活动水平的组合，以最小的成本来实现最低可接受的各种收益的一类线性规划问题。共性在于函数约束均可表现为完成的水平最低可接受水平指明每种收益的最低可接受水平，以及实现收益的最小成本，获得成本与收益之间的适度平衡成本收益平衡问题需要的三类数据：每种收益的
22、最低可接受水平、每种活动对每一收益的贡献、每种活动的单位成本,Summary,Summary of Formulation Procedure for Cost-Benefit-Tradeoff Problems(成本收益平衡问题建模步骤的总结),Identify the activities for the problem at hand.(确定当前问题的活动类型)Identify an appropriate overall measure of performance(commonly cost).(确定一个合适的总体绩效测度，通常为成本)For each activity,estima
23、te the contribution per unit of the activity to the overall measure of performance.(估计每一种活动对于总绩效测度的单位贡献),Identify the benefits that must be achieved.(确定必须取得的收益)For each benefit,identify the minimum acceptable level and then the contribution of each activity to that benefit.(对于每一项收益，确定其最小可接受水平和每项活动对该
24、收益的贡献大小)Enter the data in steps 3 and 5 into data cells.(将第3步和第5步的数据输入数据单元格)Designate changing cells for displaying the decisions.(指定可变单元格用于显示决策变量),Summary,In the row for each benefit,use SUMPRODUCT to calculate the level achieved.Enter and the minimum acceptable level in two adjacent cells.(在表示收益的每
25、一行中，用SUMPRODUCT函数计算获得的收益水平，在两个连续的单元格中输入号和最小可接受水平)Designate a target cell.Use SUMPRODUCT to calculate this measure of performance.(指定一个目标单元格，用SUMPRODUCT函数计算其绩效测度),Summary,思考教材案例“控制空气污染问题”(P112),成本收益平衡问题,The Big M Distribution-Network Problem,The Big M Company produces a variety of heavy duty machiner
26、y at two factories.One of its products is a large turret lathe.(大M公司在两个工厂生产一系列中型机器，产品之一是一种大型的六角车床)Orders have been received from three customers for the turret lathe.(该六角车床的订单来自于3个客户),Some Data(有关数据),How many lathes should be shipped from each factory to each customer?(应该从每一个工厂运载多少车床到每一个客户？),The Big
27、 M Distribution-Network Problem,The Distribution Network(配送网络),Algebraic Formulation(数学模型),Let(假定)Sij=Number of lathes to ship from i to j(i=F1,F2;j=C1,C2,C3)Minimize(最小化)Cost=$700SF1-C1+$900SF1-C2+$800SF1-C3+$800SF2-C1+$900SF2-C2+$700SF2-C3,subject to(约束)Factory 1:SF1-C1+SF1-C2+SF1-C3=12Factory 2:S
28、F2-C1+SF2-C2+SF2-C3=15Customer 1:SF1-C1+SF2-C1=10Customer 2:SF1-C2+SF2-C2=8Customer 3:SF1-C3+SF2-C3=9andSij 0(i=F1,F2;j=C1,C2,C3).,Algebraic Formulation(数学模型),Spreadsheet Formulation(电子表格模型),配送网络问题,配送网络问题的函数约束是确定的需求约束，可表示为：提供的数量=需要的数量,Continuing the Super Grain Case Study,David and Claire conclude t
29、hat the spreadsheet model needs to be expanded to incorporate some additional considerations.(大卫和克莱略认为公司的电子表格模型还需要进一步扩展以增加一些考虑事项)In particular,they feel that two audiences should be targeted young children and parents of young children.(他们尤其觉得必须将目标观众定位为儿童及他们的家长),Two new goals(两个新的目标)The advertising
30、should be seen by at least five million young children.(必须至少有500百万儿童看到该广告)The advertising should be seen by at least five million parents of young children.(必须至少有500万儿童家长看到该广告)Furthermore,exactly$1,490,000 should be allocated for cents-off coupons.(而且正好还有149万美元的预算可以分配到商家优惠卷),Continuing the Super Gra
31、in Case Study,Benefit and Fixed-Requirement Data,Algebraic Formulation,Let(假定)TV=Number of commercials for separate spots on television(电视上的广告时段数目)M=Number of advertisements in magazines(杂志上的广告数目)SS=Number of advertisements in Sunday supplements(星期天增刊上的广告数目)Maximize(最大化广告受众量)Exposure=1,300TV+600M+50
32、0SS,subject to(约束)Ad Spending(广告花费):300TV+150M+100SS 4,000($thousand)Planning Cost(计划成本):90TV+30M+30SS 1,000($thousand)Number of TV Spots(TV广告时段数):TV 5Young children:1.2TV+0.1M 5(millions)Parents:0.5TV+0.2M+0.2SS 5(millions)Coupons(优惠卷):40M+120SS=1,490($thousand)andTV 0,M 0,SS 0.,Algebraic Formulati
33、on,Spreadsheet Formulation,Types of Functional Constraints,混合问题,混合问题也是一类典型的线性规划问题，它包含的约束是多种多样的，即可能有资源约束，也可能有收益约束，还可能有确定需求的约束,The Save-It Company operates a reclamation center that collects four types of solid waste materials and then treats them so that they can be amalgamated into a salable product
34、.(赛维特公司经营一个回收中心，专门从事四种固体废弃物的回收，并将回收物处理、混合成为可销售的产品)Three different grades of product can be made:A,B,and C(depending on the mix of materials used)(不同的原料混合，一共可以生成3种不同等级的产品：A、B和C),Save-It Company Waste Reclamation,Product Data for the Save-It Company,Material Data for the Save-It Company,Save-It Compan
35、y Waste Reclamation,What quantity of each of the three grades of product should be produced from what quantity of each of the four materials?(四种原料各应使用多少？三种不同等级的产品各应生产多少？),Algebraic Formulation,Let(假定)xij=Pounds of material j allocated to product i per week(i=A,B,C;j=1,2,3,4)(每周原料j分配给产品i的数量)Maximize(
36、最大化收益)Profit=5.5(xA1+xA2+xA3+xA4)+4.5(xB1+xB2+xB3+xB4)+3.5(xC1+xC2+xC3+xC4),subject to(约束)Mixture Specifications(混合比例规定):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
37、+xC2+xC3+xC4),Algebraic Formulation,Availability of Materials(可获得的材料):xA1+xB1+xC1 3,000 xA2+xB2+xC2 2,000 xA3+xB3+xC3 4,000 xA4+xB4+xC4 1,000Restrictions on amount treated(处理的材料数量约束):xA1+xB1+xC1 1,500 xA2+xB2+xC2 1,000 xA3+xB3+xC3 2,000 xA4+xB4+xC4 500,Algebraic Formulation,Restriction on treatment
38、cost(处理成本约束):3(xA1+xB1+xC1)+6(xA2+xB2+xC2)+4(xA3+xB3+xC3)+5(xA4+xB4+xC4)=30,000andxij 0(i=A,B,C;j=1,2,3,4),Algebraic Formulation,Spreadsheet Formulation,混合问题建模过程,明确问题的各种活动确定总绩效测度确定活动对绩效测度的单位贡献确定分配给各种活动的有限资源，明确每一种资源的可用量和活动的单位使用量确定各种活动可获得的收益，明确收益的最低可接受水平以及每种活动的单位收益贡献,判别确定的需求，明确每一种活动对需求的单位贡献输入数据单元格内容确定可变单元格(活动水平)使用输出单元格指明各种约束关系指定目标单元格显示总绩效测度优化求解,混合问题建模过程,管理视角的建模,管理层和业务层长期、连续的参与、沟通和支持模型的不断扩展、完善和确认结果的客户化定制系统的互动性和what-if分析,The End of Chapter 4,Operations Research,
