Задачи линейного программирования, решения и приложения [с примером]

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

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

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

Теперь один пакет апельсинов стоит вам 500 рупий, а пакет яблок — 750 рупий. Вы можете заработать 100 рупий от продажи одного мешка апельсинов и 200 рупий от продажи одного мешка яблок.

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

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

Что такое линейное программирование?

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

Основы линейного программирования

Вот некоторые основные термины линейного программирования:

Ограничение

Ограничения (или ограничения) переменных вашего решения называются ограничениями. В большинстве случаев временные ограничения — это ограничения ваших ресурсов для решения проблемы.

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

Эти переменные определяют ваш вывод. Ваш результат зависит от этих переменных, поэтому мы называем их «переменными решения».

Неотрицательность Ограничение

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

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

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

Формулировка задач линейного программирования

Вы должны знать, как сформулировать линейное программирование, чтобы применить его в реальной жизни. Предположим, вы производитель игрушек и производите только две игрушки: A и B. Грубо говоря, для производства ваших игрушек требуется два ресурса X и Y. Вот требования к вашим игрушкам:

• Одна единица игрушки A требует от вас одной единицы ресурса X и трех единиц ресурса Y.

• Одна единица игрушки B требует одной единицы ресурса X и двух единиц ресурса Y.

У вас есть пять единиц ресурса X и 12 единиц ресурса Y. Ваша норма прибыли от продажи этих игрушек составляет:

• 6 индийских рупий за каждую проданную единицу игрушки А
• 5 индийских рупий за каждую проданную единицу игрушки B

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

Решение

Представим нашу задачу линейного программирования в виде уравнения:

Z = 6а + 5б

Здесь z обозначает общую прибыль, a обозначает общее количество единиц игрушек A, а b обозначает общее количество до единиц B. Наша цель — максимизировать значение Z (прибыль).

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

а + б 5

Теперь каждая единица игрушек A и B требует 3 и 2 единицы ресурса Y соответственно. И всего у нас всего 12 единиц ресурса Y, так что математически это будет выглядеть так:

3а + 2б 12

Помните, что значения единиц измерения игрушки А могут быть только целыми числами. Это означает, что у нас также есть ограничения a->0 и b<-0.

Итак, теперь у вас есть правильная задача линейного программирования. Вы можете сформулировать другие задачи линейного программирования, следуя этому примеру. Хотя этот пример был довольно простым, задачи LP могут стать очень сложными.

Читайте: Идеи и темы проекта линейного программирования

Этапы формулирования задач линейного программирования

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

• Найдите переменные решения
• Найдите целевую функцию
• Определите ограничения
• Помните об ограничении неотрицательности

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

Решение задач линейного программирования с помощью R

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

Пример

Начнем с основной проблемы. У организации есть два продукта с продажными ценами 25 и 20 индийских рупий, которые называются продуктами А и В соответственно. Каждый день у них есть 1800 единиц ресурсов для производства этих продуктов. Продукт A требует 20 единиц ресурсов, а B требует 12 единиц ресурсов. Время производства обоих этих продуктов составляет четыре минуты, и организация получает в общей сложности восемь рабочих часов каждый день. Проблема в том, каким должен быть объем производства каждого из этих продуктов, чтобы максимизировать прибыль компании?

Решение:

Мы начнем решать эту задачу с определения ее целевой функции:

макс(Продажи) = макс( 25 y 1 + 20 y 2 )

Здесь 25 и 20 — цены продуктов A и B соответственно, y1 — общее количество произведенных единиц продукта A, а y2 — общее количество произведенных единиц продукта B. Наши переменные решения — y1 и y2.

Теперь мы установим ограничения для нашей задачи:

Ограничение ресурсов:

20 лет 1 + 12 лет 2 1800

Ограничение времени:

4 года 1 + 4 года 2 8 * 60

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

Использование R для решения проблемы:

Мы будем использовать lpsolve для решения этой задачи LP и начнем с установки целевой функции:

> требуется (lpSolve)

Загрузка необходимого пакета: lpSolve

> target.in <- c(25, 20)

> цель.in

[1] 25 20

Затем мы построим матрицу ограничений:

> const <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> константа

[,1] [,2]

[1,] 20 12

[2,] 4 4

> time_constraints <- (8*60)

