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 a^{j} may be carried out at any non-negative level x^{j}. 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 a^{j} is a c_{j} which gives the net profit if activity a^{j} 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 c_{1}x^{1} + c_{2}x^{2}+…+ c_{n}x^{n}. A compact representation of the above maximization problem is the following.

Given an m- column vector b, an n-row vector c^{T} (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 c^{T}x

subject to Ax ≤ b, x ≥ 0. (LP)

Here the i^{th} element of activity a^{j} (which is the j^{th} column of A) denoted a_{ij} is the amount of good i required as input if activity a^{j} 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 R^{n} denote the set of all ordered n-tuples of real numbers.

A function f:R^{n}→R is said to be *piecewise affine and concave* (**PA concave**) if there exists a positive integer K and K (n+1)- row vectors <(c_{k}^{T}, d_{k})| k= 1,…, K> such that for all x in R^{n}, f(x) = min{c_{k}^{T}x + d_{k}| k= 1,…, K}.

A function g:R^{n}→R is said to be *piecewise affine and concave* (**PA convex**) if there exists a positive integer K and K (n+1)- row vectors <(a_{k}^{T}, q_{k})| k= 1,…, K> such that for all x in R^{n}, g(x) = max{a_{k}^{T}x + q_{k}| k= 1,…, K}.

A *piecewise affine programming problem* (**PAP**) is a maximization problem of the following form.

maximize f(x)

subject to g_{i}(x) ≤ b_{i}, i = 1,…,m, x ≥ 0. (PAP)

Here f is a PA-concave function, each g_{i} is PA-convex and each b_{i} is a real number.

Suppose f(x) = min{c_{k}^{T}x + d_{k}| k= 1,…, K} and for each iÎ{1,…,m} there exists a positive integer K(i) and K(i) (n+1)- row vectors <(A_{i}(k)^{T},q_{i}(k))|k = 1,…,K(i)> such that g_{i}(x) = max{A_{i}(k)^{T}x +q_{i}(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 g_{i} the cost or input requirement function of the i^{th} good, and each b_{i} 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 c_{k}^{T}x + d_{k }≥ u, k= 1,…, K, A_{i}(k)^{T}x +q_{i}(k) ≤ b_{i}, 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.