INSEAD Library

Includes bibliographical references and index

Digitized

Principles of Mathematics in Operations Research Contents 1 Introduction........................................................................................................... 1 1.1 Mathematics and OR ................................................................................. 1 1.2 Mathematics as a language ........................................................................ 2 1.3 The art of making proofs ........................................................................... 5 1.3.1 Forward­Backward method............................................................. 5 1.3.2 Induction Method ............................................................................ 7 1.3.3 Contradiction Method ...................................................................... 8 1.3.4 Theorem of alternatives ................................................................... 9 Problems ............................................................................................................ 9 Web material..................................................................................................... 10 2 Preliminary Linear Algebra.............................................................................. 13 2.1 Vector Spaces............................................................................................. 13 2.1.1 Fields and linear spaces ................................................................. 13 2.1.2 Subspaces ....................................................................................... 14 2.1.3 Bases .............................................................................................. 16 2.2 Linear transformations, matrices and change of basis............................. 17 2.2.1 Matrix multiplication ..................................................................... 17 2.2.2 Linear transformation..................................................................... 18 2.3 Systems of Linear Equations .................................................................... 20 2.3.1 Gaussian elimination...................................................................... 20 2.3.2 Gauss-Jordan method for inverses ................................................ 23 2.3.3 The most general case ................................................................... 24 2.4 The four fundamental subspaces............................................................... 25 2.4.1 The row space of A......................................................................... 25 2.4.2 The column space of A................................................................... 26 2.4.3 The null space (kernel) of A ......................................................... 26 2.4.4 The left null space of A ................................................................. 27 2.4.5 The Fundamental Theorem of Linear Algebra.............................. 27 Problems .......................................................................................................... 28 Web material..................................................................................................... 29 X Contents 3 Orthogonality ...................................................................................................... 33 3.1 Inner Products............................................................................................. 33 3.1.1 Norms ............................................................................................ 33 3.1.2 Orthogonal Spaces......................................................................... 35 3.1.3 Angle between two vectors............................................................ 36 3.1.4 Projection....................................................................................... 37 3.1.5 Symmetric Matrices ...................................................................... 37 3.2 Projections and Least Squares Approximations.......................................... 38 3.2.1 Orthogonal bases............................................................................ 39 3.2.2 Gram-Schmidt Orthogonalization.................................................. 40 3.2.3 Pseudo (Moore-Penrose) Inverse................................................... 42 3.2.4 Singular Value Decomposition...................................................... 43 3.3 Summary for Ax = b.................................................................................... 44 Problems ........................................................................................................... 47 Web material..................................................................................................... 47 4 Eigen Values and Vectors................................................................................... 51 4.1 Determinants .............................................................................................. 51 4.1.1 Preliminaries ................................................................................. 51 4.1.2 Properties ....................................................................................... 52 4.2 Eigen Values and Eigen Vectors ................................................................ 54 4.3 Diagonal Form of a Matrix ......................................................................... 55 4.3.1 All Distinct Eigen Values............................................................... 55 4.3.2 Repeated Eigen Values with Full Kernels .................................... 57 4.3.3 Block Diagonal Form .................................................................... 58 4.4 Powers of A ................................................................................................ 60 4.4.1 Difference equations ..................................................................... 61 4.4.2 Differential Equations.................................................................... 62 4.5 The Complex case....................................................................................... 63 Problems ........................................................................................................... 65 Web material..................................................................................................... 66 5 Positive Definiteness............................................................................................ 71 5.1 Minima, Maxima, Saddle points ................................................................ 71 5.1.1 Scalar Functions ............................................................................ 71 5.1.2 Quadratic forms.............................................................................. 73 5.2 Detecting Positive-Definiteness ................................................................. 74 5.3 Semidefinite Matrices ................................................................................ 75 5.4 Positive Definite Quadratic Forms ............................................................. 76 Problems ........................................................................................................... 77 Web material..................................................................................................... 77 Contents XI 6 Computational Aspects....................................................................................... 81 6.1 Solution of Ax = b...................................................................................... 81 6.1.1 Symmetric and positive definite .................................................... 81 6.1.2 Symmetric and not positive definite............................................... 83 6.1.3 Asymmetric .................................................................................... 83 6.2 Computation of eigen values ..................................................................... 86 Problems .......................................................................................................... 89 Web material..................................................................................................... 90 7 Convex Sets ......................................................................................................... 93 7.1 Preliminaries............................................................................................... 93 7.2 Hyperplanes and Polytopes ....................................................................... 95 7.3 Separating and Supporting Hyperplanes.................................................... 97 7.4 Extreme Points ........................................................................................... 98 Problems .......................................................................................................... 99 Web material..................................................................................................... 100 8 Linear Programming.......................................................................................... 103 8.1 The Simplex Method ................................................................................. 103 8.2 Simplex Tableau ........................................................................................ 107 8.3 Revised Simplex Method ...........................................................................110 8.4 Duality Theory............................................................................................111 8.5 Farkas' Lemma............................................................................................113 Problems .......................................................................................................... 115 Web material..................................................................................................... 117 9 Number Systems .................................................................................................121 9.1 Ordered Sets............................................................................................... 121 9.2 Fields...........................................................................................................123 9.3 The Real Field ........................................................................................... 125 9.4 The Complex Field .................................................................................... 127 9.5 Euclidean Space..........................................................................................128 9.6 Countable and Uncountable Sets ...............................................................129 Problems .......................................................................................................... 133 Web material..................................................................................................... 134 10 Basic Topology ................................................................................................. 137 10.1 Metric Spaces........................................................................................... 137 10.2 Compact Sets ...........................................................................................146 10.3 The Cantor Set ......................................................................................... 150 10.4 Connected Sets......................................................................................... 151 Problems .......................................................................................................... 152 Web material.....................................................................................................154 XII Contents 11 Continuity.......................................................................................................... 157 11.1 Introduction ............................................................................................ 157 11.2 Continuity and Compactness................................................................... 159 11.3 Uniform Continuity................................................................................ 160 11.4 Continuity and Connectedness ............................................................... 161 11.5 Monotonic Functions............................................................................... 164 Problems ......................................................................................................... 166 Web material................................................................................................... 166 12 Differentiation.................................................................................................... 169 12.1 Derivatives .............................................................................................. 169 12.2 Mean Value Theorems ............................................................................ 170 12.3 Higher Order Derivatives ...................................................................... 172 Problems ......................................................................................................... 173 Web material................................................................................................... 173 13 Power Series and Special Functions ............................................................... 175 13.1 Series .......................................................................................................175 13.1.1 Notion of Series .......................................................................... 175 13.1.2 Operations on Series.................................................................... 177 13.1.3 Tests for positive series................................................................ 177 13.2 Sequence of Functions............................................................................. 178 13.3 Power Series ........................................................................................... 179 13.4 Exponential and Logarithmic Functions .................................................180 13.5 Trigonometric Functions......................................................................... 182 13.6 Fourier Series .......................................................................................... 184 13.7 Gamma Function..................................................................................... 185 Problems ........................................................................................................... 186 Web material.................................................................................................... 188 14 Special Transformations .................................................................................. 191 14.1 Differential Equations............................................................................... 191 14.2 Laplace Transforms...................................................................................192 14.3 Difference Equations................................................................................ 197 14.4 Z Transforms ............................................................................................ 199 Problems ........................................................................................................... 201 Web material..................................................................................................... 202 Solutions ................................................................................................................. 205 Index........................................................................................................................ 293