Chapter 4. Linear Programming: Formulation and Applications

Presentation on theme: "Chapter 4. Linear Programming: Formulation and Applications"— Presentation transcript:

1 Chapter 4. Linear Programming: Formulation and Applications
第四章. 线性规划：建模与应用 运筹学

2 满足以下三个条件的模型称为线性规划模型 线性规划模型 每一个问题都用一组决策变量(通常非负)表示某一方案，这组决策变量的值就代表一个具体方案
存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示 都有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示，按照问题的不同，要求目标函数实现最大化或最小化

3 线性规划模型的一般形式

4 线性规划问题的分类 资源分配问题(resource-allocation)：资源约束。伟恩德玻璃制品公司产品组合问题
成本收益平衡问题(cost-benefit-trade-off)：收益约束。利博公司广告组合问题，大沼泽地金色年代公司的现金流问题 网络配送问题(distribution-network)：确定需求约束。 混合问题(mix)：多种约束。 线性规划 建模与应用

5 Table of Contents (主要内容)
Super Grain Corp. Advertising-Mix Problem (Section 4.1)(超级食品公司的广告组合问题) Resource Allocation Problems & Think-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公司)

6 Table of Contents (主要内容)
Continuing the Super Grain Corp. Case Study (Section 4.5) (超级食品公司案例的再研究) Mixed Formulations & Save-It Solid Waste Reclamation (Section 4.6) (混合问题和赛维特公司固体废弃物回收问题)

7 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 Saturday morning programs for children. (星期六上午儿童节目的电视广告) Advertisements in food and family-oriented magazines. (食品与家庭导向的杂志上的广告)

8 Super Grain Corp. Advertising-Mix Problem
Advertisements in Sunday supplements of major newspapers. (主要报纸星期天增刊上的广告) The limited resources in the problem are (该问题的有限资源如下) Advertising budget ($4 million). (广告预算400万美元) Planning budget ($1 million). (计划预算100万美元) TV commercial spots available (5). (可获得的电视广告时段有5个单位)

9 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 advertise Crunchy Start in each of the three media? 确定各种媒介的广告力度以获得最有效的广告组合？

10 Cost and Exposure Data (成本和广告受众数据)
Costs Cost Category Each TV Commercial Each Magazine Ad Each Sunday Ad Ad Budget $300,000 $150,000 $100,000 Planning budget 90,000 30,000 40,000 Expected number of exposures 1,300,000 600,000 500,000

11 Spreadsheet Formulation (电子表格模型)

12 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 + 500SS

13 Algebraic Formulation (数学模型)
Subject to (约束) (广告总费用) Ad Spending: 300TV + 150M + 100SS ≤ 4,000 ($thousand) (计划总成本) Planning Cost: 90TV + 30M + 30SS ≤ 1,000 ($thousand) (电视广告的时段数目) Number of TV Spots: TV ≤ 5 and TV ≥ 0, M ≥ 0, SS ≥ 0. 线性规划 建模与应用

14 超级食品公司问题探讨 假设是否合理？ 数学模型是否和实际问题相吻合？ 可行域的小数问题 正比的线性关系是否成立？ 不同媒介之间是否相关？
目标函数的选取是否可行？ 市场细分的问题 促销优惠券的问题 模型需要不断完善！！ 线性规划 建模与应用

15 资源分配问题 资源分配问题是将有限的资源分配到各种活动中去的线性规划问题。共性在于函数约束均可表现为： 使用的资源数量≤可用的资源数量
确定资源、资源可用量、活动、活动水平、活动消耗的资源数量以及活动对绩效测度的贡献等 目标就是在满足资源限制的条件下使活动水平能够最大化所选择的绩效测度

16 资源分配问题 决策变量是活动水平 活动水平与绩效测度的贡献成正比 活动水平与资源使用量成正比
需要确定三类数据：资源可用量、单位活动消耗的资源量和单位活动对绩效测度的贡献量 线性规划 建模与应用

17 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. (建造高层办公楼) Construct a hotel. (建造宾馆) Construct a shopping center. (建造购物中心)

