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

Графический метод решения задачи линейного программирования.

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

1. На плоскости X₁0X₂ строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂+ c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.

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

Алгоритмический метод.

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

Рассмотренные выше методы служат для сбора информации о субъекте труда или профессиональной среде. Вместе с тем существует ряд методов упорядочения полученной информации. Одним из таких методов является алгоритмический анализ. Алгоритм — строгая последовательность действий, которая неизбежно приводит к решению задачи определенного класса. Эта последовательность действий может иметь словесное описание, в котором представлены все элементарные действия и логические условия, определяющие порядок этих действий, а может быть описана в символической форме или в виде графика. Метод дает возможность представить совокупность действий в компактной форме и понять их закономерные связи. Благодаря своей полноценности, конкретности и систематичности алгоритмы позволяют постепенно проследить характер операций, выполняемых работниками, и установить те звенья процесса, в которых наиболее часты аварии и брак и которые необходимо рационализировать или автоматизировать в первую очередь, либо функции, требующие перераспределения или изменения.

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

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

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

Попытаемся ход рассуждений, который был в каком-то разделе учебника выше, описать словесно. Упомянутая модель содержит два уравнения. Пробные решения выбирались следующим образом: допускалось, что две переменные прини­мают некоторые положительные значения, а остальные переменные предполагались тождественно равными нулю. Стремясь к обобщению, можно предположить, что в тех случаях, когда модель содержит т уравнений, для построения пробных решений используются т пере­менных, принимающих некоторые положительные значения при нулевых значениях остальных переменных. Вначале допустим, что решение существует, причем оптимальное значение целевой функции конечно ). В этом случае вычислительная процедура будет выгля­деть следующим образом:

Шаг 1. Выберем т переменных, задающих допустимое пробное решение. Исключим эти переменные из выражения для целевой функции.

Шаг 2. Проверим, нельзя ли за счет одной из переменных, при­равненной вначале к нулю, улучшить значение целевой функции, придавая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к шагу 3. В противном случае прекра­тим вычисления.

Шаг 3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из вы­ражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.

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

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

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

Источник

Задача выпуклого программирования

Если в задаче математического программирования требуется найти экстремум функции, например: (4.7) на множестве допустимых решений, заданных ограничениями , (4.8) причем: 1) целевая функция является дифференцируемой и вогнутой, т.е. для нее выполняется условие: при любых , 2) а левые части всех ограничений — дифференцируемыми и выпуклыми функциями, т.е. для них выполняются условия: при любых , Тогда задача (4.7)(4.8) называется задачей выпуклого программирования. Любая линейная функция одновременно удовлетворяет условиям и выпуклости, и вогнутости; т.е. её можно считать как выпуклой, так и вогнутой. Это позволяет считать линейные задачи частным случаем задач выпуклого программирования. Если для задач математического программирования в общем случае пока отсутствует стройная теория существования и устойчивости решения, то для задач выпуклого программирования такая теория есть. Введём три определения: 1). Функцией Лагранжа задачи выпуклого программирования (4.7)(4.8) называется функция: , , (4.9) 2). Говорят, что задача выпуклого программирования (4.7)(4.8) удовлетворяет условию регулярности, если существует хотя бы одна внутренняя точка множества допустимых решений , определяемого строгими неравенствами, полученными из (4.8) (т.е.). 3). Точка называетсяседловой точкой функции , если для всехвыполнено: (4.10) Если целевая функция (убрать) В теории нелинейного программирования центральное место занимает теорема КунаТаккера, обобщающая классический метод множителей Лагранжа на случай, когда ограничения нелинейной задачи наряду с ограничениями в виде равенств содержат также и ограничения в виде неравенств. Теорема КунаТаккера. Если задача выпуклого программирования (4.7)(4.8) удовлетворяет условию регулярности, то точка является оптимальным решением этой задачи тогда и только тогда, когда существует такая точкас неотрицательными координатами, чтоявляется седловой точкой функции Лагранжа данной задачи. Условия КарушаКунаТаккера в дифференциальной форме: Если функция Лагранжа является выпуклой по, вогнутой пои непрерывно дифференцируемой по всеми, то для того чтобы парабыла седловой точкой функции Лагранжа , необходимо и достаточно, чтобы выполнялись следующие условия: , , , Пример. Найти максимум функции на множестве допустимых решений . Решение: Функция является вогнутой, система ограничений содержит только линейные неравенства, поэтому задача является задачей выпуклого программирования. Составим функцию Лагранжа Найдём седловую точку функции Лагранжа из условий: . В данном случае седловой точкой является пара ,. Ответ: Теорема КунаТаккера обосновывает сведение задачи выпуклого программирования к задаче поиска седловой точки функции Лагранжа. Чтобы такое сведение имело практический смысл, необходимо, чтобы получившаяся задача была в чём-то проще исходной. Это происходит не всегда, поэтому разработан ряд прямых методов поиска решения нелинейной задачи (4.5), (4.6). Рассмотрим некоторые из них.

Метод кусочно-линейной аппроксимации

Этот метод удобно использовать для некоторых задач специального вида, а именно в случае, когда целевая функция (4.5) и ограничивающие функции из (4.6) являются сепарабельными. Напомним, что функция называетсясепарабельной, если её можно представить в виде суммы функций, зависящих только от одной переменной: . Пусть дана задача: (4.11) на множестве допустимых решений, заданных ограничениями: , (4.12) . (4.13) Такую задачу можно свести к ЗЛП. Для этого:  определяем максимально возможные значения (чаще всего по соображениям здравого смысла), т.е. полагаем, что;  разбиваем интервал на равных промежутков длиныточками:,, . . . где. Очевидно, можно записать (4.14) получаем естественные ограничения для ; (4.15)  заменяем кусочно-линейной аппроксимацией, т.е. представляем в виде ; (4.16)  также обходимся с ограничивающими функциями , представив их в виде . (4.17) Учитывая, что значения ,известны при любых, подставляем (4.144.16) в (4.114.13) и получаем задачу линейного программирования с неизвестными . Решение исходной задачи получим, найдя искомые значения по (4.14) и вычислив по (4.11) оптимум целевой функции. Точность решения зависит отпринятых шагов разбиения. Чем мельче шаги, тем точнее решение. Пример: Найти максимум целевой функции: при условиях: . Решение: В целевой функции нелинейным является только первое слагаемое , второе слагаемоелинейно. Из вида области допустимых решений следует, что . Разбиваем этот промежуток на 8 частей точками: и вычисляем в этих точках значения: , ,. По (4.14), (4.16) находим: В итоге получаем задачу линейного программирования: Найти максимум целевой функции с десятью неизвестными при условиях: , , , Решив линейную задачу, найдем, что достигает максимума при Переходя к исходной нелинейной задаче, получаем Ответ:, .

Источник

3.2. Выпуклое программирование Постановка задачи выпуклого программирования.

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и g_i, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (3.3) — (3.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (3.4) — (3.5), — выпуклая.

Функция f(x₁, x₂, . x_n), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X₁ и X₂ из X и любого 01 выполняется соотношение

Функция f(x₁, x₂, . x_n), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X₁, X₂ из X и любого 01 выполняется соотношение

Если f (X) — выпуклая функция, то –f (X) — вогнутая функция, и наоборот.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция. Задача (3.3) — (3.5) является задачей выпуклого программирования, если функция f(x₁, x₂, . x_n) является вогнутой (выпуклой), а функции g_i (X) (i=1, . m) — выпуклыми.

Т е о р е м а. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Говорят, что множество допустимых решений задачи (3.3) — (3.5) удовлетворяет условию регулярности, если существует по крайней мере одна точка X_i, принадлежащая ОДР такая, что g_i (X_i)b_i (i=1. m).

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера.

Для задачи выпуклого программирования (3.3) — (3.5), множество допустимых решений которой обладает свойством регулярности, X₀ тогда и только тогда является оптимальным решением, когда существует такой вектор , что — седловая точка функции Лагранжа.

Эта теорема называется также теоремой о седловой точке.

3.3. Классические методы оптимизации Метод прямого перебора.

Если известна функциональная связь целевой функции Y и искомой переменной X, то можно последовательно вычислить значения целевой функции для некоторых значений искомой переменной. Вычисления повторяются до тех пор, пока не будет найден min (max) значения целевой функции

Y=f(x₁, . x_i, . x_n, u₁, . u_j, . u_m),

x_i=x_0i+x_ik (k=0, 1, 2, . l).

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

Особенность и преимущества метода прямого перебора заключаются: 1) в независимости поиска от вида и характера целевой функции; 2) в цикличности поисковой процедуры; 3) в определении глобального экстремума целевой функции; 4) в простоте алгоритма и программы оптимизации; 5) в малом объеме необходимой машинной памяти.

В случае большой области изменения искомой переменной и (или) наличия более чем одного экстремума исследуемой функции использование этого метода неэффективно.

Источник