import numpy as np
from fractions import Fraction
from tabulate import tabulate
from sympy import symbols, simplify, oo
M = symbols('M')
# 초기 설정
obj = [20, 10, 0, M, 0, M, 0]
A = [
[5, 1, -1, 1, 0, 0, 6],
[2, 2, 0, 0, -1, 1, 8],
]
basic = np.array([4, 6]) - 1 # x5, x6
non_basic = np.array([1, 2, 3, 5]) - 1 # x1, x2, x3, x4
def to_fraction(array):
return [Fraction(x).limit_denominator() if isinstance(x, (int, float)) else x for x in array]
# 초기 배열을 분수로 변환
obj = to_fraction(obj)
A = [to_fraction(row) for row in A]
def print_table():
headers = ["", "Z"] + [f"x{i+1}" for i in range(len(obj)-1)] + ["RHS"]
table = [["Z", 1] + [str(x) for x in obj]]
for i in range(len(A)):
row = [f"x{basic[i]+1}", 0] + [str(x) for x in A[i]]
table.append(row)
print("\nCurrent Simplex Tableau:")
print(tabulate(table, headers=headers, tablefmt="grid"))
def adjust_obj_for_big_m():
global obj
print("\nAdjusting Objective Function for Big M Method")
for i in range(len(basic)):
basic_var_idx = basic[i]
if obj[basic_var_idx] != 0: # 인공변수일 경우(M이 포함된 경우)
factor = obj[basic_var_idx]
obj = [simplify(obj[j] - factor * A[i][j]) for j in range(len(obj))]
def simplex():
global obj, A, basic, non_basic
adjust_obj_for_big_m()
print_table()
iteration = 1
while True:
print(f"\nIteration {iteration}")
print("=" * 60)
print_table()
# 음의 계수 찾기 (entering variable)
eval_obj = [x.evalf(subs={M: 1e6}) if x.has(M) else float(x) for x in obj[:-1]]
min_rc_idx = min(range(len(obj)-1), key=lambda j: eval_obj[j])
if eval_obj[min_rc_idx] >= 0:
print("Optimal solution reached.")
# 최적 해 출력
solution = {f"x{i+1}": 0 for i in range(len(obj)-1)}
for i, var_idx in enumerate(basic):
solution[f"x{var_idx+1}"] = A[i][-1]
print("Optimal Solution:")
for var, val in solution.items():
print(f"{var} = {val}")
print(f"Objective Value = {obj[-1]}")
break
# Pivot 열 선택 및 ratio 계산
ratios = []
for i in range(len(A)):
if A[i][min_rc_idx] > 0:
ratios.append((A[i][-1] / A[i][min_rc_idx], i))
else:
ratios.append((oo, i))
min_ratio, pivot_row = min(ratios)
if min_ratio == oo:
print("Unbounded solution detected.")
break
print(f"Entering variable: x{min_rc_idx + 1}")
print(f"Leaving variable: x{basic[pivot_row] + 1}")
# Pivot 연산
pivot = A[pivot_row][min_rc_idx]
A[pivot_row] = [simplify(x / pivot) for x in A[pivot_row]]
# 다른 행 업데이트
for i in range(len(A)):
if i != pivot_row:
factor = A[i][min_rc_idx]
A[i] = [simplify(A[i][j] - factor * A[pivot_row][j]) for j in range(len(obj))]
# 목적함수 업데이트
factor = obj[min_rc_idx]
obj = [simplify(obj[j] - factor * A[pivot_row][j]) for j in range(len(obj))]
# 기본 변수 업데이트
leaving_var = basic[pivot_row]
basic[pivot_row] = min_rc_idx
non_basic[non_basic == min_rc_idx] = leaving_var
iteration += 1
simplex()
