The document summarizes the simplex method for solving linear programming problems. It describes the steps to set up and solve both maximization and minimization problems using the simplex method. For maximization problems, the objective is to select the optimal column with the most positive value and iterate until all values in the bottom row are non-positive. For minimization, the optimal column has the most negative value and iterations continue until all bottom row values are non-negative. Worked examples demonstrate converting a problem to standard form and performing the simplex method iterations to arrive at an optimal solution.
The document summarizes the simplex method for solving linear programming problems. It describes the steps to set up and solve both maximization and minimization problems using the simplex method. For maximization problems, the objective is to select the optimal column with the most positive value and iterate until all values in the bottom row are non-positive. For minimization, the optimal column has the most negative value and iterations continue until all bottom row values are non-negative. Worked examples demonstrate converting a problem to standard form and performing the simplex method iterations to arrive at an optimal solution.
The document summarizes the simplex method for solving linear programming problems. It describes the steps to set up and solve both maximization and minimization problems using the simplex method. For maximization problems, the objective is to select the optimal column with the most positive value and iterate until all values in the bottom row are non-positive. For minimization, the optimal column has the most negative value and iterations continue until all bottom row values are non-negative. Worked examples demonstrate converting a problem to standard form and performing the simplex method iterations to arrive at an optimal solution.
The document summarizes the simplex method for solving linear programming problems. It describes the steps to set up and solve both maximization and minimization problems using the simplex method. For maximization problems, the objective is to select the optimal column with the most positive value and iterate until all values in the bottom row are non-positive. For minimization, the optimal column has the most negative value and iterations continue until all bottom row values are non-negative. Worked examples demonstrate converting a problem to standard form and performing the simplex method iterations to arrive at an optimal solution.
Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 24
Simplex Method
LINEAR PROGRAMMING
Adiel Aislin S. Tagumpay
Dominic G. Jason Justine Ara Guzman Jon Edison C. Montejo
Simplex Maximization Steps in Solving Maximization Problems 1.Set up the objective function and the constraints of the problem. 2.Convert the objective function and the explicit constraints to equation form (standard form). Follow the following rules in converting the LP model to standard form:
Symbol in the constraint
To put into standard form
<
Add a slack variable (S1) that represents the
amount by which the right-hand side of the constraint exceed its left-hand side.
Add an artificial variable (A1) or extraneous
variable, which serves a starting basic variable. This variable has no physical meaning in the problem hence it is called artificial .
>
Subtract a surplus variable (S1), which
represents the excess amount of the left-hand side of the constraint over the right-hand side, and add an artificial variable (A1).
The artificial variables in the optimum or final solution should be zero provided a feasible solution exists. The reasonable way to do this is to penalize these variables in the objective function by using a very small number coefficient, -M, (M for million), or -100 if the numerical coefficient found in the constraints and objective function are all less than or equal to 10, let it equal to -1000 if the numerical coefficients are all less than or equal to 100, let it equal to -10000, if the numerical coefficients are all less than or equal to 1000,and so on.
3. Set up the initial tableau.
The number of rows = no. of constraints +4
The number of columns = no. decision variable + no. of slacks/surplus variables + no. of artificial variables + 4 3.1. Fill up the first and second rows of the initial tableau. a) The variable row (second row) contains the variable of the objective function. List the variables in order, beginning with the decision, followed be the slack variables then the artificial variables (the subscripts follow the constraint number) b) The Cj row (first row) takes the numerical coefficients of the variables in the variable row. 3.2. Put the entries in the first three columns of the initial tableau. a) The second column is the solution column (also called basis or variable column). b) the first column is the contribution to profit column (Ci), which takes the coefficients of the variables in the solution column. c) The third column is the quantity column or the constant column, which takes the constant terms or the right-hand values of the constraints.
4. Select the optimum column, the column with the most positive value in the Ci Zi row of the initial table 5. Select the pivot in the pivotal row. 6. Use the pivot to clear the optimum column in the normal manner. This gives the next tableau. 7. Repeat steps 4-6 until there are no more negative numbers in the bottom row (with the possible expectation of the Answer column.)
Writing LP Model to Equation Form
Example: Maximize Z= 5x+12y Subject to 2x+3y80 3x+4y100 x,y0
Solution: 2x+3y+S1=80 3x+4y+S2=100 Objective function Max Z= 5x+12y+0S1+0S2
Since the inequalities involve less than,
simply add slack variable. For constraint 1, 2x+3y80, add S1. The subscript 1 indicates that the slack variable is added to the left side of the 1st constraint. Thus, constraint 1 becomes 2x+3y+S1=80 Doing the same process to constraint 2, then it becomes 3x+4y+S2=100
The objective function should also
contain the slack variable added in the constraints. But since the slack variable has no contribution to the objective function, its numerical coefficient must be zero. Thus the objective function becomes Max Z= 5x+12y+0S1+0S2
Obtaining the Final Solution of LPP
Example 1. Maximize Z= 90x + 110y Subject to 6x + 4y 120 Explicit constraint 3x + 10y 180 Explicit constraint x 0, y 0
Iteration 1 i. Determine the optimum column and the pivotal row, and then highlight them. ii. The intersection of these column and row is the pivot element. iii. Determine the Qi column. 60 2 = 30 180 10 = 18
Table 2
Iteration 2 i. Pivotal row: second constraint coefficient row Change the outgoing variable by the entering variable (reflect corresponding coefficients in the Ci Col.) Pivot element in the replacing pivot row should be equal to one (1), thus divide each entry in this row by the pivot element (10)
Table 3
ii. Remaining rows
1. First coefficient row The intersection with the optimum column should be ZERO. There are several algebraic manipulations that can be used to make it zero, one is to apply formula 7.1.
Table 4
Table 5
The solution is not yet final at this point since there is still positive entry in the Cj Zj row
Table 6
Since the entries in the Cj Zj are zeros and negative
numbers, then the last iteration gives the optimum solution. Thus optimum values of x = 10, y = 15 Z = 2550
Simplex Minimization Steps in solving Minimization Problems The steps in solving minimization problems by simplex method are the same as in maximization except for steps 2, 4, and 7. 2. Convert the objective function and the explicit constraints to equation form (standard form). Follow the following rules in converting the LP model to standard form: Symbols in the constraint
To put into standard form
Add a slack variable (S1)
Subtract a surplus variable (S!) and
add an artificial variable (A1)
Add an artificial variable (A1)
4. Select the optimum column, column with the most negative value in the Cj-Zj row of the initial table. 7. Repeat steps 4-6 until there are no more positive numbers in the bottom row (with the possible exception of the Answer column.
Iteration 1 Cj
Qi
Ci
Solution
Quantity
A1
S2
S3
A3
A1
10
S2
A3
18
-1
19
28M
4M
4M
-M
Zj Cj - Zj
6 4M 4 4M
Iteration 2 Cj
Qi
Ci
Solution
Quantity
A1
S2
S3
A3
A1
-2
---
A3
10
-2
-1
3.33
16 + 12M
4M
4 4M
-M
6 4M
-4 + 4M
Zj Cj - Zj
Final tableau Cj
Ci
Solution
Quantity
A1
S2
S3
A3
-1/2
-1/2
1/2
3/4
1/4
-1/4
S2
-3/4
-1/4
1/4
36
-2
M-2
Zj Cj - Zj
From the last table, The Cj Zj has zeros and positive entries, thus it gives the optimum Solution. The solution are x = 4,y = 3and the minimum value of Z = 36.
