**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 **

**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.

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.

- The final and answer key are now posted.

- 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+

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

- For additional practice, please see Professor Joel Sobel's problems (and answer keys)

- 2008 Problem Set #1, due Thursday, January 31 at start of class (no late papers) (pdf)

- 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.

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)

- 2008 Midterm exam (pdf)

- Answer key to 2008 midterm exam with corrected graph for problem 2.d (pdf)

- 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+

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.

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).

**Download free Foxit Reader for pdf files**; Read Preston McAfee on why it's better (it is: a lot) and on the also-free PDF Forge Creator to make your own pdf files

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.)

A. Linear Programming

I.
Introduction
and
Problem Formulation (pdf)

Typos:

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.

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.

Supplementary Handout on
problem formulation (pdf)

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

III.
A
Simplex
Algorithm Example (pdf) (extra material, not covered in lectures or
examinations)

IV.
Using
Excel to
Solve Linear Programming Problems (pdf) (extra material, not
covered in lectures or examinations)

V.
Problem
Transformations (pdf) (extra material, not covered in lectures or
examinations)

VI.
Duality
and
Complementary Slackness (pdf)

Typos:

p. 2, line 6 from bottom, "is" should
be "it"

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"

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"

VII. Sensitivity
Analysis (pdf) Examples
(xls)

HL pp. 229–275; Problems pp. 286-289:
6.8-1 to 6.8-7, p. 289-290: cases 6.1 to 6.4

VIII.

Two-Person
Zero-Sum Game Theory (pdf)

Typos:

Typos:

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.

HL pp. 659-675, Problems pp. 675-676: 14.1-1 to 14.1-3, 14.2-1, 14.2-3 to 14.2-6

The
Transportation Problem (pdf)
Examples
(xls)

HL pp. 320–363; Problems pp. 366-367: 8.2-1 to 8.2-3, p. 370: 8.3-1 to 8.3-4

HL pp. 320–363; Problems pp. 366-367: 8.2-1 to 8.2-3, p. 370: 8.3-1 to 8.3-4

Supplementary Handout on the Hungarian Method for the assignment problem (pdf)

Integer Programming (pdf)

Basics and Branch and Bound:

HL pp. 478-527, Problems pp. 535-536: 11.1-1 to 11.1-7, pp. 540-541: 11.6 to 11.6-8

Network Algorithms (time permitting):

HL pp.
374-404, Problems
pp. 428-431: 9.3-1 to 9.3-5,
9.4-1 to 9.4-3, 9.5.3 to 9.5-5

Vincent Crawford

Copyright © Vincent P. Crawford, 2008. All federal and state
copyrights reserved for all original material on this site.