Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
4.6 kB
3
Indexable
Never
class simplex():
    def __init__(self, tableau, basic_var, integer=False):
        self.tableau = tableau
        self.basic_var = basic_var
        self.integer = integer
        self.solution = []
        self.z = 0
        self.optimal = False
        self.unbounded = False
        self.infeasible = False

    def print_solution(self):
        if self.solution != None:
            print('The tableau has an optimal solution x = {}\nThe optimal value is z = {}'.format(self.solution, self.z))
        elif self.unbounded:
            print('The tableau is unbounded')
        elif self.infeasible:
            print('The tableau is infeasible')

    #parameters: tableau, index t of the row, index h of the column
    def pivot_operation(self, t, h):
        '''
        Performs the pivot operations of the cell represented by the input values for row t and column h
        '''
        tableau = self.tableau
        #shape of the tableau
        m = tableau.shape[0]
        n = tableau.shape[1]
        pivot = tableau[t][h]
        #divide the pivot row by the pivot element
        for i in range(n):
            tableau[t][i] /= pivot
        #update all the other rows
        save = pivot
        for i in range(m):
            if i != t and tableau[i][h] != 0:
                save = tableau[i][h]
                for j in range(n):
                    tableau[i][j] -= save*tableau[t][j]
                    
                    
    def dual_simplex_method(self, verbose=0):
        '''
        Solve the model using the dual simplex method in tableau form.
        Parameters:
            - verbose: integer value to obtain the followig informations
                - 1 print the intermediate tableau
                - 2 show the pivot operations made
        '''
        tableau = self.tableau
        beta = self.basic_var
        #print the starting tableau
        if verbose:
            print('TABLEAU:\n{}\n'.format(tableau))
        iteration_count = 0
        #number of rows in the tableau
        m = tableau.shape[0]
        #number of columns in the tableau
        n = tableau.shape[1]
        #final cases
        infeasible = False
        optimal = False
        while optimal == False and infeasible == False:
            iteration_count+=1
            #get the vector of costs
            b_vector = [tableau[b][0] for b in range(1, m)]
            #verify if all the costs are >= 0, thus the tableau is in optimal form
            if all(b >= 0 for b in b_vector):
                optimal = True
                break
            else:
                #index of basic variable that will leave the basis
                t = 1
                #find the first negative variable with b < 0
                for i in range(1, m):
                    if i != 0 and tableau[i][0] < 0:
                        t = i
                        break
                if all(tableau[t][i] >= 0 for i in range(1, n)):
                    infeasible = True
                    break
                else:
                    #choose the variable that will enter the basis
                    min = 100000
                    h = 1
                    for i in range(1, n):
                        if tableau[t][i] < 0 and tableau[0][i] / abs(tableau[t][i]) < min:
                            min = tableau[0][i] / abs(tableau[t][i])
                            h = i
                    if verbose == 2:
                        print('Pivot operation on the cell(iteration_count: {1}): {0}\n'.format((t, h),iteration_count))
                    #pivot operation
                    self.pivot_operation(t, h)
                    #update the vector beta, containing the indices of the basis variables
                    beta[t-1] = h

            #Print the intermediate tableau
            if verbose:
                #print('TABLEAU:\n{}\n'.format(tableau))
                plt.figure(figsize = (75,5))
                hmp(tableau)
                plt.show()

        if optimal:
            #solution
            x = [0]*(n - 1)
            for i, b in enumerate(beta):
                x[b-1] = tableau[i+1][0]
                self.optimal = True
            self.solution = x
            self.z = -tableau[0][0]
            #print('The tableau has an optimal solution x = ', x)
        elif infeasible:
            self.infeasible = True
            #print('The tableau is infeasible')