Python script to execute linear programming with Simplex method.

linear_programming_simplex.py

#! /usr/local/bin/python3.6
"""
Linear programming with Simplex method
"""
import sys
import traceback


class LinearProgrammingSimplex:
    N_ROW = 4  # Number of rows
    N_COL = 6  # Number of columns
    N_VAR = 2  # Number of variants

    def __init__(self):
        self.a = [
            [ 1.0,  2.0,  1.0,  0.0,  0.0, 14.0],
            [ 1.0,  1.0,  0.0,  1.0,  0.0,  8.0],
            [ 3.0,  1.0,  0.0,  0.0,  1.0, 18.0],
            [-2.0, -3.0,  0.0,  0.0,  0.0,  0.0]
        ]

    def exec(self):
        """ Execution """
        try:
            while True:
                mn, y = self.__select_col(9999)
                if mn >= 0:
                    break
                mn, x = self.__select_row(9999, y)
                self.__divide_pivot_var(x, y)
                self.__sweep_out(x, y)
            self.__display()
        except Exception as e:
            raise

    def __select_col(self, mn):
        """ Column selection

        :param  float mn
        :return list: [float, int]
        """
        y = 0
        try:
            for k in range(self.N_COL - 1):
                if self.a[self.N_ROW - 1][k] >= mn:
                    continue
                mn, y = self.a[self.N_ROW - 1][k], k
            return [mn, y]
        except Exception as e:
            raise

    def __select_row(self, mn, y):
        """ Row selection

        :param  float mn
        :param  int    y
        :return list: [float, int]
        """
        x = 0
        try:
            for k in range(self.N_ROW - 1):
                p = self.a[k][self.N_COL - 1] / self.a[k][y]
                if self.a[k][y] <= 0 or p >= mn:
                    continue
                mn, x = p, k
            return [mn, x]
        except Exception as e:
            raise

    def __divide_pivot_var(self, x, y):
        """ Pivot coefficient division by p

        :param int x
        :param int y
        """
        try:
            p = self.a[x][y]
            for k in range(self.N_COL):
                self.a[x][k] /= p
        except Exception as e:
            raise

    def __sweep_out(self, x, y):
        """ Pivot sweeping out

        :param int x
        :param int y
        """
        try:
            for k in range(self.N_ROW):
                if k == x:
                    continue
                d = self.a[k][y]
                for j in range(self.N_COL):
                    self.a[k][j] -= d * self.a[x][j]
        except Exception as e:
            raise

    def __display(self):
        """ Display """
        try:
            for k in range(self.N_VAR):
                flag = -1
                for j in range(self.N_ROW):
                    if self.a[j][k] == 1:
                        flag = j
                v = 0.0 if flag == -1 else self.a[flag][self.N_COL - 1]
                print("x{:d} = {:8.4f}".format(k, v))
            z = self.a[self.N_ROW - 1][self.N_COL - 1]
            print("z  = {:8.4f}".format(z))
        except Exception as e:
            raise


if __name__ == '__main__':
    try:
        obj = LinearProgrammingSimplex()
        obj.exec()
    except Exception as e:
        traceback.print_exc()
        sys.exit(1)