《线性规划：建模与应用》由会员分享，可在线阅读，更多相关《线性规划：建模与应用（67页珍藏版）》请在金锄头文库上搜索。
1、1运筹学 Operations ResearchOperations Research2Chapter 4. Linear Programming: Formulation and Applications第四章. 线性规划：建模与应用Operations Research3n满足以下三个条件的模型称为线性规划模型 u 每一个问题都用一组决策变量(通常非负)表示 某一方案，这组决策变量的值就代表一个具体 方案 u 存在一定的约束条件，这些约束条件可以用一 组线性等式或线性不等式来表示 u 都有一个要求达到的目标，它可用决策变量的 线性函数(称为目标函数)来表示，按照问题的 不同，要求目标函数实
2、现最大化或最小化什么是线性规划模型4线性规划模型的一般形式什么是线性规划模型5n资源分配问题(resource-allocation)：资源 约束。伟恩德玻璃制品公司产品组合问题 n成本收益平衡问题(cost-benefit-trade-off) ：收益约束。利博公司广告组合问题，大 沼泽地金色年代公司的现金流问题 n网络配送问题(distribution-network)：确 定需求约束。 n混合问题(mix)：多种约束。线性规划问题的分类6nSuper Grain Corp. Advertising-Mix Problem (Section 4.1)(超级食品公司的广告 组合问题) nRe
3、source Allocation Problems j = C1, C2, C3)Minimize (最小化)Cost = $700SF1-C1 + $900SF1-C2 + $800SF1-C3 + $800SF2-C1 + $900SF2-C2 + $700SF2-C344subject 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
4、 Customer 3: SF1-C3 + SF2-C3 = 9 and Sij 0 (i = F1, F2; j = C1, C2, C3).Algebraic Formulation (数学模型)45Spreadsheet Formulation (电子表格模型)46配送网络问题n配送网络问题的函数约束是确定的需求 约束，可表示为： 提供的数量=需要的数量线性规划 建模与应用47Continuing the Super Grain Case StudyDavid and Claire conclude that the spreadsheet model needs to be expan
5、ded to incorporate some additional considerations. (大卫和克莱略 认为公司的电子表格模型还需要进一步扩展以 增加一些考虑事项) In particular, they feel that two audiences should be targeted young children and parents of young children. (他们尤其觉得必须 将目标观众定位为儿童及他们的家长)48Two new goals (两个新的目标) The advertising should be seen by at least five m
6、illion 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 Study49Benefit a
7、nd Fixed-Requirement Data50Algebraic 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 + 500SS
8、51subject 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
9、) and TV 0, M 0, SS 0.Algebraic Formulation52Spreadsheet Formulation53Types of Functional ConstraintsTypeForm*Typical InterpretationMain UsageResource constraintLHS RHSFor some resource,Amount used Amount availableResource- allocation problems and mixed problemsBenefit constraintLHS RHSFor some bene
10、fit,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 con
11、stant).54混合问题n混合问题也是一类典型的线性规划问 题，它包含的约束是多种多样的，即 可能有资源约束，也可能有收益约束 ，还可能有确定需求的约束线性规划 建模与应用55The 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. (赛维特公司经营一个回收中心，专 门从事四种固体废弃物的回收，并将回
12、收物 处理、混合成为可销售的产品)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 Reclamation56Product Data for the Save-It CompanyGradeSpecificationAmalgamation Cost per PoundSelling Price per PoundAMaterial 1:
13、 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 tha
14、n 70% of the total2.005.5057Material 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 treated. 2. $30,000 per week should be used to treat these
15、materials.22,0006.00 34,0004.00 41,0005.0058Save-It Company Waste ReclamationWhat quantity of each of the three grades of product should be produced from what quantity of each of the four materials? (四种原料各应使用多少？ 三种不同等级的产品各应生产多少？)59Algebraic FormulationLet (假定)xij = Pounds of material j allocated to
16、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)60subject 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 + x
