simplex_algo.py

def put_surplus_var(tab):
	rows = len(tab)
	cols = len(tab[0])

	cols_add = rows - 1

	tab = [x + [0]*cols_add for x in tab]	
	for i in range(1, rows):
		for j in range(1, rows):
			if i ==j:
				tab[i][j+cols-1] = 1
			else:
				tab[i][j+cols-1] = 0
	return tab

def find_pivot_col(tab):
	ret = min(tab[0])
	if ret >= 0:
		return -1
	else:
		return tab[0].index(ret)

def find_pivot_row(tab, col):
	pivot_row =0
	min = -1
	rows = len(tab)
	cols = len(tab[0])

	for i in range(1, rows):
		ratio = tab[i][0]/tab[i][col]
		if ((ratio > 0 and ratio < min) or min < 0):
			min = ratio
			pivot_row = i

	if min == -1:
		return -1

	return pivot_row

def equals(a,b):
	if a-b < 1.0e-5:
		return True
	return False


def pivot(tab, row, col):
	rows = len(tab)
	cols = len(tab[0])
	pivot = tab[row][col]
	
	for i in range(cols):
		tab[row][i] /= pivot

	for i in range(rows):
		mul = tab[i][col]
		if i == row:
			continue
		for j in range(cols):
			tab[i][j] -= mul*tab[row][j]

	return tab

	
def pr_tab(tab):
	print('\n'.join(['\t'.join(['{:4}'.format(item) for item in row]) for row in  tab]))

def read_usr_input():
	m = int(input("Enter matrix row sz: "))
	n = int(input("Enter matrix col sz: "))

	tab = []
	print "Now, enter the elements:"
	for i in range(m):
		for j in range(n):
			tab.append(float(input()))

	return [tab[i:i+n] for i in range(0, len(tab), n)]
	



tab = read_usr_input()
print tab
# tab=[
# 	[0.0 , -0.5 , -3.0 ,-1.0 , -4.0],  # Max: z = 0.5*x + 3*y + z + 4*w,
#     [40.0 ,  1.0 ,  1.0 , 1.0 ,  1.0,], # x + y + z + w <= 40 
#     [10.0 , -2.0 , -1.0 , 1.0 ,  1.0,], # -2x - y + z + w <= 10
#     [10.0 ,  0.0 ,  1.0 , 0.0 , -1.0,], # y - w <= 10
#]	

 
surplus_tab = put_surplus_var(tab)

iter=1
while(iter):
	p_col = find_pivot_col(surplus_tab)
	if p_col < 0:
		break

	p_row = find_pivot_row(surplus_tab, p_col)
	if p_row < 0:
		print "unbounded"
		break

	print "pivot_row =", p_row, "pivot_col =", p_col

	surplus_tab = pivot(surplus_tab, p_row, p_col)

	pr_tab(surplus_tab)

	if (iter > 100):
		print "100+ iterations...Abort! "
		break
	print "iteration#", iter
	iter+=1

print "Max is", surplus_tab[0][0]