TOC-线性规划

©TheMcGraw-HillCompanies,Inc.,2009第2章线性规划：基本概念学习目标2.2伟伯玻璃公司产品组合问题（2.1节）2.3在试算表上架构伟伯问题模式（2.2节）2.4–2.8伟伯问题之代数模式（2.3节）2.9利用图解法求解伟伯问题（2.4节）2.10–2.20用ExcelSolver求解伟伯问题（2.5节）2.21–2.26最小化范例—TheProfit&Gambit公司（2.6节）2.27–2.32补充教材线性规划导论（华盛顿大学上课教材）2.33–2.48图解法与LP解之性质（华盛顿大学上课教材）2.49–2.57©TheMcGraw-HillCompanies,Inc.,20092-2学习目标在读完本章后，你应该能够：1.解释什么是「线性规划」。2.了解建构试算表模式前所必须找出的三项核心问题。3.指出及确认线性规划试算表模式中四种储存格的目的。4.根据问题描述于试算表中建构线性规划模式。5.在试算表中表示线性规划模型的代数式。6.运用图解法求解双变数线性规划问题。7.使用Excel求解线性规划试算表模式。©TheMcGraw-HillCompanies,Inc.,20092-3伟伯玻璃公司产品组合问题伟伯公司发展以下的新产品：–铝框8呎玻璃门–4呎6呎可双面悬挂的木框窗户公司拥有三间工厂：–工厂1：生产铝框及金属器件–工厂2：生产木框–工厂3：生产玻璃并进行门及窗户的组装问题：1.公司是否应该从事新产品的生产？2.如果是的话，最佳的产品组合为何？©TheMcGraw-HillCompanies,Inc.,20092-4发展试算表模式步骤一：资料储存格–在试算表上输入问题所有相关的资料–使用一致性的栏与列储存方式–利用不同颜色来显示这些「资料储存格」（例如：浅色）是不错的方法©TheMcGraw-HillCompanies,Inc.,20092-5发展试算表模式（续）步骤二：变动储存格–在试算表上替每个需要做的决策设置一储存格–若是你没有特殊的起始解（initialvalues）考量，只要输入0即可–利用颜色与框线等来显示这些「变动储存格」（例如：浅色并加框线）是不错的方法©TheMcGraw-HillCompanies,Inc.,20092-6发展试算表模式（续）•步骤三：目标储存格–发展一个方程式来定义模式的目标–基本上此方程式涉及资料储存格与变动储存格以便决定感兴趣的数量（例如：总利润或总成本）–利用颜色来显示这个储存格（例如：深色并加粗框线）是不错的方法©TheMcGraw-HillCompanies,Inc.,20092-7发展试算表模式（续）步骤四：限制式–对于受限制的资源，在试算表某一储存格中计算该资源使用量（输出储存格）–在三个连续的储存格中定义限制式。例如：若数量A=数量B，将此三项（数量A、=、数量B）置于相邻的储存格©TheMcGraw-HillCompanies,Inc.,20092-8一组试验解伟伯问题试算表中将一组试验解（4扇门及3个窗户）输入于变动储存格©TheMcGraw-HillCompanies,Inc.,20092-9伟伯玻璃公司之代数模式令D=玻璃门的生产数量W=木框窗户的生产数量最大化P=$300D+$500W受限于D≤42W≤123D+2W≤18且D≥0,W≥0©TheMcGraw-HillCompanies,Inc.,20092-10产品组合示意图©TheMcGraw-HillCompanies,Inc.,20092-11满足限制式：D≥0及W≥0之区域示意图Productionrateforwindows864224680ProductionratefordoorsProductionrateforwindowsDW木框窗户的产能玻璃门的产能©TheMcGraw-HillCompanies,Inc.,20092-12满足D≤4之非负解ProductionrateforwindowsDW864224680ProductionratefordoorsProductionrateforwindowsD=4木框窗户的产能玻璃门的产能©TheMcGraw-HillCompanies,Inc.,20092-13满足2W≤12之非负解Productionratefordoors8642246802W=12DWProductionrateforwindows木框窗户的产能玻璃门的产能©TheMcGraw-HillCompanies,Inc.,20092-14限制式3D+2W≤18之边界线Productionratefordoors86422468010(0,9)(2,6)(4,3)21_(1,7)21_(3,4)21_(5,1)(6,0)3D+2W=18DWProductionrateforwindows木框窗户的产能玻璃门的产能©TheMcGraw-HillCompanies,Inc.,20092-15改变右侧值将产生一些平行的限制式边界线121086420246810ProductionratefordoorsDW3D+2W=243D+2W=183D+2W=12Productionrateforwindows木框窗户的产能玻璃门的产能©TheMcGraw-HillCompanies,Inc.,20092-16满足3D+2W≤18之非负解86402468102ProductionratefordoorsDW3D+2W=18Productionrateforwindows木框窗户的产能玻璃门的产能©TheMcGraw-HillCompanies,Inc.,20092-17可行解区域之示意图©TheMcGraw-HillCompanies,Inc.,20092-18目标函数（P=1,500）024688642ProductionrateforwindowsProductionratefordoorsFeasibleregionP=1500=300D+500WDW木框窗户的生产率玻璃门的生产率可行区域©TheMcGraw-HillCompanies,Inc.,20092-19寻找最佳解©TheMcGraw-HillCompanies,Inc.,20092-20图解法摘要画出每个函数限制式的限制边界线，利用原点（或其他不在线上的点）决定线的哪一边才能满足限制式。确定是否同时满足所有的限制式，找出可行区域。求出目标函数线的斜率，所有的目标函数线的斜率要相同。以这个斜率，在可行区域内往可改善目标值的方向移动线段，直到此线段与可行区域只交于一点即停止移动，包含这条线段的直线即是最佳目标函数线。在最佳目标函数线上的可行点即为最佳解。©TheMcGraw-HillCompanies,Inc.,20092-21辨识目标储存格与变动储存格从「工具」选单选择「规划求解」在「设定目标储存格」视窗中，选择你想要最佳化的储存格依据你是否要最大化或最小化目标储存格，选择「最大值」或「最小值」在「变动储存格」视窗中输入所有变动储存格©TheMcGraw-HillCompanies,Inc.,20092-22新增限制式若要输入限制式，选择限制式视窗右侧的「新增」按钮在「新增限制式」对话视窗中输入限制式相关资料©TheMcGraw-HillCompanies,Inc.,20092-23完整的「规划求解」对话视窗©TheMcGraw-HillCompanies,Inc.,20092-24一些重要的选项按「选项」钮，并且选取「采用线性模式」以及「采用非负值」二个选项–「采用线性模式」告诉规划求解这是一个线性规划模式–「采用非负值」会将非负限制式加到所有变动储存格©TheMcGraw-HillCompanies,Inc.,20092-25「规划求解结果」对话视窗©TheMcGraw-HillCompanies,Inc.,20092-26最佳解©TheMcGraw-HillCompanies,Inc.,20092-27Profit&Gambit公司管理阶层决定推动一个新的广告活动，并把目标锁定在以下三种主要产品上：–喷雾去渍剂–液态洗衣精–洗衣粉这个活动将运用电视及平面媒体作广告最根本的目标是希望增加这些产品的销售量管理阶层为该广告活动订定以下目标：–去渍剂的销售额至少要增加3%。–洗衣精的销售额至少要增加18%。–洗衣粉的销售额至少要增加4%。问题：目标是要决定于各种媒体应该广告多少数量，在达到销售目标的前提下，使总成本最小化？©TheMcGraw-HillCompanies,Inc.,20092-28Profit&Gambit公司试算表模式©TheMcGraw-HillCompanies,Inc.,20092-29Profit&Gambit公司问题之代数模式令TV=电视广告的单位数量PM=平面媒体广告的单位数量最小化成本=TV+2PM(百万美元)受限于去溃剂增加的销售量：PM≥3液状洗衣精增加的销售量：3TV+2PM≥18洗衣粉增加的销售量：–TV+4PM≥4TV≥0,PM≥0©TheMcGraw-HillCompanies,Inc.,20092-30运用图解法86420246810-2-4AmountofTVadvertisingFeasibleregion103TV+2PM=18PM=3PMTV-TV+4PM=4Amountofprintmediaadvertising电视广告的单位数量平面媒体广告的单位数量可行区域©TheMcGraw-HillCompanies,Inc.,20092-31最佳解AmountofTVadvertisingFeasibleregion051015104(4,3)optimalsolutionCost=15=TV+2PMCost=10=TV+2PMTVPM电视广告的单位数量平面媒体广告的单位数量可行区域最佳解©TheMcGraw-HillCompanies,Inc.,20092-32图解法摘要画出每个函数限制式的限制边界线，利用原点（或其他不在线上的点）决定线的哪一边才能满足限制式。确定是否同时满足所有的限制式，找出可行区域。求出目标函数线的斜率，所有的目标函数线的斜率要相同。以这个斜率，在可行区域内往可改善目标值的方向移动线段，直到此线段与可行区域只交于一点即停止移动，包含这条线段的直线即是最佳目标函数线。在最佳目标函数线上的可行点即为最佳解。©TheMcGraw-HillCompanies,Inc.,20092-33一个生产问题原物料每周供给量：8个小木块6个大木块产品：桌子利润=$20/桌子椅子利润=$15/椅子©TheMcGraw-HillCompanies,Inc.,20092-34线性规划线性规划使用数学模式来找出对于各项活动最佳的资源配置以使得利润最大或是成本最小令T=桌子生产量C=椅子生产量最大化利润=($20)T+($15)C受限于2T+C≤6大木块2T+2C≤8小木块且T≥0,C≥0©TheMcGraw-HillCompanies,Inc.,20092-35图形表示©TheMcGraw-HillCompanies,Inc.,20092-36线性规划模式的组成元素资料储存格变动储存格（决策变数）目标储存格（目标函数）限制式©TheMcGraw-HillCompanies,Inc.,20092-37线性规划的四项假设线性（Linearity）不可分割性（Divisibility）确定性（Certainty）非负值（Nonnegativity）©TheMcGraw-HillCompanies,Inc.,20092-38何种情况下试算表模式为线性？所有方程式（输出储存格）必须具有以下形式：=ax+by+cz+…其中a,b,c为常数（资料储存格）且x,y,z为变动储存格若C1:C6为变动储存格，D1:D6为资料储存格以下何者可能为LP模式的