1技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案运筹学 Operations ResearchOperations Research2技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Chapter 4. Linear Programming: Formulation and Applications第四章. 线性规划：建模与应用Operations Research3技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案n满足以下三个条件的模型称为线性规划模型 u 每一个问题都用一组决策变量(通常非负)表示 某一方案，这组决策变量的值就代表一个具体 方案 u 存在一定的约束条件，这些约束条件可以用一 组线性等式或线性不等式来表示 u 都有一个要求达到的目标，它可用决策变量的 线性函数(称为目标函数)来表示，按照问题的 不同，要求目标函数实现最大化或最小化什么是线性规划模型4技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案线性规划模型的一般形式什么是线性规划模型5技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案n资源分配问题(resource-allocation)：资源 约束。伟恩德玻璃制品公司产品组合问题 n成本收益平衡问题(cost-benefit-trade-off) ：收益约束。利博公司广告组合问题，大 沼泽地金色年代公司的现金流问题 n网络配送问题(distribution-network)：确 定需求约束。 n混合问题(mix)：多种约束。线性规划问题的分类6技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案nSuper Grain Corp. Advertising-Mix Problem (Section 4.1)(超级食品公司的广告 组合问题) nResource Allocation Problems j = C1, C2, C3)Minimize (最小化)Cost = $700SF1-C1 + $900SF1-C2 + $800SF1-C3 + $800SF2-C1 + $900SF2-C2 + $700SF2-C344技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案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).Algebraic Formulation (数学模型)45技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Spreadsheet Formulation (电子表格模型)46技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案配送网络问题n配送网络问题的函数约束是确定的需求 约束，可表示为： 提供的数量=需要的数量线性规划 建模与应用47技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Continuing the Super Grain Case StudyDavid 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. (他们尤其觉得必须 将目标观众定位为儿童及他们的家长)48技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案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万美元的预算可以分配到商家优惠卷)Continuing the Super Grain Case Study49技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Benefit and Fixed-Requirement Data50技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Algebraic FormulationLet (假定)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 + 500SS51技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案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.Algebraic Formulation52技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Spreadsheet Formulation53技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Types of Functional ConstraintsTypeForm*Typical InterpretationMain UsageResource constraintLHS RHSFor some resource,Amount used Amount availableResource- allocation problems and mixed problemsBenefit constraintLHS RHSFor some benefit,Level achieved Minimum AcceptableCost-benefit-trade- off problems and mixed problemsFixed- requirement constraintLHS = RHSFor some quantity,Amount provided =Required amountDistribution- network problems and mixed problems* LHS = Left-hand side (a SUMPRODUCT function).RHS = Right-hand side (a constant).54技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案混合问题n混合问题也是一类典型的线性规划问 题，它包含的约束是多种多样的，即 可能有资源约束，也可能有收益约束 ，还可能有确定需求的约束线性规划 建模与应用55技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案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)Save-It Company Waste Reclamation56技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Product Data for the Save-It CompanyGradeSpecificationAmalgamation Cost per PoundSelling Price per PoundAMaterial 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.50BMaterial 1: Not more than 50% of total Material 2: Not less than 10% of the total Material 4: Exactly 10% of the total2.507.00CMaterial 1: Not more than 70% of the total2.005.5057技术创新概念特点及案例继电保护基础知识加快转变发展方式课件家居门店业绩提升方案Material Data for the Save-It CompanyMaterialPounds/Week AvailableTreatment Cost per PoundAdditional Restrictions13,000$3.001. For each material, at least half of the pounds/week available should be collected and tr