Линейное программирование и симплекс-метод: создание и сравнение реализаций на Python

Создание симплексного метода с нуля в Python

1. Введение

Исследование операций (OR) и машинное обучение (ML) меняют мир бизнес-аналитики. OR фокусируется на оптимизации и принятии решений, в то время как ML выявляет закономерности и прогнозирует результаты на основе данных. Вместе они предлагают мощные возможности решения проблем и ценную информацию для бизнеса.

OR использует математическое моделирование и алгоритмы оптимизации для решения сложных проблем в таких областях, как управление цепочками поставок, логистика и распределение ресурсов. Машинное обучение использует анализ данных и прогнозное моделирование для извлечения информации, персонализации опыта и оптимизации операций. Комбинируя системы поддержки принятия решений OR с подходом ML, основанным на данных, организации могут принимать обоснованные решения и обеспечивать устойчивый рост.

В этой статье мы исследуем симплекс-метод, фундаментальный алгоритм ИЛИ для линейного программирования (ЛП), и продемонстрируем его реализацию в Python. Мы представляем Pyomo, мощную среду моделирования оптимизации, и демонстрируем ее интеграцию с решателем GNU Linear Programming Kit (GLPK). Мы также подчеркиваем, как OR и ML дополняют друг друга в бизнес-аналитике, позволяя организациям решать сложные проблемы, получать более глубокое понимание и принимать решения на основе данных, которые способствуют успеху.

2. Концепции: объяснение важности LP и симплекс-метода

LP — это метод математической оптимизации, используемый для максимизации или минимизации линейной целевой функции при соблюдении набора линейных ограничений. Задачи LP имеют множество реальных приложений и обеспечивают мощную основу для принятия решений в различных областях.

2.1. Приложения LP

LP имеет широкий спектр применения в различных отраслях:

Управление цепочкой поставок: LP может оптимизировать планирование производства, управление запасами и распределение, чтобы минимизировать затраты и эффективно удовлетворить спрос.
Финансы и инвестиции: LP можно использовать для оптимизации портфеля, распределения активов и управления рисками, чтобы максимизировать прибыль и минимизировать риски.
Транспорт и логистика: LP может оптимизировать маршрутизацию, планирование и распределение ресурсов, чтобы минимизировать транспортные расходы и повысить эффективность.
Управление энергией и ресурсами: LP может оптимизировать распределение ресурсов и планирование производства, чтобы свести к минимуму потребление энергии, отходы и воздействие на окружающую среду.
Производство и эксплуатация: LP может оптимизировать планирование производства, распределение ресурсов и планирование мощностей, чтобы максимизировать производительность и минимизировать затраты.

2.2. LP объяснил

Чтобы понять LP, давайте рассмотрим простой пример. Представьте себе компанию, которая производит два вида продукции: продукт А и продукт Б. Прибыль на единицу продукта А составляет 10 долларов, а прибыль на единицу продукта Б — 8 долларов. Компания имеет ограниченные ресурсы. 100 единиц сырья X и 80 единиц сырья Y. Для продукта A требуется 2 единицы сырья X и 1 единица сырья Y, а для продукта B требуется 1 единица сырья X и 2 единицы сырья Y.

Цель состоит в том, чтобы определить оптимальные объемы производства продуктов A и B, которые максимизируют общую прибыль при соблюдении ограничений ресурсов. Это задача линейного программирования, целью которой является максимизация прибыли (линейная функция) с учетом ограничений (линейных уравнений).

2.3. Стандартная форма LP

В LP стандартная форма представляет собой особый формат для задач LP. Он обеспечивает единообразие и облегчает применение алгоритмов оптимизации, таких как симплекс-метод. Стандартная форма имеет три характеристики:

Цель максимизации. Цель состоит в том, чтобы максимизировать линейную функцию. Если задача состоит в минимизации, целевую функцию можно преобразовать, умножив ее на -1.
Ограничения равенства. Все ограничения выражаются в виде ограничений равенства (т. е. уравнений). Ограничения неравенства, такие как «‹=» или «›=», необходимо преобразовать в ограничения равенства, введя переменные резерва или избытка.
Неотрицательные переменные решения: предполагается, что все переменные неотрицательны.

Давайте рассмотрим задачу ЛП, которая не удовлетворяет трем характеристикам:

В этом примере задача имеет цель минимизации, ограничения неравенства и отрицательную переменную решения (x₂). Чтобы преобразовать его в стандартный вид, нам нужно сделать несколько модификаций.

2.3.1. От минимизации к максимизации

Поскольку задача находится в форме минимизации, мы можем преобразовать ее в максимизирующую, умножив целевую функцию на -1:

3.2.2. Ограничения неравенства для ограничений равенства

Чтобы преобразовать ограничения неравенства в ограничения равенства, мы вводим переменные резерва или излишка. Давайте введем переменные резерва s₁ и s₂:

Обратите внимание, что символ (-/+), сопровождающий переменную резерва, зависит от неравенства.

2.3.3. Неотрицательные переменные

Замените отрицательную переменную x₂ двумя неотрицательными переменными, x₂′ и x₂″:

Теперь задача ЛП имеет стандартную форму:

2.4. Симплексный метод

Симплекс-метод — это итерационный алгоритм, используемый для решения задач LP. Он начинается с начального допустимого решения и систематически движется к оптимальному решению, улучшая значение целевой функции на каждой итерации.

2.4.1. Некоторые концепции

Применяя симплекс-метод, помните о следующих принципах:

Базовые переменные.Эти переменные имеют только одну ненулевую запись в соответствующих столбцах таблицы (см. раздел 2.4.2). Ненулевой элемент обычно соответствует коэффициенту базовой переменной в соответствующем уравнении ограничения. Основные переменные играют решающую роль в определении текущего решения и его осуществимости.
Неосновные переменные.Эти переменные имеют более одной ненулевой записи в соответствующих столбцах таблицы (см. Раздел 2.4.2). Ненулевые записи соответствуют коэффициентам неосновных переменных в уравнениях ограничений. Небазовые переменные представляют собой значения, которые еще предстоит определить и являются кандидатами на вход или выход из базиса во время итераций симплекс-метода.
Основа. В LP основой называется набор линейно независимых ограничений или уравнений, определяющих допустимую область задачи. В симплексном методе базис состоит из подмножества переменных, которые выбираются так, чтобы удовлетворять уравнениям связи и образуют систему уравнений.
Базовое возможное решение. Базовое допустимое решение — это решение задачи LP, которое удовлетворяет как ограничениям, так и условиям неотрицательности. Он характеризуется наличием допустимого набора значений для основных переменных при установке неосновных переменных на ноль. Базовое допустимое решение находится на пересечении ограничений и представляет собой угловую точку допустимой области.

Симплекс-метод опирается на понятия базовых и небазисных переменных. Базисные и небазисные переменные определяют осуществимость решения и направление улучшения. Количество ограничений и переменных в стандартной форме задачи ЛП определяет количество базовых и небазисных переменных. Для стандартной задачи ЛП с m ограничениями и n переменными имеется m базовых переменных и n-m небазисных переменных.

2.4.2. Симплексная таблица

Чтобы применить симплекс-метод, мы используем инструмент, называемый симплекс-таблицей. Симплексная таблица представляет собой табличное представление ограничений задачи ЛП, коэффициентов целевой функции и значений решения. Это позволяет нам выполнять вычисления для обновления решения на каждой итерации.

Процесс обновления симплексной таблицы аналогичен методу исключения Гаусса, используемому в линейной алгебре. В методе исключения Гаусса мы выполняем операции со строками, чтобы преобразовать систему уравнений в эквивалентную треугольную систему. Точно так же в симплексном методе мы обновляем таблицу, выполняя операции со строками, чтобы получить таблицу, представляющую улучшенное решение.

На каждой итерации симплекс-метода мы выполняем следующие шаги, используя симплекс-таблицу:

Выберите опорный столбец. Определите опорный столбец в таблице, соответствующий самому отрицательному коэффициенту в целевой строке. В этом столбце указано, какая небазисная переменная должна войти в базис.
Выберите сводную строку. Определите сводную строку, найдя минимальное отношение значений правой части к коэффициентам в сводной колонке. Эта строка представляет собой ограничение, которое в наибольшей степени ограничивает продвижение к оптимальному решению.
Обновление сводного элемента: разделите сводную строку на значение сводного элемента, чтобы оно стало равным 1. Это гарантирует, что выбранная неосновная переменная станет базовой переменной.
Обновить другие элементы. Настройте оставшиеся элементы в таблице так, чтобы в опорном столбце появились нули, за исключением опорного элемента.
Повторять до оптимальности. Повторяйте описанные выше шаги до тех пор, пока в целевой строке не останется отрицательных коэффициентов, что указывает на то, что текущее решение является оптимальным.

Симплексная таблица позволяет нам эффективно выполнять эти операции и отслеживать текущие значения решения и значения целевой функции. Итеративно обновляя таблицу, мы движемся к оптимальному решению, которое максимизирует или минимизирует целевую функцию.

