The first step is to get the linear program into standard form. Suppose you have the following linear program:
Maximize:
3x1 +5x2
subject to:
Standard form dictates that the objective function should be minimized, and all inequality constraints be of the equality variety. The last constraint is is known as the non-negativity constraint. We can see that this linear program is not in standard form. There are two steps we have take to put this linear program into standard form. We have to change maximization to mimization.
This is quite simple. Multiply the objective function by -1. In this case, the
objective function becomes
Minimize:
-3x1 + -5x2
Convert the inequalities to equalities by the use of slack variables or surplus variables.
Consider the less-than constraint #1. We know x1+x2 should be 50. Since x1+x2
50, we can
add a variable x3 to x1 + x2 to "take up the
slack". We can write x1 +x2 +x3= 50 As long as x3
0,
constraint 1 holds.
When we add variables to the constraints, we need to consider the cost of these variables in the objective function. The cost of a slack variable is 0. There is no cost for not "using" some of the "available resources."
To illustrate this, let's say x1+x2 = 30. This satisfies
constraint 1 because 30 50. If we set x3 to 20, we can write x1+x2+
x3 = 50. The slack variable x3
0 because 20
0.
If we let x3 = 20, this "extra" 20 is not contributing anything to the objective function. This is why it has a cost of 0.
Alternatively, let's say that x3 = -1. This violates the condition x3
0. Then
we write x1+x2+x3 = 50 Whatever x1 and x2
are, we know they add up to 51 because we have to subtract 1 to get their total to equal
50. Thus, constraint 1 does not hold because 51
50.
The concept of a surplus variable is very similar to that of a slack variable. Surplus variables are associated with greater-than constraints similar to constraint 1. In the case of the slack variable you added it to the inequality to "take up the slack" and make the inequality an equality. This time, you subtract a surplus variable to get rid of the "surplus" in the total of the variables. The cost of a surplus variable in the objective function is 0, too.
We can now write our original linear program as follows:
Minimize:
-3x1 -5x2 + 0x3 + 0x4
subject to:
where x3 is a slack variable associated with constraint 1 and x4 is a surplus variable associated with constraint 2. This takes us to the next step of finding the first basic feasible solution.