4 laba

import sys
from Table_printer import print_table


def parse_file(filename):
    f = open(filename)
    lines = []
    for line in f:
        if not line.startswith('#'):
            lines.append(line.split('|'))
    return lines


def det2(table):
    return table[0][0]*table[1][1] - table[0][1]*table[1][0]


def get_submatrix(table, line, colon):
    matrix = []
    for i in range(len(table)):
        if i != line:
            matrix.append([])
            for j in range(len(table)):
                if j != colon:
                    matrix[-1].append(table[i][j])
    return matrix


def det(table):
    if len(table) == 1:
        return table[0][0]
    if len(table) == 2:
        return det2(table)
    result = 0
    for i in range(len(table)):
        result += ((-1)**i)*table[i][0]*det(get_submatrix(table, i, 0))
    return result


def transpose(table):
    matrix = []
    for i in range(len(table)):
        matrix.append([])
        for j in range(len(table)):
            matrix[-1].append(table[j][i])
    return matrix


def mul_matrix(table, c):
    for i in range(len(table)):
        for j in range(len(table)):
            table[i][j] *= c
    return table


def print_matrix(table):
    t = []
    t.append('split')
    for l in range(len(table)):
        t.append(table[l])
        t[-1].append(' ')
        t.append('split')
    print_table(t, 2*len(table) + 1, len(table) + 1)


def invertible_matrix(table):
    print(" Исходная матрица:", end='')
    print_matrix(table)
    d = det(table)
    print("\n det:    {}".format(d))
    if d == 0:
        print('Определитель равен нулю')
        sys.exit()
    d = 1 / d
    print(" det^-1: {}".format(d))
    table = transpose(table)
    new_table = []
    for i in range(len(table)):
        new_table.append([])
        for j in range(len(table)):
            new_table[-1].append((-1)**(i+j)*det(get_submatrix(table, i, j)))
    print("\n Матрица алгебраических дополнений:", end='')
    print_matrix(new_table)
    table = mul_matrix(new_table, d)
    print("\n Обратная матрица: ", end='')
    print_matrix(table)
    return table


def vector_mull_matrix(vector, matrix):
    if len(vector) != len(matrix):
        print("ERROR")
        sys.exit()
    result = []
    for i in range(len(vector)):
        result.append(0)
        for j in range(len(matrix)):
            result[i] += vector[j]*matrix[i][j]
    return result


def create_vector(size, index):
    v = []
    for i in range(size):
        if i == index:
            v.append(1)
        else:
            v.append(0)
    return v


