Что такое линейное программирование? [закрытый]
5 ответов
В ответах до сих пор было дано алгебраическое определение линейного программирования и операционное определение. Но есть и геометрическое определение. политоп - это n-мерное обобщение многоугольника (в двух измерениях) или многогранника (в трех измерениях). выпуклый политоп - это политоп, который также является выпуклым множеством. По определению, линейное программирование - это задача оптимизации, в которой требуется максимизировать или минимизировать линейную функцию на выпуклом многоугольнике.
Например: Предположим, что вы хотите купить некоторую комбинацию красного и синего песка. Предположим также:
- Вы не можете купить отрицательное количество ни того, ни другого.
- На складе есть только 300 фунтов красного песка и 400 фунтов синего песка.
- Также ваш джип имеет ограничение по весу в 500 фунтов.
Если вы нарисуете на плоскости, сколько вы можете купить при этих ограничениях, то это будет выпуклый пятиугольник. Тогда, что бы вы ни хотели оптимизировать (скажем, общее количество золота в песке), вы можете знать, что оптимум (не обязательно единственный оптимум) находится в одной из вершин политопа. На самом деле, существует гораздо более сильный результат: Даже в больших размерностях любая такая задача линейного программирования может быть решена за полиномиальное время по числу ограничений, или предполагаемых сторон политопа. Обратите внимание, что не каждое ограничение соответствует стороне. Если ограничение является равенством, оно может уменьшить размерность политопа. Или, если ограничение является неравенством, оно может не создавать сторону, если она уже подразумевается всеми остальными ограничениями.
Существует множество практических задач оптимизации, которые являются линейным программированием. Одним из первых примеров была "проблема диеты": Учитывая меню, состоящее из множества видов продуктов, какой самый дешевый из возможных сбалансированных рационов? Это проблема линейного программирования, потому что стоимость линейна, и потому что все ограничения (витамины, калории, предположение, что вы не можете купить отрицательное количество еды, и т.д.) линейны.
Но линейное программирование еще более важно по теоретической причине. Это один из самых мощных алгоритмов полиномиального времени для оптимизации или для любой другой цели. Как таковое, оно очень важно как замена для приблизительного решения других задач оптимизации и как подпрограмма для их точного решения.
Да, два обобщения - это выпуклое программирование и целочисленное программирование. С некоторыми оговорками, выпуклое программирование может работать так же хорошо, как и линейное, при условии, что цель (то, что нужно максимизировать) линейна. Оказывается, что выпуклость, а не плоские стороны, является основной причиной того, что линейное программирование имеет хороший алгоритм.
Целочисленное программирование, с другой стороны, обычно трудно. Например, предположим, что в примере задачи вам нужно купить песок в мешках фиксированного размера, а не навалом; тогда это целочисленное программирование. Существует теорема, что оно может быть NP-трудным. Насколько оно сложно на практике, зависит от того, насколько оно близко к линейному программированию. Есть несколько известных примеров задач целочисленного программирования, в которых, чудесным образом, все вершины линейной программы являются целочисленными точками. Тогда вы можете решить линейную программу, и решение окажется целочисленным. Одним из примеров такой проблемы является проблема брака: как женить n мужчин и n женщин друг на друге, чтобы максимизировать общее счастье. (Или: n городов - n фабрик, n рабочих мест - n соискателей, n компьютеров - n принтеров и т.д.)
.Линейное программирование - это тема «математического программирования», которую также называют «математической оптимизацией». Линейные программы отличаются от общих математических программ тем, что для линейной программы (LP) все функции ограничений и целевая функция являются линейными по отношению к своим переменным.
Хорошее место для начала было бы здесь , если вам нужна оригинальная работа Данцига или если вы хотите получить учебник, я рекомендую этот . Если вы хотите найти свои собственные ресурсы, начните с поиска Симплексного метода - это очень распространенный метод решения этих программ или менее распространенный, но определенно полиномиальный метод Эллипсоидный метод . Хотя я еще не читал его полностью, беглый просмотр предполагает, что этот PDF-файл может быть хорошим местом для начала. Убедитесь, что все, что вы в конечном итоге прочитаете, касается двойственности (и, возможно, конкретно леммы Фаркаса ), поскольку это центральная идея в большинстве решателей LP.
Наиболее естественными расширениями являются либо целочисленные программы (аналогичные LP, но все переменные должны принимать целочисленные значения, т. Е. Без дробных компонентов), либо выпуклое программирование (возможно, более общее расширение). Хороший учебник по выпуклой оптимизации доступен в формате PDF здесь .
Линейное программирование - это метод оптимизации, который включает линейные ограничения и линейную целевую функцию. Ограничения написаны так, чтобы ограничить проблемное пространство, а целевая функция - это то, что вы пытаетесь минимизировать (или, возможно, максимизировать), что удовлетворяет ограничениям. Симплексный алгоритм обычно используется для обхода краев пересечения ограничений, чтобы найти минимальное (или максимальное) значение целевой функции, удовлетворяющее ограничениям.
При постановке задачи LP важно убедиться, что ограничения правильно ограничивают целевую функцию. Можно определить ограничения, которые не приводят к возможному решению (например, x> 1 и -x> 1). Это слишком ограничено. Также возможно ограничить проблему (например, найти min x такое, что x <1).
Одно большое отличие (или, по крайней мере, отличительная черта) линейного программирования заключается в том, что ограничения моделируются как линейные уравнения, т. Е. Они все в форме c_1 x_1 + c_2 x_2 ... . Раздел стандартной формы статьи в Википедии дает довольно хороший обзор этого.
Еще одно отличие / особенность заключается в том, что линейное программирование стремится максимизировать (или минимизировать) ОДНУ функцию - вы не можете эффективно выполнить многокритериальную оптимизацию.
Как уже все сказали, линейное программирование - это способ решения задач оптимизации, в котором условия линейны.
Это может помочь понять, какие типы задач решает ЛП
Один из примеров, где я использовал линейное программирование, это построение расписания ресторана. В ресторане у вас есть наборы навыков:
- Повара
- Серверы
- Посудомойщики
- Хозяева
- Бустеры
- Управляющий и т.д.
И у вас есть сотрудники, каждый из которых имеет один или несколько наборов навыков. Каждый сотрудник также имеет определенную доступность. Например, Боб не может работать по утрам в воскресенье, потому что он пастор местной церкви. Сотрудники также имеют соответствующую стоимость. Боб может стоить $10,50/час, а Сьюзи - $5,15/час. Наконец, у сотрудников могут быть минимальные гарантированные часы. Поскольку Боб работает уже 15 лет, босс говорит, что он всегда будет получать не менее 35 часов.
У самого ресторана есть требования. Например, у него есть 3 смены: Утренняя, Дневная и Ночная, и каждая из этих смен имеет свой набор требований к персоналу: 1 повар, 1 сервер, 1 менеджер утром, 3 повара, 2 сервера, 2 хозяина, 2 менеджера днем, и 4 повара, 4 сервера, 3 хозяина, 2 менеджера, 2 грузчика вечером. Каждая смена будет иметь продолжительность, и вы можете определить стоимость каждой смены, умножив продолжительность на почасовую заработную плату работника.
Наконец, у нас есть законы штата и федеральные законы, а также некоторые основные правила "бизнеса": Ни один сотрудник не может работать более 8 часов, не переходя на сверхурочную работу. Ни один сотрудник не может работать менее 2 часов (потому что было бы отстойно добираться 30 минут на работу в течение двухчасовой смены), сотрудники не могут работать в две пересекающиеся смены и т.д.
Теперь, учитывая все эти требования, дайте мне расписание, которое отвечает всем требованиям и дает самые низкие трудовые затраты.
Это пример оптимизационной задачи линейного программирования.
Линейная программа обычно состоит из:
Целевой функции, переменных, границ переменных, и ограничения.
Поскольку мы хотим минимизировать затраты, наша объективная функция будет включать смены, в которые работают сотрудники, и связанные с ними затраты (продолжительность смены * заработная плата).
Переменными в данном случае являются смены, в которые может работать каждый сотрудник.
Границы этих переменных целые числа от 0 до 1, потому что либо сотрудник работает в смену (1), либо он не работает в смену (0). Это, кстати, специальная программа, называемая Binary Integer Program или сокращенно BIP, потому что все переменные - целые числа (никаких дробных значений) и все значения либо 0, либо 1.
Ограничения - это ограничения равенства/неравенства, основанные на требованиях, приведенных выше.
Например, если Боб и Сюзи могут работать поварами по утрам, то Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1, причем Bob_Morning_Cook_Shift = {0,1} и Suzy_Morning_Cook_Shift = {0,1} из-за ограничений, указанных выше. Эти три части информации указывают, что максимум только один сотрудник может быть назначен первым утренним поваром.
Итак, как только вы определили все ограничения, моделирующие вашу проблему, можно приступать к ее решению. Если решение может быть найдено (а в зависимости от ограничений задача может быть невыполнимой), оно даст вам назначения сотрудников, которые дают наименьшие недельные затраты на рабочую силу.