Линейное программирование — это метод, используемый в математике для оптимизации операций при определенных ограничениях.
В линейном программировании основная цель — максимизировать или минимизировать числовое значение. Он состоит из линейных функций, которые должны соответствовать ограничениям, которые могут принимать форму неравенств или линейных уравнений.
Для определения наилучшего использования ресурсов линейное программирование считается важнейшим методом. Два термина, линейное и программирование, составляют фразу «линейное программирование». Связь между несколькими переменными первой степени определяется словом «линейная». Процесс выбора оптимального решения из множества вариантов называется «программированием».
Другими словами, линейное программирование рассматривается как способ максимизировать или уменьшить целевую функцию данной математической модели при соблюдении набора условий, которые представлены линейной зависимостью. Основная цель задачи линейного программирования — найти оптимальный ответ.
Метод linprog()
В Python Scipy есть метод linprog() в модуле scipy.optimize. Использование линейной целевой функции минимизируется при соблюдении ограничений равенства и неравенства.
Синтаксис:
scipy.optimize.linprog(c, b_eq=None, bounds=None, A_ub=None, method='highs', A_eq=None, b_ub=None, callback=None, options=None, x0=None, integrality=None)
Где параметры:
- c (1d_array): коэффициенты линейной целевой функции должны быть минимизированы.
- A_ub (2d_array): матрица ограничений-неравенств. Каждая строка A ub содержит коэффициенты ограничения на x, основанного на линейном неравенстве.
- b_ub (1d_array): вектор ограничений для неравенства. Верхний предел соответствующего значения A_ub @ x для каждого элемента представлен этим элементом.
- A_eq (2d_array): матрица ограничений равенства. Каждая строка A eq содержит коэффициенты ограничения на x, основанного на линейном равенстве.
- b_eq (1d_array): вектор ограничения равенства. Каждый элемент A eq @ x должен совпадать с элементом b eq.
- callback (последовательность): нижние и верхние значения каждого компонента переменной решения для x представлены серией пар(мин, максимум). Используйте None, чтобы продемонстрировать отсутствие границы. Границы по умолчанию установлены на 0 и 0. Если задан только один кортеж(мин, максимум), границы для всех переменных выбора будут установлены на более низкие и более высокие значения.
- method (строка): алгоритм, используемый для решения проблемы в стандартной форме. Поддерживаются следующие значения: «highs»(по умолчанию), «highs-ds», «highs-ipm», «внутренняя точка», «обновленный симплекс» и «симплекс».
- callback (callable): если указана функция обратного вызова, алгоритм будет вызывать ее хотя бы один раз для каждой итерации. Функция обратного вызова может принимать только один аргумент.
- options(dict): словарь возможных решателей.
- x0 (1d_array): переменная решения предполагает, что будет улучшено с помощью метода оптимизации. Эта опция в настоящее время используется только в рамках «пересмотренного симплексного» подхода и может использоваться только в том случае, если x0 представляет собой простой и правдоподобный ответ.
- Integrity (1d_array): указывает тип ограничения целостности, которому подчиняется каждая переменная решения.
- 0: Непрерывная переменная; нет требований к целостности.
- 1: Целочисленная переменная, которая должна подпадать под определенные ограничения, является переменной решения.
- 2: Переменная решения должна находиться в пределах своего диапазона или иметь значение 0. Полунепрерывная переменная.
- 3: Полуцелая переменная; переменная результата должна либо принимать значение 0, либо, в пределах ограничений, быть целым числом.
- По умолчанию все переменные являются непрерывными. Этот аргумент в настоящее время принимается во внимание только методом «максимумов».
«scipy.optimize.OptimizeResult» состоит из полей ниже и возвращается методом linprog().
Следует отметить, что типы возвращаемых полей могут меняться в зависимости от того, прошла ли оптимизация успешно, поэтому рекомендуется проверить «OptimizeResult.status», прежде чем полагаться на другие поля.
- x (1d_array): значения переменных решения, которые удовлетворяют требованиям при минимизации целевой функции.
- fun (float): оптимальное значение целевой функции c @ x.
- slack (1d_array): значения слабых переменных(номинально положительные), «b ub – A ub @ x».
- con (1d_array): остатки ограничений равенства(номинально ноль), «b eq – A eq @ x».
- success (логическое): если алгоритм находит лучшее решение, то утверждение верно.
- status (int): целое число, указывающее статус завершения алгоритма. 0: оптимизация успешно завершена. 1: Достигнут предел итераций. 2: Проблема кажется неразрешимой. 3: Проблема, кажется, не имеет границ. 4: Были проблемы с числами.
- nit (int): общее количество повторений, выполненных на всех этапах.
Давайте возьмем целевую функцию и найдем ее оптимальное значение, выполнив следующие шаги:
- Импортируйте необходимые библиотеки методов, используя приведенный ниже код.
from scipy import optimize
- Определите неравенство и его границы, используя приведенный ниже код.
c_ = [-1, 3] A_ = [[-2, 1], [1, 3]] b_ = [5, 3] x0_bounds_ =(None, None) x1_bounds_ =(-2, None)
- Теперь решите приведенное выше неравенство определения, передав его методу linprog(), используя приведенный ниже код.
res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_]) print(res_.fun) print(res_.x) print(res_.message)
Симплексный метод
Для решения задачи линейного программирования существует симплексный метод, обычно неравенства представляют собой функцию со многими ограничениями. Многоугольник — это неравенства, а вершины — решение неравенств.
Симплексный метод — это методический процесс оценки вершин как потенциальных решений.
Обрисовав ограничения на графике, можно решить некоторые простые проблемы оптимизации. Однако этим методом можно решить только системы неравенств с двумя переменными. В реальных ситуациях задачи часто включают сотни уравнений и тысячи переменных, что может привести к астрономическому количеству крайних точек.
Метод Python Scipy linprog() принимает метод параметра, указывающий, какой метод использовать для решения линейных задач. Итак, здесь мы будем использовать симплексный метод для решения ЛП.
Синтаксис:
scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='simplex', callback=None, options={'maxiter': 5000, 'disp': False, 'presolve': True, 'tol': 1e-12, 'autoscale': False, 'rr': True, 'bland': False}, x0=None)
Давайте возьмем пример и найдем оптимальное значение целевой функции с помощью симплексного метода, выполнив следующие шаги:
- Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.
from scipy import optimize
Определяет проблему неравенства или равенства, показанную ниже.
Scipy Linprog
c_ = [-40, 30] A_ = [[1, 1], [2, 1]] b_ = [8, 12] x0_bounds_ =(0, None) x1_bounds_ =(0, None)
- Теперь найдите решение, используя симплексный метод в linprog().
res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_],method='simplex') print(res_.fun) print(res_.x) print(res_.message)
Метод Highs
Method=’simplex’ устарел с версии 1.9.0 и будет удален в SciPy 1.11.0. Вместо него используется Method=’highs’, поскольку он быстрее и надежнее.
Давайте возьмем тот же пример, который мы использовали в предыдущем подразделе, чтобы найти оптимальное решение для целевой функции, выполнив следующие шаги:
- Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.
from scipy import optimize
- Определяет проблему неравенства или равенства, показанную ниже.
c_ = [-40, 30] A_ = [[1, 1], [2, 1]] b_ = [8, 12] x0_bounds_ =(0, None) x1_bounds_ =(0, None)
- Теперь найдите решение, используя симплексный метод в linprog().
res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_],method='highs') print(res_.fun) print(res_.x)
Границы
Метод linprog() принимает границы параметров, которые представляют собой наименьшее и максимальное значения каждого элемента в x, заданные серией пар(мин, максимум). Если границ нет, используйте None, чтобы указать это. Границы обычно устанавливаются на(0, Нет)(все переменные решения неотрицательны).
Границы для всех переменных решения будут установлены одним предоставленным кортежем (мин, максимум).
Давайте возьмем пример целевой функции и настроим границы функции, чтобы увидеть оптимальные значения функции, выполнив следующие шаги:
Фирма из США производит два разных типа телевизоров: один цветной, а другой черно-белый. Предприятие может производить не более 150 комплектов в неделю. рупий. Для создания черно-белого набора необходимо 2500 рупий, а рупий. Для сборки цветного набора необходимо 3000. Производство телевизоров не должно стоить компании более 640 000 рупий в неделю.
Сколько черно-белых и цветных комплектов следует выпустить, если они принесут рупий? 500 за комплект и рупий. 600 за каждый набор цветов, чтобы заработать больше денег? Создайте это, используя LPP.
from scipy.optimize import linprog
Определите проблемы, используя приведенный ниже код.
- С учетом ограничений:
- x, y ≥ 0(неотрицательное ограничение)
- x + y ≤ 150(количественные ограничения)
- 2500x+3000y ≤ 640000(ограничения по стоимости)
- Целевая функция: Z = 500x + 600y
c_ = [500, 600] A_ = [[1, 1], [2500, 3000]] b_ = [150, 640000] x0_bounds_ =(0, None) x1_bounds_ =(0, None)
Теперь найдите оптимальное значение для определенной выше целевой функции, используя приведенный ниже код.
res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_]) print(res_.x) print(res_.slack) print(res_.fun) print(res_.message)
Границы
Снова измените x0_bounds_ =(0, None) и x1_bounds_ =(0, None) на x0_bounds_ =(3, None), x1_bounds_ =(3, None).
c_ = [500, 600] A_ = [[1, 1], [2500, 3000]] b_ = [150, 640000] x0_bounds_ =(3, None) x1_bounds_ =(3, None)
Разреженная матрица
Мы считаем, что создание плотной матрицы (или двух) для решения значительной разреженной ЛП, вероятно, не является хорошей идеей. Крайне важно использовать решатель, способный обрабатывать огромные разреженные ЛП при их решении, а также создавать модель без преднамеренного создания каких-либо из этих нулевых элементов.
Создать надежный, быстрый и разреженный решатель Simplex LP на Python для замены плотного решателя SciPy — непростая задача. Кроме того, решатель на чистом Python может работать не так хорошо.
Несмотря на то, что размер модели, которую мы хотим использовать, может быть не очень и очень огромным(возможно, модель большого или среднего размера будет разумным описанием), размер модели, которую мы хотим использовать, может гарантировать использование коммерческого решателя, такого как Cplex, Gurobi или Mosek.
Эти специалисты по решению проблем работают быстро и последовательно(они решают любую проблему LP, которую вы им зададите). У каждого из них есть API Python. Академические решатели бесплатны или вполне доступны по цене.
Если невозможно создать
Если не существует возможного решения, удовлетворяющего всем ограничениям, или если невозможно создать допустимое решение, то линейная программа неосуществима. Неосуществимость обычно означает какую-то ошибку, поскольку какую бы реальную операцию мы ни моделировали, она должна соответствовать ограничениям реальности.
Это может быть результатом неправильных значений данных или ошибки в указании некоторых ограничений.
Если для любой линейной программы в стандартной форме не существует оптимального решения, проблема либо неразрешима, либо неограничена. Простое жизнеспособное решение также существует, если оно существует. Существует фундаментально работоспособное решение, которое также является оптимальным решением, когда существует оптимальное решение.
Давайте возьмем тот же пример, с изменением связанных значений, выполнив следующие шаги:
- Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.
from scipy import optimize
- Определяет проблему неравенства или равенств с неправильными границами, показанными ниже.
c_ = [-40, 30] A_ = [[1, 1], [2, 1]] b_ = [8, 12] x0_bounds_ =(0, -1) x1_bounds_ =(0, None)
- Теперь найдите решение, используя симплексный метод в linprog().
res_ = optimize.linprog(c_, A_ub=A_, b_ub=b_, bounds=[x0_bounds_, x1_bounds_],method='highs') print(res_.fun) print(res_.x)
