AE-MA
1 CHAPTER 6:
LINEAR
PROGRAMMING
PART II
ANGUSTO, STEFFANIE ANONUEVO, JANNA MAE VILLANUEVA, FAITH GROUP 18
INTRODU
CTION
·Developed in 1947 by American George Dantzig, the simplex method solves
linear programming problems.
·It handles multiple unknowns that are difficult to plot graphically.
·The method starts at a corner with zero unknowns and moves between
corners.
·It optimizes the objective function until the best solution is identified.
Following are the steps in solving LP
maximization model using the simplex method:
Step 1. Set the LP problem by determining the
unknown variables, objective function and
constraints.
Step 2. Add the necessary slack variables. Slack
variables are variables added to constraints in
order to translate them into a linear form.
Step 3. Prepare the initial tableau.
Step 4. Assess the tableau if the solution is
already maximal. Otherwise, proceed to step 5.
Step 5. Calculate another simplex tableau:
choose the pivot columns and find the pivot row
and pivot entry.
Step 6. Proceed to step 4.
·Iteration – refers to a sequence of steps or row operations in order to move one feasible
solution to another
·Simplex Tableau – a table that keeps track of the calculations for the simplex method
·Right-Hand-Side (RHS) – is at the rightmost column of a simplex tableau that indicates
the capacities or requirements
·Basic Variables – variables considered in a basic solution
·Pivot Column – in a maximization problem should have the lowest negative value in the
last row
·Pivot Row – a row in the simplex tableau that contains the basic variable that will gout of
the solution
·Intersectional Elements – the elements in the pivot column
·Pivot – the element in the simplex tableau located both in the pivot row and pivot column
·Pivoting - process of moving from one simplex tableau to the next
Step Maximization Minimization
Identify and define the objective function and Identify and define the objective function
1. Objective Function and Constraints constraints. and constraints.
Convert the LP problem to linear
equations. For minimization, subtract
2. Convert to Linear Equations Convert the LP problem to linear equations.
surplus variables to convert constraints
into equations.
3. Setup the Initial Tableau Set up the initial simplex tableau. Set up the initial simplex tableau.
Choose the column with the most negative entry in Choose the column with the highest
4. Select Pivot Column the bottom row. positive entry in the bottom row.
Apply the test ratio (RHS / IE). The row with
Apply the test ratio (RHS / IE). The row with the the lowest quotient is the pivot row. RHS
5. Find Pivot Row smallest positive quotient is the pivot row. values are divided by the nonzero and non-
negative elements in the pivot column.
Divide all values in the pivot row by the pivot element Divide all values in the pivot row by the
6. Compute New Entries to find new entries. pivot element to find new entries.
Compute new entries for the rest Compute new entries for the rest of the
THANK
YOU
