Skip to content

Instantly share code, notes, and snippets.

@kmod-midori
Created May 15, 2022 11:19
Show Gist options
  • Save kmod-midori/475a29176e52e4182a47e8f0653a8ba4 to your computer and use it in GitHub Desktop.
Save kmod-midori/475a29176e52e4182a47e8f0653a8ba4 to your computer and use it in GitHub Desktop.
Solving linear programming problems using simplex method
from fractions import Fraction
def to_frac(item):
if isinstance(item, (int, float)) and not isinstance(item, bool):
return Fraction(item)
elif isinstance(item, tuple):
(num, denom) = item
return Fraction(num, denom)
else:
raise TypeError("Invalid type for fraction")
# Basic variables (left, column)
basic = ['x4', 'x5', 'x6', 'z']
# Nonbasic variables (top, row)
nonbasic = ['x1', 'x2', 'x3']
coeff = [
[2, 3, 1],
[4, 1, 2],
[3, 4, 2],
[-5,-4,-3]
]
coeff = list(map(lambda row: list(map(to_frac, row)), coeff))
rhs = [5, 11, 8, 0]
rhs = list(map(to_frac, rhs))
while True:
objective_row = coeff[-1]
pivot = None
for pivot_col_value in sorted(objective_row):
if pivot_col_value >= 0: # Only choose negative values
break
pivot_col_index = objective_row.index(pivot_col_value)
pivot_row_index = None
min_ratio = 99999.0
for i, coeff_row in enumerate(coeff[:-1]):
coeff_row_value = coeff_row[pivot_col_index]
if coeff_row_value <= 0: # Only choose positive values
continue
ratio = rhs[i] / coeff_row_value
if ratio < min_ratio:
min_ratio = ratio
pivot_row_index = i
if pivot_row_index is not None:
pivot = (pivot_row_index, pivot_col_index)
break
(pivot_row, pivot_col) = pivot
pivot_value = coeff[pivot_row][pivot_col]
print("Pivot: ({}, {})".format(pivot_row + 1, pivot_col + 1))
# Interchange variables
(basic[pivot_row], nonbasic[pivot_col]) = (nonbasic[pivot_col], basic[pivot_row])
# Update other items, ignore pivot row and column
for i, coeff_row in enumerate(coeff):
if i == pivot_row:
continue
for j, value in enumerate(coeff_row):
if j == pivot_col:
continue
coeff[i][j] = coeff[i][j] - (coeff[i][pivot_col] * coeff[pivot_row][j] / pivot_value)
for i, value in enumerate(rhs):
if i == pivot_row:
continue
rhs[i] = rhs[i] - (rhs[pivot_row] * coeff[i][pivot_col] / pivot_value)
# Update pivot
coeff[pivot_row][pivot_col] = 1 / pivot_value
# Update pivot row
for i, value in enumerate(coeff[pivot_row]):
if i != pivot_col:
coeff[pivot_row][i] = coeff[pivot_row][i] / pivot_value
rhs[pivot_row] = rhs[pivot_row] / pivot_value
# Update pivot column
for i, coeff_row in enumerate(coeff):
if i != pivot_row:
coeff[i][pivot_col] = -(coeff[i][pivot_col] / pivot_value)
# Print out
print(" ", end="")
print(" ".join(nonbasic))
for i, row in enumerate(coeff):
print(basic[i], end = " ")
for j, value in enumerate(row):
if value.denominator == 1:
print(value.numerator, end = " ")
else:
print("{}/{}".format(value.numerator, value.denominator), end=" ")
print(rhs[i])
if min(coeff[-1]) > 0:
print("Solution found!")
break
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment