UCSD Department of Economics

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.

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+

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.
0-29: D or F
30-49: C-, C, or C+
50-69: B-, B, or B+
70-100: A-, A, or A+
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.

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)

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.

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

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

Sample Spreadsheets: Template (pdf); Solution (pdf); Sensitivity (pdf); Template in Excel Format (xls)

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

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

VI.     Duality and Complementary Slackness (pdf)


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"

                        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

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


B.    Two-Person Zero-Sum Game Theory   

Two-Person Zero-Sum Game Theory (pdf)

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.

Supplementary Handout on Zero-Sum Games (pdf)

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

C.     Integer Programming

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

Supplementary Handout on Integer Programming (pdf)

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
/ UCSD Department of Economics / last modified 28 March 2008

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