18 Think-Big Capital Budgeting Problem
Each project requires each partner to make four investments: a down payment now, and additional capital after one, two, and three years. (每个项目都要求投资者在四个不同时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资) 线性规划 建模与应用

19 Think-Big Capital Budgeting Problem
梦大公司要在每个项目中投资多少百分比，才能获得最大收益？ Question: At what fraction should Think-Big invest in each of the three projects?

20 Financial Data for the Projects
Investment Capital Requirements Year Office Building Hotel Shopping Center $40 million $80 million $90 million 1 60 million 80 million 50 million 2 90 million 20 million 3 10 million 70 million Net present value $45 million $70 million $50 million

21 Spreadsheet Formulation

22 Algebraic Formulation
Let (假定) OB = Participation share in the office building (办公楼项目中的投资比例), H = Participation share in the hotel (宾馆项目中的投资比例), SC = Participation share in the shopping center (购物中心项目中的投资比例). (最大化总投资净现值) Maximize NPV = 45OB + 70H + 50SC

23 Algebraic Formulation
Subject to (约束) Total invested now (现期总投资): 40OB + 80H + 90SC ≤ 25 ($million) Total invested within 1 year (一年后的总投资): 100OB + 160H + 140SC ≤ 45 ($million) Total invested within 2 years (一年后的总投资) : 190OB + 240H + 160SC ≤ 65 ($million) Total invested within 3 years (一年后的总投资) : 200OB + 310H + 220SC ≤ 80 ($million) and OB ≥ 0, H ≥ 0, SC ≥ 0.

24 Summary Summary of Formulation Procedure for Resource-Allocation Problems (资源分配问题的建模步骤总结)： Identify the activities for the problem 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. (估计每一种活动对于总绩效测度的单位贡献)

25 Identify the resources that must be allocated. (明确分配给各种活动的有限资源)
Summary Identify the resources that must be allocated. (明确分配给各种活动的有限资源) 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步中的数据录入数据单元格)

26 Summary Designate changing cells for displaying the decisions. (指定可变单元格来显示活动水平的决策变量) In the row 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函数计算绩效测度)

27 Union 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 PM Shift 3: Noon to 8:00 PM Shift 4: 4:00 PM to midnight Shift 5: 10:00 PM to 6:00 AM

28 Union Airways Personnel Scheduling
每个轮班需要安排多少人？ Question: How many agents should be assigned to each shift?

29 Time Periods Covered by Shift Minimum Number of Agents Needed
Schedule Data (排程数据) Time Periods Covered by Shift Time Period 1 2 3 4 5 Minimum Number of Agents Needed 6 AM to 8 AM √ 48 8 AM to 10 AM 79 10 AM to noon 65 Noon to 2 PM 87 2 PM to 4 PM 64 4 PM to 6 PM 73 6 PM to 8 PM 82 8 PM to 10 PM 43 10 PM to midnight 52 Midnight to 6 AM 15 Daily cost per agent $170 $160 $175 $180 $195

30 Spreadsheet Formulation

31 Algebraic Formulation
Let (假定) Si = Number working shift i (for i = 1 to 5), Minimize (最小化) Cost = $170S1 + $160S2 + $175S3 + $180S4 + $195S5 Subject to (约束) Total agents 6AM–8AM: S1 ≥ 48 Total agents 8AM–10AM: S1 + S2 ≥ 79 Total agents 10AM–12PM: S1 + S2 ≥ 65 Total agents 12PM–2PM: S1 + S2 + S3 ≥ 87 Total agents 2PM–4PM: S2 + S3 ≥ 64 Total agents 4PM–6PM: S3 + S4 ≥ 73

32 Algebraic Formulation
Subject to (约束) Total agents 4PM–6PM: S3 + S4 ≥ 73 Total agents 6PM–8PM: S3 + S4 ≥ 82 Total agents 8PM–10PM: S4 ≥ 43 Total agents 10PM–12AM: S4 + S5 ≥ 52 Total agents 12AM–6AM: S5 ≥ 15 and Si ≥ 0 (for i = 1 to 5)

