So let's put it this way: As the title says, this will be a tutorial for Linear Programming Simplex Method concentrating on Maximization Problems.
Linear Programming is a method of dealing with decision problems that can be expressed as constrained linear models. Simplex Method is a method formulated by George L. Dantzig in solving linear programming models.
Simplex Method is an iterative or repetitive process whereby, following a standard pattern, the computational process is repeated over and over until the optimum solution is reached. It starts with a zero profit (in maximization of profit problems) or with a very high cost figure (in minimization of cost problems). Gradually, the solution is improved until the optimum solution is reached.Procedures for Maximization of Profit Problems:
- Represent the unknowns in the problems in mathematical form.
- Tabulate the data about the facts (if necessary).
- Formulate the objective function and constraints by restating the information in mathematical form.
- Objective Function - an expression which shows the relationship between the variables in the problem and the firm's goal.
- Structural Constraint (Explicit Constraint) - limit on the availability of resources.
- Non-negativity Constraint (Implicit Constraint) - restrict all the variables to zero or positive numbers.
- Convert the constraints to equality.
- For <= inequalities, add slack variables the change the sign to =
- For >= inequalities, multiply the whole equation by -1, add slack variables, then change to = sign
- Ex. 2x + 9y >= 36 to -2x - 9y + S1 = -36
- For equalities, just add slack variables.
- Enter the coefficient of the constraints in the tableau. The tableau looks like the table at the bottom.
- Determine the optimum column by choosing the largest positive entry in the [Cj - Zj] row.
- Identify the pivot row by dividing the quantity columns to the optimal column.
- Compute the values of the replacing row by dividing all the entries by the pivot.
- Compute the new values of the remaining numbers.
- Calculate Zj and [Cj - Zj]. If there are still positive entries in the [Cj - Zj] row, repeat from step 6.
- If [Cj - Zj] row do not contain a positive entry, the tableau is optimum.
For illustration, I will use my homework. <(^^<)
Maximize:
Zj = 4x + 2y - 3z + 5w
Subject to:
2x - y + z + 2w >= 50
3x - z + 2w <= 80
x + y + w = 60
x, y, z, w >= 0
Adding slack variables and changing inequalities, the new program would look like:
Maximize:
Zj = 4x + 2y - 3z + 5w + 0S1 + 0S2 + 0S3
Subject to:
-2x + y - z - 2w + S1 = -50
3x - z + 2w + S2 = 80
x + y + w + S3 = 60
x, y, z, w >= 0
Next step is to plot the constraints on the tableau.
To find Zj, multiply the Cj column with the values on the left. To find [Cj - Zj], subtract Zj from the uppermost values in the tableau. The results would be:
Now the optimum column is the column with the highest value. Column w is the optimum column with 5 as value.
To find the pivot row, Divide the values in the quantity column by the values in the optimum column. The row with the lowest positive value is the pivot row.
s1: -50 / -2 = 25
s2: 80 / 2 = 40
s3: 60 / 1 = 60
Now we will be computing the values of the incoming row (w). The values are computed as follows:
Next, we will be computing the values of the remaining row(s). This is done as follows:
Solving for the remaining rows, we have our next tableau (optimum column and pivot row highlighted).
Since there are still non-negative values in the [Cj - Zj] row, we will repeat steps 6 - 11.
Tableau 3 would look like this:
Again, there is still non-negative value, so repeat steps 6 - 11.
Tableau 4:
Since there are no more non-negative values in the tableau, the solution is now optimum.
The decision will be:
x = 0
y = 20
z = 0
w = 40
s1 = 10
s2 = 0
s3 = 0
Zj = 240
To check, you can substitute the values in the program we created earlier.
There are also online applications for solving linear programming problems using simplex method. Here are the sites.
Suggestions and comments will be appreciated. Thanks. (^^,)
No comments:
Post a Comment