Optimization Methods for Decision Science

Welcome to MATH S373. Please read this Course Guide before reading any of the other materials that you have received — it gives you an idea of what the course is about and includes essential information on when and how to use the other materials that make up the course.

We hope you enjoy your study of MATH S373.

An optimization problem is one in which the optimum (i.e. maximum or minimum) value of something is sought. The 'something' can usually be modelled as a function of one or more variables, often subject to one or more constraints on the values that the variables can take. The solution consists not only of the optimum value of the function but also the values of the variables that correspond to the optimum value.

This course deals with how optimization problems arise and with the analytic and numerical techniques that are used to find solutions. Although optimization method is a practical subject, it is supported by an ever-increasing body of mathematical theory. Optimization problems arise in science, technology, business, economics, management, decision science and many other fields. Finding a solution usually involves the following main stages.

1. Modelling
   Formulating the problem in mathematical terms (i.e. as a mathematical model).

2. Devising a method of solution
   Finding an efficient way to obtain a numerical solution of the mathe­matical model to an acceptable level of accuracy.

3. Collecting data
   Making observations of the numerical quantities (i.e. data) relevant to the solution of the problem.

4. Computing a solution
   Calculating a solution to the problem, usually with the aid of a computer or calculator.

5. Assessing accuracy
   Assessing the probable accuracy of the computed solution, where possible by estimating error bounds for the solution and by analysing the sensitivity of the solution to small changes in the data.

6. Checking the solution
   Comparing the computed solution with the original problem and checking that the calculated results are reasonable.

7. Decision making
   In the course, we shall analyse in some detail the numerical methods used to solve optimization problems. While such methods form only a small subset of the numerical methods that are used in practice, many of the underlying principles of the methods we consider are common to all numerical methods.

In the first block of the course we look at the solution of problems that can be modelled by a single equation or by a system of equations. In the following two blocks we concentrate on methods for numerical optimization — finding the optimal solution to a problem, subject to a variety of constraints — a topic that plays a major role in a branch of applied mathematics known as operational (or operations) research.

A higher-level course builds on study skills and subject knowledge acquired from studies at Levels 1 and 2. Learners are expected to have some knowledge of the following before studying MATH S373:

• Calculus concepts of differentiation and integration; ability to differentiate and integrate a variety of functions; Taylor's theorem; partial derivatives; understanding of continuity and convergence
• Matrices ability to manipulate equations with matrices and vectors; system of equations; Gaussian elimination; eigenvalues and eigenvectors.

Students could get the above background from M221 Mathematical Methods or M215 Linear Algebra. The important prerequisite mathematical theory and formulas are summarized in the MATH S373 Handbook. Students are more likely to successfully complete this course if they have acquired their recommended advisory knowledge.

Apart from this course guide, the course consists of the following items:

• 13 printed course units
• one computing booklet;
• one computing package CD-ROM;
• one computer software (Mathcad 15);
• one course handbook.

These are described below. The assessment for the course is described in Section 6. The course makes extensive use of computing resources. You will also need a computer and a scientific calculator.

5.1 Study units

The thirteen units in the course are divided into three blocks of five, four and four units.

Block I

• Unit I.1  Introduction to iterative methods
• Unit I.2  Systems of linear equations
• Unit I.3  Ill-conditioning and induced instability
• Unit I.4  Systems of non-linear equations
• Unit I.5  Mathematical modelling

Block II

• Unit II.1 Linear programming — the basic ideas
• Unit II.2 Linear programming — the two-phase simplex method
• Unit II.3 Integer programming
• Unit II.4 Applications of linear and integer programming

Block III

• Unit III.1 Minimizing a function of one or two variables
• Unit III.2 Unconstrained non-linear optimization
• Unit III.3 Constrained non-linear optimization
• Unit III.4 Optimization problem-solving

[The study outline of each unit is shown in Appendix A.]

Each unit represents approximately 18–20 hours of study, up to a quarter of which may be spent working at your computer. Each block is scheduled to be studied over a ten to twelve weeks period.

At the beginning of each unit you will find a study guide. This lists the prerequisites for the unit (from earlier units and/or other courses) and also helps you to plan your study by giving you an idea of the relative importance of the different sections of the unit, whether any sections are expected to be very time-consuming compared with the others, and when you will need to use your computer.

At the end of the main text of each unit you will find a list of outcomes, which tells you what we expect you to have achieved after studying the unit. You should always check this list on completion of a unit to ensure that you understand all the key concepts and have mastered the required techniques before going on to the next unit. You may also find these lists of outcomes useful when planning your revision.

In each unit you will find four types of problems:

Examples in Units

