Econ 172A - Slides from Lecture 1Joel SobelSeptember 27, 2012Econ 172A SobelWELCOME1. Outlines Distributed.2. Copying Information from Slides is Probably a Waste of TimeEcon 172A SobelINTRODUCTIONSIJoel, 311 Econ, TuTh 2:30–3:20ITAs1. Leland Farmer, 128 Econ, M 2:30–3:302. Erin Giffin, 117 Econ, Tu 5:00–6:00Class email: [email protected] 172A SobelCOURSE MATERIAL1. Book: Expensive, available, old editions OK. Buying itunnecessary.2. Lecture “notes”: Class web page, Soft Reserves.3. Old problems, exams, solutions: Class web page4. Excel’s Solver5. Sections Tuesdays in York Hall 226 from 8-9 PM and from9-10 PM.http://www.econ.ucsd.edu/%7Ejsobel/172f12/172f12home.htmEcon 172A SobelPrerequisites1. Whatever is in the catalog. (Intermediate Micro, Probability,Linear Algebra)2. In fact: Linear Algebra, ability to follow a logical argument,spreadsheet experience.Econ 172A SobelWAIT LISTNot my job.Go to departmental office, Sequoyah Hall 245.Econ 172A SobelGRADING1. 15% quizzes (4 given, best 3 count)2. 35% midterm (November 1)3. 50% final (December 10)Ground rules: No books, no notes, no electronic aids.Curve? Not really.Straight scale? Not really.Econ 172A SobelADMINISTRATIVE1. Wait List? 245 Sequoyah.2. Don’t have access to Excel? Installed on campus machines.3. Google docs spreadsheet also has a solver.4. Don’t have access to campus machines? See me.5. Can’t make the quizzes, midterm, final at scheduled time?One quiz: Drop it. Otherwise: Drop class.6. If you are not sure what cheating is, talk to me.Econ 172A SobelHOW TO STUDY1. Work problems.2. Learn terminology and results from lecture.3. Ask yourself questions.Econ 172A SobelHOW NOT TO STUDY1. “Read” lecture notes and book.2. Review answers to problems prior to working problems.Econ 172A SobelWHAT (I hope) YOU WILL LEARN1. Translate verbal statement to math and back.(Econ/Management)2. Basic Structure of Linear Programming. (Math)3. What is an Algorithm. (Computer Science)4. What solutions look like and how they change when problemchanges. (Math/Econ)Econ 172A SobelTOPICSProblem FormulationGraphDualityComplementary SlacknessSensitivity AnalysisInteger ProgrammingBranch and BoundNetwork AlgorithmsTransportation and Assignment ProblemsEcon 172A SobelWARNING1. Second time slide presentation for UG.2. It did not work well last time.3. This time I plan to post slides but use a lot of chalk inlectures.Econ 172A SobelOPERATIONS RESEARCH1. Originally: research designed to “optimize” militaryoperations.2. Currently: Use of mathematical models to study problemsthat arise in managerial/industrial decision making.3. Aspects:3.1 Pure Mathematics: When do problems have solutions?Characterization? Existence/properties of algorithms.3.2 Computer Science: Design of algorithms. Complexity ofProblems.3.3 Management Science: Domain of applications. Interpretationof Solutions.Econ 172A SobelMATHEMATICAL PROGRAMMING PROBLEMProblem of the form:max f (x) subject to x ∈ S.1. f is called the objective function.2. S is called the feasible set or constraint set.Econ 172A SobelMEANINGmax f (x) subject to x ∈ S.Isolution: Special choice of x, x∗, satisfying1. x∗∈ S. (“x∗is feasible.”)2. If x ∈ S then f (x∗) ≥ f (x). (“x∗is optimal.”)Ivalue: f (x∗).Econ 172A SobelPROPERTIES OF SOLUTIONS1. Solutions: May not exist for two reasons.1.1 S is empty (“problem is not feasible”).1.2 It is possible to make the value f (x) arbitrarily large (“problemis unbounded”).2. Solution may be unique.3. There may be more than one solution.Econ 172A SobelPROPERTIES OF VALUESValues must be unique (if they exist).Econ 172A SobelMINIMIZATION PROBLEMSame theory as max.If you can solve:max f (x) subject to x ∈ S,then you can solvemin g(x) subject to x ∈ SSolve:max −f (x) subject to x ∈ S.This describes the solution(s) to the min problem.Value is multiplied by −1.Econ 172A SobelSPECIAL KINDS OF MATH PROG PROBLEMS1. Linear Programming (f linear function, S defined by linearinequalities)2. Non-linear programming (f arbitrary function, S defined bynon-linear inequalities)3. Integer Programming (Some components of x constrained tobe integers.)Linear Programming – this class. “Discrete” methods.Non-linear Programming – 172B. “Calculus” methods.Integer Programming – this class. Specialized algorithms.Econ 172A SobelLINEAR FUNCTIONf (x) = c · x =nXj=1cjxj= c1x1+ · · · + cnxnHere x = (x1, . . . , xn) are variables. c = (c1, . . . , cn) are constants.Econ 172A SobelLINEAR CONSTRAINTnXj=1aijxj≤ biorAx ≤ bwhere A is technology matrix, with n columns and m rows.b = (b1, . . . , bm).Econ 172A SobelDEFINING PROPERTIES OF LINEAR FUNCTIONS1. Additivity: f (x + y) = f (x) + f (y )2. Constant Returns to Scale: f (ax) = af (x) for any number a.Econ 172A SobelEconomic InterpretationIAdditivity: You can combine independent productionprocesses.IReturns to Scale: Doubling Process Costs Twice as Much.Econ 172A SobelGENERAL FORM OF LINEAR PROGRAMmax c · x subject to Ax ≤ b, x ≥ 0.Ix = (x1, . . . , xn) are the n variables.Ic = (c1, . . . , cn) are the n coefficients of the objectivefunction.IA is a matrix with n columns and m rows.IThe entry in row i and column j is aijIt turns out that any linear programming problem can be written inthis way.Econ 172A SobelJARGONTogether A, b, c are the data of the problem (given constants).Jargon:Ic: coefficients of the objective functionIb: Right hand side constantsIA: technologyIx ≥ 0: nonnegativity constraint.Econ 172A SobelWHEN IS LINEARITY SENSIBLE?1. Typically a good assumption about pricing.(if pjis price per unit of good j; xjis number of units of goodj purchased, thenp · xis how much it costs to buy x.)But: maybe volume discounts; maybe you can’t buy half anapple.2. Linearity is not a good model of utility (when there isdecreasing marginal utility).3. Linearity is not a good assumption when there are decreasingor increasing returns to scale.4. Linearity is not a good assumption when there areindivisibilities (units come in whole numbers).Econ 172A