线性规划基本概念

单击此处编辑母版标题样式,Copyright 2007,深圳大学管理学院 运筹学,#,Three Classic Applications of LP(Section 2.1),(,线性规划的三个经典应用第2.1节),The Wyndor Glass Company Product Mix Problem(Section 2.2),(,伟恩德玻璃制品公司产品组合问题第2.2节),Formulating the Wyndor Problem on a Spreadsheet(Section 2.3),(,在电子表格上建立韦恩德公司问题的模型第2.3节),The Algebraic Model for Wyndor(Section 2.4),(,韦恩德公司问题的数学模型第2.4节),Table of Contents,(,主要内容),The Graphical Method Applied to the Wyndor Problem(Section 2.5),(,韦恩德公司问题的图形方法第2.5节),Using the Excel Solver with the Wyndor Problem(Section 2.6),(,使用,Excel Solver,解决韦恩德公司问题第2.6节),A Minimization ExampleThe Profit&Gambit Co.(Section 2.7),(,一个最小化的例子利博公司广告组合问题第2.7节),Table of Contents,(,主要内容),Three Classic Applications of LP,Product Mix at Ponderosa Industrial,(,潘得罗索工业公司的产品组合问题),Considered limited resources,and determined optimal mix of plywood products.,(,考虑了有限资源，并确定了胶合板产品的最优组合),Increased overall profitability of company by 20%.,(,公司的总利润增加了20%),Three Classic Applications of LP,Personnel Scheduling at United Airlines,(,联合航空公司的员工排程),Designed work schedules for all employees at a location to meet service requirements most efficiently.,(,在每个地点为所有员工设计工作排程以最有效地满足服务需求),Saved$6 million annually.,(,每年可节约600万美元),线性规划,太有用了！,Planning Supply,Distribution,and Marketing at Citgo Petroleum Corporation,(Citgo,石油公司的供应、配送和营销计划),The SDM system uses LP to coordinate the supply,distribution,and marketing of each of Citgos major products throughout the United States.,(SDM,系统使用,LP,来协调全美,Citgo,石油公司主要产品的供应、配送和营销),The resulting reduction in inventory added$14 million annually to Citgos profits.,(,库存成本的下降每年为公司增加1400万美元的收入),Three Classic Applications of LP,Wyndor has developed the following new products,(,韦恩德公司开发了下列新产品),:,An 8-foot glass door with aluminum framing.,(8,英尺的铝框玻璃门),A 4-foot by 6-foot double-hung,wood-framed window.,(4,英尺*6英尺的双把木框门),The company has three plants,(,公司有三个工厂),Plant 1 produces aluminum frames and hardware.,(,工厂1生产铝框和五金件),Plant 2 produces wood frames.,(,工厂2生产木框),Plant 3 produces glass and assembles the windows and doors.,(,工厂3生产玻璃并组装窗和门),Wyndor Glass Co.Product Mix Problem,Wyndor Glass Co.Product Mix Problem,Should they go ahead with launching these two new products?,If so,what should be the,product mix,?,公司是否应该生产这两个新产品？如果生产，两个新产品的生产组合如何？,Developing a Spreadsheet Model,(,建立电子表格模型,),Step#1:Data Cells,(,第一步:数据单元格),Enter all of the data for the problem on the spreadsheet.,(,在电子表格中输入问题的所有数据),Make consistent use of rows and columns.,(,有效利用行和列),It is a good idea to color code these“data cells”(e.g.,light blue).,(,为这些数据单元格标上颜色便于区分和建模),Wyndor Glass Co.Product Mix Problem,Wyndor Glass Co.Product Mix Problem,Developing a Spreadsheet Model,(,建立电子表格模型,),Step#2:Changing Cells,(,第二步:可变单元格),Add a cell in the spreadsheet for every decision that needs to be made.,(,在电子表格中为每一决策添加一个单元格),If you dont have any particular initial values,just enter 0 in each.,(,如果没有任何初始值，输入0即可),It is a good idea to color code these“changing cells”(e.g.,yellow with border).,(,为这些可变单元格标上颜色便于区分和建模),Developing a Spreadsheet Model,(,建立电子表格模型,),Wyndor Glass Co.Product Mix Problem,Developing a Spreadsheet Model,(,建立电子表格模型,),Wyndor Glass Co.Product Mix Problem,4,12,18,Developing a Spreadsheet Model,(,建立电子表格模型,),Wyndor Glass Co.Product Mix Problem,Step#3:Target Cell,(,第三步:目标单元格),Develop an equation that defines the objective of the model.,(,建立定义模型目标的方程式),Typically this equation involves the data cells and the changing cells in order to determine a quantity of interest(e.g.,total profit or total cost).,(,典型地，这个方程式包含了数据单元格和可变单元格的数据，以确定有关的数量值，如总利润和总成本),It is a good idea to color code this cell(e.g.,orange with heavy border).,(,给目标单元格标记颜色),Wyndor Glass Co.Product Mix Problem,Developing a Spreadsheet Model,(,建立电子表格模型,),4,12,18,Developing a Spreadsheet Model,(,建立电子表格模型,),Step#4:Constraints,(,约束),For any resource that is restricted,calculate the amount of that resource used in a cell on the spreadsheet(an output cell).,(,对所有有限资源，在电子表格的输出单元格中计算出资源的使用量),Define the constraint in three consecutive cells.For example,if Quantity A Quantity B,put these three items(Quantity A,Quantity B)in consecutive cells.,(,在三个连续的单元格中定义约束),Wyndor Glass Co.Product Mix Problem,Wyndor Glass Co.Product Mix Problem,Developing a Spreadsheet Model,(,建立电子表格模型,),4,12,18,Wyndor Glass Co.Product Mix Problem,A Trial Solution,(,试验解),The spreadsheet for the Wyndor problem with a trial solution(4 doors and 3 windows)entered into the changing cells.,(,含试验解的韦恩德公司问题的电子表格模型，在可变单元格中输入了4扇门和3扇窗),4,12,18,Wyndor Glass Co.Product Mix Problem,Algebraic Model for Wyndor Glass Co.,(,韦恩德公司问题的数学模型),Let,D,=the number of doors to produce,(,门的生产量),W,=the number of windows to produce,(,窗的生产量),Maximize,P,=$300,D,+$500,W,subject to,(,约束),D,42,W,123,D,+2,W,18,and,D,0,W,0.,运筹学,Wyndor Glass Co.Product Mix Problem,产品组合图形,Wyndor Glass Co.Product Mix Problem,非负约束,Wyndor Glass Co.Product Mix Problem,非负约束,D,4,Wyndor Glass Co.Product Mix Problem,非负约束,2,W,12,Wyndor Glass Co.Product Mix Problem,Boundary Line for Constraint 3,D,+2,W,18,(,约束条件边界线),Wyndor Glass Co.Product Mix Pro。