These are problems that are solved as part of the main text. Their aim, generally, is to illustrate a particular technique or method.

Exercises in Units

These are designed to give you a chance to practise what the preceding text has taught and/or to extend the ideas taught in the text. You should tackle all the exercises as you reach them in your study of the text, and make a real attempt to solve them before you turn to the solutions, which are printed at the back of each unit.

It is often said that mathematics is something that must be learnt by practice. There is probably no branch of the subject that it is truer than numerical optimization, for it is almost as much a craft as a science. It relies heavily on experience and intuition, qualities which need to be acquired gradually by practice in solving problems. Having said this, you should not exhaust yourself struggling with any individual exercise; make a reasonable attempt and then read the solution. Whether or not you complete an exercise, you should always read its solution, since the printed solutions often contain important ideas that may not be repeated elsewhere.

You may use the computer for the calculations in any exercise, but you are advised to get into the habit of using your calculator too. Since you will not be able to take the computer into the examination, it is important to build up speed and confidence with your calculator. Also, working out a key sequence for your calculator can deepen your understanding of a method in a way that use of the computer may not.

End-of-section exercises in Units

The end-of-section exercises are usually rather longer and more comprehensive than the ordinary exercises. You can either work through them as you reach them, or use them as revision problems later. Otherwise, what was said above for ordinary exercises applies.

Computer activities in Units

These appear grouped at the end of appropriate sections of each unit, and are signposted by an icon in the margin. Each group often contains activities associated with more than one section. These activities make use of the Mathcad worksheets provided as part of the software for this course. The software includes comments on the computer activities; solutions are not included in the course units.

Working through the computer activities is as essential a part of your study as working through the other exercises. While hand calculations give you useful practice, problems that can be solved by hand are necessarily small and usually artificial. To get a feel for the solution of real-world problems, you need to use a computer.

In addition to the computer activities, some units require you to work through a multimedia package on your computer. These are also signposted by the same icon in the margin.

5.2 Computing booklet

This booklet introduces the MATH S373 software, tells you how to load and run it on your computer, and gives you details of how to use the multimedia packages and Mathcad worksheets. You should work through the booklet before you start to study the course. However, if you have not worked with Mathcad or multimedia packages before, working through the Computing Booklet may take some time, and you should allow for this in your study plan.

5.3 Computer software

The software for this course is supplied to you on CD-ROMs. It consists of multimedia packages, the Mathcad 15 computer algebra package and MATH S373 Mathcad worksheets. The use of these packages and worksheets is described in more detail in the Computing Booklet.

In order to use Mathcad 15 in your home computer, you need an appropriate license file for installation. HKMU will send you an individual 'Mathcad Product Code' via your HKMU email. Please check your email for it. The Product Code is a 22-character string of letters and numbers required to install Mathcad. Each student will have a different Product Code. The installation procedure can be found in the Computing Booklet.

The multimedia packages each relate to a particular unit and are to be used as part of your study of that unit. You will be given advice about when to study each multimedia package in the corresponding unit.

The Mathcad worksheets are for use with the computer activities and some of the continuous assessment questions. They are designed to be as self-explanatory as possible. As well as using the worksheets for the computer activities, you can also use them to check your calculations for the exercises and assessment questions. However, remember what we said above about practising the use of your calculator.

You do not need any knowledge of computer programming or of other computer packages in order to use the MATH S373 software, but previous experience of using Mathcad would be useful. If you have not used Mathcad before, you should work your way through the Mathcad tutorial worksheets, as described in the Computing Booklet, before starting the course.

5.4 Course Handbook and its regulation

In the first part of the Handbook you will find the prerequisite mathematical theory and notation, together with references to the Open University courses where further details can be found. You should quickly glance through this part of the Handbook before you start the course, and perhaps look up the relevant units of other courses if there are topics that you feel you need to revise. You may expect to refer back to this part of the Handbook when mathematical theory from other courses is required in your study of this course.

The second part consists of unit-by-unit summaries of the main concepts, definitions, notation, methods and techniques in the course. There is also an index at the back of the Handbook.

Please read carefully the handbook regulation as given below:

Important: You must not write notes in your Handbook during your study. You should always keep your handbook clean and tidy. Any written notes found in your Handbook will be treated as misconduct in the examination.

5.5 Stop presses

The stop presses for the course contain important information regarding various aspects of the course. They will include corrections to the course materials, advice relating to computing, advice on whom to contact in case of difficulties, details of any changes to the assessment of the course, and the recommended reading list. It is important that you read the stop presses as soon as you receive them.

Any additional errata or course news will only be sent to you via the course website. It is therefore important that you check the OLE regularly.

The grade awarded at the end of the course is determined by the following two components:

6.1 Assignment

