Scribd
Upload
1 views2 pages

Algorithm Simplex Method

The document outlines the steps of the Simplex Method for solving linear programming problems, starting from formulating the problem to reading the final solution. It details the conversion of the general form to standard form, the construction of the initial simplex tableau, and the iterative process to check for optimality. The process includes identifying entering and leaving variables, performing key operations, and updating the tableau until an optimal solution is reached.

Uploaded by

Nasir Ali
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views2 pages

Algorithm Simplex Method

The document outlines the steps of the Simplex Method for solving linear programming problems, starting from formulating the problem to reading the final solution. It details the conversion of the general form to standard form, the construction of the initial simplex tableau, and the iterative process to check for optimality. The process includes identifying entering and leaving variables, performing key operations, and updating the tableau until an optimal solution is reached.

Uploaded by

Nasir Ali
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm Simplex Method

Steps:

1. Formulate Linear Programming Problem

Objective function: Z = C1X1 + C2X2 + …………. +CnXn

Constraints: A1X1 + A2X2 ≤ B1


…………………………..
…………………………..
AnXn+ AnXn ≤ Bn
where all Xn ≥ 0

2. Convert General Form to Standard Form


1. Convert inequalities (≤) into equalities by adding slack variables:

A1X1 + A2X2 + S1 = B1

…………………………..
…………………………..

AnXn + AnXn + Sn= Bn

2. Write the Objective Function as an Equation


Move all terms to one side:
Z - C1X1 -C2X2 -…………. - CnXn =0
This form allows Z to be included directly in the Simplex table.

3. Standard into Matrix Form


AX=B
Where
A: coefficients of each variable in new objective function equation and coefficients of
each variable in each constraint except Z variable of new objective function constraints.
X: All variables of standard form including Slack variables (Basic Variables), Decision
Variables (x No Basic Variables) and Z.
B: R.H.S of each equation in step 2.
4. Construct the Initial Simplex Tableau
3. Columns:
o The basic variables (initially the slack variables) are on the left-hand side.
o Variables: X1, X1 ,.., Xn, S1, S2,…., Sn
o XB which is R.H.S i.e B
4. Rows: one for the Z-equation and One for each constraint
5. Check Optimality
1. If all Z row values are ≥ 0, then solution is optimal
2. If at least one value in Z row is < 0, Then proceed to next iteration by finding
Entering Variable (Key Column), Leaving Variable and Key Value from previous
iteration’s table. And proceed to iterations until optimality reached.
3. If in Z row’s Key Column’s has all negative values then solution is unbounded i.e
no solution o the problem.

6. Repeat until optimality is reached:


a. Identify the Entering Variable (Key Column)
In the Z-row, select the most negative coefficient (for maximization problems). The
corresponding variable is the entering variable (it will increase Z the most).
b. Identify leaving variable (Key Row)
Create a new column with label Ratio
For all rows with positive coefficient in Key column:
Ratio = XB / coefficient of Entering Variable (Key column)
Select row with smallest positive ratio which is actually identifies the Basic Leaving
Variable
c. Key Value
The intersection of the entering column and leaving row gives the pivot element.
7. Key Operation
o Divide the leaving row by the pivot element to make it 1.
8. Row Operation
o For all other rows (including Z-row), Use row operations to make all other elements
in Key column 0.
9. Update the Tableau
o Update basic variable labels by replacing leaving variable with entering variable
o Repeat Steps 5–9 until no negative coefficient remains in the Z-row.

10. Read final solution


o Basic variables = XB values in final table
o Optimal value of Z = XB entry in Z-row

You might also like