33 成本收益平衡问题 成本收益问题是通过选择各种活动水平的组合，以最小的成本来实现最低可接受的各种收益的一类线性规划问题。共性在于函数约束均可表现为 完成的水平≥最低可接受水平 指明每种收益的最低可接受水平，以及实现收益的最小成本，获得成本与收益之间的适度平衡 成本收益平衡问题需要的三类数据：每种收益的最低可接受水平、每种活动对每一收益的贡献、每种活动的单位成本

34 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, estimate the contribution per unit of the activity to the overall measure of performance. (估计每一种活动对于总绩效测度的单位贡献)

35 Summary 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. (对于每一项收益，确定其最小可接受水平和每项活动对该收益的贡献大小) Enter the data in steps 3 and 5 into data cells. (将第3步和第5步的数据输入数据单元格) Designate changing cells for displaying the decisions. (指定可变单元格用于显示决策变量)

36 Summary In the row for each benefit, use SUMPRODUCT to calculate the level achieved. Enter ≥ and the minimum acceptable level in two adjacent cells. (在表示收益的每一行中，用SUMPRODUCT函数计算获得的收益水平，在两个连续的单元格中输入≥号和最小可接受水平) Designate a target cell. Use SUMPRODUCT to calculate this measure of performance. (指定一个目标单元格，用SUMPRODUCT函数计算其绩效测度)

37 成本收益平衡问题 思考教材案例“控制空气污染问题”(P112) 线性规划 建模与应用

38 The Big M Distribution-Network Problem
The Big M Company produces a variety of heavy duty machinery 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个客户)

39 The Big M Distribution-Network Problem
How many lathes should be shipped from each factory to each customer? (应该从每一个工厂运载多少车床到每一个客户？)

40 Shipping Cost for Each Lathe
Some Data (有关数据) Shipping Cost for Each Lathe To Customer 1 Customer 2 Customer 3 From Output Factory 1 $700 $900 $800 12 lathes Factory 2 800 900 700 15 lathes Order Size 10 lathes 8 lathes 9 lathes

41 The Distribution Network (配送网络)

42 Spreadsheet Formulation (电子表格模型)

43 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

44 Algebraic Formulation (数学模型)
subject to (约束) Factory 1: SF1-C1 + SF1-C2 + SF1-C3 = 12 Factory 2: SF2-C1 + SF2-C2 + SF2-C3 = 15 Customer 1: SF1-C1 + SF2-C1 = 10 Customer 2: SF1-C2 + SF2-C2 = 8 Customer 3: SF1-C3 + SF2-C3 = 9 and Sij ≥ 0 (i = F1, F2; j = C1, C2, C3).

45 配送网络问题 配送网络问题的函数约束是确定的需求约束，可表示为： 提供的数量=需要的数量 线性规划 建模与应用

46 Continuing the Super Grain Case Study
David and Claire conclude that 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. (他们尤其觉得必须将目标观众定位为儿童及他们的家长)

47 Continuing the Super Grain Case Study
Two new goals (两个新的目标) The advertising 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万美元的预算可以分配到商家优惠卷)

48 Benefit and Fixed-Requirement Data

49 Spreadsheet Formulation

50 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 + 500SS

51 Algebraic Formulation
subject to (约束) Ad Spending (广告花费): 300TV + 150M + 100SS ≤ 4,000 ($thousand) Planning Cost (计划成本): 90TV + 30M + 30SS ≤ 1,000 ($thousand) Number of TV Spots (TV广告时段数): TV ≤ 5 Young children: 1.2TV + 0.1M ≥ 5 (millions) Parents: 0.5TV + 0.2M + 0.2SS ≥ 5 (millions) Coupons (优惠卷): 40M + 120SS = 1,490 ($thousand) and TV ≥ 0, M ≥ 0, SS ≥ 0.

52 Types of Functional Constraints
Form* Typical Interpretation Main Usage Resource constraint LHS ≤ RHS For some resource, Amount used ≤ Amount available Resource-allocation problems and mixed problems Benefit constraint LHS ≥ RHS For some benefit, Level achieved ≥ Minimum Acceptable Cost-benefit-trade-off problems and mixed problems Fixed-requirement constraint LHS = RHS For some quantity, Amount provided = Required amount Distribution-network problems and mixed problems * LHS = Left-hand side (a SUMPRODUCT function). RHS = Right-hand side (a constant).

