Linear Programming Notes I: Introduction and …

1 Linear Programming Notes I: Introduction and Problem Formulation1 Introduction to operations ResearchEconomics 172 is a two quarter sequence in operations research . ManagementScience majors are required to take the course. I do not know what ManagementScience is. Most of you picked the major. I assume that you either know whatit is or do not care. You may not know what operations research is. I amgoing to tell you, but it will leave you research is research into operations . The field began duringthe Second World War. The military needed to solve a lot of different kindsof resource allocation problems.

2 A prototypical problem was a form of thetransportation problem that we ll study later in the course. In this problemthe military had supplies available in several different locations (ammunitionfactories), it had several different locations that needed the supplies (battlefronts), it knew how much it cost to ship supplies from any factory to any knew how much was produced at each factory and how much was needed ineach front. It wanted to figure out how to minimize the cost of shipping thesupplies to the various locations while meeting two types of resource availabilityconstraints (that you do not send more ammunition from a factory than isavailable and that you send as much as necessary to each battle front).

3 Manyother resource allocation problems arose in the planning of military research was a field of study that tried to come up with practicalsolutions to these need to allocate resources even in peacetime. Economics is a disciplinedevoted to the study of methods to allocate scarce resources. It is naturalto study the methods of operations research in an economics class. Someof the methods developed have direct relevance to decision making. Coursesin operations research are therefore traditional parts of undergraduate andgraduate business research as a discipline involves several different things.

4 First,there is the identification of real world situations that lend themselves to for-mulation as mathematical optimization problems. Second, there is a process oftranslating these problems into mathematical language. Third, there is the de-velopment of mathematics that explains the general structure of the mathemat-ical problems that arise in the second stage. Fourth, there is the developmentof methods for solving these operations research sequence introduces some of the basic mathemat-ical techniques for describing and solving problems (steps 3 and 4 above).

5 Itprovides practice in the formulation of problems (steps 1 and 2 above).A mathematical Programming problem is an optimization problem subjectto constraints. In the general problem, you are given a functionfand a are asked to find a solution to the problem:1maxf(x) subject tox S.(1)A Linear Programming problem is a mathematical Programming problem inwhich the functionfis Linear and the setSis described using Linear inequalitiesor equations. It turns out that lots of interesting problems can be described aslinear Programming problems. It turns out that there is an efficient algorithmthat solves Linear Programming problems efficiently and exactly.

6 It turns outthat the solutions to Linear Programming problems provide interesting economicinformation. Economics 172A concentrates on these 172B primarily studies non- Linear Programming . That is, prob-lems in which the functionfis non- Linear and the setSis described usingnon- Linear inequalities or equations. This theory uses calculus the Economics 172 sequence, the word Programming has nothing todo with computer Programming (although it is true that there are computerprograms that can be used to solve mathematical Programming problems). Thisterminology is confusing, but it is Introduction to Linear ProgrammingEconomics 172A studies Linear Programming .

7 So you need to know what a linearfunction is. The functionfofnvariablesx= (x1, .. , xn) is Linear if there areconstantsa1, .. , ansuch thatf(x) =a1x1+..+anxn.(2)This expression is also written:f(x) =n i=1aixi=a x,(3)wherea= (a1, .. , an).Two properties characterize Linear functions: additivity and constant returnsto scale. Additivity means thatf(x+y) =f(x) +f(y). Constant returns toscale means thatf(cx) =cf(x) for any constantc. These properties make sensesometimes. Other times they are silly. Supposef(z) is how much it costs youto buyz. Remember,zhasncomponents, so you can think ofzas a list.

8 Theith entry in the list,zi, tells you the amount of goodithat you are says that if you first buyxand then buyy, it costs the same amountif you boughtx+yat one time. Constant returns to scale says that buyinghalf as much costs half as much and buying twice as much costs twice as that there are no specials ( buy two, get one free ), most of what youbuy at the grocery store satisfies these properties. It certainly describes howyou pay for gasoline at the pump. On the other hand, linearity does not hold in2milk prices: a gallon container costs less than two half gallon containers.

9 Still,one of the most basic Linear functions that we deal with is the one that assignsvalue to lists of goods. Ifpiis the price per unit of goodi, then the linearfunctionf(x) =p xgives the cost of buying the bundle xconsisting ofx1units of good 1,x2units of good 2, and so is usually not a very good assumption for utility functions. Iff(z) represents the utility (loosely, happiness) you get from havingz, then bothadditivity and constant returns to scale are likely to fail. For example, ifxrepresents having a CD player (and nothing else), whileyrepresents having aCD of your favorite music, then presumablyf(x+y)> f(x) +f(y) and also2f(x+y)> f(2(x+y)).

10 The first inequality says that having both the CD playerand the CD is better than the sum of utilities available from having exactly one.(You could argue that having only the CD player or only the CD is worthless.)The second inequality says that having twice the utility from both CD playerand CD is better than having the utility of two CD players and two copies of theCD. (You could argue that the second copy of the disk and the second playeris useless.) In economics it is typical to assume diminishing marginal our context that is just a fancy way of saying that doubling what you havedoes less than double your utility (the second $100,000,000 does not generateas much additional utility as the first $100,000,000.)