simplex.py

from fractions import Fraction

def fraccionalizar(mat):
	for f in xrange(len(mat)):
		for c in xrange(len(mat[0])):
			mat[f][c] = Fraction(mat[f][c])
	return mat

def mostrar(mat):
	for f in mat:
		print '\t'.join(str(c) for c in f)

def simplex(mat):
	mostrar(mat)
	print
	
	nf = len(mat)
	nc = len(mat[0])
	
	if all(mat[-1][c] >= 0 for c in xrange(nc - 1)):
		return mat
	
	# columna de trabajo
	ct = 0
	for c in xrange(1, nc - 1):
		if mat[-1][c] < mat[-1][ct]:
			ct = c
	
	# fila de trabajo
	ft = None
	
	for f in xrange(nf - 1):
		if mat[f][ct] <= 0:
			continue
		vf = mat[f][-1] / mat[f][ct]
		if vf < 0:
			continue
		if ft is None or vf < ft[1]:
			ft = f, vf
	
	ft = ft[0]
	
	raw_input()
	
	# volver mat[ft][ct] == 1
	tmp = mat[ft][ct]
	for c in xrange(nc):
		mat[ft][c] /= tmp
	
	# volver mat[..][ct] == 0
	for f in xrange(nf):
		if f == ft:
			continue
		tmp = -mat[f][ct]
		for c in xrange(nc):
			mat[f][c] += tmp * mat[ft][c]
	
	return simplex(mat)

def minimizar(mat):
	return simplex(mat)

def minimizar_conFA(mat):
	return minimizar(minimizar(mat)[:-1])

def maximizar(mat):
	for i in xrange(len(mat[-1])):
		mat[-1][i] *= -1
	return simplex(mat)

def maximizar_conFA(mat):
	return maximizar(minimizar(mat)[:-1])

if __name__ == '__main__':
	mat = [
		[3, -1, 2, 1, 0, 0, 7],
		[-2, 4, 0, 0, 1, 0, 12],
		[-4, 3, 8, 0, 0, 1, 10],
		[1, -3, -2, 0, 0, 0, 0]
	]
	
	fraccionalizar(mat)
	
	#minimizar(mat)
	
	mat = [
		[1, 1, 1, 0, 0, 0, 10],
		[1, 2, 0, -1, 1, 0, 8],
		[-1, 1, 0, 0, 0, 1, 2],
		[2, 2, 0, 0, 0, 0, 0],
		[0, -3, 0, 1, 0, 0, -10]
	]
	
	fraccionalizar(mat)
	
	#maximizar_conFA(mat)
	
	mat = [
		[1, 0, 1, 0, 0, 4],
		[0, 2, 0, 1, 0, 12],
		[3, 2, 0, 0, 1, 12],
		[3, 3, 0, 0, 0, 0]
	]
	
	maximizar(fraccionalizar(mat))
	
	mat = [
		[1, 0, 1, 0, 0, 4],
		[0, 2, 0, 1, 0, 12],
		[3, 2, 0, 0, 1, 18],
		[3, 2, 0, 0, 0, 0]
	]
	
	#maximizar(fraccionalizar(mat))