CS 471-3
Introduction to Optimization Techniques
Catalog Description
(Same as Mathematics 471) Nature of optimization problems. General and special purpose methods of optimization, such as linear programming, classical optimization, separable programming, integer programming, and dynamic programming.
Prerequisite:
Mathematics 221 and 250.
Objectives
This course is meant to investigate basic methods of optimization which are used in industry and government. The topics are meant to be introductory so that one could build mathematical models and then develop simple computer code to solve the models.
Course Outline
| Lectures | ||
| 1. | Dynamic Programming
Stages, states and decision variables Examples Review of Homework |
12 |
| 2. | Introduction to Linear Programming
Standard Model Graphical Solution Simplex Method Big M Method Unboundedness, inconsistency, shawdow priceslower bounds for finding minimum and sorting, lower bound arguments. |
6 |
| 3. | Graphs and the Transportation Model
The Transportation Model Rooted Spanninf Tree Noide Potentials Pivoting Assignment Problem Transshipment Problemmergesort, quicksort, median selection, polynomial algorithms, matrix algorithms. |
6 |
| 4. | Integer Programming
Why not LP? Formulations with binary variables Branch and Bound Binary Integer Programming Dual Simplex Method Mixed Integer Programming |
7 |
| 5. | Game Theory
Introduction Solving Simple Games Games with Mixed Strategies Graphical Solution Procedure Solving by Linear Programming |
5 |
| 6. | Network Analysis
Shortest Route Problem Minimal Spanning |
4 |
| Total | 40 | |