Introduction

Not every optimization problem can be solved using Linear Programming (LP). Before applying techniques such as the Graphical Method or the Simplex Method, it is important to determine whether the problem satisfies the foundational properties of a linear programming model.

Linear Programming is a mathematical optimization technique used to determine the best possible allocation of limited resources. However, this method only works when specific assumptions about the problem are met. If even one of these assumptions is violated, the problem may require a different optimization approach, such as Integer Programming, Nonlinear Programming, or Stochastic Programming.

This article discusses the essential properties that a problem must possess to qualify as a Linear Programming problem.

1. Linearity

The most fundamental property of a linear programming problem is linearity. Both the objective function and all constraints must be linear expressions of the decision variables.

A linear expression satisfies the following conditions:

• Decision variables appear only to the first power.
• Variables are never multiplied together.
• Variables do not appear inside nonlinear functions such as square roots, logarithms, trigonometric functions, or exponentials.
• The coefficients of the variables remain constant.

For example, the following objective function is linear:

Max Z = 5x + 8y

However, the following expressions are not linear:

• (x^2) + y
• (xy)
•  
• log(y)

Linearity is the defining characteristic of a linear programming model. Without it, the problem belongs to the field of nonlinear optimization.

2. Proportionality

The proportionality assumption states that each decision variable contributes to the objective function and constraints in direct proportion to its value.

For instance, if manufacturing one unit of a product requires two hours of labor, then:

• Two units require four hours.
• Five units require ten hours.
• Ten units require twenty hours.

Similarly, if one unit generates a profit of $15, then producing twice as many units generates exactly twice the profit.

There are no economies of scale, discounts, learning effects, or diminishing returns under this assumption.

3. Additivity

The additivity property states that the total effect of all decision variables is simply the sum of their individual effects.

Suppose Product A contributes $50 profit and Product B contributes $80 profit. Producing both products results in a total profit of:

[50 + 80 = 130]

There are no interaction effects among decision variables. In other words, producing one product does not alter the contribution of another.

This assumption also applies to resource consumption. If Product A requires two hours of labor and Product B requires three hours, then producing both requires exactly five hours.

4. Divisibility

Linear programming assumes that decision variables may take fractional values whenever necessary.

Examples include:

• Producing 12.5 tons of cement.
• Allocating 3.75 machine hours.
• Shipping 45.8 kilograms of material.

This assumption is realistic for many continuous processes involving liquids, chemicals, electricity, or raw materials.

However, when decision variables must be whole numbers—such as the number of employees, vehicles, or machines—the problem becomes an Integer Programming problem rather than a standard LP model.

5. Certainty (Deterministic)

Another key assumption is certainty, also called the deterministic assumption.

All numerical values in the model are assumed to be known and fixed before optimization begins. These include:

• Unit profits
• Production costs
• Resource availability
• Processing times
• Demand limits

For example, if each product requires four kilograms of raw material, that requirement is assumed to remain constant throughout the analysis.

If these values are uncertain or subject to random variation, alternative optimization methods such as stochastic programming or robust optimization may be more appropriate.

6. Non-Negativity

Decision variables in a linear programming model cannot take negative values.

Mathematically,

Xi >= 0

This restriction reflects practical reality because:

• A company cannot produce negative products.
• Labor hours cannot be negative.
• Transportation quantities cannot be negative.

The non-negativity assumption ensures that every solution remains meaningful in the real world.

Why These Properties Are Important

The six foundational properties work together to make linear programming both mathematically tractable and computationally efficient. Because the relationships are linear and predictable, algorithms such as the Simplex Method can efficiently identify the optimal solution, even for large-scale optimization problems involving thousands of variables and constraints.

Before attempting to formulate an LP model, analysts should verify that the problem satisfies these assumptions. Doing so prevents the application of an inappropriate optimization technique and helps ensure that the resulting solution accurately represents the decision problem.

When a Problem Is Not a Linear Programming Problem

A problem no longer qualifies as a linear programming problem if any of the foundational properties are violated. Common examples include:

• Profit depends on the square of production.
• Costs decrease because of quantity discounts.
• Decision variables must be integers only.
• Resource availability is uncertain or random.
• Decision variables are multiplied together.
• Relationships involve nonlinear functions such as exponential growth or logarithms.

In such cases, other optimization methods should be considered.

Conclusion

Linear Programming is one of the cornerstones of Operations Research because it provides a systematic way to optimize limited resources. However, its successful application depends on six foundational properties: linearity, proportionality, additivity, divisibility, certainty, and non-negativity.

These assumptions define whether a problem can be modeled and solved using linear programming techniques. By understanding these properties, students, engineers, managers, and researchers can correctly identify LP problems and select the most appropriate optimization method for real-world decision-making.

Mastering these foundational concepts is the first step toward solving more advanced optimization problems in Operations Research and developing effective mathematical models for industry, business, engineering, and public-sector applications.