21-257 Exam Information, Fall 1999

21-257 Exam Information
Fall 1999

There will be two midterm exams. The exams are scheduled during the lecture time on Friday, October 1, 1999 and Friday, November 19, 1999. The final exam will be held on Thursday, December 9, 1999 from 5:30-8:30pm in the University Center's McConomy Hall.

Final Exam Information

Material Covered: The exam will cover material from all the lectures plus material from Sections 8.3 and 8.4 and Chapters 1, 3, 4, and 7 (except Sections 3.4, 4.4, and 4.5).
Exam Format: The exam will consist of 10 problems and will be scored from 200 points. The exam is designed to be completed in 2 hours, but you will have 3 hours to complete it. Therefore, time pressure will be less of an issue for this exam. The questions on the exam will be of a similar flavor to the questions on the midterms. However, the final exam will not be limited to questions from the midterms!
Study Guides: The student should use homework problems, examples from class and the old exams as study guides for the final. Note that the final exam will not be limited to questions from the midterms.
Review Sessions: Part of the recitation on Thursday, December 2 and the lecture Friday, December 3 will be dedicated to reviewing for the exam.
What to expect: The problems on the exam will be of the following nature.
- Dynamic Programming approach to the Cargo Problem
- Travelling Salesman Problem
- Setting up and performing one pivot of the transportation problem
- Drawing a network and finding the critical path
- Transportation Formulation
- Project Scheduling Formulation
  - Meeting deadline while minimizing cost
  - Minimizing total project completion time while keeping within a budget
  - Finding the optimal completion time while minimizing the total cost of the project
- Integer Programming Formulation
  - Set-Covering
  - Minimum Batch Size
  - Fixed Cost
  - Piece-wise Linear Functions
  - Cut and Trim
- Knapsack Algorithm (perform one branch and bound and indicate the next branching node)
- Dual Simplex Algorithm
  - Setting up an initial tableau and performing one pivot
  - Adding a Constraint to a LP
  - Finding the optimal solution if a resource is increased
- Branch and Bound Algorithm for solving Integer LP
- Graphical Solution to a 2-dimensional LP
- Simplex Algorithm
  - Introducing slack variables
  - Setting up the tableau and pivoting
  - Identifying basic solutions, identifying when the LP is unbounded, finding non-unique solutions
- 2-Phase simplex algorithm
  - Introducing slack, surplus and artificial variables
  - Finding the artificial objective function
  - Setting up the tableau and pivoting
  - Solving a Minimization LP
  - Identifying basic solutions, identifying when the LP is unbounded or has no feasible solutions, finding the non-unique solutions.
- Dual LPs
  - Finding the dual of a LP
  - Understanding the dual's interpretation in story problems
  - Reading the basic solution of the dual from the simplex tableau.
- Sensitivity Analysis (similar to sensitivity analysis problems from the homeworks and lectures)
- Formulation problems
- Multiple choice section (which may cover some of the items listed above). This section will be similar in nature to the multiple choice portion of the midterm exams. In particular you should be able to identify special situations of the varioius algorithms (such as when the LP in undbounded, has no feasible solution, ...) and you should be familar with the terminology used in the course.

Exam 2 Information

Material Covered: The exam will cover material from Chapter 4 and 7 of the text (except Sections 4.4, 4.5 and 7.7); all lectures from October 4, 1999 to November 17, 1999 (inclusively) and the problems from Homeworks 6 through 11.
Exam Format: The exam will be scored from 100 points. There will be 5 to 6 questions. No notes or books are to be consulted during the exam. No calculators or computers are allowed.
Study Guides: The student should use the homework problems and the examples from the text as study guides.
Review Sessions: Part of lecture on Wednesday, November 17 and recitation on Thursday, November 18 will be dedicated to reviewing for the exam.
What to Expect: The problems on the exam will be of the following nature.
- Setting up and performing one pivot of the transportation problem
- Drawing a network and finding the critical path
- Transportation Formulation
- Project Scheduling Formulation
  - Meeting deadline while minimizing cost
  - Minimizing total project completion time while keeping within a budget
  - Finding the optimal completion time while minimizing the total cost of the project
- Integer Programming Formulation
  - Set-Covering
  - Minimum Batch Size
  - Fixed Cost
  - Piece-wise Linear Functions
  - Cut and Trim
- Knapsack Algorithm (perform one branch and bound and indicate the next branching node)
- Dual Simplex Algorithm
  - Setting up an initial tableau and performing one pivot
  - Adding a Constraint to a LP
  - Finding the optimal solution if a resource is increased
- Branch and Bound Algorithm for solving Integer LP
- Multiple choice section (which may cover some of the items listed above). This section will be similar in nature to the multiple choice portion of the first exam. In particular you should be able to identify special situations of the varioius algorithms (such as when the LP in undbounded, has no feasible solution, ...) and you should be familar with the terminology used in the course.

Grade Distribution:


                                                                          
   X                                                                       
   X                                                                      
   X                                                                       
   X                                                                      
   X                                                                      
   X       X                                                              
   X       X                                                              
   X       X                                                             
   X       X                                                              
   X       X                               X                               
   X       X               X       X       X                                  
   X       X               X       X       X                                  
   X       X               X       X       X                                  
   X       X               X       X       X                                  
   X       X               X       X       X               X                   
   X       X       X       X       X       X               X                   
   X       X       X       X       X       X               X                   
   X       X       X       X       X       X               X                        
   X       X       X       X       X       X       X       X       X                 
   X       X       X       X       X       X       X       X       X        X         
   X       X       X       X       X       X       X       X       X        X        X          
   X       X       X       X       X       X       X       X       X        X        X         
110-100  99-95   94-90   89-84   83-78   77-71   70-65   64-60   59-55    54-50    49-0          
 (21)     (17)    (7)     (12)    (12)    (13)    (4)     (8)     (4)      (3)      (2)

Exam 1 Information

Material Covered: The exam will cover material from Chapters 1 and 3 of the text (except Section 3.4); all lectures from the beginning of the semester to September 29, 1999 (inclusively) and the problems from Homeworks 1 through 5.
Exam Format: The exam will be scored from 100 points. There will be 4 to 5 questions. No notes or books are to be consulted during the exam. No calculators or computers are allowed.
Study Guides: The student should use the homework problems and the examples in the Objective Sections 1.5 and 3.9 from the textbook as study guides. (Objectives 5, 15 and 19 in section 3.9 will not be covered on the exam).
Review Sessions: Part of lecture on Wednesday, September 29 and recitation on Thursday, September 30 will be dedicated to reviewing for the exam.

Grade Distribution:


                                                                          
                                                                          
                                                                          
                                                                          
                   X                                                       
                   X                                                       
                   X               X                                        
                   X               X                                        
                   X       X       X                                        
                   X       X       X                                         
   X               X       X       X                                         
   X               X       X       X       X                                  
   X       X       X       X       X       X                                  
   X       X       X       X       X       X                                  
   X       X       X       X       X       X                                  
   X       X       X       X       X       X                                  
   X       X       X       X       X       X       X                           
   X       X       X       X       X       X       X       X                   
   X       X       X       X       X       X       X       X       X                 X
   X       X       X       X       X       X       X       X       X                 X
   X       X       X       X       X       X       X       X       X                 X
   X       X       X       X       X       X       X       X       X        X        X         
   X       X       X       X       X       X       X       X       X        X        X        X
110-100  99-95   94-90   89-84   83-78   77-71   70-65   64-60   59-55    54-50    49-40    39-0

Return to Optimization Page.
Return to the Syllabus.
Last updated November 23, 1999.