26 27 Linear Programming 1 The Problem This subject is a central part of the area is called Operations Research as it developed after the Second World War Its name is a bit peculiar since it is not what we now call programming Rather linear programming involves so certain optimization problems which are called linear programs A linear program represents a problem in which you are asked to find the maximum value of a linear function of certain variables subject to linear constraints on them Here is a simple example Suppose we have two variables x1 and x2 and they obey the following constraints 1 both are non negative 2 the function 3x1 2x2 is at most 4 3 the function x1 x2 is at most 2 And suppose further that we want the maximum value of 3x1 4x2 given these restrictions This is a linear program Here is a standard form for such problems We have n variables xk for k 1 n Each variable is non negative We have m constraints each of the form Aj1x1 Aj2x2 Ajnxn bj We seek the maximum value of an Objective Function of the form v 0 v 1 x 1 v 2 x 2 vn x n This is not the only possible form for a linear program Some of our variables may not have to be non negative A some of our inequalities may actually be equalities These do not make the problem harder in fact it becomes a bit easier when such things exist However we hav introduce notation to account for such variables and constraints and rather than do so we will ignore any such variables for the moment 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 fractional parts of solution values for the variables are uninteresting and can be ignored In other cases they a important and integer or mixed linear programs can be much harder to solve than ordinary linear programs We will begin by considering some examples of problems that give rise to linear programs Then we will discuss some approaches to solving them and some of their curious properties 2 The General Resource Allocation Problem Suppose you are engaged in some sort of a manufacturing process That is you put together various raw materials into objects that you make 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 resour available to you You are then confronted with the problem how much of each possible product should you produce in a given t period This problem in its simplest form is a linear program Let us index your raw materials or resources from 1 to m and your 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 Then with the assumption that you cannot unmake your products 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 yo 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 SUMk 1nAjkxk bj Each resource has a cost associated with it and your finished products have values that you can estimate them Let vk represent the value of a unit of product k above the total cost of the resources that go into its manufacture in oth words the value added by creating it out of its constituent parts Then to maximize the utility of your efforts you want to maximize SUMk 1n vk xk subject to the constraints previously mentioned This is a linear program in standard form In practice there are various complications that we will mention here before continuing but not discuss in detail now 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 fuzziness in all the parameters here that ought to be considered 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 i particular you have to consider the additional constraint that xk must be an integer In many circumstances the optimal xk will be large enough or the integer condition does not exist in which case you can safely ignore this addition constraint If not the problem becomes a different one an integer linear program or if some variables need not be integers a mixed integer linear program Problems of this kind are much more general than ordinary linear programs and we will defer discussion of them until later Third there may be other costs associated with your manufacturing process such as transition costs on your machines in shifting from one product to another which are not included in the model described above but which can affect the optimal policy In any given situation it may well be possible to model such costs but we will not talk further about them here Fixed including overhead rent the costs of setting up your process are easy to model here because they just add a constant to the cost of the enterprise Finally in many cases production is geared to orders on hand or are dictated by priorities other than val added These may or may not be modeled in similar ways Linear Programs arise in many other contexts and there are variations in them from the standard form exhibited in this model In particular some of the variables may take on negative values in a sensible way and some of the constraints may be equalities rather than equalities and the resulting problem is still called an LP or linear program We shall encounter at least one such problem later There are many other practical problems which can under favorable circumstances be modeled as li programs Flows of commodities in networks assignments of jobs to machines are examples of these 3 Basic Properties and Forms for describing a Linear Program In the description of an LP that we start with we have n m hyperplane constraints in an n dimensional space each of which confines solutions to one side of it and we have a linear objective function that we want to maximize subject to these conditions Let us call a 0 dimension intersection of any of these hyperplanes a vertex and a 1 dimensional intersection a line Since