Какие примеры проблем хорошо подходят для целочисленного линейного программирования?

Question

Я всегда писал программное обеспечение для решения бизнес-задач. Я наткнулся на LIP, пока просматривал один из SO-постов. Я гуглил это, но я не могу сказать, как я могу использовать это, чтобы решить деловые проблемы. Цените, если кто-то может помочь мне понять с точки зрения непрофессионала.

Answer 1

ILP может быть использован для решения по существу любой проблемы, связанной с принятием множества решений, каждое из которых имеет только несколько возможных результатов, известных заранее, и в которых общее «качество» любогоКомбинация вариантов может быть описана с использованием функции, которая не зависит от «взаимодействий» между вариантами.Чтобы увидеть, как это работает, проще всего ограничиться переменными, которые могут быть только 0 или 1 (наименьший полезный диапазон целых чисел).Теперь:

• Каждое решение, требующее ответа да / нет, становится переменной
• Целевая функция должна описывать то, что мы хотим максимизировать (или минимизировать), как взвешенную комбинацию этих переменных
• Вам необходимо найти способ выражения каждого ограничения (комбинации вариантов, которые нельзя сделать одновременно), используя одно или несколько ограничений линейного равенства или неравенства

Пример

Например, предположим, что у вас есть 3 рабочих, Энн, Билл и Карл, и 3 рабочих места, «Чистка», «Печать» и «Упаковка».Все люди могут выполнять все работы, но у каждого из них разные уровни эффективности / способностей на каждой работе, поэтому мы хотим найти лучшую задачу для каждого из них, чтобы максимизировать общую эффективность.Мы хотим, чтобы каждый человек выполнял ровно 1 задание.

Переменные

Один из способов решения этой проблемы - 9 переменных, по одной на каждую комбинацию работника и задания.Переменная x_ad получит значение 1, если Anne должна Dust в оптимальном решении, и 0 в противном случае;x_bp получит значение 1, если Билл должен упаковать оптимальное решение, и 0 в противном случае;и т. д.

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

Следующее, что нужно сделать, это сформулировать целевую функцию, которую мы хотим максимизировать или минимизировать.Предположим, что, основываясь на самых последних оценках производительности Анны, Билла и Карла, у нас есть таблица из 9 чисел, показывающая, сколько минут требуется каждому из них для выполнения каждого из 3 заданий.В этом случае имеет смысл взять сумму всех 9 переменных, каждая из которых умножена на время, необходимое этому конкретному работнику для выполнения этой конкретной работы, и попытаться минимизировать эту сумму, то есть минимизировать общее время, необходимое дляВыполняйте всю работу.

Ограничения

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

Чтобы убедиться, что Анна выполняет ровно 1 задание, мы можем добавить ограничение: x_ad + x_at + x_ap = 1. Аналогичные ограничения можно добавить дляБилл и Карл.

Чтобы убедиться, что ровно 1 человек пылится, мы можем добавить ограничение, которое x_ad + x_bd + x_cd = 1. Аналогичные ограничения могут быть добавлены для набора текста и упаковки.

В целомЕсть 6 ограничений.Теперь вы можете поставить эту задачу с 9 переменными и 6 ограничениями для решателя ILP, и она выплюнет значения переменных в одном из оптимальных решений - ровно 3 из них будут равны 1, а остальные - 0.3, которые равны 1, говорят вам, какие люди должны выполнять какую работу!

ILP является общим

Как это происходит, эта конкретная проблема имеет специальную структуру , которая позволяет ейбыть решена более эффективно, используя другой алгоритм.Преимущество использования ILP состоит в том, что вариации проблемы могут быть легко включены: например, если на самом деле было 4 человека и только 3 рабочих места, тогда нам нужно было бы ослабить ограничения, чтобы каждый человек делал максимум 1 работа, а не ровно 1 работа.Это можно выразить, просто изменив знак равенства в каждом из первых 3-х ограничений на знак «меньше или равно».

Answer 2

Сначала прочитайте пример линейного программирования из Википедии

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

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

Так пользователь flolo говорит: случаи использования, в которых я часто встречался: в цифровыхПри проектировании схемы у вас есть объекты, которые нужно разместить / отобразить на определенных частях микросхемы (FPGA-Placing) - это можно сделать с помощью ILP.Также в коде HW-SW часто возникает проблема с разделами: какая часть программы все еще должна работать на ЦП, а какая часть должна быть ускорена на аппаратном обеспечении.Это также можно решить с помощью ILP.

Answer 3

