লিনিয়ার প্রোগ্রামিং — সিমপ্লেক্স মেথড

# maximize Z = 3x + 5y
# s.t.  x        <= 4
#           2y   <= 12
#       3x + 2y  <= 18
#       x, y >= 0

# tableau columns: [x, y, s1, s2, s3, RHS]
tableau = [
    [1, 0, 1, 0, 0, 4],
    [0, 2, 0, 1, 0, 12],
    [3, 2, 0, 0, 1, 18],
]
obj = [-3, -5, 0, 0, 0, 0]
basis = ['s1', 's2', 's3']
var_names = ['x', 'y', 's1', 's2', 's3']

def print_tableau(tableau, obj, basis, iteration):
    print(f"-- ইটারেশন {iteration} --")
    header = "      " + "".join(f"{v:>8}" for v in var_names) + f"{'RHS':>8}"
    print(header)
    for bi, row in zip(basis, tableau):
        print(f"{bi:>5} " + "".join(f"{c:8.3f}" for c in row))
    print(f"{'Z':>5} " + "".join(f"{c:8.3f}" for c in obj))
    print()

iteration = 0
print_tableau(tableau, obj, basis, iteration)

while min(obj[:-1]) < -1e-9:
    pivot_col = obj.index(min(obj[:-1]))          # এন্টারিং ভেরিয়েবল
    ratios = []
    for i, row in enumerate(tableau):
        if row[pivot_col] > 1e-9:
            ratios.append((row[-1] / row[pivot_col], i))
    ratios.sort()
    pivot_row = ratios[0][1]                        # রেশিও টেস্ট (লিভিং ভেরিয়েবল)

    pivot_val = tableau[pivot_row][pivot_col]
    tableau[pivot_row] = [v / pivot_val for v in tableau[pivot_row]]
    for i, row in enumerate(tableau):
        if i != pivot_row:
            factor = row[pivot_col]
            tableau[i] = [row[j] - factor * tableau[pivot_row][j] for j in range(len(row))]
    factor = obj[pivot_col]
    obj = [obj[j] - factor * tableau[pivot_row][j] for j in range(len(obj))]

    basis[pivot_row] = var_names[pivot_col]
    iteration += 1
    print_tableau(tableau, obj, basis, iteration)

solution = {v: 0.0 for v in var_names}
for bi, row in zip(basis, tableau):
    solution[bi] = row[-1]

print("=== অপ্টিমাল সমাধান ===")
print(f"x = {solution['x']:.4f}, y = {solution['y']:.4f}")
print(f"Z (সর্বোচ্চ মান) = {obj[-1]:.4f}")

x, y = solution['x'], solution['y']
print(f"চেক: x = {x:.4f} <= 4 ? {x <= 4 + 1e-9}")
print(f"চেক: 2y = {2*y:.4f} <= 12 ? {2*y <= 12 + 1e-9}")
print(f"চেক: 3x+2y = {3*x + 2*y:.4f} <= 18 ? {3*x + 2*y <= 18 + 1e-9}")