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

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
УСЛОВИЯ ОПТИМАЛЬНОСТИ ПЕРВОГО ПОРЯДКА
БИБЛИОГРАФИЯ
Необходимость в экстремальных значениях (максимумах или минимумах) функции. Переменные которой могут удовлетворять определенным ограничениям. Приводит к проблеме оптимизации. В самом общем виде. Задачи оптимизации. Как правило. Выражается в максимизации F(х) при условии Х Х, символ стоя на элемент. Постановка проблемы с точки зрения максимизации не ограничительными. Поскольку мин х х F(х) = макс Х Х { ф (х

Такие экстремальные задачи классифицируются в соответствии с математическими свойствами

целевой функции F и допустимой области X. Говорят. Что задача оптимизации выполнима тогда и только тогда. Когда ее выполнимая область непуста. Эта запись ограничит внимание на случай. Когда X-подмножество конечномерного векторного пространства. Скажем евклидово n-пространство , E n так. Что x = (x1, x 2,, x n ) обозначает вектор из n переменных. Задачи такого рода называются также математическими программами, а их изучение-математическим программированием. Когда X= en , говорят. Что задача ничем не ограничена Нахождение относительных минимумов и максимумов в элементарном дифференциальном исчислении обычно имеет дело с неограниченными оптимизационными задачами на вещественной прямой.

В продвинутом исчислении мы сталкиваемся с многомерной неограниченной оптимизацией. Родственным классом задач является тот. В котором X-множество решений системы уравнений gi (x) = 0, i = 1, m. Символически X = {x: gi (x ) = 0, i = 1,, mПри наличии подходящих условий дифференцируемости и линейной независимости оптимизационные задачи этой формы могут быть решены методом множителей Лагранжа, подход. Восходящий к восемнадцатому веку (задолго до того. Как был использован термин программирование).

Среди задач ограниченной оптимизации ведущим представителем является задача линейного программирования. Линейное программирование (LP) можно описать как задачу максимизации линейной функции F над многогранником X. Это означает . Что целевая функция имеет вид F (x ) = c 1x 1 + + c n x n, где c 1,, cn заданы константы , а многогранник X-множество решений системы линейных неравенств, скажем:

Невозможно воспроизвести видео в связи с технической ошибкой.(Код ошибки: 100000)

Во многих практических приложениях переменные x j должны удовлетворять xj 0. Такое ограничение неотрицательности эквивалентно xj 0, частному случаю (1).

Экономика-это ведущая область применения социальных наук для LP (и нелинейного программирования также).

Типичным примером является оптимальное распределение дефицитных ресурсов. Например, предположим. Что фирма производит n продуктов из m ресурсов. Каждая единица продукта j потребляет a ij единиц ресурса i, из которых имеется bi единиц. Предполагается. Что потребление ресурсов по продукту j пропорционально уровню x j соответствующей производственной деятельности; далее предполагается. Что эффекты потребления аддитивны. В этом случае общий объем ресурса

i потребляемая n уровней производства x 1, x 2, x n, является a i 1, x 1 + a i 2x 2 + + a в x n , каждая из этих сумм не должна превышать имеющуюся сумму. А именно b i . Неизвестные уровни производства xj, естественно. Неотрицательны. Наконец, предполагается. Что целью является максимизация прибыли. Получаемой в результате производства. И что она имеет вид p 1x 1 + p 2x 2 + + p nx n. Таким образом. Задача оптимизации такова:

В некоторых случаях целесообразно ввести другие линейные ограничения в (2). Это может быть выход требований я 1х 1 + а я 2х 2 + + а вх н б я , я я 2, или материальный баланс уравнения а

я 1х 1 + а я 2х 2 + + а вх н = б мне, Я Я 3. Какие результаты — это все еще проблема линейного программирования.

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

n ингредиентов j = 1, , n, имеющих удельные затраты c 1,, cn, соответственно. Каждая единица ингредиента j вносит свой вклад в ij единицы питательного вещества i. Предполагается пропорциональность и аддитивность этих вкладов. Таким образом. Проблему можно сформулировать как:

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

Второе из этих приложений называется

транспортной проблемой:

который возникает в контексте судоходства. Но на самом деле находит применение и в других областях. В этом случае один товар должен быть отправлен из m источников в n пунктов назначения. В начале координат i = 1, , mимеется запас a i единиц товара. В пункте назначения j = 1,, nсуществует спрос на dj единиц товара. Для удовлетворения потребностей в поставках необходимо. Чтобы a 1 + + a m d 1 + + d n . Стоимость доставки единицы товара из i в j обозначается c ij. В предположении о линейности стоимость доставки x ij единиц товара из пункта отправления

i в пункт назначения j будет c ijx ij. Общая стоимость составляет c 11x 11 + + cmnx mn. Задача назначения является частным случаем транспортной задачи. В которой m = n и a i = d j = 1 для всех i и j. Соображения осуществимости затем заставляют неравенства “ держаться в виде уравнений. Проблема назначения возникает как в ситуациях минимизации. Так и в ситуациях максимизации.

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

Такие темы освещены в книге Джорджа Б. ДанцигаЛинейное программирование и расширения

В стандартной форме Для вычислительных целей ограничения линейной программы обычно выражаются в виде системы линейных уравнений с неотрицательными переменными. Это называется стандартной формой. Любая законная линейная программа может быть легко приведена к стандартной форме. Таким образом, в Я 1х 1 + + а в х н б мне становится , а я 1х 1 + + а в х н + з я = б я , с ы я 0, и это я 1х 1 + + а в х н б мне становится а я ЛХ 1 + + а в Х Н С Я = б я , с ы я 0. Любая переменная xj, не ограниченная знаком. Может быть заменена разностью двух неотрицательных переменных:

xj =xjj. Переменная x j ограниченная тем что она непозитивна может быть заменена на xj = -xдж.

Каждой задаче линейного программирования соответствует двойственная задача, построенная из одних и тех же данных. Используемых по-разному. Дуальная задача-это опять-таки линейная программа. Форма которой зависит от формы данной задачи. Которая в этом отношении называется первичной задачей. Таким образом. Если первичная задача (2). То двойственная задача:

Двойственность линейной программы в стандартной форме подобна (3). За исключением того. Что ее переменные y i свободны (не ограничены знаком).

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

Теорема двойственности линейного программирования Пусть X и Y обозначают допустимые области (2) и (3) соответственно. Затем

для любого x X и любого y Y. Если равенство выполняется в (4), то x и y являются оптимальными решениями их соответствующих программ. Более того, первичная задача имеет оптимальное решение x тогда и только тогда. Когда двойственная задача имеет оптимальное решение y ; в этом случае выполняется равенство (4). Если допустимые области X и Y непусты. То обе задачи имеют оптимальные решения. Если возможна только одна из двух задач. То целевая функция этой задачи неограничена в направлении экстремизации.

Симплексный метод Общая постановка задачи линейного программирования и симплексный метод ее решения были выдвинуты американским математиком Джорджем Б. Данцигом (1914-2005) в 1947 году. Этот метод продолжает оставаться основным алгоритмом решения задач данного класса.

Симплексный метод работает с линейными программами в стандартном виде и использует тот факт. Что для нахождения оптимального решения достаточно ограничиться вершинами многогранной допустимой области X. Начиная с известной вершины X, метод генерирует путь вдоль ребер X по мере его перемещения из одной вершины в соседнюю вершину. До тех пор. Пока езда на велосипеде если этого не происходит. Процесс гарантированно завершается после посещения конечного числа вершин. Когда алгоритм находит оптимальное решение первичной задачи. Он также обнаруживает оптимальное решение двойной задачи. Однако может случиться так. Что вершина X не известна заранее и ее придется найти. Существуют методы. Позволяющие найти вершину X (если она существует) и предотвратить цикличность.

Анализ чувствительности Оптимальное значение целевой функции LP, скажем (2). Зависит от коэффициентов ввода-вывода aij , констант правой части bi и коэффициентов целевой функции pj . Изучение того. Как изменения этих параметров влияют на оптимальное значение. Называется анализом чувствительности или постоптимальным анализом. Наиболее часто используемый факт. Вытекающий из такого рода анализа. Состоит в том. Что (в невырожденном случае) скорость изменения оптимального значения z по отношению к изменению i-го правого параметра bi равна двойной переменной yi, соответствующей i-му правому параметру. th ограничение; в символах z/bi = yi.

Крупномасштабное линейное программирование Многие практические приложения порождают очень крупномасштабные модели. Часто работающие с десятками или сотнями тысяч уравнений и миллионом или более переменных. Решение крупномасштабных задач требует мощных компьютеров и специализированных алгоритмов. Которые часто используют структуру матрицы коэффициентов. Соответствующую ограничениям. Принцип декомпозиции Данцига и Филипа Вулфа (1960) относится к этому типу. Он предназначен для задач с блочно-угловой структурой. В которой существует много организационных единиц. Соответствующие переменные которых появляются в относительно небольшом числе ограничений связи. Представляющих центральное управление. И в противном случае только в ограничениях. Относящихся к этой единице.

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

Нелинейность может возникать по-разному. Что приводит к различным типам НЛП. Самыми древними и простыми для понимания являются задачи квадратичного программирования. В которых ограничения аналогичны ограничениям LP. Но целевая функция квадратична (а не линейна). Первым обозначил (и назвал) этот класс проблем экономист Роберт Дорфман (1916-2002) в своей монографии При анализе планирования производства монополизированных продуктов предположение о постоянных предельных издержках производства может оказаться несостоятельным. Как монополистс ростом производства он может начать насыщать рынок. Тем самым снижая цену. По которой можно продавать продукцию. В качестве альтернативы монополист может ограничить производство. Чтобы поддержать цену продукта. Модель Дорфманаохватывает те случаи. Когда фирма производит м монополизированных продуктов совместно и где она сталкивается с линейно уменьшающимися предельными доходами. Когда цены . По которым может быть реализована продукция . Убывают линейные функции выхода y i, такие как p i (y ) = f i g i y i , где f i и g i -положительные константы. Выручка от реализации вектора выходаy = (y1,,ym) .

Предполагается . Что затраты на n производственных процессов составляют x 1, x n , измеряемые в денежных единицах. Предполагается. Что отношения

Сумма xj представляет собой издержки производства. То есть прибыль. Возникающую в результате затрат на производство. Уравнения позволяют заменить yi, получая таким образом целевую функцию только в терминах xj. xj может нуждаться в удовлетворении линейных ограничений. Таких как (2). В результате получается линейно ограниченная задача максимизации с квадратичной целевой функцией. То есть квадратичная программа.

Иногда проблемы оптимизации возникают в чисто технических условиях. Например, часто необходимо минимизировать расстояние от точки x до множества X. Когда мерой расстояния является евклидова метрика и рассматриваемое множество определяется через систему линейных неравенств. Полученная задача представляет собой квадратичную программу с целевой функцией:

Выпуклость и выпуклое программирование Одним из наиболее важных понятий в линейном и нелинейном программировании является понятие выпуклости. Множество X называется выпуклым, если оно содержит весь отрезок прямой между любыми двумя его точками. Отрезок прямой между точками u и v в реальном векторном пространстве равен {x : x =λu + (1 λ)v, для всех 0 λ . Все многогранные множества (1) легко увидеть выпуклыми. Функция f не определена на выпуклом множестве Х называется выпуклым. Если есть неравенство ф (λс U + (1 — λ)V в ) λ ф (у ) + (1 — λ)Ф (в ) проводит для всех векторов у, в Х и все скаляра λ , удовлетворяющих 0 λ 1.

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

Во всех задачах оптимизации важно иметь четкое. Проверяемое определение того. Что подразумевается под (локальной) оптимальностью возможного решения задачи. Поскольку LPS и NLPs обычно имеют бесконечно много возможных решений. Важно знать. Каким дополнительным условиям должны удовлетворять те. Которые являются (локально) оптимальными. В случае линейного программированиягде используется симплексный метододин из них. По существу. Имеет информацию. Которая показывает. Улучшит ли переход от конкретной вершины к любой соседней вершине значение целевой функции. Если нет, вершина дает оптимальное решение. Эта информация получена путем проверки знаков некоторых чисел в алгебраическом представлении задачи.

В нелинейном программировании дело обстоит гораздо менее просто. Основным инструментом. Используемым для поиска локального минимума. Является следующий результат.

Теорема (теорема Каруша-Куна-Такера) Предположим, что x = (x1,, x n ) является локальным максимумом для нелинейной программы

и что функции F, g 1, , g m дифференцируемы при x. Если градиенты g i (x ) функций ограничения в точке x удовлетворяют подходящему условию регулярности (одному из таких условий является линейная независимость градиентов). То существуют множители y 1, , ym 0 такие, что

В совокупности (7) и (8) называются условиями Каруша-Куна-Такера (ККТ). Поскольку g i (x ) 0 yi для каждого i, условия (8) подразумевают. Что по крайней мере один из y i и g i (x ) должен быть равен нулю. Соответственно. Они называются комплементарными условиями слабости. Тогда условие стационарности (7) говорит. Что при локальном максимуме градиент целевой функции представляет собой линейную комбинацию градиентов ограничений. Для которых gi (x ) = 0; соответствующие yi называются обобщенными множителями Лагранжа.

Следует повторить. Что если допущения теоремы ККТ справедливы. То условия (7) и (8) обязательно выполняются. Поскольку эти предположения справедливы в большинстве случаев. Теорема ККТ обеспечивает механизм поиска возможных локальных максимумов. В отсутствие дальнейших гипотез не гарантируется. Что решение условий ККТ будет локальным максимумом НЛП. Однако, когда целевая функция и ограничительные функции все вогнуты. Решение условий ККТ должно быть глобальным максимумом задачи оптимизации. В этом случае условия KKT необходимы и достаточны для глобальной оптимальности x. Помимо условий оптимальности первого порядка. Приведенных выше. Существуют условия оптимальности второго порядка. Но обсуждение таких вопросов выходит за рамки данной статьи.

Лагранжева двойственность Относительно (6) с допустимой областью Xсуществует соответствующая лагранжева функция

Из функции Лагранжа можно определить двойственную задачуЛагранжа. Которая требует минимизации функции φ(y ) = sup x X L (x, y ). Непосредственным следствием этого определения является sup x X F (x ) inf y 0 φ(y ). Если F (X ) = φ (y ), где x X и y 0, то x и y являются оптимальными для их соответствующих программ. Выпуклый анализ Р. Тиррелла Рокафеллара (1970) дает всеобъемлющую теорию двойственности для выпуклого программирования.

Нелинейные программы могут сильно отличаться по математическим свойствам. Которыми обладают (или не обладают) функции. С помощью которых они определяются. Примеры таких свойств включают выпуклость и дифференцируемость. НЛП , ограничительные функции которых аффинны, то есть имеют вид a i 1x 1 + + a в x n b i при i = 1, , m, составляют особый класс. Заметным членом которого является задача квадратичного программирования. Другим свойством является структура проблемы: некоторые из них очень большие и разреженные; другие маленькие и плотные Плотная задача-это та. В которой каждая из функций фактически зависит от высокого процента общего набора переменных. Некоторые нелинейные программы включают в себя (линейные или нелинейные) уравнения среди ограничений. Методы, используемые для решения НЛП. Как правило. Используют преимущества характеристик проблемы и по этой причине сильно отличаются друг от друга. Тем не менее. У них есть некоторые общие свойства.

Общей чертой алгоритмов математического программирования является их итеративная природа. Начиная с пробного решения x 0, генерируется последовательность пробных решений x 1, x 2, до тех пор. Пока одно из них. Скажем x k удовлетворяет заданному критерию. Указывающему на то. Что это (приблизительно) оптимальное решение или что имеет место какая-то другая причина остановки процесса. Шаги алгоритма представляют собой процесс перехода от данной итерации к следующей. В некоторых случаях это может повлечь за собой решение одной или нескольких оптимизационных подзадач. Для линейного программирования и некоторых случаев квадратичного программирования существуют алгоритмы. Которые генерируют конечную последовательность пробных решений. Заканчивающихся оптимальным решением или доказательством его отсутствия. Алгоритмы нелинейного программирования чаще всего сходящимся, чем конечным. Когда теорема ККТ применима. Вопрос нахождения решения сводится к решению системы уравнений (для которой имеются численные методы). Но прежде чем это сделать. Необходимо попытаться определить. Какие именно уравнения необходимо решить. Условия оптимальности и особенно информация. Предоставляемая множителями Лагранжа. Играют большую роль в алгоритмических стратегиях.

СМ. ТАКЖЕ Правило Гамильтона; Линейные системы; Многообразия; Матричная алгебра; Принцип Максимина; Максимизация; Минимизация; Нелинейные системы; Целевая функция; Оптимизирующее поведение

Данциг, Джордж Б. 1963. Линейное программирование и расширения. Принстон, Нью-Джерси: Издательство Принстонского университета.

Данциг, Джордж Б. и Мукунд Н. Тапа, 1997. Линейное программирование 1: Введение. Нью-Йорк: Спрингер.

Данциг, Джордж Б. и Филип Вулф. 1960. Принцип декомпозиции для линейных программ. Исследование операций 8: 101-111.

Дорфман, Роберт, 1951. Применение линейного программирования к теории фирмы. Berkeley: University of California Press.

Fiacco, Anthony V. 2001. Нелинейное программирование. В Энциклопедии исследования операций и науки управления, 2-е изд., ред. Сол И. Гасс и Карл М. Харрис, 572580. Boston: Kluwer.

Гилл, Филип Э.. Уолтер Мюррей и Маргарет Х. Райт. 1981. Практическая оптимизация. Лондон: Академическая пресса.

Хильер, Фредерик С. и Джеральд Дж. 2005. Введение в операционные исследования. 8-е изд. Бостон: Макгроу-Хилл.

Nemhauser, George L., Alexander Rinnooy Kan и Michael J. Todd, eds. 1989. Оптимизация. Амстердам: Северная Голландия.

Ночедал, Хорхе и Стивен Дж. Райт, 1999. Численная Оптимизация. Нью-Йорк: Спрингер.

Рокафеллар, Р. Тиррелл, 1970. Выпуклый анализ. Принстон, Нью-Джерси: Издательство Принстонского университета.

Ричард У. Коттл

Международная энциклопедия социальных наук