The assignment booklets contain information about which units are covered and when you should submit them.

1. Assignments consist of four to five long questions. Your answers should be sent directly to your tutor for marking. Your tutor will use your answers as a basis for teaching points, as well as award you a grade for your work.

2. You will be awarded a score for each assignment. The best three assignment scores will be counted towards your final continuous assessment score.

For those assignment questions that require the use of the computer, you should submit annotated printout from your computer to accompany your answer. The computing printout should supplement and not replace your answer to the question, and the annotation should highlight the key results you use in your answer. The printout should also include the worksheet pages where you input the data for the problem, so that your tutor can check whether you entered the data correctly. Please do not submit more printout than is necessary to support your answer; your tutor will not be pleased to receive too many unnecessary printouts.

The coverage and the allocation of each assignment are shown in the following table

About 20–30% of loading is assigned to the course computing activities in each assignment.

6.2 Examination

The other aspect of assessment is the three-hour examination at the end of the course, which is based on the whole course.

The format of the examination is shown in the Specimen Examination Paper, which will be sent to you near to the final examination. You may also download it from the MATH S373 OLE. A set of model solutions to the questions of the Specimen Examination Paper will also be provided.

In order to study this course you must have access, preferably at home, to a multimedia computer that meets the Open University specification. Details of whom to contact in case you have difficulties in using your computer or if you have enquiries about the suitability of a particular machine will be given in one of the stop presses for the course.

Computer use forms an integral part of each unit and of the continuous assessment questions. You will usually need access to it once or twice per unit, and you should plan your work accordingly. When working through the Mathcad worksheets you will frequently need to save your worksheets.

The software is described in Section 5 above and in the Computing Booklet. Before you attempt to load and use the software, it will help to read through this booklet.

Note that the course does not aim to teach you programming or computer science -- the computer is used as a tool to perform calculations and as a teaching aid. In particular, note that you will not be expected to write any programs as part of this course.

7.1 Computer minimum specification

In order to study the course you need to have a computer with a DVD drive that meets the minimum specification, which is as follows:

• A computer with English Windows XP or Windows 7.
• A speed of 66 MHs (any slower may seriously delay the running of the software).
• At least 16 MB of memory (RAM).
• At least 120 MB free hard disk space.
• A DVD drive (to run the computing exercises and watch the video programmes).
• A sound card.
• A display resolution of 800x600. (A lower resolution will mean that you will not be able to see about one third of the screens in the multimedia packages.)
• A printer (optional).

You will need a scientific calculator for use in the exercises in the units, for the assignments and in the examination. You should practise using your calculator as often as possible, in order to develop confidence, speed and efficiency.

According to OUHK policy, all students are required to use an approved scientific calculator in the examination. The list of approved calculator models can be found in Appendix C.

8.1 Accuracy of calculations

Most of the calculations in the examples and solutions in this course have been made using full calculator or computer accuracy. However, in the text we have generally adopted the convention of only displaying the recorded results to six decimal places. When you perform your own calculations, you are advised to store and carry forward all results as accurately as possible, but to save yourself time by only recording results to as many figures as you think are needed. You will get a feel for this as your study of the course progresses.

With the first mailing, you will receive an Academic Timetable to help you plan your study. This timetable indicates all the important dates, including cut-off dates for assignments and the dates of tutorials, among other things. In addition, to help you plan your study time, each unit is divided into five to six sections. Each unit requires about 18 to 20 hours study time.

You will receive STOP PRESSES and ERRATA bringing you last-minute news of errors and changes to the course material. You should always read these immediately when you receive them.

9.1 Tutorials

You should refer to the Academic Timetable about tutorial arrangements and the schedule. You should note that none of the tutorials is compulsory.

9.2 Surgeries

Throughout the presentation, a number of surgeries will be provided to assist your study. You should refer to the later Stop Presses for details on the arrangements for the surgeries schedule.

9.3 Keep up to the academic schedule

It is important to keep as close to the study schedule laid down in the Academic Timetable as you can (of course there is no harm in being ahead of it, but few students are in the fortunate position of being able to keep that up for any length of time). The main reason for keeping up to schedule is that you will lose marks if you miss any question in the assignments. For any of the assignments, the cut-off date comes very soon after the end of the study week for the last of the relevant units. We recommend that you finish the assignment questions for each unit as soon as you finish the unit, otherwise you will have a lot of work to do in a few days before the cut-off date.

If you have not done all the work in time for an assignment, you should still submit as much of the assignment as you can do, and start the new unit on time. As a matter of survival, it is more important to start each unit on time than to do every assignment question.

If it becomes apparent during your study that you will not have enough time to do all the work in it, you will have to make some decisions about which parts of which units to leave out. Such omissions will, in general, cause you to lose marks in your assignment but this is better than getting hopelessly behind and dropping out.

9.4 Cut-off date for Assignments

The cut-off date means the deadline for the submission of the assignment; that is, the date by which your tutor must receive your assignment. The cut-off date is very important. In the case of assignments they represent the last date on which your tutor may accept your work for marking, unless he or she feels there are exceptional reasons why you should be allowed to submit the work late.

It is best to do each question immediately after working through the associated material.

9.5 Apply for late assignments submission

If you find that your study has fallen behind the study schedule and you wish to apply for late submission, you should apply for your late submission extension through the OLE system. The details of the OLE extension system can be found in the OLE User Guide.

9.6 MATH S373 Online Learning Environment (OLE)

MATH S373 is supported by an online platform called the Online Learning Environment (OLE). The OLE is an interactive online learning system (Internet system) developed by HKMU. Through the OLE, you can communicate and interact with other students, your tutor and the Course Coordinator and this would help to enhance your learning experience. To help you to use the OLE system, HKMU will provide you with the OLE User Guide if you are a new student. Otherwise, please access the online version — http://ole.hkmu.edu.hk/help.html. You should read the guide if you are unfamiliar with the OLE system.

9.7 Assignment Submission and Extension

MATH S373 OLE includes the following sub-components for the assignment component:

• Assignment File -- All assignment questions will be posted on the OLE.
• Assignment Submission and Extension -- This component allows you to:
  • Check the status of your assignments
  • Submit your assignments
  • Check your assignment scores
  • Apply for an extension for late submission

9.8 Discussion Board

The OLE has a Discussion Board which allows you to post your problems that you would like to discuss with other students and tutors. In addition, you can access the University's email system through the OLE. Using it, you can send emails to students, tutors and your Course Coordinator, and receive emails from them.

Other details on how to use this component are given in the OLE User Guide. Your first tutorial will demonstrate how you can use the OLE system.

10.1 From your tutor

Your tutor is there to help you understand the ideas in the course, and the best way for him or her to do this is through the comments written on your assignment scripts. When your assignment is returned, go through the script and take note of the comments written by your tutor; they will help you avoid similar errors in later assignments and in the examination. Try to attend tutorials and surgeries because there you will have the opportunity to talk to your tutor directly and, just as important, to talk to other students.

10.2 From your fellow students

One of the best ways of learning is by talking about your work with fellow students. Unfortunately, you will see them only at the infrequent tutorials during the year. That leaves a lot of weeks when you could be on your own. Make sure then that you have the email addresses and telephone numbers of other students in your course; that way, you can stay in touch all the time. You might even like to form your own self-help group to meet regularly; this is often a good way of getting people to discuss common difficulties, especially in the assessment questions.

10.3 From the Course Coordinator

If there are any academic queries that your tutor cannot handle, then your tutor will probably advise you to contact the Course Coordinator. The Course Coordinator of this course:

Dr. Tony Chan,
Room D1157, HKMU Homantin Jockey Club Campus
Office telephone is 3120 2612
Email: tmtchan@ouhk.edu.hk

10.4 From Online Learning Environment (OLE)

The OLE provides you with an interactive learning environment for communication among students, tutors and the Course Coordinator. When you find problems that you would like to discuss with other students, you are welcome to post your problem on the OLE Discussion Board. Details of how to use the OLE component can be found in the OLE User Guide.

• Discussion board: All students and tutors can access the Discussion Board. Problems and queries can be posted for anyone to offer help. Often you can find that the answer to your problem has already been supplied to another student with a similar problem.
• Email: Each student and tutor has an email account for direct communication. Most of the news and comments from the Course Coordinator will be sent to you through this email system.

1. First of all, read any stop presses you have received, in case they contain urgent information or corrections.
2. Check quickly through the first part of the Handbook to see if you need to do any revision before you start the course.
3. Install the course software and work through the Computing Booklet exercises to become familiar with using the Math-cad worksheets and multimedia packages. (If you have not used Math-cad before, you may need to allow several hours for working through the Mathcad tutorial worksheets associated with the Computing Booklet.)
4. You are now ready to study Unit 1.1.

(Some sections of the Course Guide are adapted from MATH S373 Optimization produced by OUUK)

The course was produced by the following team of the OUUK:

(In addition to the following models, calculators bearing the “HKEA/HKEAA Approved” labels are also allowed.)

A.MAX

ATABA/AURORA

BISTEC

BLT

CANON

CASIO

CITIZEN

HEWLETT‑PACKARD

KARCE

SHARP

TEXAS INSTRUMENTS

TRULY

[End of calculator list]