Связь между симплекс-методом, симплекс-таблицей, методом исключения Гаусса и линейной алгеброй заключается в концепции преобразования системы уравнений или неравенств для улучшения решения. Итерации симплекс-метода с таблицей напоминают операции со строками, выполняемые при исключении Гаусса, обе из которых направлены на достижение улучшенного представления решения. Однако симплекс-метод специально разработан для решения задач линейного программирования, оптимизации целевой функции с учетом линейных ограничений.

2.4.3. Пример симплексного метода

Рассмотрим следующую задачу ЛП в стандартной форме:

Чтобы применить симплекс-метод с использованием симплекс-таблицы, мы выполним следующие шаги:

Шаг 1.Настройте начальную симплексную таблицу.

В приведенной выше таблице RHS означает правую сторону.

Шаг 2. Выберите сводной столбец. Самый отрицательный коэффициент в z-строке (то есть в строке цели) равен -3, что соответствует столбцу x₁. Следовательно, x₁ будет входной переменной.

Шаг 3. Выберите сводную строку. Чтобы определить опорную строку, мы вычисляем отношение значений правой части к коэффициентам столбца x₁. Минимальное отношение соответствует предельному ограничению. Здесь минимальное соотношение равно 5 (соответствует второй строке).

Шаг 4. Обновите элемент сводки. Обновите опорный элемент. Разделите сводную строку на значение опорного элемента (в данном случае 2, т. е. коэффициент при x₁ во второй строке), чтобы сделать его равным 1:

Шаг 5. Обновите другие элементы. Отрегулируйте оставшиеся элементы в таблице так, чтобы в столбце x₁ появились нули.

Это похоже на исключение Гаусса в линейной алгебре. Третья строка в приведенной выше матрице получается путем вычитания второй строки из третьей строки в матрице на шаге 4, а первая строка получается путем суммирования первой строки в три раза со второй строкой. Целевое значение равно 15, а базовые переменные (т. е. только одна ненулевая запись) x₁ и s₂ равны 5 и 3 соответственно. Таким образом, основное допустимое решение равно x₁, а x₂ (т. е. переменные решения реальной задачи) равны 5 и 0.

Шаг 6.Повторяйте шаги 2–5, пока в z-ряду не останется отрицательных коэффициентов.

3. Использование Python для создания симплекс-метода с нуля

В этом разделе мы рассмотрим, как реализовать симплекс-метод с нуля с помощью Python. Мы создадим программу Python, которая принимает задачу LP в стандартной форме в качестве входных данных и применяет симплекс-метод для поиска оптимального решения. Мы будем использовать NumPy, мощную библиотеку для числовых вычислений, чтобы эффективно выполнять матричные операции.

# Import libraries
import numpy as np
import warnings

# Ignore specific warning category
warnings.filterwarnings("ignore", category=RuntimeWarning)

def initialize_simplex_tableau(c, A, b):
    '''
    This function initializes the simplex tableau by constructing the
    initial matrix representation of the LP problem in standard form.

    Inputs:
    - c (numpy.array): Coefficients of the objective function.
    - A (numpy.array): Coefficient matrix of the constraint equations.
    - b (numpy.array): Right-hand side values of the constraint equations.
    Output:
    - tableau (numpy.array): The initialized simplex tableau.
    '''

    m = A.shape[0]
    n = c.shape[0]
    tableau = np.zeros((m + 1, m + n + 1))
    tableau[0, 0:n] = -c
    tableau[1:, 0:n] = A
    tableau[1:, n:-1] = np.eye(m)
    tableau[1:, -1] = b

    return tableau

def pivot_column(tableau):
    '''
    This function determines the pivot column, which corresponds to
    the variable that will enter the basis.

    Input:
    - tableau (numpy.array): The simplex tableau.
    Output:
    - pivot_col (int): The index of the pivot column.
    '''

    pivot_col = np.argmin(tableau[0, :-1])
    return pivot_col

def pivot_row(tableau, pivot_col):
    '''
    This function determines the pivot row, which corresponds to the
    constraint that will become the basis.

    Inputs:
    - tableau (numpy.array): The simplex tableau.
    pivot_col (int): The index of the pivot column.
    Output:
    - pivot_row (int): The index of the pivot row.
    '''

    ratios = tableau[1:, -1] / tableau[1:, pivot_col]
    pivot_row = np.argmin(ratios) + 1
    return pivot_row

def update_tableau(tableau, pivot_row, pivot_col):
    '''
    This function updates the simplex tableau by performing row
    operations to pivot and adjust the variables.

    Inputs:
    - tableau (numpy.array): The simplex tableau.
    - pivot_row (int): The index of the pivot row.
    - pivot_col (int): The index of the pivot column.
    Output:
    - updated_tableau (numpy.array): The updated simplex tableau.
    '''

    m, n = tableau.shape
    pivot_element = tableau[pivot_row, pivot_col]
    pivot_row_values = tableau[pivot_row, :] / pivot_element
    tableau[pivot_row, :] = pivot_row_values  

    for i in range(m):
        if i == pivot_row:
            continue
        row_multiplier = tableau[i, pivot_col] / pivot_element
        tableau[i, :] -= row_multiplier * pivot_row_values

    updated_tableau = tableau

    return updated_tableau

def simplex_method(c, A, b):
    '''
    The simplex_method function implements the simplex method algorithm
    to solve a linear programming problem in standard form. It takes the
    coefficients of the objective function (c), the coefficient matrix of
    the constraint equations (A), and the right-hand side values of the
    constraint equations (b) as input. The function iteratively updates
    the simplex tableau until an optimal solution is reached, and returns
    the optimal solution in the form of a dictionary.

    Inputs:
    - c (numpy.array): Coefficients of the objective function.
    - A (numpy.array): Coefficient matrix of the constraint equations.
    - b (numpy.array): Right-hand side values of the constraint equations.
    Output:
    - optimal_solution (dict): A dictionary representing the optimal solution,
      including the objective value and the values of decision variables.
    '''

    n = c.shape[0]

    tableau = initialize_simplex_tableau(c, A, b)

    condition = False
    while not condition:
        pivot_c = pivot_column(tableau)
        pivot_r = pivot_row(tableau, pivot_c)
        tableau = update_tableau(tableau, pivot_r, pivot_c)
        condition =  np.all(tableau[0, :] >= 0)

    optimal_solution = dict()
    optimal_solution['Objective Value'] = tableau[0, -1]

    for i in range(n):
        idx = np.argmax(tableau[1:, i]) + 1
        optimal_solution[f'x{i + 1}'] = tableau[idx, -1]

    return optimal_solution

Кратко объясним код:

Функция initialize_simplex_tableau инициализирует симплексную таблицу, создавая начальное матричное представление задачи LP в стандартной форме.
Функция pivot_column определяет сводную колонку, которая соответствует переменной, которая войдет в основу.
Функция pivot_row определяет опорную строку, которая соответствует ограничению, которое станет основой.
Функция update_tableau обновляет симплексную таблицу, выполняя операции со строками для поворота и корректировки переменных.
Функция simplex_method реализует алгоритм симплекс-метода. Он итеративно обновляет таблицу, пока не будет достигнуто оптимальное решение. Он возвращает оптимальное решение, включая целевое значение и значения переменных решения.

Вы можете использовать функцию simplex_method, указав коэффициенты целевой функции (c), матрицу коэффициентов уравнений ограничений (A) и правые значения уравнений ограничений (b).

Примечание. Этот код предполагает, что задача LP находится в стандартной форме с целью максимизации. Корректировки могут потребоваться для различных вариантов задач LP.

4. Сравнение результатов с Pyomo

В этом разделе давайте сравним результат, полученный с помощью метода Simplex, созданного с нуля в Python, с результатом, полученным Pyomo. Для сравнения давайте воспользуемся следующей задачей оптимизации, сохранив предположения, чтобы приведенный выше фрагмент кода был верным.

Этот пример взят из следующего сообщения, написанного Хенни де Хардер, чтобы вы могли сравнить его с ее решением:

Руководство по линейному программированию и симплексному алгоритму для начинающих
Решение широкого круга задач оптимизации.towardsdatascience.com

4.1. Симплекс, созданный с нуля

Используя numpy, мы можем передать коэффициенты целевой функции (c), матрицу коэффициентов уравнений ограничений (A) и правые значения уравнений ограничений (b).

# Example usage
c = np.array([100, 150])
A = np.array([[1, 0], [0, 1], [2, 1]])
b = np.array([50, 40, 120])

solution = simplex_method(c, A, b)
print(solution)

Ниже приводится результат использования кода:

{'Objective Value': 10000.0, 'x1': 40.0, 'x2': 40.0}

4.2. Использование Pyomo для решения проблемы LP с помощью GLPK Solver

В области оптимизации Pyomo выделяется как мощная платформа, позволяющая моделировать и решать сложные задачи математического программирования. Когда дело доходит до LP, Pyomo предоставляет удобный интерфейс для интеграции с различными решателями, включая GLPK. В этом разделе мы рассмотрим, как использовать Pyomo и GLPK для эффективного решения проблем LP.

