LINEAR PROGRAMMING
This is a very useful and powerful technique that is often used by large corporations, not-for-profit organizations, and government agencies to analyze very complex production, commercial, financial, and other activities.
The Meaning and Assumptions of Linear Programming
Linear programming is a mathematical technique for solving constrained maximization and minimization problems when there are many constraints and objective function to be optimized, as well as the constraints faced, are linear i.e. can be represented by straight lines.
Linear programming was developed by Russian mathematician L.V. Kantorovich in 1939 and extended by the American mathematician G. B. Dantzig in 1947. Its acceptance and usefulness have been greatly enhanced by the advent of powerful computers since the technique often requires vast calculations.
The usefulness of linear programming arises because firms and other organizations face many constraints in achieving their goals of profit maximization, cost minimization or other objectives. With only one constraint, the problem| easily be solved with the traditional techniques that in order to maximize output i.e., reach a given isoquant, subject to a given cost constraint (isocost), the firm should produce at the point where the isoquant is tangent to the firm's isocost. Similarly, in order to minimize the cost of producing a given level of output firm seeks the lowest isocost that is tangent to the given isoquant. In the world, however, firms and other organizations often face numerous constraints trying to achieve their objective. For example, in the short run, a firm may not be able to hire more labor with some type of special skill, obtain more than a specified quantity of some raw material, purchase some. advanced equipment, and it may be bound by contractual agreements to supply a minimum quantity of certain products, to keep labor employed for a minimum number of hours, to abide by some pollution regulations, .and so on. To solve such constrained optimization problems, traditional methods break down and linear programming must be used.
Linear programming is based on the assumption that the objective function that the organization seeks to optimize (i.e., maximize or minimize), as well as the constraints that it faces, are linear and can be represented graphically by straight lines. This means that we assume that input and output prices are constant, that we have constant returns to scale, and that production can rake place with limited technologically fixed input combinations. Constant input prices and constant returns to scale mean that average and marginal costs are constant and equal (i.e., they are linear). With constant output prices, the profit per unit is constant, and the profit function that the firm may seek to maximize is linear. Similarly, the total cost function that the firm may seek to minimize is also linear.
Since firms and other organizations often face a number of constraints, and the objective function that they seek to optimize as well as the constraints that they face are often linear over the relevant range of operation, linear programming is applicable and very useful.
Applications of Linear Programming
Linear programming has been applied to a wide variety of constrained optimization problems. Some of these are
1. Optimal process selection.
Most products can be manufactured by using a, number of processes,
each requiring a different technology and combination of inputs. Given input prices and the quantity of the commodity that the firm wants to produce, linear programming can be used to determine the optimal combination of processes needed to produce the desired level and output at the lowest possible cost, subject to the labor, capital, and other constraints, that the firm may face.
2. Optimal product mix.
In the real world, most firms produce a variety of products rather than a single one and must determine how to best utilize their plants, labor, and other inputs to produce the combination or mix of products that maximizes their total profits subject to the constraints they face. For example the production of a particular commodity may lead to the highest profit per unit but may nor utilize all the firm's resources. The unutilized resources can be used to produce another commodity, bur this product mix may not lead to overall profit maximization for the firm as a whole. The product mix that would lead to profit maximization while satisfying all the constraints under which the firm is operating can be determined by linear programming.
3. Satisfying minimum product requirements.
Production often requires that certain minimum product requirements be met at minimum cost. For example, the manager of a college dining hall may be required to prepare meals that satisfy the minimum daily requirements of protein, minerals, and vitamins at a minimum cost. Since different foods contain various proportions of the various nutrients and have different prices, the problem can be very complex. This problem, however, can be solved easily by linear programming by specifying the total cost function that the manager seeks to minimize and the various constraints that he or she must meet or satisfy. The same type of problem is faced by a chicken farmer who wants to minimize the cost of feeding chickens the minimum daily requirements of certain nutrients; a petroleum firm that wants to minimize the cost of producing a gasoline of a particular octane subject to its refining, transportation, marketing, and exploration requirements.
4. Long-run capacity planning.
An important question that firms seek to answer is how much contribution to profit each unit of the various inputs makes. If this exceeds the price that the firm must pay for the input, this is an indication that the firm's total profits would increase by hiring more of the input. On the other hand, if the input is underutilized, this means that some units of the input need not be hired or can be sold to other firms without affecting the firm's output. Thus, determining the marginal contribution shadow price of an input to production and profits can be very useful to the firm in its investment decisions and future profitability.
5. Other specific applications of linear programming.
Linear programming has also been applied to determine
(a) the least-cost route for shipping commodities from plants in different locations to warehouses in other locations, and from there to different markets (the so-called transportation problem)
(b) the best combination of operating schedules, payload, cruising altitude speed, and seating configurations for airlines;
Although these problems are very different in nature, they all basically involve constrained optimization, and they can all be solved and have been solved by linear programming. This clearly points out the great versatility and usefulness of this technique. While linear programming can be very complex and is usually conducted by the use of computers, it is important to understand its basic principles and how to interpret its results.
PROCEDURE USED IN FORMULATING AND SOLVING LINEAR PROGRAMMING PROBLEMS
The most difficult aspect of solving a constrained optimization problem by linear programming is to formulate or state the problem in a linear programming format or framework. The actual solution to the problem is then straightforward.
Simple linear programming problems with only a few variables are easily solved, graphically or algebraically. More complex problems are invariably solved by the use of computers. It is important, however, to know the process by which even the most complex linear programming problems are formulated and solved and how the results are interpreted. To show this, we begin by defining some important terms and then using them to outline the steps to follow in formulating and solving linear programming problems.
The function to be optimized in linear programming is called the objective function. This usually refers to profit maximization or cost minimization. In linear programming problems, constraints are given by inequalities (called inequality constraints). The reason is that the firm can often use up to, but not more than specified quantities of some inputs, or the firm must meet some minimum requirement. In addition, there are non negativity constraints on the solution to indicate that the firm cannot produce a negative output or use a negative quantity of any input. The quantities of each product to produce in order to maximize profits or inputs to use to minimize costs are called decision variables.
The steps followed in solving a linear programming problem are
1. Express the objective function of the problem as an equation and the constraints as
inequalities.
2. Graph the inequality constraints, and define the feasible region
3. Graph the objective function as a series of isoprofit (i.e. equal profit) or isocost lines, one for
each level of profit or costs, respectively.
4.. Find the optimal solution (i.e., the values of the decision variables) at the extreme point or
corner of the-feasible region that touches the highest isoprofit line or the lowest isocost line. This represents the optimal solution to the problem subject to the constraints faced.
