1
Introduction

This book deals with the application of linear programming to firm decision making. In particular, an important resource allocation problem that often arises in actual practice is when a set of inputs, some of which are limited in supply over a particular production period, is to be utilized to produce, using a given technology, a mix of products that will maximize total profit. While a model such as this can be constructed in a variety of ways and under different sets of assumptions, the discussion that follows shall be limited to the linear case, i.e. we will consider the short-run static profit-maximizing behavior of the multiproduct, multifactor competitive firm that employs a fixed-coefficients technology under certainty (Dorfman 1951, 1953; Naylor 1966).

How may we interpret the assumptions underlying this profit maximization model?

1. All-around perfect competition - the prices of the firm's product and variable inputs are given.
2. The firm employs a static model - all prices, the technology, and the supplies of the fixed factors remain constant over the production period.
3. The firm operates under conditions of certainty - the model is deterministic in that all prices and the technology behave in a completely systematic (nonrandom) fashion.
4. All factors and products are perfectly divisible - fractional (noninteger) quantities of factors and products are admissible at an optimal feasible solution.
5. The character of the firm's production activities, which represent specific ways of combining fixed and variable factors in order to produce a unit of output (in the case where the firm produces a single product) or a unit of an individual product (when the number of activities equals or exceeds the number of products), is determined by a set of technical decisions internal to the firm. These input activities are:
   1. independent in that no interaction effects exist between activities;
   2. linear, i.e. the input/output ratios for each activity are constant along with returns to scale (if the use of all inputs in an activity increases by a fixed amount, the output produced by that activity increases by the same amount);
   3. additive, e.g. if two activities are used simultaneously, the final quantities of inputs and outputs will be the arithmetic sums of the quantities that would result if these activities were operated separately. In addition, total profit generated from all activities equals the sum of the profits from each individual activity; and
   4. finite - the number of input activities or processes available for use during any production period is limited.
6. All structural relations exhibit direct proportionality - the objective function and all constraints are linear; unit profit and the fixed-factor inputs per unit of output for each activity are directly proportional to the level of operation of the activity (thus, marginal profit equals average profit).
7. The firm's objective is to maximize total profit subject to a set of structural activities, fixed-factor availabilities, and nonnegativity restrictions on the activity levels. Actually, this objective is accomplished in two distinct stages. First, a technical optimization problem is solved in that the firm chooses a set of production activities that requires the minimum amount of the fixed and variable inputs per unit of output. Second, the firm solves the aforementioned constrained maximum problem.
8. The firm operates in the short run in that a certain number of its inputs are fixed in quantity.

Why is this linear model for the firm important? It is intuitively clear that the more sophisticated the type of capital equipment employed in a production process, the more inflexible it is likely to be relative to the other factors of production with which it is combined. That is, the machinery in question must be used in fixed proportions with regard to certain other factors of production (Dorfman 1953, p. 143). For the type of process just described, no factor substitution is possible; a given output level can be produced by one and only one input combination, i.e. the inputs are perfectly complementary. For example, it is widely recognized that certain types of chemical processes exhibit this characteristic in that, to induce a particular type of chemical reaction, the input proportions (coefficient) must be (approximately) fixed. Moreover, mechanical processes such as those encountered in cotton textile manufacturing and machine-tool production are characterized by the presence of this limitationality, i.e. in the latter case, constant production times are logged on a fixed set of machines by a given number of operators working with specific grades of raw materials.

For example, suppose that a firm produces three types of precision tools (denoted x1, x2, and x3) made from high-grade steel. Four separate production operations are used: casting, grinding, sharpening, and polishing. The set of input-output coefficients (expressed in minutes per unit of output), which describe the firm's technology (the firm's stage one problem, as alluded to above, has been solved) is presented in Table 1.1. (Note that each of the three columns represents a separate input activity or process.)

Additionally, capacity limitations exist with respect to each of the four production operations in that upper limits on their availability are in force. That is, per production run, the firm has at its disposal 5000?minutes of casting time, 3000?minutes of grinding time, 3700?minutes of sharpening time, and 2000?minutes of polishing time. Finally, the unit profit values for tools x1, x2, and x3 are $22.50, $19.75, and $26.86, respectively. (Here these figures each depict unit revenue less unit variable cost and are computed before deducting fixed costs. Moreover, we are tacitly assuming that what is produced is sold.) Given this information, it is easily shown that the optimization problem the firm must solve (i.e. the stage-two problem mentioned above) will look like (1.1):

Table 1.1 Input-output coefficients.

How may we rationalize the structure of this problem? First, the objective function f represents total profit, which is the sum of the individual (gross) profit contributions of the three products, i.e.

Next, if we consider the first structural constraint inequality (the others can be interpreted in a similar fashion), we see that total casting time used per production run cannot exceed the total amount available, i.e.

Finally, the activity levels (product quantities) x1, x2, and x3 are nonnegative, thus indicating that the production activities are nonreversible, i.e. the fixed inputs cannot be created from the outputs.

To solve (1.1) we shall employ a specialized computational technique called the simplex method. The details of the simplex routine, as well as its mathematical foundations and embellishments, will be presented in Chapters 2-5. Putting computational considerations aside for the time being, the types of information sets that the firm obtains from an optimal solution to (1.1) can be characterized as follows. The optimal product mix is determined (from this result management can specify which product to produce in positive amounts and which ones to omit from the production plan) as well as the optimal activity levels (which indicate the exact number of units of each product produced). In addition, optimal resource utilization information is also generated (the solution reveals the amounts of the fixed or scarce resources employed in support of the optimal activity levels) along with the excess (slack) capacity figures (if the total amount available of some fixed resource is not fully utilized, the optimal solution indicates the amount left idle). Finally, the optimal dollar value of total profit is revealed.

Associated with (1.1) (hereafter called the primal problem) is a symmetric problem called its dual. While Chapter 6 presents duality theory in considerable detail, let us simply note without further elaboration here that the dual problem deals with the internal valuation (pricing) of the firm's fixed or scarce resources. These (nonmarket) prices or, as they are commonly called, shadow prices serve to signal the firm when it would be beneficial, in terms of recouping forgone profit (since the capacity limitations restrict the firm's production and thus profit opportunities) to acquire additional units of the fixed factors. Relative to (1.1), the dual problem appears as

where the dual...