Spaces:
Build error
Build error
| # a series of functions to perform the simplex tableau method | |
| from enum import Enum | |
| from typing import Callable, Any, Union | |
| import numpy as np | |
| array = np.ndarray | list[int] | |
| class Extremum(Enum): | |
| MAX = True | |
| MIN = False | |
| # noinspection PyPep8Naming | |
| class SimplexTableau: | |
| def __init__(self, c, A: np.ndarray, b, sigma, z0, extremum: Extremum, dual: bool, variables: list[str], | |
| basic: list[int], arti: list[int], vectorize: Union[np.vectorize, Callable[[Any], np.ndarray]] = None): | |
| self.m, self.n = A.shape | |
| assert len(c) == self.n == len(variables), 'c, A, and variables must have the same length' | |
| assert len(b) == self.m, 'A and b must have the same number of rows' | |
| self.extremum = extremum | |
| self.dual = dual | |
| self.c = c | |
| self.A = A | |
| self.variables = variables | |
| self.basic = basic | |
| self.arti = arti | |
| self.z0 = z0 | |
| self.sigma = sigma | |
| self.b = b | |
| self.vectorize = vectorize | |
| if self.dual: | |
| self.pivot = [-1, np.argmin(self.b)] | |
| ratios = [self.sigma[i] / self.A[self.pivot[1], i] if i not in self.basic else np.inf for i in | |
| range(self.n)] | |
| self.ratios = [r if r != np.inf and r >= 0 else np.inf for r in ratios] | |
| self.pivot[0] = np.argmin(self.ratios) | |
| else: | |
| self.pivot = [np.argmax(self.sigma) if self.extremum.value else np.argmin(self.sigma), -1] | |
| self.ratios = [self.b[i] / A[i, self.pivot[0]] if A[i, self.pivot[0]] > 0 else np.inf for i in | |
| range(self.m)] | |
| self.pivot[1] = np.argmin([r if r != np.inf and r >= 0 else np.inf for r in self.ratios]) | |
| def init_tableau(c: array, A: np.ndarray | list[list[int]], b: array, extremum: Extremum = Extremum.MAX, | |
| dual: bool = False, all_vars: list[str] = None, basic_vars: list[int] = None, | |
| arti_vars: list[int] = None, vectorize: Union[np.vectorize, Callable[[Any], np.ndarray]] = None, | |
| solve: bool = True): | |
| c = vectorize(c) if vectorize else np.array([float(x) for x in c]) | |
| b = vectorize(b) if vectorize else np.array([float(x) for x in b]) | |
| A = vectorize(A) if vectorize else np.array([[float(x) for x in row] for row in A]) | |
| m, n = A.shape | |
| if all_vars is None: | |
| all_vars = [f'x_{i}' for i in range(1, n + 1)] | |
| if basic_vars is None: | |
| basic_vars = SimplexTableau.calc_basic_variables(A) | |
| b = np.linalg.solve(A[:, basic_vars], b) if solve else b | |
| sigma = c - np.dot(c[basic_vars], A) | |
| z0 = -np.dot(c[basic_vars], b) | |
| return SimplexTableau(c, A, b, sigma, z0, extremum, dual, all_vars, basic_vars, arti_vars, vectorize) | |
| def calc_basic_variables(A): | |
| _, r = np.linalg.qr(A.T) | |
| return [i for i in range(len(r)) if np.allclose(r[i], 0)] | |
| def __iter__(self): | |
| return self | |
| def __next__(self): | |
| """ | |
| calculate the next iteration of the simplex tableau | |
| :rtype: SimplexTableau | |
| """ | |
| # check if all sigma values are negative(positive) for maximization(minimization) problem | |
| if self.dual: | |
| if all(self.b > 0): | |
| raise StopIteration('Optimal solution found.') | |
| elif all(x <= 0 if self.extremum.value else x >= 0 for x in self.sigma): | |
| if self.arti is None: | |
| raise StopIteration('Because no artificial variables are passed, solution can\'t determined') | |
| # check if basic variables contains non-zero artificial variables | |
| if any(self.basic[i] in self.arti for i in range(self.m) if self.b[i] != 0): | |
| raise StopIteration('No feasible solution exists.') | |
| # check if contains nonbasic variables with zero check coefficients | |
| if any(self.sigma[i] != 0 for i in range(self.n) if i not in self.basic): | |
| raise StopIteration('There contains infinite optimal solutions.') | |
| else: | |
| raise StopIteration('Optimal solution found.') | |
| # check if all ratios are negative | |
| if all(x <= 0 for x in self.ratios): | |
| raise StopIteration('Unbounded solution found.') | |
| matrix = self.vectorize(np.eye(self.m)) if self.vectorize else np.eye(self.m) | |
| matrix[:, self.pivot[1]] = -self.A[:, self.pivot[0]] / self.A[self.pivot[1], self.pivot[0]] | |
| matrix[self.pivot[1], self.pivot[1]] = 1 / self.A[self.pivot[1], self.pivot[0]] | |
| self.z0 = self.z0 - self.b[self.pivot[1]] * self.sigma[self.pivot[0]] / self.A[self.pivot[1], self.pivot[0]] | |
| self.sigma -= self.A[self.pivot[1]] * self.sigma[self.pivot[0]] / self.A[self.pivot[1], self.pivot[0]] | |
| self.A = np.dot(matrix, self.A) | |
| self.b = np.dot(matrix, self.b) | |
| self.basic[self.pivot[1]] = self.pivot[0] | |
| if self.dual: | |
| self.pivot[1] = np.argmin(self.b) | |
| ratios = [self.sigma[i] / self.A[self.pivot[1], i] if i not in self.basic else np.inf for i in | |
| range(self.n)] | |
| self.ratios = [r if r != np.inf and r >= 0 else np.inf for r in ratios] | |
| self.pivot[0] = np.argmin(self.ratios) | |
| else: | |
| self.pivot[0] = np.argmax(self.sigma) if self.extremum.value else np.argmin(self.sigma) | |
| self.ratios = [self.b[i] / self.A[i, self.pivot[0]] if self.A[i, self.pivot[0]] > 0 else np.inf for i in | |
| range(self.m)] | |
| self.pivot[1] = np.argmin([r if r != np.inf and r >= 0 else np.inf for r in self.ratios]) | |
| return self | |
| def __copy__(self): | |
| return SimplexTableau(self.c, self.A, self.b, self.sigma, self.z0, self.extremum, self.dual, self.variables, | |
| self.basic, self.arti) | |
| def __str__(self): | |
| """ | |
| return a string representation of the simplex tableau | |
| +----+----+----+-------------------+-------+ | |
| | | | | | | | |
| | CB | Xb | b | A | ratio | | |
| | | | | | | | |
| +----+----+----+-------------------+-------+ | |
| | | | -z | sigma | | | |
| +----+----+----+-------------------+-------+ | |
| :return: | |
| """ | |
| cb_strs = [str(x) for x in self.c[self.basic]] | |
| xb_strs = [str(self.variables[x]) for x in self.basic] | |
| b_strs = [str(x) for x in self.b] | |
| a_strs = [[str(x) for x in row] for row in self.A] | |
| sigma_strs = [str(x) for x in self.sigma] | |
| ratio_strs = [str(x) if x != np.inf and x >= 0 else '-' for x in self.ratios] | |
| cb_len = max(len(x) for x in cb_strs) + 2 | |
| xb_len = max(len(x) for x in xb_strs) + 2 | |
| b_len = max(len(x) for x in b_strs + [str(self.z0)]) + 2 | |
| a_len = [max(len(x) for x in col) for col in zip(*a_strs + [sigma_strs])] | |
| ratio_len = max(len(x) for x in ratio_strs) + 2 | |
| divider = f'+{"-" * cb_len}+{"-" * xb_len}+{"-" * b_len}+{"-" * (sum(a_len) + self.n + 1)}+{"-" * ratio_len}+\n' | |
| result = divider | |
| x, y = self.pivot | |
| for i, (cb, xb, b, a, ratio) in enumerate(zip(cb_strs, xb_strs, b_strs, a_strs, ratio_strs)): | |
| # ratio display '-' if it is inf or negative | |
| if i == y: | |
| # use [] to highlight the pivot number | |
| a_str = ' '.join(f'{z:^{a_len[j]}}' for j, z in enumerate(a[:x])) + \ | |
| f'[{a[x]:^{a_len[x]}}]' + \ | |
| ' '.join(f'{z:^{a_len[j]}}' for j, z in enumerate(a[x + 1:])) | |
| if a_str[0] != '[': | |
| a_str = ' ' + a_str | |
| if a_str[-1] != ']': | |
| a_str += ' ' | |
| else: | |
| a_str = ' ' + ' '.join(f'{z:^{a_len[j]}}' for j, z in enumerate(a)) + ' ' | |
| result += f'|{cb:^{cb_len}}|{xb:^{xb_len}}|{b:^{b_len}}|{a_str}|{ratio:^{ratio_len}}|\n' | |
| result += divider | |
| sigma_str = ' '.join(f'{x:^{a_len[j]}}' for j, x in enumerate(sigma_strs)) | |
| z0_str = str(self.z0) | |
| result += f'|{"":^{cb_len}}|{"":^{xb_len}}|{z0_str:^{b_len}}| {sigma_str} |{"":^{ratio_len}}|\n' | |
| result += divider | |
| return result | |