Я прочитал статью , но, похоже, это выходит за рамки моего понимания. Он говорит об этом для оптимизации, но как он отличается от любого другого метода для оптимизации?
Ответ, который вводит меня в линейное программирование, поэтому я могу начать погружение в какой-то менее доступный для новичков материал, будет наиболее полезным.
До сих пор ответы дали алгебраическое определение линейного программирования и оперативное определение. Но есть и геометрическое определение. Многогранник представляет собой n-мерное обобщение многоугольника (в двух измерениях) или многогранника (в трех измерениях). Выпуклый многогранник является многогранником, который также является выпуклым множеством. По определению, линейное программирование является задачей оптимизации, в которой вы хотите максимизировать или минимизировать линейную функцию на выпуклом многограннике.
Например: предположим, что вы хотите купить комбинацию красного песка и синего песка. Предположим также:
Если вы рисуете изображение в плоскости, сколько вы можете купить с этими ограничениями, это выпуклый пятиугольник. Затем, независимо от того, что вы хотите оптимизировать (например, общее количество золота в песке), вы можете знать, что оптимальный (не обязательно единственный оптимальный) находится в одной из вершин многогранника. Фактически, есть гораздо более сильный результат: даже в больших измерениях любая такая проблема линейного программирования может быть решена в полиномиальное время, в числе ограничений или предполагаемых сторон многогранника. Обратите внимание, что не каждое ограничение соответствует стороне. Если ограничение является равенством, оно может уменьшить размерность многогранника. Или, если ограничение является неравенством, это может быть не создание стороны, если оно уже подразумевается всеми другими ограничениями.
Существует множество практических проблем оптимизации, которые являются линейным программированием. Одним из первых примеров была "проблема с диетой": учитывая меню кучи видов пищи, какова самая дешевая сбалансированная диета? Это проблема линейного программирования, потому что стоимость линейна и потому что все ограничения (витамины, калории, предположение, что вы не можете купить отрицательное количество пищи и т.д.) Являются линейными.
Но линейное программирование еще более важно по теоретической причине. Это один из самых мощных алгоритмов полиномиального времени для оптимизации или для любых других целей. Таким образом, это очень важно как замена примерно для решения других задач оптимизации и как подпрограмма для их точного решения.
Да, два обобщения - это выпуклое программирование и целочисленное программирование. С некоторыми характеристиками выпуклое программирование может работать так же хорошо, как и линейное программирование при условии, что цель (вещь для максимизации) является линейной. Оказывается, что выпуклость, а не плоские стороны, является основной причиной того, что линейное программирование имеет хороший алгоритм.
Целочисленное программирование, с другой стороны, обычно сложно. Например, предположим, что в примере проблемы вы должны покупать песок в мешках фиксированного размера, а не навалом; то есть целочисленное программирование. Существует теорема о том, что она может быть NP-жесткой. Насколько это сложно на практике, зависит от того, насколько близко оно связано с линейным программированием. Есть некоторые знаменитые примеры целых задач программирования, в которых, чудом, все вершины линейной программы являются целыми точками. Затем вы можете решить линейную программу, и решение будет неотъемлемым. Одним из примеров такой проблемы является проблема брака, как жениться на русских мужчинах и русских женщинах друг с другом, чтобы максимизировать полное счастье. (Или, n городов для n заводов, n заданий для n претендентов, n компьютеров для n принтеров и т.д.)
Линейное программирование - это тема "математического программирования", которая также называется "математической оптимизацией". Линейные программы отличаются от общих математических программ тем, что для линейной программы (ЛП) все функции ограничения и целевая функция линейны относительно своих переменных.
Хорошим местом для начала было бы здесь, если вы хотите оригинальную работу Данцига, или если вы хотите получить учебник, я рекомендую этот. Если вы хотите посмотреть свои собственные ресурсы, начните с поиска Simplex method - это очень распространенная техника для решения этих программ или менее общее, но определенно многочленное время Метод эллипсоида. Хотя я не прочитал все это, быстро просмотрев его, также предлагает this. PDF может быть хорошим началом. Удостоверьтесь, что все, что вы в конечном итоге читаете, рассматривает двойственность (и, возможно, в частности, лемму Фаркаса), поскольку это центральная идея в большинстве решателей LP.
Наиболее естественными расширениями являются либо программы Integer (похожие на LP, но все переменные должны принимать целочисленные значения, то есть не дробные компоненты) или выпуклое программирование (возможно, более общее расширение). Хорошая выпуклая текстовая книга оптимизации доступна в формате PDF здесь.
Как и все остальные, линейное программирование - это способ решения задач оптимизации, в которых члены линейны.
Это может помочь понять, какие типы проблем решаются LP
Один пример, где я использовал Линейное программирование, - это построение графика ресторана. В ресторане у вас есть наборы навыков:
И у вас есть сотрудники, каждый с одним или несколькими наборами навыков. У каждого сотрудника также есть определенная доступность. Например, Боб не может работать в воскресенье утром, потому что он пастор в местной церкви. Сотрудники также имеют соответствующую стоимость. Боб может составлять 10,50 долл./Час, тогда как Сьюзи - 5,15 долл./Час. Наконец, у сотрудников могут быть минимальные гарантированные часы. Поскольку Боб был сотрудником в течение 15 лет, босс говорит, что он всегда будет получать как минимум 35 часов.
В ресторане есть свои требования. Например, он имеет 3 смены: утро, вечер и ночь, и каждая из этих смен имеет набор требований к персоналу: нам нужно 1 повар, 1 сервер, 1 менеджер по утрам, 3 повара, 2 сервера, 2 хоста, 2 менеджеры во второй половине дня и 4 повара, 4 сервера, 3 хоста, 2 менеджера, 2 человека вечером. Каждая смена будет иметь длительность, и вы можете определить стоимость каждой смены, умножив ее продолжительность на заработную плату работника.
Наконец, у нас есть государственные и федеральные законы, а также некоторые основные "бизнес-правила": ни один сотрудник не может работать более 8 часов без перехода в овертайм. Ни один сотрудник не может быть назначен менее чем за 2 часа (потому что он сосать, чтобы совершить 30-минутный переезд на 2-часовой смену), сотрудники не могут работать с двумя перекрывающимися сменами и т.д.
Теперь, учитывая все эти требования, дайте мне график, который отвечает всем требованиям и дает самую низкую стоимость рабочей силы.
Это пример проблемы оптимизации линейного программирования.
Линейная программа обычно состоит из:
Объектная функция, переменные, границы переменных и ограничения.
Поскольку мы хотим минимизировать затраты, наша целевая функция будет включать в себя сдвиги, которые работают сотрудники, и связанные с ними затраты (продолжительность перехода * заработная плата).
Переменные в этом случае - это сдвиги, которые могут выполнять каждый сотрудник.
Оценки этих переменных целые числа от 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} из-за ограничений, упомянутых выше. Эти три части информации указывают, что в качестве первого утреннего повара можно назначить не более одного сотрудника.
Итак, как только вы определили все ограничения, которые моделируют вашу проблему, вы можете начать решать проблему. Если решение можно найти (и в зависимости от ограничений проблема может быть неосуществимой), она даст вам задания для сотрудников, которые производят самую низкую недельную стоимость рабочей силы.
Линейное программирование - это метод оптимизации, который включает в себя линейные ограничения и линейную целевую функцию. Ограничения записываются для ограничения пространства проблем, а целевая функция - это то, что вы пытаетесь свести к минимуму (или, возможно, максимизировать), который удовлетворяет ограничениям. симплекс-алгоритм обычно используется для перемещения по краям пересечения ограничений, чтобы найти минимальное (или максимальное) значение целевой функции, удовлетворяющей ограничениям.
При настройке проблемы с LP важно следить за тем, чтобы ограничения правильно привязывали целевую функцию. Можно определить ограничения, которые не приводят к возможному решению (например, x > 1 и -x > 1). Это связано с ограничением. Кроме того, можно недооценивать проблему (например, найти min x такой, что x < 1).
Одна большая разница (или, по крайней мере, отличительная особенность) линейного программирования состоит в том, что ограничения моделируются как линейные уравнения, т.е. все они являются формами c_1 x_1 + c_2 x_2.... Раздел стандартной формы статьи wikipedia дает довольно хороший обзор этого.
Еще одно отличие состоит в том, что линейное программирование стремится максимизировать (или минимизировать) ОДНУ функцию - вы не можете эффективно выполнять многооконную оптимизацию.