class Table:
    def __init__(self):
        self.basis_coefficient = []
        self.basis_variable = []
        self.non_basis_coefficient = []
        self.non_basis_variable = []
        self.free_numbers = []
        self.table = []
        self.coefficient_in_function = {}
        self.delta = []
        self.Q = 0
        self.count_variables = 0
        self.A = {}
        self.const_free_numbers = []

    def input_table(self, filename):
        lines = parse_file(filename)
        counter = 1
        lines[-1].pop(0)
        for token in lines[-1]:
            self.non_basis_coefficient.append(float(token))
            self.non_basis_variable.append('x{}'.format(counter))
            self.coefficient_in_function.setdefault('x{}'.format(counter), float(token))
            counter += 1

        lines.pop(-1)
        for line in lines:
            self.basis_coefficient.append(0.0)
            self.basis_variable.append('x{}'.format(counter))
            self.coefficient_in_function.setdefault('x{}'.format(counter), 0.0)
            self.free_numbers.append(float(line.pop(-1)))

            counter += 1
            line.pop(0)
            self.table.append([])
            for token in line:
                self.table[-1].append(float(token))

        self.count_variables = counter - 1
        i = 0
        for x in self.non_basis_variable:
            self.A.setdefault(x, get_colon(self.table,i))
            i += 1
        i = 0
        for x in self.basis_variable:
            self.A.setdefault(x, create_vector(len(self.table),i))
            i += 1
        self.const_free_numbers.extend(self.free_numbers)

    def print_A(self):
        print(self.A)

    def update_delta(self):
        delta = []
        for i in range(len(self.non_basis_coefficient)):
            delta.append(scalar_multi(self.basis_coefficient, get_colon(self.table, i)) - self.non_basis_coefficient[i])
        self.delta = delta

    def update_Q(self):
        self.Q = scalar_multi(self.basis_coefficient, self.free_numbers)

    def stop(self):
        for val in self.delta:
            if val < 0:
                return False

        return True

    def get_resolution_colon(self):
        min = self.delta[0]
        min_index = 0
        for i in range(len(self.delta)):
            if min > self.delta[i]:
                min = self.delta[i]
                min_index = i
        return min_index

    def get_resolution_line(self, colon):
        min_index = -1
        min = 0
        for i in range(len(self.basis_coefficient)):
            if colon[i] > 0:
                min_index = i
                min = self.free_numbers[i] / colon[i]
                break

        for i in range(min_index, len(self.basis_coefficient)):
            if colon[i] > 0:
                if (self.free_numbers[i] / colon[i]) < min:
                    min = self.free_numbers[i] / colon[i]
                    min_index = i
        if min_index == -1:
            print("ERROR")
            sys.exit()
        return min_index

    def update_line(self, line_index, r):
        for i in range(len(self.non_basis_coefficient)):
            self.table[line_index][i] /= r
        self.free_numbers[line_index] /= r

    def update_colon(self,colon_index,r):
        for i in range(len(self.basis_coefficient)):
            self.table[i][colon_index] /= r
            self.table[i][colon_index] *= -1

    def update_free_number(self, line_index, colon_index):
        for i in range(len(self.free_numbers)):
            if i != line_index:
                self.free_numbers[i] = rectangle_rule(self.free_numbers[i], self.table[i][colon_index],
                                                      self.free_numbers[line_index], self.table[line_index][colon_index])

    def update_other_element(self, line_index, colon_index):
        self.update_free_number(line_index, colon_index)
        for i in range(len(self.basis_coefficient)):
            for j in range(len(self.non_basis_coefficient)):
                if i != line_index and j != colon_index:
                    self.table[i][j] = rectangle_rule(self.table[i][j],          self.table[i][colon_index],
                                                      self.table[line_index][j], self.table[line_index][colon_index])

    def update_coefficient_in_function(self):
        for i in range(len(self.basis_variable)):
            self.coefficient_in_function[self.basis_variable[i]] = self.free_numbers[i]
        for i in range(len(self.non_basis_variable)):
            self.coefficient_in_function[self.non_basis_variable[i]] = 0

    def print_function(self):
        print("\n Целевая функция: ")
        X = list(self.coefficient_in_function.keys())
        print(' f(',end='')
        for i in range(len(X) - 1):
            print('{}, '.format(X[i]), end='')
        print('{})'.format(X[-1]), end=' = ')
        print('f(', end='')
        for i in range(len(X) - 1):
            print('{}, '.format(self.coefficient_in_function[X[i]]), end='')
        print('{})'.format(self.coefficient_in_function[X[-1]]), end=' = ')
        print(self.Q)

    def update_table(self):
        if self.stop():
            return
        print(" Текущее решение не оптимально. Перестроим симплекс таблицу\n Найдем разрешающий элемент:")
        j = self.get_resolution_colon()
        i = self.get_resolution_line(get_colon(self.table, j))
        r = self.table[i][j]
        temp_x_coef = self.basis_coefficient[i]
        temp_x = self.basis_variable[i]
        self.basis_coefficient[i] = self.non_basis_coefficient[j]
        self.basis_variable[i] = self.non_basis_variable[j]
        self.non_basis_coefficient[j] = temp_x_coef
        self.non_basis_variable[j] = temp_x
        print(' Разрешающий столбец: {} Разрешающая строка: {} Разрешающий элемент {}'.format(j, i, r))
        self.update_other_element(i, j)
        self.update_colon(j, r)
        self.update_line(i, r)
        self.table[i][j] = 1.0 / r
        self.update_delta()
        self.update_Q()
        self.update_coefficient_in_function()
        self.print_table()

    def dual_solution(self):
        dual_matrix = []
        for x in self.basis_variable:
            dual_matrix.append(self.A[x])
        dual_matrix = invertible_matrix(dual_matrix)
        result = vector_mull_matrix(self.basis_coefficient, dual_matrix)
        print(' Умножим вектор коэффициентов при базисных векторах на получившуюся матрицу:\n')
        print(' В результате получим вектор-столбец значений двойственной задачи переменных двойственной задачи\n ' + str(result))
        print("\n min(g(y)) = max(f(x)) = ",end='')
        print(scalar_multi(self.const_free_numbers, result))

    def print_table(self):
        t = list()
        t.append('split')
        t.append(['  ', ' свободные '])
        t[1].extend(self.non_basis_coefficient)
        t[1].append(' ')
        t[1].append(' ')
        t.append('split')
        t.append([' базис ', '  '])
        t[3].extend(self.non_basis_variable)
        t[3].append(' А ')
        t[3].append(' ')
        t.append('split')
        for i in range(len(self.basis_variable)):
            t.append([self.basis_coefficient[i], self.basis_variable[i]])
            for j in range(len(self.non_basis_coefficient)):
                t[-1].append(self.table[i][j])
            t[-1].append(self.free_numbers[i])
            t[-1].append(' ')
            t.append('split')

        t.append([' '])
        t[-1].append('   f ')
        for i in range(len(self.non_basis_coefficient)):
            t[-1].append(self.delta[i])
        t[-1].append(self.Q)
        t[-1].append(' ')
        t.append('split')
        print_table(t, 2*len(self.basis_variable) + 7, len(self.non_basis_variable) + 4)
        self.print_function()


def get_colon(table, index):
    colon = []
    for line in table:
        colon.append(line[index])
    return colon


def scalar_multi(C, A):
    if len(C) != len(A):
        print('ERROR 1')
        return
    result = 0
    for i in range(len(C)):
        result += C[i] * A[i]
    return result


def rectangle_rule(x1, x2, x3, x4):
    return (x1 * x4 - x2 * x3) / x4


t = Table()
t.input_table('input2.txt')
t.update_delta()
t.update_Q()
t.print_table()
while not t.stop():
    t.update_table()
    print()

t.dual_solution()