OR6205 Class Packet Fall 2018 PDF

Preview

Summary

Overview of Deterministic Operations Research Class Packet...

Description

OR 6205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET

Lecture Notes by Professor Emanuel Melachrinoudis

Mechanical and Industrial Engineering Northeastern university Boston, MA

FALL 2009

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

TABLE OF CONTENTS WHAT IS OPERATIONS RESEARCH (OR) ...................................................................................3 HISTORY OF OR .............................................................................................................................3 INTRODUCTION TO LINEAR PROGRAMMING (LP) ....................................................................5 FINDING A SOLUTION TO THE SYSTEM OF SIMULTANEOUS LINEAR EQUATIONS BY THE GAUSS-JORDAN METHOD (GAUSSIAN ELIMINATION) .......................................... 6 MATRIX INVERSION .......................................................................................................................... 7 HOW THE GAUSS JORDAN METHOD CAN RECOGNIZE OTHER CASES ........................... 8 LINEAR PROGRAMMING ................................................................................................................. 9 LINEAR PROGRAMMING MODEL IN A STANDARD FORM .................................................. 10 EXAMPLE FOR ENTERING IN THE COMPUTER A LINGO MODEL ................................... 11 CHAPTER 3 PROBLEM 3.4-13 ......................................................................................................... 13 MATHEMATICAL FORMULATION OF PROBLEM 3.4-13 ....................................................... 14 The Fourier-Motzkin Elimination (FME) Method for Linear Programming ................................ 18 AUGMENTED SOLUTION ...............................................................................................................21 SHADOW (DUAL) PRICES ............................................................................................................... 25 BREAKING TIES IN THE SIMPLEX METHOD ........................................................................... 26 DEGENERATE BASIC SOLUTION ................................................................................................. 27 ILLUSTRATION OF AN UNBOUNDED Z-VALUE PROBLEM.................................................. 28 DETECTING MULTIPLE OPTIMAL SOLUTIONS USING THE SIMPLEX TABLEAU .......29 ADAPTING NONSTANDARD TO STANDARD LP FORM .......................................................... 30 Minimization ...................................................................................................................................30 Equality Constraints........................................................................................................................ 30 Big-M Method Iterations .................................................................................................................31 Two Phase Method ..........................................................................................................................32



" " Inequality Constraints ............................................................................................................. 33 Constraints with negative right-hand sides (rhs) ............................................................................ 34 Variables Unrestricted In Sign ........................................................................................................34 Example...........................................................................................................................................35 Solution by the Big-M Method ........................................................................................................37 THEORY OF SIMPLEX ..................................................................................................................38 CORNER POINT SOLUTIONS OF THE PROTOTYPE EXAMPLE PROBLEM ..................... 40 PROPERTIES OF CORNER POINT FEASIBLE SOLUTIONS (EXTREME POINTS) ............ 41 COMPUTATIONAL COMPLEXITY OF SIMPLEX ...................................................................... 42 INTERIOR-POINT ALGORITHMS ................................................................................................. 43 ANATOMY OF SIMPLEX ................................................................................................................. 45 FUNDAMENTAL INSIGHT .............................................................................................................. 48 DUALITY THEORY ........................................................................................................................51 PRIMAL-DUAL RELATIONSHIPS ................................................................................................. 56 CLASSIFICATION OF BASIC SOLUTIONS .................................................................................. 58 DUAL SIMPLEX ALGORITHM ....................................................................................................... 59 SENSITIVITY ANALYSIS ..............................................................................................................60 FLOWCHART FOR SENSITIVITY ANALYSIS ............................................................................ 61 SENSITIVITY ANALYSIS EXAMPLE ............................................................................................ 62 DETERMINING OBJECTIVE ROW AND RHS RANGES ........................................................... 63 SENSITIVITY ANALYSIS WITH REOPTIMIZATION ................................................................ 64

1

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

A TRANSPORTATION PROBLEM ...............................................................................................68 THE TRANSPORTATION MODEL ................................................................................................. 71 PROTOTYPE EXAMPLE PROBLEM ............................................................................................. 72 THE TRANSPORTATION SIMPLEX ALGORITHM ................................................................... 74 OBTAINING AN INITIAL BFS USING THE NORTHWEST CORNER RULE ......................... 75 OBTAINING AN INITIAL BFS USING VOGEL'S APPROXIMATION METHOD .................. 76 TRANSPORTATION SIMPLEX EXAMPLE .................................................................................. 77 THE ASSIGNMENT PROBLEM ....................................................................................................79 THE GENERALIZED ASSIGNMENT PROBLEM (GAP) ..............................................................82 THE GENERALIZED TRANSPORTATION PROBLEM (Transshipment Problem) ................... 83 NETWORK ANALYSIS ..................................................................................................................87 TERMINOLOGY OF NETWORKS .................................................................................................. 87 SHORTEST PATH PROBLEM ......................................................................................................... 89 Flow Chart Of Dijkstra's Algorithm ................................................................................................90 Shortest Path Example ....................................................................................................................91 Shortest Path Example With Multiple Optima ................................................................................93 Shortest Path Example of a Directed Network ................................................................................ 94 MINIMUM SPANNING TREE PROBLEM ..................................................................................... 95 Minimum Spanning Tree Example ..................................................................................................96 Network Example With Multiple Optimal Spanning Trees .............................................................97 STEINER TREE PROBLEM ........................................................................................................... 989 TRAVELLING SALESMAN PROBLEM (TSP) ............................................................................ 100 TSP Formulation ........................................................................................................................... 101 MAXIMUM FLOW PROBLEM ...................................................................................................... 101 Maximum Flow Algorithm ............................................................................................................103 GENERALIZED NETWORK FLOW PROBLEM OR MINIMUM COST FLOW PROBLEM (GNFP) ....................................................................................................................................... 1067 MATHEMATICAL FORMULATION OF GNFP ........................................................................ 1089 HOW GNFP CAN BE MODIFIED TO MODEL SPECIAL CASE PROBLEMS ..................11011 Transportation Problem ............................................................................................................11011 Assignment Problem .................................................................................................................. 11011 Transshipment Problem ............................................................................................................ 11112 Shortest path problem ............................................................................................................... 11213 Maximum Flow Problem ...........................................................................................................11314 NETWORKS FOR PROJECT MANAGEMENT ........................................................................1145 A Prototype Example – The Reliable Construction Co. Problem ...............................................1145 CPM Method of Time-Cost Tradeoff ...........................................................................................1234 DYNAMIC PROGRAMMING......................................................................................................1256 PROTYPE EXAMPLE .................................................................................................................... 1256 Stagecoach Problem.................................................................................................................... 1257 GENERAL CHARACTERISTICS OF A DYNAMIC PROGRAMMING PROBLEM ........... 1289 A NONLINEAR OPTIMIZATION PROBLEM SOLVED BY DYNAMIC PROGRAMMING12930 SOME DYNAMIC PROGRAMMING APPLICATIONS/MODELS ....................................... 13031 APPENDIX: PROBLEMS FOR FORMULATION AND SOLUTION ..........................................1312

2

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

WHAT IS OPERATIONS RESEARCH (OR)  OR is the professional discipline that deals with the application of scientific methods to decision making, especially to the allocation of resources  OR uses analytical and numerical techniques to develop and manipulate mathematical and computer models of organizational systems composed of people, machines, and procedures  OR draws upon ideas from many diverse areas, such as, engineering, management, mathematics and psychology to contribute to a wide variety of application domain  OR is closely related to several other fields in the "Decision Sciences" - Applied Mathematics, Computer Science, Systems Engineering, Industrial Engineering and Economics.

HISTORY OF OR  During world war II by the British government  Research on military operations problems OR  Develop methods for effectively utilizing new defense technologies, such as the radar  The air chief marshal directed the project for the Royal Air Force, 1938  This first OR project contributed to the first allied victory, the battle of Britain, 1940  Rapid expansion of OR in the USA began in 1942, again as military operations research

3

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

 After the war, interest spread from the military to other government organizations and to the industry  In 1952 ORSA was founded by professor Philip Morse of MIT  By the early 1970's a large body of theory and methods was developed.  Linear programming  Network analysis  Dynamic programming  Markov Chains  Queueing theory  Inventory theory  Forecasting  Game theory  Integer and nonlinear programming  Scheduling  Simulation  Multiple criteria decision making  Practitioners have successfully used the above OR methods in many application areas, in addition to military, such as:  Manufacturing  Transportation  Communication  Construction  Health care

 Banking  In 1995 ORSA merged with the Institute of Management Sciences to form the INFORMS organization

4

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

