# -*- coding: utf-8 -*-
from fractions import Fraction
from itertools import count, izip
print_width = 5 #увеличить если дроби не будут влезать
m = 3 #количество уравнений
n = 5 #количество переменных
basis = [3,4,5] #номера базисных переменных (считаются с единицы)
C = [2, 3, 0, 0, 0] #коеффициенты целевой функции
table = [[-1, -5, 1, 0, 0, -16], #сама симплекс-таблица,
         [-3, -2, 0, 1, 0, -12], #должна быть в почти-каноничной форме
         [-2, -4, 0, 0, 1, -16]] #и с уже найденным опорным базисом
#поехали, епт

table = [[Fraction(x) for x in row] for row in table]
C = [Fraction(x) for x in C]
basis = [x-1 for x in basis]

def pretty_print(matrix,basis):
    width = print_width
    print  "Cb".rjust(width),"Xb".rjust(width)," ".join(("x%d"%(i+1)).rjust(width) for i in xrange(n)),"bt".rjust(width)
    for line in zip(basis,matrix):
        (xb,row) = line
        print str(C[xb]).rjust(width),("x%d"%(xb+1)).rjust(width),
        for elem in row:
            print str(elem).rjust(width),
        print ""
def pretty_print2(name,array):
    width = print_width
    print "%s is: %s"%(name," ".join(str(x).rjust(width) for x in array).strip())

def make_basis(matrix,r,c):
    (h,w) = (m,n+1)
    b_row = matrix[r]
    newb = b_row[c]
    for i in xrange(w):
        b_row[i] /= newb
    for i,row in enumerate(matrix):
        if i!=r:
            if row[c]!=0:
                multiplier = row[c]
                for j in xrange(w):
                    row[j] = row[j] - multiplier*b_row[j]
iteration = 1
while True:
    print "###ITERATION %d###"   %iteration
    pretty_print(table,basis)
    rowmin,out_basis = min(izip(table, count()),key=lambda x:x[0][-1])
    delta = [(C[i] - sum(C[basis[j]]*table[j][i] for j in xrange(m))) for i in xrange(n)]
    pretty_print2("\nDelta", delta)
    deltamin = min(delta)
    if deltamin>=0:
        if rowmin[-1]>=0:
            print "All delta are positive and so are betta, plan is optimal!"
            break
        else:
            print "Getting x%d out of basis"%(basis[out_basis]+1)
    else:
        print "Another Whoops"
    gamma = [(-1 if rowmin[i]>=0 else abs(delta[i]/rowmin[i])) for i in xrange(n)]
    pretty_print2("Gamma", gamma)
    in_basis = -1
    min_gamma = None
    for i,val in enumerate(gamma):
        if val!=-1:
            if min_gamma is None:
                min_gamma = val
                in_basis = i
            elif val<min_gamma:
                min_gamma = val
                in_basis = i
    if in_basis==-1:
        print "Unlimited probably, no solution"
        break
    print "Inserting x%d into basis"%(in_basis+1)
    basis[out_basis] = in_basis
    make_basis(table,out_basis,in_basis)
    iteration = iteration+1
raw_input("Oh noes")