Economics 172A: Introduction to Operations
Research, Winter 2008
Description:
Economics 172A is the first
course in the two-quarter Introduction to Operations Research sequence.
It
covers linear and integer programming, elements of zero-sum, two-person
game
theory, and specific combinatorial algorithms. Linear and integer
programs are
types of mathematical optimization problem. The class will introduce
you to the
problems, teach you how to formulate economic and
business problems as linear or integer programming problems,
teach you how to solve the problems, including some specific methods
called combinatorial
algorithms, and teach you how to interpret the solutions. Zero-sum,
two-person
game theory is the theory of how to make optimal decisions in
situations of
pure conflict, in which the outcome is influenced by another person’s
decision
as well as one’s own, and in which the other person is also trying to
make an
optimal decision. The class will teach you how to formulate situations
of pure
conflict as games and teach you how to use linear programming to solve
for the
optimal decisions.
Instructor: Professor Vincent Crawford, Economics 319 (vcrawfor at
dss.ucsd.edu, 858-534-3452)
Office hours in Economics 319, Wednesday 2:00-3:00, or by appointment
TA: Benjamin Kay (bkay at ucsd.edu), Economics 124, office
hours Mondays and Fridays 9:00-10:00
You should
direct all email
questions about course content to Benjamin Kay (bkay at ucsd.edu). He will try to
respond to you by noon
the following Monday. Please place “Econ 172A” in the subject line of
your message.
Face-to-face contact is the most reliable way to get an answer from me.
Please
do not expect me to respond to your emails regarding course content.
Preparation:You should be
comfortable
with linear algebra, basic microeconomics, and the operation of a
spreadsheet
computer program such as Microsoft Excel. In order to enroll in the
class you
must have the prerequisites listed in the UCSD catalog: ECON 100A or
170A; and
ECON 120A or ECE 109 or MATH 180A or MATH 183 or MATH 186; and MATH
20F. Note
that credit is not allowed for both ECON 172A and MATH 171A.
Organization:
Economics
172A meets from 8:00-9:20 a.m. on Tuesdays and Thursdays, in Center Hall, Room 214. Your grade will be based on
written homeworks (10%); a
midterm
in class Thursday, February 7, the end of the fifth week (35%); and a
final on
Thursday, March 20 from 8:00-11:00 a.m. (55%). Exams will be given only
at the
scheduled times except for compelling
(and fully documented) medical excuses. It is your
responsibility to avoid
conflicts. You may use calculators (but not
other electronic devices) during exams, but you may not consult notes,
books,
or your classmates’ exam papers. I take violations of academic honesty
seriously. Any act of academic dishonesty will be reported to
your
academic dean, and will lead to a failing grade in the course and
possibly
dismissal from the university.
Course Material: Lecture
notes and other course materials are
linked below. I will follow the lecture notes fairly closely. The exams
will cover only material that is discussed in the lectures, lecture
notes, or the problem sets. There are no required texts, but I have
ordered copies of a recommended text, (HL) Hillier and Lieberman: Introduction to Operations Research,
McGraw-Hill, for the bookstore, and more are on reserve in Geisel
Library. This book is a useful supplement, but it is expensive and not
essential. Most of the material is standard and you can find decent
treatments in many other places.
Problem Sets: Problem sets will be announced in
class and
posted below. Some problems will involve using standard spreadsheet
computer programs, such as Microsoft Excel, to solve linear programming
problems. You will need Microsoft Excel (with the “solver” option
installed) to do these assignments. The program is available on the
computers in Econ 100, but there is no need to go there if you have
access elsewhere. The notes contain information about using Excel to
solve linear programming problems. The use of Excel is not discussed in
lectures. I encourage you to discuss your homework assignments with
classmates, but you must write your answers independently. Problem sets
should be turned in by the start of class on the announced dates, or
put in the course mailbox in Econ Student Services by the same time.
Except for documented medical excuses, late problem sets will not be
accepted.
Graded finals
can be picked
up in my office (Economics 319) on March 31, April 1, or April 2.
After that they will be available in the Department Student Services
Office in Sequoyah Hall.
Grading appeals on the final
must be presented to Ben Kay by Friday April 11, 4 p.m. at the latest
(email him to make an appointment).
Computation of final grades: As
announced, your final grade is
based on homeworks (10%), the midterm (35%), and the
final (55%). Homework letter grades were converted to numbers using the
scale A = 80, B = 60, C = 40 and then averaged with the midterm and
final grades to form a course grade from 0 to 100 written on the lower
right conrner of your final exam. These course grades were converted to
letter grades using the following scale (the scale is shifted up a bit
from the approximate midterm scale because on average, people had
higher grades on the homeworks, especially #2, and final than on the
midterm):
0.00-29.99:
F 30.00-44.99: D 45.00-49.99: C- 50.00-54.99: C 55.00-59.99: C+ 60.00-64.99: B- 65.00-69.99: B 70.00-74.99: B+ 75.00-79.99: A- 80.00-89.99: A 90.00-100: A+
2008 Syllabus(pdf) (but
note
that the syllabus does not reflect the latest course information; this
page does)
Correction (with apologies) to answer key for 2008 PS#1 problem
1H:
Question from one of
you (2008):
My question is concerning 1H. When I worked problem one and the
different variations I first did the transformations by hand and then
did them in Excel to double check. When my answer
didn't match up with the answer key's I looked at the excel answer
sheet. I checked the solver and what I don't understand is why
the inequality was not changed in the second constraint. I
remember you emphasized in class that when multiplying a negative
constant in an inequality, the inequality change.
My answer: Your question alerts me to an ambiguity in how 1H was
written. What I had in mind was multiplying everything by -12 but not
changing the sense of the inequality, which does flip the side you are
allowed to be on as in my answer key. (This is what's done on the
Solver answer key too.) In this case they are all unbounded. If instead
you flip the sense of the inequality too, it doesn't change the
constraint at all and the answer is unchanged from 1F. If I were dumb
enough to ask a question this ambiguous on an exam, I would accept
consistent answers of both kind as correct.
Excel
worksheet for Solver parts of 2008 Problem Set #1 (includes
sensitivity reports for Solver parts of problems 1-3, which were not
required in the problem set but which may be helpful to you in figuring
out sensitivity analysis)
Approximate mapping from midterm number (median: 58) to
letter grades (does not yet take homewroks into account):
0-29: D or F
30-49: C-, C, or C+
50-69: B-, B, or B+
70-100: A-, A, or A+
Questions from one of you, and my answers, regarding
sensitivity analysis as in problem 3 on the 2008 midterm:
Q: I have a question on the midterm
solution. In #3, part d), why does the solution change even though the
decrease is in the
allowable range?
A: The "allowable range" in Excel is about changes in the optimal
basis.
The control variable can change even when the optimal basis does not,
e.g. when you change a constraint constant in the primal, normally x*
will change.
Q: Also, in part e), since he can get 15 more for $15, the allowable
increase is 10, the shadow price is 1.875, then it worth him 18
dollars, why is it not benefit for him to pay $15 to get 15 more units?
A: On part (e), the question as written is ambiguous (it was a Hillier
and Lieberman problem bank question, but I should have checked it
better). The question as written is about whether you want to buy (and
use) the whole 15 units. The answer on the answer key is that you can't
tell from the solver printout without resolving the problem, because
the optimal basis changes. (Of course it's plausible in this kind of
problem that the value of the 10th through 15th unit can't be negative,
but you can't tell that from the Solver output.) As you say, in reality
you could buy the 15 units for $15, throw away 5 units, and it would
still be worth it. But as the problem is written, you're not allowed to
do that: you either take and use the whole 15, or not.
I have done my best to make sure that my final exam questions are not
ambiguous, in this or any other way.
2008
Problem
Set #2, due Thursday, March 13 at the start of class (no late
papers) (pdf)
Graded finals can be picked
up in my office (Economics 319) on March 31, April 1, or April 2.
After that they will be available in the Department Student Services
Office in Sequoyah Hall.
Grading appeals on the final
must be presented to Ben Kay by Friday April 11, 4 p.m. at the latest
(email him to make an appointment).
Outline and Readings:
Below is
a schedule of topics and associated readings in Hillier and Lieberman.
(The page references are from the latest edition; other editions do not
differ greatly, and you should have little trouble finding the relevant
reading.) In the column labeled “problems,” the first line gives page
and problem numbers in (HL) Hillier and Liebermann’s book. The class
website has links to some of Professor Sobel’s old problem sets and
examinations (and answers). (I have never taught this class before,
though I have taught the material on game theory and integer
programming in Econ 172B, five or more years ago. There is no material
on my old 172B website that will help you in this class and is not also
on this website. Professor Sobel’s class materials from the Fall 2007
offering of 172A are used with his permission.)
Equation (3);
summation from i = 1 to n
p. 4, line 15 from top: "infeasible" should be "unbounded"
p. 4, line 5 from bottom: "jth"should b "ith"
p. 6, bottom line: "the nutritional requirement for nutrient i"
p. 8, equations (6) and (7): both summations should be from j = 1 to n,
not from i = 1 to m.
p. 10, line 9 from bottom: constraint constant vector b should be p.
HL pp. 1-23, 32–68; Problems p. 92:
3.1-7 to 3.1–10, pp. 95-97: 3.4-7 to 3.4-15
II. Graphical
Solutions(pdf)
HL pp. 28–31; Problems pp.
92-93: 3.1-11 to 3.1-13
Notes
on installing Excel Solver (doc); if you cannot find it, and you
haven't got the disk, try this link;
for Office 2007, the directions are different, and are at this link
p. 6, line 7: "infeasible" should be
"unbounded"
p. 10, line 16: "with one unknown per equation" should be "with the
same number of equations and unknowns"
p. 14, bottom line: "coffin" must refer to a problem set before 2007
p. 17, line 2: delete "not"
HL pp.
209-225; Problems p. 277: 6.1-4 to 6.1-5, 6.1-10, p. 278: 6.3-5 to 6.3-6
p. 12: It is not correct that
"Game-theoretic analysis recommends that
you mix between your first three strategies (there are mixed strategies
that guarantee an expected payoff of zero that use 12 with
positive probability)." The only optimal strategies are those described
in my Supplementary Notes, which mix in the stated proportions between
13 and 23, putting zero probability on 12.
