In his paper entitled “Linear Programming and the Simplex Method”, (Notices of the AMS (March 2007), Volume 54, No:3, pages 364-369), David Gale defines the subject of linear programming in the following manner: “It is concerned with the problem of maximizing or minimizing a linear function whose variables are required to satisfy a system of linear constraints, a constraint being a linear equation or (weak linear: author’s insertion) inequality”. The application of linear programming in solving problems faced by human society or social groups (which includes industry) is vast and listing them could comprise several volumes.
David Gale continues to say that almost all linear programming applications can be formulated using the framework of activity analysis, which for our purposes may be described as follows. There is a given set of goods. “There is also a set of processes or activities which are specified by amounts of the goods consumed as inputs or produced as outputs”, when the processes are operated at unit level. An activity is represented by a column vector “a”; positive entries of the column vector denote inputs and negative entries denote outputs, when the activity is operated at unit level. Any activity aj may be carried out at any non-negative level xj. There is an initial endowment column vector denoted by b, which specifies the right hand side of the constraints. The initial endowment of a good may be positive (as in the case of natural, human or other resources), negative (as in the case of clean air versus pollution, which is a bad) or zero. Associated with each activity aj is a cj which gives the net profit if activity aj is operated at unit level. Given ‘m’ goods and ‘n’ activities, the linear programming problem (LP) is to find activity levels given by a n-vector x that satisfies the constraints and maximizes the total profit c1x1 + c2x2+…+ cnxn. A compact representation of the above maximization problem is the following.
Given an m- column vector b, an n-row vector cT (where T denotes the transpose of a vector; thus c is an n-column vector) and an m×n matrix A, find an n-column vector x so as to
maximize cTx
subject to Ax ≤ b, x ≥ 0. (LP)
Here the ith element of activity aj (which is the jth column of A) denoted aij is the amount of good i required as input if activity aj is operated at unit level.
Operations research, or management science as it is sometimes referred to, is for most purposes little more than theoretical and applied linear programming, although smooth non-linear functions are invoked for the theory and applications of non-linear programming. Most successful applications of operations research have taken place in industry. However in spite of its initial success and popularity in economics (particularly economic theory), the main reason for people to be hesitant about the use of LP is because constant marginal costs, marginal profits and marginal output might be a hasty over simplification of reality. Thus, although smooth cost, smooth production and smooth utility functions were even more counterfactual from any reasonable standpoint, greater faith was reposed on models of rational economic choice that used smooth objective and/or constraint functions, than on LP models.
A more realistic and non-smooth version of the activity analysis model would assume piecewise affine and concave profit functions (to allow for market imperfections, i.e. imperfect competition) and piecewise affine and convex joint cost (input requirement) functions. It is customary (though imprecise) to refer to piecewise affine functions as piecewise linear functions.
In what follows, let R denote the set of real numbers and let Rn denote the set of all ordered n-tuples of real numbers.
A function f:Rn→R is said to be piecewise affine and concave (PA concave) if there exists a positive integer K and K (n+1)- row vectors <(ckT, dk)| k= 1,…, K> such that for all x in Rn, f(x) = min{ckTx + dk| k= 1,…, K}.
A function g:Rn→R is said to be piecewise affine and concave (PA convex) if there exists a positive integer K and K (n+1)- row vectors <(akT, qk)| k= 1,…, K> such that for all x in Rn, g(x) = max{akTx + qk| k= 1,…, K}.
A piecewise affine programming problem (PAP) is a maximization problem of the following form.
maximize f(x)
subject to gi(x) ≤ bi, i = 1,…,m, x ≥ 0. (PAP)
Here f is a PA-concave function, each gi is PA-convex and each bi is a real number.
Suppose f(x) = min{ckTx + dk| k= 1,…, K} and for each iÎ{1,…,m} there exists a positive integer K(i) and K(i) (n+1)- row vectors <(Ai(k)T,qi(k))|k = 1,…,K(i)> such that gi(x) = max{Ai(k)Tx +qi(k)| k= 1,…, K(i)}.
If we were to interpret a PAP as an extension of the LP framework based on activity analysis, then f would represent a profit function, each gi the cost or input requirement function of the ith good, and each bi as the initial endowment of good i.
The nice result that puts a PAP squarely within the domain of LP is the following.
Proposition x* solves PAP if and only there exists a real number u* such that x*, u* solve the following LP problem.
maximize u
subject to ckTx + dk ≥ u, k= 1,…, K, Ai(k)Tx +qi(k) ≤ bi, k = 1,…,K(i), i = 1,…,m, x ≥ 0.
The implication of the above proposition is that solving a PAP is no more or less difficult than solving an LP. Thus algorithms (or software) that solve an LP can be used to solve a PAP, once the latter has been properly formulated. However economic theory is also concerned with mathematical representation of both qualitative and quantitative properties and most such results in the case of smooth objective functions make use of duality theory. In order to apply duality theory to a PAP and obtain meaningful results, the PAP itself needs to be in a manageable form. To begin with, it may be prudent to assume that each piecewise affine function has at most two affine segments and see how far the analysis proceeds.
