Skip to main content
main-content

Über dieses Buch

A tried and true manual for students and scholars of economists to understand linear programming.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction to Linear Programming

Abstract
This book discusses economics in an “operational way.” It deals with that part of microeconomics that can be reasonably formulated using linear relationships. Prominent among the various scenarios is the behavior of an economic agent who is a “price taker.” This expression refers to an economic agent who cannot influence market prices but, on the contrary, must accept market prices as given. As a first approximation, we assume that entry and exit into the competitive market is costless. An economic agent who is a price taker is assumed to make economic decisions that would maximize his profit subject to technological and environmental constraints. The technological constraints may be given by his level of know-how about production processes. Environmental constraints may be represented by his perceived market opportunities and risk preference.
Quirino Paris

Chapter 2. Primal and Dual LP Problems

Abstract
The notion of duality plays a very important role in linear programming. Indeed, it also plays a crucial role in nonlinear programming, economics, engineering, physics, and statistics. It is possible to assert that every problem has a primal and a dual specification.
Quirino Paris

Chapter 3. Setting Up LP Problems

Abstract
Linear programming problems are like any others: they require first a careful and complete description. Then the procedure of setting up a problem within a framework suitable for linear programming is principally a matter of common sense and simple logic. No theory of setting up linear programming problems exists. One must begin by studying a few examples, trying to grasp their essential features and then attempt to adapt these features to new problems. Although much of this book’s interest rests with the ability to solve linear programming problems and to analyze the corresponding results from an economic viewpoint, one can hardly achieve these goals without the ability to set up the problems properly.
Quirino Paris

Chapter 4. The Transportation and Transshipment Problems

Abstract
To further motivate the structure and the economic interpretation of a linear programming model, we will now discuss a transportation problem. Together with the minimum-cost diet problem of Stigler, the transportation problem was among the first formulations of linear programming problems. The Russian L. V. Kantorovich formulated the first specification of the problem in 1939, but his work became known in the West about a decade later. In 1941, Frank L. Hitchcock wrote a paper in the Journal of Mathematics and Physics whose title seems more fit for a journal of economics: “The Distribution of a Product from Several Sources to Numerous Localities.” In that paper he also gave the correct solution of a numerical example by means of an algorithm, which is probably the first solution method for a linear programming problem.
Quirino Paris

Chapter 5. Spaces, Cones, Bases and Extreme Points

Abstract
In previous chapters we learned how to set up LP problems, their economic interpretation and the proper relations between their primal and dual specifications. In this chapter we will examine more closely the geometric and algebraic structure of a linear programming model. For ease of exposition and graphing, we will discuss a very simplified linear programming problem with only two outputs and two inputs because we want to graph it in two-dimensional diagrams. Every notion and result presented here, however, can be extended to more complex LP formulations with many hundreds and even thousands of outputs and inputs.
Quirino Paris

Chapter 6. Solving Systems of Equations

Abstract
The information about linear programming problems developed up to this point has revealed the need to know an efficient method for solving systems of linear equations. In fact, the main results achieved in previous chapters can be summarized as follows:
1.
Optimal solutions occur always at an extreme point of the primal feasible region, as illustrated in the output space diagram of figure 5.1.
 
2.
To each extreme point in the output space there corresponds a feasible basis (a cone that contains the RHS vector b) in the input space, as in figure 5.2.
 
3.
To solve a linear programming problem, therefore, it is sufficient to explore only extreme points that, in an output space diagram similar to figure 5.1, can be identified only in qualitative terms.
 
4.
An extreme point of the primal feasible solution region is associated with a basic system of equations (see section 5.4) whose solution provides a basic feasible solution in quantitative terms. In the intuitive jargon developed previously, a basic system of linear equations is composed of three parts: an object to be measured, a ruler for measuring the object, and the measurement of the object.
 
5.
As a consequence, we will discuss a solution procedure for linear programming problems called the simplex method, which is organized around a process of solving a sequence of systems of linear equations. A member of this sequence is called an iteration.
 
Quirino Paris

Chapter 7. Primal Simplex Algorithm: The Price-Taking Firm

Abstract
Since 1947, the discovery year of the simplex method, several different approaches have been proposed for solving linear programming problems. Surprisingly, the first method still seems to be the best procedure. The simplex method is “best” in the sense that it is a very efficient procedure for solving a large class of empirical LP problems and, furthermore, every single step can be given an economic interpretation.
Quirino Paris

Chapter 8. The Dual Simplex Algorithm

Abstract
In chapter 7 we studied the primal simplex algorithm which, for several years after its discovery, was regarded as a procedure to find a LP solution working on the primal problem. Analogously, a procedure that solves a dual linear programming problem may be called a dual simplex algorithm. This algorithm was discovered by C. E. Lemke in 1954, seven years after the primal simplex procedure. It is fair to say that without the dual simplex algorithm modern computer codes could not be as reliable as they are. At present, any respectable computer program based on the simplex method incorporates both the primal and the dual simplex algorithms. The reason for the importance of the dual simplex algorithm has its source in the duality and symmetry of linear programming. That it took seven years to discover it is somewhat of a mystery given the obvious symmetry of linear programming.
Quirino Paris

Chapter 9. Linear Programming and the Lagrangean Function

Abstract
In previous chapters we have discussed the relationship between primal and dual problems using only knowledge of economics, as in the theory of the competitive price-taking firm. It is important, however, to realize that duality relations are general features of reality (as interpreted by mathematics) and that the principal method for studying them is the Lagrangean method.
Quirino Paris

Chapter 10. The Artificial Variable Algorithm

Abstract
With knowledge of the primal simplex and the dual simplex algorithms, it is possible to solve two large classes of linear programming problems. The first class contains those problems whose constraints are all inequalities and admit an easy primal feasible basis (the identity matrix I). An equivalent way to regard these problems is to say that the origin of the space (the zero point in the Cartesian coordinate system of the output space) belongs to the feasible region. For such problems, a primal basic feasible solution can be established simply by inspection and, therefore, we can find their optimal solution by immediately applying the primal simplex algorithm. The second class contains those problems whose constraints are inequalities and satisfy the primal optimality criterion (equivalently, the dual feasibility criterion). These problems can be solved by an application of the dual simplex algorithm. It is important to notice that the use of either simplex algorithm requires the availability of an explicit basic feasible solution to either problem. Let us recall that primal feasibility means a nonnegative vector x that satisfies all the primal constraints. Analogously, dual feasibility means that the dual solution is nonnegative in all its components (z j − c j ). If neither of these conditions are satisfied, neither simplex algorithm can be applied directly to the LP problem.
Quirino Paris

Chapter 11. The Artificial Constraint Algorithm

Abstract
When it is difficult to find an initial basic feasible solution for either the primal or the dual problem, the artificial constraint algorithm provides a dual alternative to the artificial variable method. This is so because the dual of a variable is a constraint and vice versa (see chapter 2). Armed with this dual notion (variable ←→ constraint), we can infer the requirements of the artificial constraint algorithm from the requirements of the artificial variable algorithm by simply exchanging every dual notion, as in the scheme shown in table 11.1.
Quirino Paris

Chapter 12. The Diet Problem Revisited

Abstract
In previous chapters we have acquired the ability to use the family of simplex algorithms for solving any linear programming problem. We also have developed the knowledge of how to interpret economically every component of the optimal solutions. It is time, therefore, to reconsider Stigler’s diet problem, as promised in section 1.6, and to compute its true optimal solution.
Quirino Paris

Chapter 13. Parametric Programming: Input Demand Functions

Abstract
The previous twelve chapters were devoted to the task of learning the following:
1.
How to set up linear programming problems.
 
2.
The duality relations that bind primal and dual formulations.
 
3.
The economic interpretation of LP problems.
 
4.
How to solve linear programming problems.
 
Quirino Paris

Chapter 14. Parametric Programming: Output Supply Functions

Abstract
The post-optimality analysis of linear programming continues with the derivation of output supply functions. As in chapter 13, we briefly review the notion of output supply function and its derivation as presented in traditional economics courses and then draw the connection with a linear programming specification.
Quirino Paris

Chapter 15. Dealing with Multiple Optimal Solutions

Abstract
For many years, LP users have regarded multiple optimal solutions either as an exceptional event or as a nuisance to be avoided. Indeed, in many circles, multiple optimal solutions are a source of embarrassment and, often, the main goal of researchers is to define sufficient conditions for unique solutions.
Quirino Paris

Chapter 16. Solid Waste Management

Abstract
Solid waste in urban settlements has become a principal problem and headache of local governments around the world. Until a couple of decades ago, the solution consisted of collecting and transporting the waste from urban areas to landfills where it was simply buried. Increasing environmental consciousness, coupled with a limited supply of suitable landfills, has raised the price of waste disposal to a level that makes it convenient to look at solid waste not simply as worthless refuse but as a source of raw materials and energy. The growth of modern economies has occurred in association with consumerism, which, in turn, has spurred a mentality of discarding goods containing considerable amounts of recoverable resources, from paper to glass, to metals, and finally, to energy (potential fuel). A new economic sector devoted to recycling was thus born. In spite of private entrepreneurship and ingenuity, the management of solid waste is a daily concern of local governments for a relentlessly growing problem that risks suffocating communities, especially when the disposal network breaks down for even a few days.
Quirino Paris

Chapter 17. The Choice of Techniques in a Farm Production Model

Abstract
When introducing the farmer’s problem in section 1.4, we listed five categories of activities a farmer must consider to insure the economic success of an enterprise:
1.
Crop, animal, and processing activities.
 
2.
Associated operations and their scheduling.
 
3.
Capital, machinery, and equipment service flows.
 
4.
Capital, machinery and equipment stock.
 
5.
Other inputs such as fertilizer, animal feed, labor, water, etc.
 
Quirino Paris

Chapter 18. Cattle Ranch Management

Abstract
Linear programming has been used for many years to help make management decisions in beef feedlot and dairy cattle operations. In this chapter we discuss a LP model applied to range cattle ranching. The main problem of this type of farm operation is the decision about the stock of animals versus the available quantities of feed during the year. Cattle ranching is a dynamic enterprise requiring a sequence of decisions overlapping several production cycles. In order to keep the problem relatively simple, however, we begin with a static specification of the problem and turn to a multistage formulation in a further section.
Quirino Paris

Chapter 19. The Measurement of Technical and Economic Efficiency

Abstract
The problem of deciding the ranking of technical and economic abilities among a group of entrepreneurs is an old one and has received considerable attention from economists at different levels of sophistication. But why is it important to determine who is the best entrepreneur, who is the second best, and who is the worst? For a long time economists have assumed that the principal goal of rational entrepreneurs is maximizing profit subject to constraints imposed by the local environment. Studying the performance of various entrepreneurs, therefore, is a step toward understanding the process of making technical and economic decisions. When the best decision makers have been identified, a further presumption exists that their strategies can be used to advise those entrepreneurs who are lagging behind in the quest for maximum profit.
Quirino Paris

Chapter 20. Decentralized Economic Planning

Abstract
Entrepreneurs conduct economic activities that are finalized to the achievement of their individual objectives and interest. When the objectives of different — but interrelated — economic agents diverge, conflicts arise. Sometimes, the marketplace can mediate these conflicts through largely unconscious and seemingly haphazard efforts, especially when those interests are held with mild intensity. Often, conflicts must be mediated by an explicit agreement among the various actors who may delegate to a higher authority the task of resolving them. More often, finally, a higher (legal) authority assumes the responsibility of imposing on its subjects the resolution of conflicts. Consider a large corporation organized into various departments: procurement, production, marketing, financial, R & D, and personnel. All department managers are usually told to establish departmental goals of performance in their own interest and that of the department and are aware that they must compete with the other managers in the allocation of the corporation’s resources. In this situation, conflicts inevitably arise and the board of directors (or its chair) will act as a final decision maker in the interest of the corporation as a whole.
Quirino Paris

Chapter 21. Theorems of Linear Programming

Abstract
The material of this chapter is taken from papers of D. Gale, A. W. Tucker, A. J. Goldman, H. W. Kuhn and G. B. Dantzig. The scope of this chapter is to provide a concise presentation of the principal theorems that justify the structure of linear programming and the development of the simplex algorithms. The theorem (lemma) by Hungarian mathematician Julius Farkas, presented in 1894 and again in 1902, is of fundamental importance for establishing the structure of a dual pair of LP problems. An imaginative and operational lemma to prove Farkas theorem is due to A. W. Tucker. The statement of standard and canonical LP problems follows the structure presented by D. Gale.
Quirino Paris

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise