Solving Linear Programming Problems using
the Simplex Method in Python
This Python implementation:
• Accepts the LPP from the user.
• Displays the simplex tableau at each step.
Python Program
import numpy as np
# Function to display the simplex tableau
def p r i n t _ t a b l e a u ( tableau , i t e r a t i o n) :
print ( f " \ n I t e r a t i o n { i t e r a t i o n }: " )
rows , cols = tableau . shape
for i in range ( rows ) :
for j in range ( cols ) :
print ( f " { tableau [i , j ]:8.2 f } " , end = " " )
print ()
Here, we import numpy for matrix operations. The print tableau func-
tion formats the simplex tableau in a readable manner. It takes the tableau
matrix and iteration count as arguments, then prints all elements with two
decimal places.
—
# Get input from user
m = int ( input ( " Enter number of c o n s t r a i n t s: " ) )
n = int ( input ( " Enter number of v a r i a b l e s: " ) )
print ( " Enter c o e f f i c i e n t s of o b j e c t i v e function ( to
maximize ) : " )
c = np . array ( list ( map ( float , input () . split () ) ) )
1
A = []
b = []
for i in range ( m ) :
print ( f " Enter c o e f f i c i e n t s of c o n s t r a i n t { i +1}: " )
row = list ( map ( float , input () . split () ) )
A . append ( row )
rhs = float ( input ( " Enter RHS value : " ) )
b . append ( rhs )
A = np . array ( A )
b = np . array ( b )
In this block: - We first ask for the number of constraints (m) and vari-
ables (n). - The user enters the coefficients of the objective function c. - Each
constraint’s coefficients are inputted one by one, along with its right-hand
side value (b). - We store A (constraint coefficients) and b (RHS) in NumPy
arrays for easy matrix operations.
—
# C o n s t r u c t initial tableau
tableau = np . zeros (( m +1 , n + m +1) )
tableau [: m , : n ] = A
tableau [: m , n : n + m ] = np . eye ( m ) # slack v a r i a b l e s
tableau [: m , -1] = b
tableau [ -1 , : n ] = -c
This step builds the **initial simplex tableau**: - First m rows corre-
spond to constraints. - Slack variables (identity matrix) are added to trans-
form inequalities into equalities. - Last column stores the RHS values. - The
last row is the objective function, negated for a maximization problem.
—
iteration = 0
while True :
p r i n t _ t a b l e a u ( tableau , i t e r a t i o n)
# Check for o p t i m a l i t y
if all ( tableau [ -1 , : -1] >= 0) :
print ( " \ nOptimal solution reached . " )
break
# Pivot column : most negative c o e f f i c i e n t in last
row
2
p i v o t _ c o l = np . argmin ( tableau [ -1 , : -1])
# Pivot row : minimum positive ratio of RHS to pivot
column
ratios = []
for i in range ( m ) :
if tableau [i , p i v o t _ c o l] > 0:
ratios . append ( tableau [i , -1] / tableau [i ,
p i v o t _ c o l ])
else :
ratios . append ( np . inf )
p i v o t _ r o w = np . argmin ( ratios )
p i v o t _ e l e m e n t = tableau [ pivot_row , p i v o t _ c o l]
# N o r m a l i z e pivot row
tableau [ pivot_row , :] /= p i v o t _ e l e m e n t
# E l i m i n a t e other entries in pivot column
for i in range ( m +1) :
if i != p i v o t _ r o w:
tableau [i , :] -= tableau [i , p i v o t _ c o l] *
tableau [ pivot_row , :]
i t e r a t i o n += 1
Explanation: 1. **Print the current tableau** for visual tracking. 2.
**Optimality check**: If all coefficients in the last row (except RHS) are
non-negative, the current solution is optimal. 3. **Pivot column**: Chosen
as the column with the most negative coefficient in the last row (entering
variable). 4. **Pivot row**: Determined by the minimum positive ratio
of RHS to pivot column value (leaving variable). 5. **Pivot element**:
The intersection of pivot row and column; used to normalize the pivot row.
6. **Row operations**: Make all other entries in the pivot column zero to
maintain feasibility. 7. **Increment iteration count** and repeat.
—
# Final solution
solution = np . zeros ( n + m )
for i in range ( m ) :
b a s i c _ v a r _ c o l = np . where ( tableau [i , : n + m ] == 1) [0]
if len ( b a s i c _ v a r _ c o l ) == 1:
solution [ b a s i c _ v a r _ c o l [0]] = tableau [i , -1]
3
print ( " \ nOptimal variable values : " )
for i in range ( n ) :
print ( f " x { i +1} = { solution [ i ]:.2 f } " )
print ( f " Optimal value of o b j e c t i v e function : { tableau
[ -1 , -1]:.2 f } " )
This final step: - Extracts the basic variables from the tableau by iden-
tifying columns with a single 1 and the rest 0. - Assigns the RHS values to
those basic variables. - Prints the final optimal solution for decision variables
and the optimal objective value.
—
This Python code allows the user to input an LPP in standard form
and applies the Simplex Method step-by-step, displaying the tableau at each
iteration. It helps visualize how the algorithm progresses towards the optimal
solution.