co370notes.pdf

184 Pages
134 Views
Unlock Document

Department
Combinatorics and Optimization
Course
CO 250
Professor
Christine Dupont
Semester
Winter

Description
Contents 1 Introduction 5 1.1 What is Operations Research? . . . . . . . . . . . . . . . . . . . . . . . . . . 5 . 1.1.1 Roots of OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5. . 1.1.2 OR Today . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 . 1.2 Goals of This Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 . . 2 Linear Programming Formulations 9 2.1 Resource Constraint Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Blending Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 . 2.3 Multiperiod Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13. 2.4 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14. . . 2.5 Modeling Piecewise Linear Functions . . . . . . . . . . . . . . . . . . . . . . . .16 2.5.1 Modeling Absolute Values . . . . . . . . . . . . . . . . . . . . . . . . . .17 2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18. . . 3 Linear Programming Review 23 3.1 Structure of Linear Programming Problems . . . . . . . . . . . . . . . . . . . . . 23 3.2 Properties of Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 . . 3.4 The Dual Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31. 3.5 Duality Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 . . 3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36. . . 4 Sensitivity Analysis 37 4.1 Shadow Prices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 . . 4.2 Pricing Out an Activity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 . 4.3 Changes in the LP Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41. 4.3.1 Change in Objective Coefficient for a Nonbasic Variable . . . . . . . . . . 42 4.3.2 Change in Objective Coefficient for a Basic Variable . . . . . . . . . . . . 43 4.3.3 Change in the Right-Hand-Side of a Non-binding Constraint . . . . . . . 44 4.3.4 Change in the Right-Hand-Side of a Binding Constraint . . . . . . . . . . 45 4.4 The Dual Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46 4.5 Simultaneous Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48. 4.6 Parametric Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55. . . 3
More Less

Related notes for CO 250

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit