Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой или она не относится ни к тому, ни к другому классу.
Говорят, что множество выпукло, если оно вместе с любыми своими точками А и В содержит и все точки отрезка АВ. Примерами выпуклых множеств в пространстве могут служить сфера, пирамида, призма и т. д. В невыпуклом множестве можно указать хотя бы две точки, такие, что не все точки отрезка АВ принадлежат рассматриваемому множеству. Примером невыпуклого множества в пространстве является тор.
Функцию y = f(x) одной переменной будем называть выпуклой, если отрезок, соединяющий две любые точки ее графика, принадлежит графику или расположен выше его. Функция вогнута, если отрезок, соединяющий две любые точки графика, принадлежит ему или расположен ниже его.
Аналогично можно сформулировать определения понятий вогнутой и выпуклой функций нескольких переменных. Говорят, что гиперповерхность z=f(x1,x2,...,xn) выпуклая, если отрезок, соединяющий две ее любые точки, лежит на поверхности или выше ее. Гиперповерхность z=f(x1,x2,...,xn) вогнута, если отрезок, соединяющий две ее любые точки, лежит на поверхности или ниже ее.
Пусть дана функция, определенная на замкнутом множестве Ф. Элементами множества Ф являются точки. Поэтому функцию можно записать так: .
Говорят, что функция, определенная на некотором множестве X, достигает в точке локального максимума (локального минимума), если найдется такое число, что для всех, удовлетворяющих неравенству, выполняется неравенство
Точка, в которой функция достигает локального максимума (минимума), называется точкой локального максимума (минимума).
Пусть функция определена на замкнутом множестве X. Если и для любой точки, то говорят, что в точке функция достигает глобального максимума (глобального минимума).
Точка, в которой все частные производные функции равны 0, называется стационарной точкой.
Необходимое условие экстремума. Если в точке функция имеет экстремум, то частные производные функции в этой точке равны нулю:
Как и в случае одной переменной, необходимое условие не является достаточным для того, чтобы стационарная точка была точкой экстремума. Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Дифференциал второго порядка обозначается и равен сумме произведений частных производных второго порядка на соответствующие приращения аргументов. Если от частной производной найти частную производную по переменной, то получим частную производную второго порядка по переменным, которая обозначается. В этом случае
Достаточные условия экстремума:
А) в стационарной точке функция имеет максимум, если, и минимум, если, при любых и, не обращающихся в нуль одновременно;
- Б) если может принимать в зависимости от и и положительные, и отрицательные значения, то в точке экстремума нет; В) если может обращаться в нуль не только при нулевых приращениях и, то вопрос об экстремуме остается открытым.
Для функции двух переменных достаточные условия не очень сложны. Существуют четыре частные производные второго порядка:
Найдем значения частных производных второго порядка в стационарной точке :
Обозначим через определитель, составленный из
(6.8)
Тогда достаточные условия экстремума функции двух переменных имеют вид:
- А) если >0 и a110 и a11>0 (a22>0), то в точке функция имеет минимум; Б) если В) если, то вопрос об экстремуме остается открытым.
Если область Ф замкнута и ограничена, то дифференцируемая функция достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области.
Таким образом, чтобы найти наибольшее (наименьшее) значение функции в области Ф, нужно:
Найти все стационарные точки внутри области Ф и вычислить значения функции в них:
Исследовать функцию на экстремум на границе области Ф;
Сравнить значения функции, полученные в п.1 и п.2: наибольшее (наименьшее) из этих чисел и будет наибольшим (наименьшим) значением функции во всей области.
Граница области Ф аналитически может быть задана системой уравнений (условий) относительно переменных. Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.
Условный экстремум. Пусть необходимо найти экстремум функции при условии, что переменные удовлетворяют уравнениям:
)=0, (6.9)
Предполагается, что функции и имеют непрерывные частные производные по всем переменным. Уравнения (6.9) называются уравнениями связи.
Говорят, что в точке, удовлетворяющей уравнениям связи (6.9), функция имеет условный максимум (минимум), если неравенство имеет место для всех точек, координаты которых удовлетворяют уравнениям связи.
Для задач линейного программирования характерно следующее:
Множество допустимых решений выпукло. Это выпуклое множество имеет конечное число вершин, называемых обычно крайними (угловыми( точками.
Множество всех точек n-мерного пространства, в которых целевая функция принимает заданное значение, есть гиперплоскость (линия) уровня. Кроме того, гиперплоскости, соответствующие разным значениям целевой функции, параллельны.
Локальный max или min является также глобальным max или min целевой функции на множестве допустимых решений, т. е. не существует локального оптимума целевой функции, отличного от глобального оптимума.
Если оптимальное значение целевой функции ограничено, то по крайней мере одна крайняя точка множества допустимых решений является оптимальным решением. Кроме того, начав с произвольной вершины множества допустимых решений, можно достичь оптимума за конечное число шагов, причем на каждом шаге совершается переход только в соседнюю вершину. Окончательно данная вершина является оптимальной тогда и только тогда, когда значение целевой функции в ней по крайней мере не меньше, чем значения целевой функции во всех примыкающих вершинах.
У произвольной задачи нелинейного программирования некоторые или все приведенные выше свойства ЗЛП отсутствуют. Поэтому ЗНП гораздо сложнее задач линейного программирования и для них не существует общего универсального метода решения (аналогично симплексному методу).
Похожие статьи
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую...
-
Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...
-
Геометрическая интерпретация и графическое решение ЗЛП - Экономико-математические методы
Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
Любое частное решения уравнения (1) на координатной плоскости х0у изображено в виде графика функции у=у (х, с) (с=const). В теории дифференциальных...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
В начале пятилетнего периода работы предприятию выделена сумма в C руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Исследуем на экстремум функцию: 1. С помощью необходимого существования экстремума, т. е. из системы Найдем координаты стационарных (критических) точек:...
-
Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Общая постановка задачи исследования операций - Экономико-математические методы
Все факторы, входящие в описание операции, можно разделить на две группы: Постоянные факторы (условия проведения операции), на которые мы влиять не...
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Метод множителей Лагранжа - Экономико-математические методы
Среди задач (4.1)-(4.3) особое место занимают задачи типа (6.10) , (6.11) Для решения которых можно воспользоваться классическим методом оптимизации...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Производной. - Методы решения системы линейных уравнений
Наиболее просто основные теоремы дифференциального исчисления формулируются для гладких функций. [ Править ] Производные и гладкие функции Пусть функция...
-
Экономико-математические методы и моделирование в землеустройстве позволяют решать большой круг задач, связанных с оптимизацией территориальной...
-
Счетные и несчетные множества - Методы решения системы линейных уравнений
Пусть, например, А и В Ї некоторые множества. Тогда их возможные взаимоотношения можно рассмотреть в виде таблицы: Диаграмма Венна Диаграмма Венна...
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы