| CODE | SOR1320 | ||||||||
| TITLE | Linear Programming | ||||||||
| UM LEVEL | 01 - Year 1 in Modular Undergraduate Course | ||||||||
| MQF LEVEL | 5 | ||||||||
| ECTS CREDITS | 4 | ||||||||
| DEPARTMENT | Statistics and Operations Research | ||||||||
| DESCRIPTION | - Problem Formulation and Graphical Solution; - Convex and Polyhedral Sets; - Extreme Points and Extreme Directions; - Fundamental Theorems of Linear Programming; - Simplex Method: - Derivation and Matrix Form; - Simplex Table and its Interpretation; - Initial Solution Search Methods; - Sensitivity Analysis. - Duality Theory: - Formulation of Dual Models; - Duality Theorems; - Dual Simplex Methods; - Interpretation of Dual Models. - Network Flow Problems (Transportation, Assignment): - Network Simplex Method. - Conversion Of Nonlinear Programs to Linear Programs - Software Packages. Study-unit Aims: - Define and describe what an LP problem is - from real life examples to the mathematical formulation; - Introduce solution methods, such as: - The Graphical Method - The Simplex Algorithm - accompanying with methods for Sensitivity analysis. The student will be exposed to the theory behind these methods and will learn to use the respective software tools; - Introduce concepts from Duality Theory and the relation between the primal and the dual problems, accompanying with the introduction and description of the Dual Simplex Algorithm; - Apply the above techniques to specific application examples of great interest. Learning outcomes: 1. Knowledge & Understanding By the end of the study-unit the student will be able to: - Convert certain real life problems into an LP formulation; - Solve LP problems and their corresponding dual; - Perform Sensitivity Analysis; - Interpret the results obtained. 2. Skills By the end of the study-unit the student will be able to: - Learn how to solve LP problems graphically; - Learn how to apply the Simplex Algorithm and the Dual Simplex Algorithm; - Use various software packages (Matlab, Lingo) to solve LP problems. Main Text/s and supplementary readings: - Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (2010) Linear Programming and Network Flows, Wiley, 4th ed. - Luenberger, D.G. (2005) Linear and Nonlinear Programming, Springer, 2nd ed. - Williams, H.P. (1999) Model Building in Mathematical Programming, Wiley, 4th ed. - Ahuja, R.K., Magnanti T.L. and Orlin, J.B. (1993) Network Flows: Theory, Algorithms and Applications, Prentice Hall Inc. - Taha, H.A. (2011) Operations Research: An Introduction, Pearson, 9th ed. - Winston,W.I. (2004) Operations Research: Applications and Algorithms, Thomson, 4th ed. Available online - Luenberger, D.G. and Ye, Y. (2016) Linear and Nonlinear Programming, Springer, 4th ed. |
||||||||
| ADDITIONAL NOTES | Pre-requisite Qualification: Advanced Level in Pure Mathematics | ||||||||
| STUDY-UNIT TYPE | Lecture and Practical | ||||||||
| METHOD OF ASSESSMENT |
|
||||||||
| LECTURER/S | Pavel Popela |
||||||||
|
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints. Units not attracting a sufficient number of registrations may be withdrawn without notice. It should be noted that all the information in the description above applies to study-units available during the academic year 2024/5. It may be subject to change in subsequent years. |
|||||||||