75 lines
2.4 KiB
Python
75 lines
2.4 KiB
Python
import numpy as np
|
|
import math
|
|
|
|
class Simplex:
|
|
def __init__(self, source):
|
|
self.m, self.n = source.shape
|
|
self.table = np.zeros((self.m, self.n + self.m - 1))
|
|
self.basis = []
|
|
|
|
for i in range(self.m):
|
|
self.table[i, :self.n] = source[i, :]
|
|
if (self.n + i) < self.table.shape[1]:
|
|
self.table[i, self.n + i] = 1
|
|
self.basis.append(self.n + i)
|
|
|
|
self.n = self.table.shape[1]
|
|
|
|
def calculate(self, result):
|
|
while not self.is_optimal():
|
|
main_col = self.find_main_col()
|
|
main_row = self.find_main_row(main_col)
|
|
self.basis[main_row] = main_col
|
|
|
|
self.table[main_row, :] /= self.table[main_row, main_col]
|
|
|
|
for i in range(self.m):
|
|
if i == main_row:
|
|
continue
|
|
self.table[i, :] -= self.table[i, main_col] * self.table[main_row, :]
|
|
|
|
for i in range(len(result)):
|
|
k = self.basis.index(i + 1) if i + 1 in self.basis else None
|
|
result[i] = self.table[k, 0] if k is not None else 0
|
|
|
|
return self.table
|
|
|
|
def is_optimal(self):
|
|
return all(self.table[self.m - 1, 1:] >= 0)
|
|
|
|
def find_main_col(self):
|
|
return np.argmin(self.table[self.m - 1, 1:]) + 1
|
|
|
|
def find_main_row(self, main_col):
|
|
positive_ratios = [i for i in range(self.m - 1) if self.table[i, main_col] > 0]
|
|
main_row = positive_ratios[0] if positive_ratios else None
|
|
|
|
for i in positive_ratios[1:]:
|
|
if (self.table[i, 0] / self.table[i, main_col]) < (self.table[main_row, 0] / self.table[main_row, main_col]):
|
|
main_row = i
|
|
|
|
return main_row
|
|
|
|
if __name__ == "__main__":
|
|
table = np.array([[45, 5, 3],
|
|
[-8, -1, 0],
|
|
[-10, 0, -1],
|
|
[0, -40, -36]])
|
|
|
|
result = np.zeros(2)
|
|
simplex_solver = Simplex(table)
|
|
table_result = simplex_solver.calculate(result)
|
|
|
|
if simplex_solver.is_optimal():
|
|
np.set_printoptions(precision=2, suppress=True)
|
|
print("Решенная симплекс-таблица:")
|
|
print(table_result)
|
|
|
|
print("\nРешение:")
|
|
print(f"X[1] = {result[0]}")
|
|
print(f"X[2] = {math.ceil(result[1])}")
|
|
print(f"F(x1, x2) = {-table[-1][-2] * result[0] + -table[-1][-1] * math.ceil(result[1])}")
|
|
else:
|
|
print("Задача не имеет оптимального решения.")
|
|
|