Chapter 2. Linear Programming: Basic Concepts

Presentation on theme: "Chapter 2. Linear Programming: Basic Concepts"— Presentation transcript:

1 Chapter 2. Linear Programming: Basic Concepts
第二章. 线性规划: 基本概念 运筹学

2 Table of Contents (主要内容)
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节])

3 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 Example—The Profit & Gambit Co. (Section 2.7) (一个最小化的例子——利博公司广告组合问题[第2.7节])

4 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%)

5 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万美元) 线性规划 太有用了！

6 Three Classic Applications of LP
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 Citgo’s major products throughout the United States. (SDM系统使用LP来协调全美Citgo石油公司主要产品的供应、配送和营销) The resulting reduction in inventory added $14 million annually to Citgo’s profits. (库存成本的下降每年为公司增加1400万美元的收入)

7 Wyndor Glass Co. Product Mix Problem
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生产玻璃并组装窗和门)

8 Wyndor Glass Co. Product Mix Problem
公司是否应该生产这两个新产品？如果生产，两个新产品的生产组合如何？ Should they go ahead with launching these two new products? If so, what should be the product mix?

9 Wyndor Glass Co. Product Mix Problem
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). (为这些数据单元格标上颜色便于区分和建模)

10 Wyndor Glass Co. Product Mix Problem
Developing a Spreadsheet Model (建立电子表格模型)

11 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 don’t 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). (为这些可变单元格标上颜色便于区分和建模)

12 Wyndor Glass Co. Product Mix Problem
Developing a Spreadsheet Model (建立电子表格模型) 4 12 18

13 Wyndor Glass Co. Product Mix Problem
Developing a Spreadsheet Model (建立电子表格模型) 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). (给目标单元格标记颜色)

14 Wyndor Glass Co. Product Mix Problem
Developing a Spreadsheet Model (建立电子表格模型) 4 12 18

15 Wyndor Glass Co. Product Mix Problem
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. (在三个连续的单元格中定义约束)

16 Wyndor Glass Co. Product Mix Problem
Developing a Spreadsheet Model (建立电子表格模型) 4 12 18

17 Wyndor Glass Co. Product Mix Problem
A Trial Solution (试验解) 4 12 18 The spreadsheet for the Wyndor problem with a trial solution (4 doors and 3 windows) entered into the changing cells. (含试验解的韦恩德公司问题的电子表格模型，在可变单元格中输入了4扇门和3扇窗)

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 = $300D + $500W subject to (约束) D ≤ 4 2W ≤ D + 2W ≤ 18 and D ≥ 0, W ≥ 0. 运筹学

19 Wyndor Glass Co. Product Mix Problem
产品组合图形

20 Wyndor Glass Co. Product Mix Problem
非负约束

21 Wyndor Glass Co. Product Mix Problem
非负约束

22 Wyndor Glass Co. Product Mix Problem
非负约束

23 Wyndor Glass Co. Product Mix Problem
Boundary Line for Constraint 3D + 2W ≤ 18 (约束条件边界线)

24 Wyndor Glass Co. Product Mix Problem
只改变约束条件右侧得到平行的约束边界线

25 Wyndor Glass Co. Product Mix Problem
3D + 2W ≤ 18 的非负可行域

26 Wyndor Glass Co. Product Mix Problem
Graph of Feasible Region (可行域图像)

27 Wyndor Glass Co. Product Mix Problem
Objective Function (P = 1,500) (目标函数)

28 Wyndor Glass Co. Product Mix Problem
Finding the Optimal Solution (寻找最优解)

29 Summary of the Graphical Method
Draw the constraint boundary line for each constraint. Use the origin (or any point not on the line) to determine which side of the line is permitted by the constraint. (画出每个函数约束的约束边界线，用原点或其它不在约束边界线上的点来确定直线的哪一边是约束条件所允许的) Find the feasible region by determining where all constraints are satisfied simultaneously. (找出由所有约束条件都同时满足所决定的可行域) Determine the slope of one objective function line. All other objective function lines will have the same slope. (确定一条目标函数线的斜率，所有其它目标函数线具有与之相同的斜率)

30 Summary of the Graphical Method
Move a straight edge with this slope through the feasible region in the direction of improving values of the objective function. Stop at the last instant that the straight edge still passes through a point in the feasible region. This line given by the straight edge is the optimal objective function line. (在可行域范围内朝着目标函数改进的方向移动目标函数线，在它还穿过可行域的一个点时停止移动，这时得到的就是最优目标函数线) A feasible point on the optimal objective function line is an optimal solution. (最优目标函数线上的可行点是一个最优解)