Для начала нам нужно убедиться, что Pyomo и решатель GLPK установлены в нашей системе. Pyomo можно установить с помощью pip менеджера пакетов Python, а GLPK можно установить отдельно в зависимости от вашей операционной системы. Как только оба будут установлены, мы можем приступить к написанию нашего кода Pyomo.

# Import library
from pyomo.environ import *

# Create a ConcreteModel
model = ConcreteModel()

# Define the decision variables
model.x1 = Var(within=NonNegativeReals)
model.x2 = Var(within=NonNegativeReals)

# Define the objective function
model.obj = Objective(expr=100*model.x1 + 150*model.x2, sense=maximize)

# Define the constraints
model.constraint1 = Constraint(expr=model.x1 <= 50)
model.constraint2 = Constraint(expr=model.x2 <= 40)
model.constraint3 = Constraint(expr=2*model.x1 + model.x2 <= 120)

# Solve the problem
solver = SolverFactory('glpk')
solver.solve(model)

# Print the optimal solution
print("Optimal Solution:")
print("Objective Value:", model.obj())
print("x1:", model.x1())
print("x2:", model.x2())

Теперь давайте сравним результат, полученный с помощью Pyomo, с результатом, полученным с помощью симплекс-метода с нуля. Мы должны заметить, что оптимальные значения решения совпадают для обоих подходов. Это демонстрирует надежность и точность Pyomo и решателя GLPK при решении задач LP.

Optimal Solution:
Objective Value: 10000.0
x1: 40.0
x2: 40.0

5. Исследование операций и машинное обучение: дополнительные подходы в бизнес-аналитике

OR и ML — взаимодополняющие подходы в бизнес-аналитике. OR фокусируется на математическом моделировании и методах оптимизации для решения сложных бизнес-задач с ограничениями и четко определенными целями. ML, с другой стороны, использует алгоритмы для анализа данных, выявления закономерностей и создания прогнозов или решений без явного программирования.

Сочетание OR и ML может улучшить бизнес-аналитику, используя сильные стороны обоих подходов. OR предоставляет рамки оптимизации и системы поддержки принятия решений для эффективного решения сложных проблем, в то время как ML вносит свой вклад, анализируя данные, делая прогнозы и обнаруживая закономерности. Эта интеграция особенно полезна в таких областях, как управление цепочками поставок, где OR оптимизирует процессы, а ML улучшает прогнозирование и обнаружение аномалий.

Интегрируя OR и ML, предприятия могут повысить эффективность работы, точность прогнозов, упреждающее управление рисками и принятие решений на основе данных. OR направляет ML, определяя цели и включая ограничения, в то время как ML обеспечивает понимание и обрабатывает сложные данные. Такой синергетический подход позволяет организациям принимать более взвешенные решения, оптимизировать ресурсы и получать ценную информацию для устойчивого роста.

Заключение

В заключение, наше исследование симплекс-метода, Pyomo с решателем GLPK и связи между OR и ML подчеркивает силу и универсальность этих подходов в бизнес-аналитике.

Симплекс-метод, реализованный с нуля в Python, обеспечивает прочную основу для решения задач линейного программирования. Его итеративный подход и построение симплексной таблицы позволяют нам находить оптимальные решения путем итеративной корректировки таблицы с помощью операций разворота. Сравнивая результаты с подходами решателя Pyomo и GLPK, мы наблюдаем согласованность и надежность оптимальных значений решения, демонстрируя эффективность Pyomo и решателя GLPK для решения задач LP.

Интеграция OR и ML в бизнес-аналитику открывает синергетические преимущества. OR предлагает методы математического моделирования и оптимизации, а ML предоставляет расширенные возможности анализа данных и распознавания образов. Это сочетание позволяет организациям использовать системы поддержки принятия решений OR и среды оптимизации, используя возможности прогнозирования и аналитики ML для принятия решений на основе данных, оптимизации ресурсов и решения сложных бизнес-задач. Интегрируя эти подходы, предприятия могут добиться операционной эффективности, точного прогнозирования, упреждающего управления рисками и получения ценной информации для устойчивого роста.

Поскольку области OR, ML и бизнес-аналитики продолжают развиваться, дальнейшее изучение передовых алгоритмов, альтернативных решателей и включение дополнительных ограничений и структур задач расширит возможности решения проблем. Взаимодополняющий характер операционных процессов и машинного обучения предоставляет комплексный набор инструментов для решения сложных бизнес-задач, позволяя организациям принимать обоснованные решения, оптимизировать процессы и оставаться конкурентоспособными в мире, управляемом данными.