74 lines
5.2 KiB
Python
74 lines
5.2 KiB
Python
import numpy as np
|
||
|
||
def simplex_method(c, A, b):
|
||
m, n = A.shape
|
||
c = np.concatenate([c, np.zeros(m)]) # Дополнение коэффициентов целевой функции нулями
|
||
A = np.column_stack([A, np.eye(m)]) # Дополнение матрицы A единичной матрицей
|
||
basis = np.arange(n, n + m) # Индексы базисных переменных
|
||
|
||
while True:
|
||
# Шаг 1: Проверка на оптимальность
|
||
|
||
# Рассчитываем приведенные затраты (reduced_costs), вычитая из коэффициентов целевой функции (c)
|
||
# линейную комбинацию базисных переменных и соответствующих им строк матрицы A.
|
||
# Приведенные затраты - оценки изменения целевой функции при изменении значений переменных.
|
||
reduced_costs = c - np.dot(c[basis], A)
|
||
|
||
# Если все приведенные затраты неотрицательны (все переменные в базисе удовлетворяют условиям оптимальности),
|
||
# то достигнуто оптимальное решение, и цикл прерывается.
|
||
if all(reduced_costs >= 0):
|
||
break
|
||
|
||
# Шаг 2: Выбор входящей переменной
|
||
# определяем индекс переменной, которую мы добавим в базис (войдет в решение) на следующей итерации.
|
||
# выбираем переменную с наименьшим уменьшенным коэффициентом в функции цели.
|
||
entering_var = np.argmin(reduced_costs)
|
||
|
||
# Шаг 3: Проверка на неограниченность
|
||
# Проверяем, если все элементы столбца матрицы A, соответствующего входящей переменной,
|
||
# меньше или равны нулю. Если это условие выполняется, то проблема неограничена.
|
||
if all(A[:, entering_var] <= 0):
|
||
raise Exception("Проблема неограничена")
|
||
|
||
# Шаг 4: Выбор выходящей переменной
|
||
# Рассчитываем отношения значений правых частей к соответствующим коэффициентам входящей переменной в матрице A.
|
||
# Если коэффициент входящей переменной положителен, оставляем отношение, иначе присваиваем бесконечность.
|
||
ratios = np.divide(b, A[:, entering_var], out=np.full_like(b, np.inf, dtype=float), where=A[:, entering_var] > 0)
|
||
|
||
# Находим индекс минимального отношения, который определяет выходящую переменную.
|
||
leaving_var = np.argmin(ratios)
|
||
|
||
# Шаг 5: Обновление базиса
|
||
# Обновляем базис, заменяя выходящую переменную на входящую переменную.
|
||
basis[leaving_var] = entering_var
|
||
|
||
|
||
# Шаг 6: Обновление симплекс-таблицы
|
||
pivot = A[leaving_var, entering_var] # Выбор опорного элемента (пересечение строки и столбца)
|
||
A[leaving_var, :] /= pivot # Деление строки с опорным элементом на опорный элемент
|
||
b[leaving_var] /= pivot # Деление правой части на опорный элемент
|
||
for i in range(m):
|
||
if i != leaving_var:
|
||
factor = A[i, entering_var] # Выбор элемента в столбце входящей переменной
|
||
A[i, :] -= factor * A[leaving_var, :] # Обновление строки матрицы
|
||
b[i] -= factor * b[leaving_var] # Обновление правой части
|
||
|
||
c -= reduced_costs[entering_var] * A[leaving_var, :] # Обновление коэффициентов целевой функции
|
||
|
||
# Извлечение решения из симплекс-таблицы
|
||
solution = np.zeros(n)
|
||
for i in range(m):
|
||
if basis[i] < n:
|
||
solution[basis[i]] = b[i] # Извлечение значений базисных переменных из симплекс-таблицы
|
||
|
||
|
||
return solution
|
||
|
||
# Пример использования:
|
||
c = np.array([-3, -2]) # Коэффициенты целевой функции для минимизации
|
||
A = np.array([[1, 2], [2, 1], [1, -1]]) # Коэффициенты ограничений-неравенств
|
||
b = np.array([4, 7, 1]) # Значения правых частей ограничений
|
||
|
||
result = simplex_method(c, A, b)
|
||
print("Оптимальное решение:", result)
|