26. Linear Programming Part I (Background & Theory) 26.1 Introduction to Linear Programming Linear programming is a central part of a field called Operations Research. Developed after the Second World War, its applications range from supply chain management, to air traffic control. In particular, the Sloan School of Business at MIT has the best Operations Research department in the United States. If you decide that this topic interests you, I would encourage you to sign up on the Sloan Lottery and take 15.764, “The Theory of Operations Management.” Linear programming is a bit of a misnomer, since it is not what we commonly consider to be “programming.” Linear programming, in the context of operations research, involves solving certain optimization problems, which are called linear programs. It is also commonly utilized in the fields of applied sciences, finance, and economics. A linear program represents a problem in which you are asked to find the maximum value of a linear function of variables, subject to linear constraints. The following is a simple example of a linear program. Suppose we have two variables x1 and x2, and we wish to maximize the value of the linear function .5x1 + .1x2. Both variables obey the following constraints: 1. Both variables are non-negative 2. The function 3x1 + 2x2 can have a value of at most 4 3. The function x1 + x2 can have a value of at most 2 As explained above we are maximizing a linear function with linear constraints. The linear function we wish to maximize will be called the objective function. Constraints on x1 and x2 could be that x1 < 8 and x2 = 50, and also xi is greater or equal to 0. 26.2 Standard Mathematical Form of a Linear Program Problem. We have n variables {xk} (for k=1 . . . n) The value of each variable is non-negative. We have m constraints, each of the form Aj1x1 + Aj2x2 + . . . + Ajnxn ≤ bj.We seek to find the maximum value of an objective function of the following form v0 + v1x1+ v2 x2 + . . . + vn xn. Besides the form described above, there are a multitude of other forms of linear programs. For instance some of our variables may not have to be non-negative, so they can take on any real value. Some of our inequalities might actually be equalities. Such variations do not make the problem more difficult, in fact it becomes a bit easier for each such occurrence. However we have to introduce notation to describe such variables and constraints. For the moment, we will ignore this and introduce the notation later. When the variables have the additional constraint that each (or some) of the xj must be an integer, the problem is called an integer linear program or a mixed linear program. In some cases the fractional parts of solution values for the variables are uninteresting and can be ignored. Typically when the value sof the solution variables are large, fractions are unimportant. In other cases they are important, and integer or mixed linear programs can be much harder to solve than ordinary linear programs. 26.3 The General Resource Allocation Problem. We begin by considering some examples of problems that give rise to linear programs. In our discussion we will see some approaches to solving linear programs, and some of their curious properties. Suppose you are engaged in some sort of a manufacturing process. That is, you put together various raw materials into objects that you make. The raw materials are called inputs. These raw materials can be bulk items, parts, wrappings, usages of machinery, time needed by those who perform the manufacture, and so on. Suppose further that you have the capability of manufacturing a number of different products using the resources available to you. The classic example of several resources producing different products would be using metal and oil to produce guns and butter. The metal and oil can be used to manufacture either guns or butter or both. The amount of metal and oil needed to create guns is different than the proportion of metal and oil needed to create butter. The amount of guns and butter produced depends on the allocation of metal and oil to either manufactured good. You are then confronted with the problem “how much of each possible product should you produce in a given time period?” This problem, in its simplest form is a linear program.Let us index the raw materials or resources from 1 to m, and the potential products from 1 to n. Let Ajk represent the amount, in appropriate units, of resource j that will be used in producing one unit of product k, and let xk represent the number of units of product k that you might produce. With the assumption that you cannot unmake your products and that you can not have negative amounts of inputs, you have the constraint. xk ≥ 0 for all k. Furthermore, we can assume that you have a limited capacity in any given time period for each of your resources; if the amount of resource j available to you in the period under consideration is bj, you have, for each resource j, the constraint… Σ k=1 n Ajkxk ≤ bj. Each resource has a cost associated with it, and your finished products each have “sale” values that you can estimate for them. Let vk represent the value of a unit of product k beyond the total cost of the resources that go into its manufacture. In other words, vk is the value added by creating it out of its constituent parts. It makes sense that in order to maximize the utility of your efforts, you want to maximize the following. Σ k=1, n vk xk, subject to the constraints previously mentioned. In practice there are various complications that we will mention here before continuing but not discuss in detail until later. First, in real life there are uncertainties both in the valuation of your products and the replacement values of your raw materials, as well as in the functioning of your processes. This means that there is a wide berth of uncertainty in all the parameters here that must be considered in practice. We ignore this for the purpose of simplicity in the course. Second, as stated above, xk represents a potential number of units of product k. When your product k is a discrete item, and a large one in particular, you have to consider the additional constraint that xk must be an integer. In many