深圳大学管理学院：《运筹学》课程教学资源（PPT课件讲稿）图论（图论与网络分析）运筹学3类 LINEAR PROGRAMME AND SOLVING GRAPHICALLY

CHAPTER 7: DEVELOPING THE LINEAR PROGRAMME AND SOLVING GRAPHICALLY

CHAPTER 7: DEVELOPING THE LINEAR PROGRAMME AND SOLVING GRAPHICALLY

TOOLS REQUIRED TO SOLVEA LINEAR PROGRAMMING ◆ linear functions o graphs and co-ordinate systems representing linear functions graphical o solving simultaneous linear equations o Software package-MS-Excel Solver

TOOLS REQUIRED TO SOLVE A LINEAR PROGRAMMING  linear functions  graphs and co-ordinate systems  representing linear functions graphically  solving simultaneous linear equations  Software package—MS-Excel Solver

FORMULATING THE LINEAR PROGRAMMING t The definition of the decision variables Let x= the number of fables manufactured per week Let y= the number of chairs manufactured per week The objective function Maximise profit =4X+3Y

FORMULATING THE LINEAR PROGRAMMING  The definition of the decision variables – Let X = the number of Tables manufactured per week – Let Y = the number of Chairs manufactured per week  The objective function – Maximise Profit = 4X + 3Y

The set of constraints 4X+lY<90 Constraint due to Wood 2X+lY<50 Constraint due to Machine-Time] 1X+ lY<40 [Constraint due to Polishing-Timel X20, Y20 [non-negative constraint

 The set of constraints – 4X + 1Y  90 [Constraint due to Wood] – 2X + 1Y  50 [Constraint due to Machine-Time] – 1X + 1Y  40 [Constraint due to Polishing-Time] – X0, Y  0 [non-negative constraint]

◆ SUMMARY Let X=the number of Tables made per week Let y= the number of Chairs made per week Maximise Profit =4X+3Y Objective Function Subject to 4X+1Y≤90 Wood 2X+1Y≤50 Machine-Time X+1Y≤40 Polishing-Time X,Y≥0

 SUMMARY – Let X = the number of Tables made per week, Let Y = the number of Chairs made per week, – Maximise Profit = 4X + 3Y Objective Function Subject to 4X+1Y  90 Wood 2X+1Y  50 Machine-Time 1X +1Y  40 Polishing-Time X, Y  0

SOLVING A LINEAR PROGRAMME ◆ Stage 1 4X+1Y≤90 Wood constraints WOOD CONSTRAINT 000 No. Tables

SOLVING A LINEAR PROGRAMME  Stage 1 – 4X+1Y  90 Wood constraints

2X+1Y<50 Machine-Time 80 WOOD CONSTRAINT MACHINE TIME CONSTRAINT No. Tables

– 2X+1Y  50 Machine-Time

1X+1Y<40 Polishing-Time ALL THREE CONSTRAINTS WOOD CoNSTRAINT MACHINE TIME SONSTRAINT 10 c POLISHING CONSTRAINT No. Tables

– 1X +1Y  40 Polishing-Time

FEASIBLE REGION (O, A, B. C, D)--the set of all possible solutions to satisfy all the constraints WOOD CONSTRAINT B FEASIBLE户GON POLISHING TIME CONSTRAINT 00 5 0D2

– FEASIBLE REGION (O, A, B. C, D)--the set of all possible solutions to satisfy all the constraints

◆ Stage2 The conclusion is that the optimal solution, the value of X and Y that maximises the profit function, must lie at one of the corner points Profit 0 0 0 Read off graph 0 40 120 Read off graph 10 130 Solving, see i) below. 0 110 Solving, see ii) below 22.5 0 90 Read off graph

 Stage 2 – The conclusion is that the optimal solution, the value of X and Y that maximises the profit function, must lie at one of the corner points. X Y Profit 0 0 0 Read off graph 0 40 120 Read off graph 10 30 130 Solving, see i) below. 20 10 110 Solving, see ii) below. 22.5 0 90 Read off graph