线性规划：建模与应用

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 Pr

3、oblems 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:SF2-C1 + SF2-C2 + SF2-C3 = 15Customer 1: SF1-C1 + SF2-C1 = 10Customer 2: SF1-C2 + SF2-C2 = 8Customer 3: SF1-C3 + SF

4、2-C3 = 9andSij 0 (i = F1, F2; j = C1, C2, C3,Algebraic Formulation (数学模型,Spreadsheet Formulation (电子表格模型,配送网络问题,配送网络问题的函数约束是确定的需求约束，可表示为： 提供的数量=需要的数量,Continuing the Super Grain Case Study,David and Claire conclude that the spreadsheet model needs to be expanded to incorporate some additional conside

5、rations. (大卫和克莱略认为公司的电子表格模型还需要进一步扩展以增加一些考虑事项) In particular, they feel that two audiences should be targeted young children and parents of young children. (他们尤其觉得必须将目标观众定位为儿童及他们的家长,Two new goals (两个新的目标) The advertising should be seen by at least five million young children. (必须至少有500百万儿童看到该广告) The

6、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 Grain Case Study,Benefit and Fixed-Requirement Data,Algebraic Formulation,Let

7、 (假定) 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,subject to (约束)Ad Spending (广告花费): 300TV + 150M +

8、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 Formulation,Spreadsheet For

9、mulation,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. (赛维特公司经营一个回收中心，专

10、门从事四种固体废弃物的回收，并将回收物处理、混合成为可销售的产品) 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 Company Waste Recl

11、amation,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的数量) Maxim

12、ize (最大化收益) 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 + x

13、B2 + xB3 + xB4) xB2 0.1 (xB1 + xB2 + xB3 + xB4) xB4 = 0.1 (xB1 + xB2 + xB3 + xB4) xC1 0.7 (xC1 + 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,000 Restrictions on amount treated (处理的材料数量约束

14、): xA1 + xB1 + xC1 1,500 xA2 + xB2 + xC2 1,000 xA3 + xB3 + xC3 2,000 xA4 + xB4 + xC4 500,Algebraic Formulation,Restriction on treatment cost (处理成本约束): 3(xA1 + xB1 + xC1) + 6(xA2 + xB2 + xC2) + 4(xA3 + xB3 + xC3) + 5(xA4 + xB4 + xC4) = 30,000and xij 0 (i = A, B, C; j = 1, 2, 3, 4,Algebraic Formulation,Spreadsheet Formulation,混合问题建模过程,明确问题的各种活动 确定总绩效测度 确定活动对绩效测度的单位贡献 确定分配给各种活动的有限资源，明确每一种资源的可用量和活动的单位使用量 确定各种活动可获得的收益，明确