Characteristics of Linear Programming Problems

[Page 55 ( continued )]

Now that we have had the opportunity to construct several linear programming models, let's review the characteristics that identify a linear programming problem.

The components of a linear programming model are an objective function, decision variables , and constraints.

A linear programming problem requires a choice between alternative courses of action (i.e., a decision). The decision is represented in the model by decision variables. A typical choice task for a business firm is deciding how much of several different products to produce, as in the Beaver Creek Pottery Company example presented earlier in this chapter. Identifying the choice task and defining the decision variables is usually the first step in the formulation process because it is quite difficult to construct the objective function and constraints without first identifying the decision variables.

---

[Page 56]

The problem encompasses an objective that the decision maker wants to achieve. The two most frequently encountered objectives for a business are maximizing profit and minimizing cost.

A third characteristic of a linear programming problem is that restrictions exist, making unlimited achievement of the objective function impossible . In a business firm these restrictions often take the form of limited resources, such as labor or material; however, the sample models in this chapter exhibit a variety of problem restrictions. These restrictions, as well as the objective, must be definable by mathematical functional relationships that are linear. Defining these relationships is typically the most difficult part of the formulation process.

Properties of Linear Programming Models

In addition to encompassing only linear relationships, a linear programming model also has several other implicit properties, which have been exhibited consistently throughout the examples in this chapter. The term linear not only means that the functions in the models are graphed as a straight line; it also means that the relationships exhibit proportionality. In other words, the rate of change, or slope, of the function is constant; therefore, changes of a given size in the value of a decision variable will result in exactly the same relative changes in the functional value.

Proportionality means the slope of a constraint or objective function line is constant.

Linear programming also requires that the objective function terms and the constraint terms be additive. For example, in the Beaver Creek Pottery Company model, the total profit ( Z ) must equal the sum of profits earned from making bowls ($40 x ₁ ) and mugs ($50 x ₂ ). Also, the total resources used must equal the sum of the resources used for each activity in a constraint (e.g., labor).

The terms in the objective function or constraints are additive .

Another property of linear programming models is that the solution values (of the decision variables) cannot be restricted to integer values; the decision variables can take on any fractional value. Thus, the variables are said to be continuous or divisible , as opposed to integer or discrete . For example, although decision variables representing bowls or mugs or airplanes or automobiles should realistically have integer (whole number) solutions, the solution methods for linear programming will not necessarily provide such solutions. This is a property that will be discussed further as solution methods are presented in subsequent chapters.

The values of decision variables are continuous or divisible .

The final property of linear programming models is that the values of all the model parameters are assumed to be constant and known with certainty . In real situations, however, model parameters are frequently uncertain because they reflect the future as well as the present, and future conditions are rarely known with certainty.

All model parameters are assumed to be known with certainty .

To summarize, a linear programming model has the following general properties: linearity , proportionality, additivity, divisibility, and certainty. As various linear programming solution methods are presented throughout this book, these properties will become more obvious, and their impact on problem solution will be discussed in greater detail.