ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ: ДЛЯ ЧЕГО, МОДЕЛИ, ОГРАНИЧЕНИЯ, ПРИЛОЖЕНИЯ - МАТЕМАТИКА - 2025

Линейное программирование представляет собой математический метод , который будет использоваться для оптимизации (максимизировать или минимизировать в зависимости от обстоятельств) , в функции которого переменные ограничены, а пока функция и ограничения являются линейно зависимыми переменными.

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

Рисунок 1. Линейное программирование широко используется для оптимизации прибыли. Источник: Piqsels.

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

Z = К ₁ Икс + К ₂ Y

При постоянных k ₁ и k ₂ . Эта функция известна как целевая функция. Конечно, есть ситуации, которые заслуживают изучения более чем двух переменных, будучи более сложными:

Z = К ₁ Икс ₁ + К ₂ Икс ₂ + К ₃ Икс ₃ +….

И ограничения также математически моделируются системой уравнений или неравенств, одинаково линейных по x и y.

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

Линейное программирование было независимо разработано американским физиком и математиком Джорджем Данцигом (1914-2005) и русским математиком и экономистом Леонидом Канторовичем (1912-1986) вскоре после Второй мировой войны.

Метод решения задач, известный как симплекс-метод, является детищем Данцига, который работал в ВВС США, Университете Беркли и Стэнфордском университете.

Рисунок 2. Математики Джордж Данциг (слева) и Леонид Канторович (справа). Источник: Ф. Сапата.

Модели линейного программирования

Элементы, необходимые для создания модели линейного программирования, подходящей для практической ситуации, включают:

-Целевая функция

-Переменные решения

-Ограничения

В целевой функции вы определяете, чего хотите достичь. Например, предположим, что вы хотите максимизировать прибыль, полученную от производства определенных продуктов. Затем устанавливается функция «прибыли» в соответствии с ценой, по которой продается продукция.

С математической точки зрения, эту функцию можно сократить, используя обозначение суммирования:

Z = ∑k _i x _i

В этом уравнении k _i - коэффициенты, а x _i - переменные решения.

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

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

Виды ограничений

У вас может быть количество M ограничений, начиная с j = 1 до j = M. Математически ограничения бывают трех типов:

1. A _j = ∑ a _ij . х _я
2. B _j ≥ ∑ b _ij . х _я
3. C _j ≤ ∑ c _ij . х _я

Первое ограничение относится к типу линейного уравнения и означает, что должно соблюдаться известное значение A _j .

Два оставшихся ограничения являются линейными неравенствами, и это означает, что известные значения B _j и C _j могут соблюдаться или превышаться, когда отображаемый символ ≥ (больше или равен), соблюдается или не превышается, если символ ≤ (меньше или равно).

Пример модели

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

Местная кондитерская известна двумя фирменными блюдами: тортом Шварцвальд и священным пирогом.

Для приготовления им необходимы яйца и сахар. Для черного леса нужно 9 яиц и 500 г сахара, для сакрипантина 8 яиц и 800 г сахара. Соответствующие цены продажи составляют 8 и 10 долларов.

Проблема заключается в следующем: сколько пирожных каждого вида должна сделать пекарня, чтобы максимизировать прибыль, зная, что в ней 10 кг сахара и 144 яйца?

Переменные решения

Переменными решения являются «x» и «y», которые принимают реальные значения:

-x: количество тортов черного леса

-y: торты сакрипантинового типа.

ограничения

Ограничения обусловлены тем фактом, что количество лепешек является положительным, а количество сырья для их приготовления ограничено.

Следовательно, в математической форме эти ограничения принимают вид:

1. х ≥ 0
2. и ≥0
3. 9x + 8y ≤ 144
4. 0,5 х + 0,8у ≤ 10

Ограничения 1 и 2 составляют ранее выявленное условие неотрицательности, и все возникающие неравенства являются линейными. В ограничениях 3 и 4 указаны значения, которые нельзя превышать: 144 яйца и 10 кг сахара.

Целевая функция

Наконец, целевая функция - это прибыль, полученная при производстве «x» количества тортов из черного леса плюс количество «y» сакрипантинов. Он строится путем умножения цены на количество приготовленных тортов и сложения каждого вида. Это линейная функция, которую мы назовем G (x, y):

G = 8x + 10 лет

Методы решения

Различные методологии решения включают графические методы, симплексный алгоритм и метод внутренней точки, и это лишь некоторые из них.

- Графический или геометрический метод

