Diego Azeta


DM Weblog

Planet of the Sapiens


Zahid the Sumerian

Music Channel

Decision Analysis

Game Theory

Systems Science edu

Slack & Surplus Variables

Slack & Surplus Variables

We employed the graphical method to solve the Lego problem because —apart from it being a two-dimensional problem where coordinate geometry works just fine— graphs facilitate visualization of both problem structure and solution process. We will continue using the graphical method to conduct the sensitivity analysis of the problem parameters. But we first need to understand the concept of slack and its correlative, surplus, in LP constraints.

LP constraints are limited to only three possible relational operators:   = ,  ≤ ,  ≥
Strict inequalities  ( <  ,  > )  are not allowed in LP.

Graphically, an equality constraint traces a line. LP inequality constraints “ ≤ ” and “ ≥ ” consist of a line (the equality part of the relation) along with a half-plane (the inequality portion). Two-dimensional inequalities are easy to work with graphically because the regions they define are depicted quite naturally by the Cartesian plane. Alas, that is not the case with analytical (algebraic) solution methods, which do not deal with geometric planes but with purely abstract symbols. It's a bit harder to visualize relations with symbols, but those representations can be very powerful. Algebra —actually, math in general— is famously powerful largely because of the logical precision afforded by symbolic equations. To say that something is equal to something else is, in math, a rigorously exact statement. On the other hand, to say that something is greater than or equal to some other quantity leaves open an infinite (real) number of possibilities. Exactness goes down the drain.

Consider the large block constraint:  2x + y ≤ 6.  The economic interpretation of this constraint is: the number of large blocks used to assemble tables plus the number of large blocks used to assemble chairs cannot exceed the six units of large blocks in inventory. Suppose we build one table and one chair. In order to determine how many blocks we have left in stock, we must plug in those values into the variables of the constraint, compute the left hand side and subtract it from 6. We find we have three blocks left in stock.

Accountants prefer another approach. Instead of computing how many blocks are left in stock every time a table or chair is assembled, they create a new account that keeps track of the blocks inventory continuously. The account is initialized at 6 and decreased in real time (perpetual inventory) as blocks are used in production. The relation can now be expressed as: the number of large blocks used to assemble tables plus the number of large blocks used to assemble chairs plus the number of large blocks left in inventory must equal the six units of large blocks originally stocked. Mathematically:

2x + y + s = 6

where  s  is a new variable that keeps track of the large-blocks inventory.

The beauty of this arrangement is twofold. First, we can always tell at a glance how many blocks are idle (or slack, i.e., not being used in production) by simply checking the slack variable. No need to recalculate balances.

Minutiae Aedificante
This slack-variable technique illustrates a general principle of computation: computational procedures can generally be reduced by increasing the size of the workspace (in our case, adding more variables). Actually, this goes back to a fundamental principle of physics: time and space are complementary concepts. That is the reason why relativity theory, and not classical mechanics, provides the correct description of reality.

In second place, the constraint has been converted from an inequality to an equation. It is this conversion into an equation that makes analytical solution methods possible.

The variable  s  is called a slack variable because it measures the amount of slack (idle) resources still remaining in stock at any point in time during the production process. Since it is not possible to have negative slack, nonnegativity constraints also apply to slack variables.

All  “ ≤ ”  constraints are automatically converted by LP software into their standard form (equations) by creating and adding slack variables.

The Lego problem has two  “ ≤ ”  constraints, so two slack variables are required:

2x +   y + s1 =  6
2x + 2y + s2 =  8

where  s1 =  number of large blocks remaining in stock,  s2 = number of small blocks remaining in stock, and  s1, s2  ≥  0.

To convert  “ ≥ ”  constraints to standard form, a surplus variable is subtracted on the left hand side of the constraint. For example, suppose that at least two items, either tables or chairs, are needed for demo purposes in the showroom. This requirement is captured by the following inequality constraint:

x + y ≥  2

Since it is possible to exceed the minimum required production quantity, the only way to obtain an equation when converting to standard form is to subtract the excess production (the quantity produced in excess of the minimum requirement):

x + y - s3 = 2

where  s3 = number of items produced in excess of showroom requirements. Nonnegativity constraints are also required for surplus variables. Thus,  s3 ≥ 0.

All  “ ≥  ”  constraints are automatically converted by LP software into their standard form by creating and subtracting surplus variables.

In practical terms, slack and surplus variables keep track of basically the same thing: by how much is the left hand side of the constraint different from the RHS constant. If there is a difference, it must be positive, by definition. If there is no difference,  s = 0. The names slack and surplus serve merely to indicate the direction of the difference, that is, to remind us that the original (pre-standard) constraint was  “ ≤ ”  or  “ ≥ ”.