> resource_constraints <- 1800

> time_constraints

[1] 480

> ресурс_ограничения

[1] 1800

Давайте теперь создадим уже определенные уравнения:

> rhs <- c(resource_constraints, time_constraints)

> правая сторона

[1] 1800 480

> направление <- c("<=", "<=")

> направление

[1] «<=» «<=»

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

lp(направление, цель, const.mat, const.dir, const.rhs)

> оптимальный <- lp(direction=”max”, target.in, const, direction, rhs)

> оптимальный

Успех: целевая функция равна 2625.

> резюме (оптимальное)

Режим класса длины

направление 1 -нет-числовое

x.count 1 -нет-числовой

цель 2 - нечисловая

const.count 1 -none- числовой

ограничения 8 -нет- числовой

int.count 1 -нет-числовой

int.vec 1 -нет-числовой

bin.count 1 -нет-числовой

двоичный.vec 1 -нет-числовой

num.bin.solns 1 -нет- числовой

objval 1 -нет- числовой

решение 2 - не числовое

presolve 1 -нет- числовой

Compute.sens 1 -нет- числовой

sens.coef.from 1 -none- числовой

sens.coef.to 1 -none- числовой

двойные 1 -нет-числовой

duals.from 1 -none- числовой

duals.to 1 -none- числовой

шкала 1 - нет - числовая

use.dense 1 -none- числовой

плотный.col 1 -нет-числовой

плотно.val 1 -нет- числовой

плотно.const.nrow 1 -нет- числовой

плотный.ctr 1 -нет-числовой

use.rw 1 -нет-числовой

tmp 1 -none- символ

статус 1 -нет-числовой

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

Оптимальные значения для y1 и y2:

Помните, что y1 и y2 были единицами продукта A и продукта B, которые мы должны были произвести:

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

[1] 45 75

Оптимальный показатель продаж:

Максимальная прибыль, которую мы можем получить с полученными значениями y1 и y2, составляет:

> оптимальный $объект

[1] 2625

Читайте также: Линейная алгебра для машинного обучения

Использование линейного программирования

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

• С ростом популярности служб доставки линейное программирование стало одним из самых популярных методов поиска оптимальных маршрутов. Когда вы берете Ola или Uber, программное обеспечение будет использовать линейное программирование, чтобы найти лучший маршрут. Компании по доставке, такие как Amazon и FedEx, также используют его для определения наилучших маршрутов для своих курьеров. Они сосредоточены на сокращении времени доставки и стоимости.
• Обучение с учителем машинного обучения работает с фундаментальными концепциями линейного программирования. В обучении с учителем вы должны найти оптимальную математическую модель для прогнозирования результата в соответствии с предоставленными входными данными.
• Сектор розничной торговли использует линейное программирование для оптимизации полочного пространства. С таким количеством доступных брендов и продуктов определить, где их разместить в магазине, является очень сложной задачей. Размещение товара в магазине может сильно повлиять на его продажи. Крупные розничные сети, такие как Big Bazaar, Reliance, Walmart и т. д., используют линейное программирование для определения продакт-плейсмента. Они должны помнить об интересах потребителей, обеспечивая при этом наилучшее размещение продукта для получения максимальной прибыли.
• Компании используют линейное программирование для улучшения своих цепочек поставок. Эффективность цепочки поставок зависит от многих факторов, таких как выбранные маршруты, сроки и т. д. Используя линейное программирование, они могут найти наилучшие маршруты, сроки и другое распределение ресурсов для оптимизации своей эффективности.

Узнайте больше о линейном программировании и науке о данных

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

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

• Главные причины стать Data Scientist
• Алгоритмы, которые должен знать каждый специалист по данным
• Как стать специалистом по данным

С другой стороны, вы можете пройти курс по науке о данных, чтобы учиться у отраслевых экспертов. Вы сможете учиться в интерактивном режиме с помощью видео, викторин и проектов. Прохождение курса поможет вам освоить необходимые навыки, чтобы стать профессиональным специалистом по данным. Ознакомьтесь с дипломом PG IIIT-B и upGrad в области науки о данных, который создан для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические практические семинары, наставничество с отраслевыми экспертами, индивидуальные встречи с отраслевыми наставниками, более 400 часов. обучения и помощи в трудоустройстве в ведущих фирмах.