Когда у вас есть проблема с двумя переменными, подобная той, что описана в предыдущем разделе, ограничения определяют полигональную область в плоскости xy, называемую допустимой областью или областью жизнеспособности.

Рис. 3. Возможная область, в которой найдено решение задачи оптимизации. Источник: Wikimedia Commons.

Эта область строится с использованием линий ограничения, которые являются линиями, полученными из неравенств ограничений, работающих только со знаком равенства.

В случае с пекарней, которая хочет оптимизировать прибыль, линией ограничений являются:

1. х = 0
2. у = 0
3. 9х + 8у = 144
4. 0,5 х + 0,8 у = 10

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

К счастью, для задачи с выпечкой посильная область не пуста, она у нас ниже.

Рисунок 4. Возможные области кондитерской проблемы. Линия с усилением 0 пересекает начало координат. Источник: Ф. Сапата с Geogebra.

Оптимальное решение, если оно существует, находится с помощью целевой функции. Например, когда мы пытаемся найти максимальную прибыль G, у нас есть следующая линия, которая называется линией iso-profit:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

С помощью этой линии мы получаем все пары (x, y), которые обеспечивают заданное усиление G, так что есть семейство линий в соответствии со значением G, но все с одинаковым наклоном -k ₁ / k ₂ , поэтому они параллельные линии.

Оптимальное решение

Теперь можно показать, что оптимальное решение линейной задачи всегда является крайней точкой или вершиной допустимой области. Так:

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

Для нашей выпечки кандидатами в вершины являются A, B и C.

- симплексный метод Данцига

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

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

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

Приложения

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

Вот несколько полей:

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

-Для постановки адекватных задач персоналу компании или завода или графиков для них.

-В выборе наиболее питательных и недорогих продуктов в животноводстве и птицеводстве.

Решенные упражнения

- Упражнение 1

Графически решите модель линейного программирования, поднятую в предыдущих разделах.

Решение

Необходимо изобразить набор значений, определяемых системой ограничений, заданной в задаче:

1. х ≥ 0
2. и ≥0
3. 9x + 8y ≤ 144
4. 0,5 х + 0,8у ≤ 10

Область, заданная неравенствами 1 и 2, соответствует первому квадранту декартовой плоскости. Что касается неравенств 3 и 4, мы начнем с поиска линий ограничения:

9х + 8у = 144

0,5 х + 0,8у = 10 → 5х + 8у = 100

Допустимая область - это четырехугольник, вершинами которого являются точки A, B, C и D.

Минимальная прибыль равна 0, поэтому линия 8x + 10y = 0 является нижним пределом, а линии равной прибыли имеют наклон -8/10 = - 0,8.

Это значение отличается от наклонов других линий ограничения, и поскольку допустимая область ограничена, единственное решение существует.

Рисунок 5. Графическое решение упражнения 1, показывающее допустимую область и точку решения C в одной из вершин указанной области. Источник: Ф. Сапата.

Это решение соответствует линии наклона -0,8, проходящей через любую из точек A, B или C, координаты которых:

А (11; 5,625)

В (0; 12,5)

С (16, 0)

Оптимальное решение

Мы вычисляем значение G для каждой из этих точек:

- (11; 5,625): G _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Самая высокая прибыль получена от производства 11 тортов из черного леса и 5 625 пирогов сакрипантина. Это решение согласуется с решением, найденным с помощью программного обеспечения.

- Упражнение 2.

Проверьте результат предыдущего упражнения с помощью функции Solver, доступной в большинстве электронных таблиц, таких как Excel или LibreOffice Calc, которые включают симплекс-алгоритм для оптимизации в линейном программировании.

Решение

Рис. 6. Подробная информация о решении из упражнения 1 с использованием электронной таблицы Libre Office Calc. Источник: Ф. Сапата.

Рис. 7. Подробная информация о решении из упражнения 1 с использованием электронной таблицы Libre Office Calc. Источник: Ф. Сапата.

Ссылки

1. Brilliant. Линейное программирование. Получено с: brilliant.org.
2. Эппен, Г. 2000. Исследование операций в административной науке. 5-е. Издание. Прентис Холл.
3. Haeussler, E. 1992. Математика для управления и экономики. 2-й. Издание. Grupo Редакционное Ибероамерикана.
4. Hiru.eus. Линейное программирование. Получено с: hiru.eus.
5. Wikipedia. Линейное программирование. Получено с: es. wikipedia.org.