53 混合问题 混合问题也是一类典型的线性规划问题，它包含的约束是多种多样的，即可能有资源约束，也可能有收益约束，还可能有确定需求的约束 线性规划
建模与应用

54 Save-It Company Waste Reclamation
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. (赛维特公司经营一个回收中心，专门从事四种固体废弃物的回收，并将回收物处理、混合成为可销售的产品) Three different grades of product can be made: A, B, and C (depending on the mix of materials used) (不同的原料混合，一共可以生成3种不同等级的产品：A、B和C)

55 Save-It Company Waste Reclamation
What quantity of each of the three grades of product should be produced from what quantity of each of the four materials? (四种原料各应使用多少？ 三种不同等级的产品各应生产多少？)

56 Product Data for the Save-It Company
Grade Specification Amalgamation Cost per Pound Selling Price per Pound A Material 1: Not more than 30% of total Material 2: Not less than 40% of total Material 3: Not more than 50% of total Material 4: Exactly 20% of total $3.00 $8.50 B Material 1: Not more than 50% of total Material 2: Not less than 10% of the total Material 4: Exactly 10% of the total 2.50 7.00 C Material 1: Not more than 70% of the total 2.00 5.50

57 Material Data for the Save-It Company
Pounds/Week Available Treatment Cost per Pound Additional Restrictions 1 3,000 $3.00 1. For each material, at least half of the pounds/week available should be collected and treated. 2. $30,000 per week should be used to treat these materials. 2 2,000 6.00 3 4,000 4.00 4 1,000 5.00

58 Spreadsheet Formulation

59 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 (最大化收益) Profit = 5.5(xA1 + xA2 + xA3 + xA4) + 4.5(xB1 + xB2 + xB3 + xB4) + 3.5(xC1 + xC2 + xC3 + xC4)

60 Algebraic Formulation
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 + xC2 + xC3 + xC4)

61 Algebraic Formulation
Availability of Materials (可获得的材料): xA1 + xB1 + xC1 ≤ 3,000 xA2 + xB2 + xC2 ≤ 2,000 xA3 + xB3 + xC3 ≤ 4,000 xA4 + xB4 + xC4 ≤ 1,000 Restrictions on amount treated (处理的材料数量约束): xA1 + xB1 + xC1 ≥ 1,500 xA2 + xB2 + xC2 ≥ 1,000 xA3 + xB3 + xC3 ≥ 2,000 xA4 + xB4 + xC4 ≥ 500

62 Algebraic Formulation
Restriction on treatment cost (处理成本约束): 3(xA1 + xB1 + xC1) + 6(xA2 + xB2 + xC2) + 4(xA3 + xB3 + xC3) + 5(xA4 + xB4 + xC4) = 30,000 and xij ≥ 0 (i = A, B, C; j = 1, 2, 3, 4) 线性规划 建模与应用

63 确定分配给各种活动的有限资源，明确每一种资源的可用量和活动的单位使用量
混合问题建模过程 明确问题的各种活动 确定总绩效测度 确定活动对绩效测度的单位贡献 确定分配给各种活动的有限资源，明确每一种资源的可用量和活动的单位使用量 确定各种活动可获得的收益，明确收益的最低可接受水平以及每种活动的单位收益贡献

64 判别确定的需求，明确每一种活动对需求的单位贡献 输入数据单元格内容 确定可变单元格(活动水平) 使用输出单元格指明各种约束关系
混合问题建模过程 判别确定的需求，明确每一种活动对需求的单位贡献 输入数据单元格内容 确定可变单元格(活动水平) 使用输出单元格指明各种约束关系 指定目标单元格显示总绩效测度 优化求解 线性规划 建模与应用

65 管理层和业务层长期、连续的参与、沟通和支持 模型的不断扩展、完善和确认 结果的客户化定制 系统的互动性和what-if分析
管理视角的建模 管理层和业务层长期、连续的参与、沟通和支持 模型的不断扩展、完善和确认 结果的客户化定制 系统的互动性和what-if分析 线性规划 建模与应用

66 The end of chapter 4