"""
solving the equation:
maximize z = 200X + 400Y
X/40 + Y/60 <= 1.0
X/50 + Y/50 <= 1.0
"""
# the z is dropped out of the table, as one couldn't enter with it anyway.
tab = [
[ -200, -400, 0.0, 0.0, 0.0],
[1.0/40, 1.0/60, 1.0, 0.0, 1.0],
[1.0/50, 1.0/50, 0.0, 1.0, 1.0],
]
def simplex(tab):
objective = tab[0]
entering = objective.index(min(objective)) # we are maximizing because (min)
if objective[entering] >= 0.0:
return False, tab # solved if reached
cand = []
vals = []
# picking the candinates and calculating b/c for each, then picking the smallest
for i, row in enumerate(tab[1:], 1):
x = row[entering]
if x > 0.0:
cand.append(i)
vals.append(row[-1] / x)
leaving = cand[vals.index(min(vals))]
# elementary row operation multiplication: divide by nonzero constant
pivot = tab[leaving]
v = pivot[entering]
for i in range(len(pivot)):
pivot[i] /= v
# elementary row operation addition: replace by sum of itself and multiple of another row
for j, row in enumerate(tab):
if j != leaving:
v = row[entering]
for i in range(len(pivot)):
row[i] -= v * pivot[i]
return True, tab
def print_table(tab):
for row in tab:
print(', '.join("%10.4f" % x for x in row))
print('')
print_table(tab)
cont = True
while cont:
cont, tab = simplex(tab)
print_table(tab)
# the solutions reads out on the right up corner of the table.