第3章 线性规划与电子表格

第三章线性规划与电子表格第三章线性规划与电子表格第三章线性规划与电子表格每个小组都有一组拼装玩具(8个小块和6大块)，这些是你们的原材料（rawmaterials），你们要用这些原材料去生产桌和椅（tablesandchairs）这两种产品（products），具体拼装图如下一个幻灯片。TheLegoProductionProblem拼装玩具生产你怎么去分析呢？想想看！第三章线性规划与电子表格原材料6大块8小块产品桌椅Profit=$20/TableProfit=$15/Chair第三章线性规划与电子表格Maximize($15)($20)subjecttoLargeBricks:26SmallBricks:228and0,0.ChairsTablesChairsTablesChairsTablesChairsTables++≤+≤≥≥为了最小化成本或最大化利润的目的需要对一些稀缺资源进行配置你的答案是什么？第三章线性规划与电子表格ComponentsoftheModel模型的组成部分ƒDecisionvariables决策变量ƒObjectivefunction目标函数ƒConstraints约束第三章线性规划与电子表格AssumptionsofLinearProgramming线性规划的假设ƒLinearity线性ƒDivisibility可分性ƒCertainty确定性ƒNonnegativity非负性第三章线性规划与电子表格WhyUseLinearProgramming?为什么要使用线性规划ƒ线性规划很容易而有效率地被求解ƒ如果存在最优解，则肯定能够找到ƒ功能强大的敏感性分析（sensitivityanalysis）ƒ许多实际问题本质上是线性的第三章线性规划与电子表格MathematicalStatementofLPProblem线性规划的数学描述线性规划要确定决策变量x1,x2,…,xn使得MaximizeZ=c1x1+…+cnxn←ObjectiveFunctionsubjecttoa11x1+…+a1nxn≤b1a21x1+…+a2nxn≤b2Mam1x1+…+amnxn≤bm⎫⎬⎪⎪⎭⎪⎪←FunctionalConstraintsandx1≥0,…,xn≥0←NonnegativityConstraints已知参数c1,…,cn;a11,…,amn;b1,…,bm.第三章线性规划与电子表格StepsinFormulatingLPProblem线性规划问题建模步骤ƒ需要做哪些决策？决策变量是什么ƒ问题的目标是什么？写出目标函数ƒ资源和需求之间的情况如何？确定约束条件第三章线性规划与电子表格12345612345ChairsTablesChairs+2Tables=6LargeBricks2Chairs+2Tables=8SmallBricksTheGraphicalMethodforSolvingLP线性规划的图解法第三章线性规划与电子表格TheSimpleMethodforSolvingLP线性规划的单纯形法(0,0)(4,0)(0,6)ProductionrateforwindowsProductionratefordoorsProfit=$3,000(2,6)Profit=$3,600Profit=$2,700Profit=$1,200Feasibleregion321(4,3)Profit=0DW第三章线性规划与电子表格UsingExcelSolvertoSolving用微软ExcelSolver求解第三章线性规划与电子表格SolvingLegoProblem求解玩具拼装问题ƒ用易理解方式输入数据和构筑数据之间的联系ƒ定义目标单元格（目标函数）ƒ确定可变单元（决策变量）ƒ添加约束变量（AddingConstraints）第三章线性规划与电子表格TheSolution求解结果第三章线性规划与电子表格KeyCategoriesofLPProblems线性规划问题主要类型ƒ资源分配问题（resource-allocation）ƒ成本收益平衡问题（cost-benefit-trade-off）ƒ网络配送问题（distribution-network）ƒ混合问题（mixedProblem）第三章线性规划与电子表格Resource-allocationProblem资源分配问题资源分配（resource-allocation）问题是将有限的资源分配到各种活动中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数限制均为资源限制(resourceconstraint),并且每一种有限资源都可以表现为如下的形式：使用的资源数量≤可用的资源数量第三章线性规划与电子表格Think-BigDevelopmentCo.梦大发展公司第三章线性规划与电子表格Distribution-networkProblem网络配送问题网络配送问题（distributionnetwork）能以最小的成本完成货物的配送，所以称之为网络配送问题并具有如下的确定性约束形式：提供的数量＝需要的数量F1DCF2W2W180unitsproduced70unitsproduced60unitsneeded90unitsneeded$700/unit$900/unit$200/unit[50unitsmax.]$400/unit[50unitsmax.]$300/unit[50unitsmax.]$400/unit[50unitsmax.]第三章线性规划与电子表格DistributionUnlimitedCo.无限配送公司第三章线性规划与电子表格MixedProblem混合问题资源分配问题，成本收益平衡问题以及网络配送问题，都以一类约束条件为特色的。实际上，纯资源分配问题的共性是它所有的函数约束均为资源约束，而成本收益平衡问题的共性是它所有的函数约束均为收益约束，网络配送问题中，主要的函数约束为一特定类型的确定需求的约束。混合问题是第四类线性规划问题，这一类型包括了三类约束函数第三章线性规划与电子表格Save-ItCompany塞维特公司实际举例第三章线性规划与电子表格Save-ItCompany塞维特公司第三章线性规划与电子表格物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）TheTransportationProblem运输问题你怎么去分析这类问题呢？想想看！第三章线性规划与电子表格TheTransportationProblem运输问题SourcesDestinations第三章线性规划与电子表格2321341s2=10s3=15d1=13d2=21d3=9d4=7s1=25供应量供应地运价需求量需求地6753842759106TransportationNetwork运输问题的网络表示第三章线性规划与电子表格0xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211≥=++=++=++=++=+++=+++=++++++++++++++=供应地约束需求地约束LPModelofTransportationProblem运输问题线性规划模型第三章线性规划与电子表格P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。豌豆罐头在三个食品罐头厂（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝·李）加工，然后用卡车把它们运送到美国西部的四个分销仓库(加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古)。TransportationProblemExample运输问题举例第三章线性规划与电子表格CANNERY1BellinghamCANNERY2EugeneWAREHOUSE1SacramentoWAREHOUSE2SaltLakeCityWAREHOUSE3RapidCityWAREHOUSE4AlbuquerqueCANNERY3AlbertLeaP&T公司问题中的仓库和加工厂位置图第三章线性规划与电子表格TransportationProblemExample运输问题举例实际举例作为一个运输问题的P&T公司电子表格描述第三章线性规划与电子表格每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品需求假设（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假设（TheCostAssumption）整数解性质（IntegerSolutionsProperty）CharacteristicsofTransportationProblems运输问题的特征第三章线性规划与电子表格需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足可行解特性：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量整数解性质：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件第三章线性规划与电子表格ƒ供应总量超出了需求总量ƒ供应总量小于需求总量ƒ一个目的地同时存在着最小需求和最大需求ƒ在配送中不能使用特定的出发地——目的地组合ƒ目标是与配送量有关的总利润最大不是成本最小VariantsofTransportationProblems各种运输问题变体第三章线性规划与电子表格现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂TheAssignmentProblem指派问题还有哪些这样的问题呢？想想看！第三章线性规划与电子表格指派问题的形式表述:给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务指派问题的假设:ƒ被指派者的数量和任务的数量是相同的ƒ每一个被指派者只完成一项任务ƒ每一项任务只能由一个被指派者来完成ƒ每个被指派者和每项任务的组合有一个相关成本ƒ目标是要确定怎样进行指派才能使得总成本最小第三章线性规划与电子表格VariantsofAssignmentProblem指派问题的变形指派问题的变形:ƒ有一些被指派者并不能进行某一些的任务ƒ任务比被指派者多ƒ被指派者比要完成的任务多ƒ每个被指派者可以同时被指派给多于一个的任务ƒ每一项任务都可以由多个被指派者共同完成第三章线性规划与电子表格AssigningPlantstoProducts指派工厂生产产品求佳产品公司问题指派问题变形的电子表格模型第三章线性规划与电子表格ApplicationsofNetworkOptimization网络最优化模型的应用网络在交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效直观和概念上的帮助，广泛应用于科学、社会和经济活动的每个