INTRODUCTION TO LINEAR PROGRAMMING (LP)  LP was the first OR area, developed in the 1940's  The most common application of LP is the allocation of limited resources to competing activities in the best possible (optimal) way. For example,  Allocating production facilities to products  Allocating limited funds to investment opportunities  Selection of shipping patterns  Agricultural planning  LP uses a mathematical model of the system. Activity levels are represented by variables which are used to define the measure of performance (objective function), and restrictions of the problem are represented by functions in equality or inequality forms (constraints)  The name linear programming stands for the linearity of the functions used (linear), and the planning of activities (programming)  The tremendous impact of LP is mostly due to the development of the digital computer and of an efficient computational procedure called simplex (Dantzig 1947)  New (interior point) methods were developed (N. Karmarkar, Bell Laboratories,1984) which can solve large size problems.

5

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

FINDING A SOLUTION TO THE SYSTEM OF SIMULTANEOUS LINEAR EQUATIONS BY THE GAUSSJORDAN METHOD (GAUSSIAN ELIMINATION)  (1) 2x1  2x 2  x 3  9   It .(0)  (2) 2x1  x2  2x3  6 (3) x  x  2 x  5 1 2 3  

Select a variable in eq (1) with a nonzerocoefficien t, say x 1 . Divide eq (1) by that coefficien t (step1) eq (1) : pivot row, column of x1 : pivot column, coeff. of x1 : pivot element

x3 9  (1) x 1  x 2  2  2 row (2)  ( 2) pivot row + row(2)  (2) 2x 1  x2  2 x3  6 (step 2) (3) x  x  2 x  5 row (3)  ( 1) pivot row + row(3) 1 2 3   x3 9   (1) x1  x 2  2  2 rep eat step 1 and 2. Pivot row  row (2)  It .(1)  (2)  3x2  x3  3 p ivot column  column of x2  3 1 (3)  2 x2  x3  pivot element  ( 3) 2 2   5 7 + x3  rep eat step 1 and 2. Pivot row  row (3) (1) x1 6 2  1  It .(2) (2) x 2  x 3 1 p ivot column  column of x 3 3   5 5  5 x3  pivot element    (3) 6 2  6   1 The variable values can be read It .(3) (1) x1 PROPER (2) FORM (3)

x2

 2 from the RHS x3  3

The elementary row operations performed are equivalent to premultip ling the original matrix B by its inverse B -1 , i.e., Bx  b  B 1Bx = B-1 b  Ix = B-1 b  x = B-1 b

6

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

MATRIX INVERSION Augment square matrix B by I, B  I  and p erformelementary row operations, so that matrix B is transformed into I  1 1  0 0 1 1  2 2 1 1 0 0  2 2    It.(0) B  I = 2 - 1 2 0 1 0 , 2 - 1 2 0 1 0 step 1 1 - 1 2 0 0 1 1 - 1 2 0 0 1     5 1 1   1 1 1 0 0    6 6 3  1 1 2 2 0 0     -1 1 -1  It.(1) 0 - 3 1 - 1 1 0  , It.(2) 0 1 0   3 3 3    3 1  5 1 -2  0 1 0 - 2  0 0 1 2 2    6 6 3   1 0 0 0 1 - 1      1 2 3 2 It.(3) 0 1 0   I B  5 5 5  1 -4 6  0 0 1  5 5 5 





  0 1 - 1   2 2 1 1 0 0   2 3 2  1   2 - 1 2    0 1 0   I and B B=    5 5 5    1 - 4 6  1 - 1 2  0 0 1     5 5 5

  0 1 - 1    9  1   2 3 2  1   6   2  B b   5 5 5      1 - 4 6   5  3    5 5 5 

 In general, if rank[A, b]= rank[A] there is one or more solutions to the system of simultaneous linear equations Ax=b. In addition,  If rank[A]=n (# of variables) there exists a unique solution (previous example).  If rank[A]rank[A] the system of equations Ax=b is inconsistent

7

IEM G205 DETERMINISTIC OPERATIONS RESEARCH CLASS PACKET FALL 2007

HOW THE GAUSS JORDAN METHOD CAN RECOGNIZE OTHER CASES A. The case of an infinite number of solutions B. Inconsistent system of equations

Example a.1 =1  1 x1  x2  x 2  x3  3  2  3  x 1  2x 2  x 3  4 

x1

 x3   2 x1   2  x3    x 2  x3  3   x 2  3  x 3  x 3: any value  0x3  0   

The above occurs because rank(A, b)= rank(A)=2...