31 Wyndor Glass Co. Product Mix Problem
Identifying the Target Cell and Changing Cells (确定目标单元格和可变单元格) Choose the “Solver” from the Tools menu. (从工具菜单中选择“Solver”) Select the cell you wish to optimize in the “Set Target Cell” window. (在“Set Target Cell”中选择要优化的单元格) Choose “Max” or “Min” depending on whether you want to maximize or minimize the target cell. (根据需要选择“Max”或者“Min”选项) Enter all the changing cells in the “By Changing Cells” window. (在“By Changing Cells”窗体中输入所有可变单元格)

32 Wyndor Glass Co. Product Mix Problem
4 12 18

33 Wyndor Glass Co. Product Mix Problem
Adding Constraints (添加约束) To begin entering constraints, click the “Add” button to the right of the constraints window. (在约束窗体的右侧点击“Add”按钮添加约束) Fill in the entries in the resulting Add Constraint dialogue box. (在添加约束对话框中填入相应内容)

34 Wyndor Glass Co. Product Mix Problem
4 12 18

35 Wyndor Glass Co. Product Mix Problem
The Complete Solver Dialogue Box (设置完成的Solver对话框)

36 Wyndor Glass Co. Product Mix Problem
Some Important Options (一些重要选项) Click on the “Options” button, and click in both the “Assume Linear Model” and the “Assume Non-Negative” box. (单击“Options”按钮，并且选中“Assume Linear Model”和“Assume Non-Negative”选项) “Assume Linear Model” tells the Solver that this is a linear programming model. (“Assume Linear Model”选项使Solver确定该模型为线性规划模型) “Assume Non-Negative” adds nonnegativity constraints to all the changing cells. (“Assume Non-Negative”选项给所有可变单元格添加非负约束条件)

37 Wyndor Glass Co. Product Mix Problem

38 Wyndor Glass Co. Product Mix Problem
The Optimal Solution (最优解) 4 12 18

39 The Profit & Gambit Co. Management has decided to undertake a major advertising campaign that will focus on the following three key products: (管理层决定集中在下列三个主要产品上实行大规模广告活动) A spray prewash stain remover. (一种喷雾去污剂) A liquid laundry detergent. (一种液体洗涤剂) A powder laundry detergent. (一种洗衣粉) The campaign will use both television and print media (这一广告活动将采用电视和印刷媒体) The general goal is to increase sales of these products. (总目标是要增加所有这些产品的销售量)

40 The Profit & Gambit Co. Management has set the following goals for the campaign: (管理层设定了如下广告目标) Sales of the stain remover should increase by at least 3%.(喷雾去污剂至少增加3%的市场份额) Sales of the liquid detergent should increase by at least 18%.(液体洗涤剂至少增加18%的市场份额) Sales of the powder detergent should increase by at least 4%.(洗衣粉至少增加4%的市场份额)

41 The Profit & Gambit Co. 要以最低的总成本满足销售目标，公司应该在每种媒体上做多少钱的广告？ How much should they advertise in each medium to meet the sales goals at a minimum total cost?

42 Profit & Gambit Co. Spreadsheet Model
The Profit & Gambit Co. Profit & Gambit Co. Spreadsheet Model (电子表格模型)

43 Algebraic Model for Profit & Gambit (数学模型)
The Profit & Gambit Co. Algebraic Model for Profit & Gambit (数学模型) Let: TV = the number of units of advertising on television (电视广告的单位数量) PM = the number of units of advertising in the print media (印刷媒体的广告数量) Minimize Cost = TV + 2PM (in millions of dollars)

44 Algebraic Model for Profit & Gambit (数学模型)
The Profit & Gambit Co. Algebraic Model for Profit & Gambit (数学模型) subject to: Stain remover increased sales: PM ≥ 3 (喷雾去污剂的销售增量) Liquid detergent increased sales: 3TV + 2PM ≥ 18 (喷雾去污剂的销售增量) Powder detergent increased sales: –TV + 4PM ≥ 4 And TV ≥ 0, PM ≥ 0.

45 Applying the Graphical Method (应用图形方法)
The Profit & Gambit Co. Applying the Graphical Method (应用图形方法)

46 The Optimal Solution (最优解)
The Profit & Gambit Co. The Optimal Solution (最优解)

47 The end of chapter 2