| Course Title | Basic Optimization | ||
| Course Code | MH3701 | ||
| Offered | Study Year 3, Semester 2 | ||
| Course Coordinator | Yan Zhenzhen (Asst Prof) | yanzz@ntu.edu.sg | 6513 7466 |
| Pre-requisites | MH1201 OR MH2800 OR MH2802 | ||
| AU | 4 | ||
| Contact hours | Lectures: 39, Tutorials: 12, Laboratories: 8 | ||
| Approved for delivery from | AY 2022/23 semester 2 | ||
| Last revised | 3 Nov 2022, 11:00 | ||
This is a first course in mathematical optimization. It builds the basic knowledge and skills in the theory and techniques of analysing and solving simple optimization models. With these foundations, you will be able to deepen your understanding of more complex optimization models, and their applications to various disciplines in subsequent mathematical optimization and operations research courses.
Upon successfully completing this course, you should be able to:
Geometric simplex method
Algebraic simplex method in tabular form
Implementing the simplex method
Revised simplex method
Fundamental Theorem of the network simplex method
The network simplex method
Linear programming duality
Sensitivity and post-optimality analysis
Lagrange duality and the Karush-Kuhn-Tucker conditions
| Component | Course ILOs tested | SPMS-MAS Graduate Attributes tested | Weighting | Team / Individual | Assessment Rubrics |
|---|---|---|---|---|---|
| Continuous Assessment | |||||
| Laboratories | |||||
| Multiple Choice Questions | 1, 2, 6 | 1. a, c, d 2. a | 5 | individual | See Appendix for rubric |
| Technology-enhanced Learning | |||||
| Multiple Choice Questions | 1, 2, 5, 6 | 1. a, c | 20 | individual | See Appendix for rubric |
| Mid-semester Quiz | |||||
| Short Answer Questions | 1, 2, 3, 4, 5, 6, 7 | 1. a, b, c 2. b 3. a 4. a | 25 | individual | See Appendix for rubric |
| Examination (2 hours) | |||||
| Short Answer Questions | 1, 2, 3, 4, 5, 6, 7 | 1. a, b, c 2. b 3. a 4. a | 50 | individual | See Appendix for rubric |
| Total | 100% | ||||
These are the relevant SPMS-MAS Graduate Attributes.
1. Competence
a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems
b. Formulate mathematical statements precisely using rigorous mathematical language
c. Discover patterns by abstraction from examples
d. Use computer technology to solve problems, and to communicate mathematical ideas
2. Creativity
a. Critically assess the applicability of mathematical tools in the workplace
b. Build on the connection between subfields of mathematics to tackle new problems
3. Communication
a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience
4. Civic-mindedness
a. Develop and communicate mathematical ideas and concepts relevant in everyday life for the benefits of society
1. Online quizzes:
Your performance in an online quiz will be immediately given upon submission of your answers. The feedback includes your performance on each question, possible misconceptions that may lead you to wrong answers, and how the question can be answered.
2. In-class test:
Comments on your answers to the questions will be written on your test scripts and returned to you upon grading.
| Lectures (39 hours) | You will learn algorithms to solve linear programs and understand the rationality of the algorithms in lectures. You will also learn the duality theory of linear programs and understand how to analyze the sensitivity of each component of a linear program during the lecture. |
| Tutorials (12 hours) | You will participate in problem-solving tutorial sessions, where problems are designed based on the theories and solution techniques covered in the lecture. |
| Laboratories (8 hours) | You will learn how to model real-world optimization problems as linear programs, and solve instances of these models in the lab sessions. The optimization problem will be introduced and the linear programming model explained at the beginning of the lab session. You will then have hands-on experience in extracting the problem data from a randomly selected problem to build a linear programming model, and solve it using a solver of your choice. |
1. Frederick S. Hillier and Gerald J. Lieberman, “Introduction to Operations Research”, McGraw-Hill, ISBN 0073376299
2. Robert J. Vanderbei, “Linear Programming: Foundations and Extensions”, Springer, ISBN 1461476291
(1) General
You are expected to attend all lectures, tutorials, and lab classes punctually, and complete all scheduled lab assignments, online quizzes, and in-class tests by due dates. You are expected to take responsibility to follow up with course notes, quizzes, lab assignments, and course related announcements for assessments you have missed. You are expected to participate in all tutorial discussions and activities.
(2) Absenteeism
A missed test will be given a mark of zero, unless prior permission is given by the course coordinator, or a leave of absence is approved by the School. If you miss an in-class test, you must inform the course coordinator via email (yanzz@ntu.edu.sg) within 2 working days of the test.
(3) Online Compulsory Lab Assignments and Quizzes
You are required to complete online compulsory lab assignments and quizzes on due dates. You have unlimited attempts. The highest score will be considered in the course assessment.
Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.
As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.
| Instructor | Office Location | Phone | |
|---|---|---|---|
| Yan Zhenzhen (Asst Prof) | SPMS-MAS-05-19 | 6513 7466 | yanzz@ntu.edu.sg |
| Week | Topic | Course ILO | Readings/ Activities |
|---|---|---|---|
| 1 | Geometric simplex method | 1 | Lecture notes Chapter 1 |
| 2 | Geometric simplex method | 1 | Lecture notes Chapter 2 |
| 3 | Algebraic simplex method in tabular form | 1, 2 | Lecture notes Chapter 2 |
| 4 | Algebraic simplex method in tabular form | 1, 2 | Lecture notes Chapter 2 |
| 5 | Implementing the simplex method | 1 | Lecture notes Chapter 3 |
| 6 | Revised simplex method | 1 | Lecture notes Chapter 3 |
| 7 | Fundamental Theorem of the network simplex method | 3, 4 | Lecture notes Chapter 4 |
| 8 | The network simplex method | 3 | Lecture notes Chapter 4, test |
| 9 | Linear programming duality | 5 | Lecture notes Chapter 6 |
| 10 | Linear programming duality | 5 | Lecture notes Chapter 6 |
| 11 | Sensitivity and post-optimality analysis | 6 | Lecture notes Chapter 7 |
| 12 | Lagrange duality and the Karush-Kuhn-Tucker conditions | 7 | Lecture notes Chapter 8 |
| 13 | Lagrange duality and the Karush-Kuhn-Tucker conditions | 7 | Lecture notes Chapter 8 |