ILP «сам по себе» может напрямую моделировать множество вещей.Если вы ищете примеры ЛП, вы, вероятно, найдете много известных случаев из учебников, таких как проблема диеты

Учитывая набор таблеток, каждая с содержанием витаминов и ежедневной квотой витаминов, найдите самый дешевыйкоктейль, который соответствует квоте.

Многие такие проблемы, естественно, имеют случаи, когда varialbe должны быть целыми числами (возможно, вы не можете разделить таблетки пополам)

Хотя действительно интересный материалчто на самом деле большая часть комбинаторных проблем сводится к LP.Одной из моих любимых является проблема назначения

Учитывая набор из N рабочих, N задач и N by N matirx, описывающих, сколько каждый работник берет за каждую задачу, определите, какую задачу дать каждойрабочий, чтобы минимизировать затраты.

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

---

Когда речь идет о ILP,У ILP есть дополнительное преимущество / сложность быть NP-завершенным.Это означает, что его можно использовать для моделирования очень широкого спектра проблем (в этом отношении также очень популярна логическая выполнимость).Поскольку существует много хороших и оптимизированных решателей ILP, часто жизнеспособно перевести NP-полную задачу в ILP вместо того, чтобы разрабатывать собственный алгоритм.

Answer 4

Пример проблемы ILP будет выглядеть примерно так:

• развернуть 37 x 1 + 45 x 2

где

• x1, x2, ... должно быть целых положительных чисел

... но есть набор ограничений в форме

• a1 ∙ x1 + b1 ∙ x2
• a2 ∙ x1 + b2 ∙ x2
• a3 ∙ x1 + b3 ∙ x2
• ...

---

Теперь, более простое изложение примера Википедии:

• У фермера L м² земли для посадки пшеницы или ячменя или их комбинации.
• У фермера есть F грамма удобрения и P грамм инсектицида.
• Каждый м² пшеницы требует F1 грамма удобрения и P1 грамм инсектицида
• Каждый м² ячменя требует F2 грамма удобрения и P2 грамм инсектицида

Теперь

• Позвольте a1 обозначить цену продажи пшеницы за1 м²
• Пусть a2 обозначает цену продажи ячменя за 1 м²
• Пусть x1 обозначить площадь земли для посадки пшеницы
• Позвольте x2 обозначить площадь земли для посадки ячменя
• x1, x2 - положительные целые числа (предположим, что мы можем посадить с разрешением 1 м²)

Итак,

• прибыль a1 ∙ x1 + a2 ∙ x2 - мы хотим максимизировать его
• Поскольку фермер имеет ограниченную площадь земли: x1 + x2 <=L </em>
• Поскольку фермер имеет ограниченное количество удобрений: F1 ∙ x1 + F2 ∙ x2
• Потому что фермер имеет ограниченное количество инсектицидов: P1 ∙ x1 + P2 ∙ x2

a1, a2, L, F1, F2, F, P1, P2, P - все константы (в нашем примере: положительные)

Мы ищем натуральные числа x1, x2 , который максимизирует указанное выражение с учетом указанных ограничений.

Надеюсь, это понятно ...

Answer 5

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

1. журнал Interfaces, опубликованный INFORMS (Институт исследований операций и наук управления)
2. победителиПремии Франца Эдельмана за достижения в области исследования операций и наук управления

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

Answer 6

Вы можете легко применять линейную программу везде, где хотите оптимизировать, а целевая функция линейна.Вы можете составить расписание (я имею в виду большие, например, железнодорожные компании, которым необходимо оптимизировать использование транспортных средств и путей), производство (оптимизировать выигрыш), почти все.Иногда сложно сформулировать свою проблему как IP, и / или иногда вы сталкиваетесь с проблемой, которая заключается в том, что ваше решение заключается в том, что вам необходимо произвести, например, 0,345 машины для оптимального выигрыша.Это, конечно, невозможно, и поэтому вы ограничиваете еще больше: ваша переменная для количества автомобилей должна быть целочисленной.Даже если сейчас это звучит проще (потому что у вас есть бесконечно меньше вариантов для вашей переменной), это на самом деле сложнее.В этот момент он становится NP-сложным.Что на самом деле означает, что вы можете решить ЛЮБУЮ проблему с вашего компьютера с помощью ILP, вам просто нужно ее преобразовать.

Для вас я бы порекомендовал вступление к чтению некоторых базовых (I) LP материалов.С моей точки зрения, я не знаю ни одного хорошего онлайн-сайта (но если вы будете работать, вы найдете его), в качестве книги я могу порекомендовать Линейное программирование из Чватал .Он имеет очень хорошие примеры, а также описывает реальные случаи использования.