102 lines
5.5 KiB
Python
102 lines
5.5 KiB
Python
|
import numpy as np
|
|||
|
|
|
|||
|
|
|
|||
|
|
class Simplex:
|
|||
|
|
def __init__(self, source):
|
|||
|
|
# Получение размеров матрицы source в переменные
|
|||
|
|
# m (количество строк) и n (количество столбцов).
|
|||
|
|
m, n = source.shape
|
|||
|
|
self.table = np.zeros((m, n + m - 1))
|
|||
|
|
# Будет содержать индексы базисных переменных.
|
|||
|
|
self.basis = []
|
|||
|
|
|
|||
|
|
|
|||
|
|
# Заполнение матрицы table значениями из матрицы source до столбца n.
|
|||
|
|
# Остальные элементы инициализируются нулями.
|
|||
|
|
for i in range(m):
|
|||
|
|
for j in range(self.table.shape[1]):
|
|||
|
|
if j < n:
|
|||
|
|
self.table[i, j] = source[i, j]
|
|||
|
|
else:
|
|||
|
|
self.table[i, j] = 0
|
|||
|
|
# Добавление единицы в ячейку подходящей строки и столбца для создания единичной матрицы.
|
|||
|
|
# Запись индекса этой переменной в список базисных переменных.
|
|||
|
|
if (n + i) < self.table.shape[1]:
|
|||
|
|
self.table[i, n + i] = 1
|
|||
|
|
self.basis.append(n + i)
|
|||
|
|
# Сохранение значений m и n в атрибуты объекта.
|
|||
|
|
self.m = m
|
|||
|
|
self.n = self.table.shape[1]
|
|||
|
|
|
|||
|
|
# Метод calculate, который выполняет итерации симплекс-метода до достижения оптимального решения
|
|||
|
|
# или обнаружения отсутствия решения.
|
|||
|
|
def calculate(self, result):
|
|||
|
|
# Цикл, выполняющийся до тех пор, пока не будет достигнут критерий окончания
|
|||
|
|
# (проверяется методом is_it_end()).
|
|||
|
|
while not self.is_it_end():
|
|||
|
|
main_col = self.find_main_col()
|
|||
|
|
main_row = self.find_main_row(main_col)
|
|||
|
|
|
|||
|
|
# Обновление списка базисных переменных.
|
|||
|
|
self.basis[main_row] = main_col
|
|||
|
|
|
|||
|
|
# Инициализация новой матрицы нулями той же размерности, что и self.table.
|
|||
|
|
new_table = np.zeros((self.m, self.n))
|
|||
|
|
|
|||
|
|
# Заполнение строки main_row новой матрицы значениями,
|
|||
|
|
# полученными делением соответствующих элементов из исходной матрицы.
|
|||
|
|
for j in range(self.n):
|
|||
|
|
new_table[main_row, j] = self.table[main_row, j] / self.table[main_row, main_col]
|
|||
|
|
|
|||
|
|
# Заполнение остальных строк новой матрицы путем вычитания соответствующих элементов исходной матрицы.
|
|||
|
|
for i in range(self.m):
|
|||
|
|
if i == main_row:
|
|||
|
|
continue
|
|||
|
|
|
|||
|
|
for j in range(self.n):
|
|||
|
|
new_table[i, j] = self.table[i, j] - self.table[i, main_col] * new_table[main_row, j]
|
|||
|
|
|
|||
|
|
# Обновление исходной матрицы.
|
|||
|
|
self.table = new_table
|
|||
|
|
|
|||
|
|
# Заполнение массива result значениями переменных в соответствии с текущим базисом.
|
|||
|
|
for i in range(len(result)):
|
|||
|
|
k = self.basis.index(i + 1) if i + 1 in self.basis else -1
|
|||
|
|
result[i] = self.table[k, 0] if k != -1 else 0
|
|||
|
|
# Возвращение итоговой матрицы после завершения симплекс-метода.
|
|||
|
|
return self.table
|
|||
|
|
|
|||
|
|
# Метод проверяет, выполнено ли условие завершения симплекс-метода.
|
|||
|
|
def is_it_end(self):
|
|||
|
|
# sВозвращает True, если все элементы последней строки матрицы больше
|
|||
|
|
# или равны нулю (условие оптимальности).
|
|||
|
|
return np.all(self.table[self.m - 1, 1:] >= 0)
|
|||
|
|
|
|||
|
|
# Метод нахождения ведущего столбца методом find_main_col().
|
|||
|
|
def find_main_col(self):
|
|||
|
|
main_col = 1
|
|||
|
|
|
|||
|
|
for j in range(2, self.n):
|
|||
|
|
if self.table[self.m - 1, j] < self.table[self.m - 1, main_col]:
|
|||
|
|
main_col = j
|
|||
|
|
|
|||
|
|
return main_col
|
|||
|
|
|
|||
|
|
# Метод для нахождения ведущий строки. Возвращает индекс найденной ведущей строки.
|
|||
|
|
def find_main_row(self, main_col):
|
|||
|
|
# Переменная для отслеживания индекса ведущей строки
|
|||
|
|
main_row = 0
|
|||
|
|
|
|||
|
|
for i in range(self.m - 1):
|
|||
|
|
if self.table[i, main_col] > 0:
|
|||
|
|
main_row = i
|
|||
|
|
break
|
|||
|
|
|
|||
|
|
# Поиск строки с минимальным отношением элемента в столбце 0 к элементу в заданном столбце
|
|||
|
|
# Отношение используется для выбора оптимальной строки для ведущей.
|
|||
|
|
for i in range(main_row + 1, self.m - 1):
|
|||
|
|
if self.table[i, main_col] > 0 and (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
|