Математическое программирование - Контрольная работа

Точка называется точкой локального минимума функции f(x), если , где - окрестность точки . Точка называется точкой глобального минимума функции f(x), если . Точка х называется стационарной, если в ней выполнено условие Доказательство следует из возможности линейного представления функции в точке . Пусть f(x) - выпуклая функция, дифференцируемая в точке , и выполнено условие (1.1).Метод множителей Лагранжа можно использовать при построении критериев оптимальности для задач с ограничениями в виде равенств. Ограничения в виде неравенства называется активным, или связывающим, в точке , если , и неактивным, или не связывающим, если , где - допустимая точка, то есть удовлетворяющая всем ограничениям. Минимизировать при ограничениях: Записав данную задачу в виде задачи линейного программирования, можно получить: Уравнение (1), входящее в состав условий Куна-Таккерапринимает следующий вид: откуда Неравенства (2) и уравнения (3) задачи Куна-Таккера в данном случае записывается в виде: Уравнения (4), известные как условие дополняющейнежесткости, принимают вид: Заметим, что на переменные U1 и U2 накладывается требование неотрицательности, тогда как ограничение на знак, отсутствует. Необходимое условие экстремума в задаче нелинейного программирования, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача: Важнейшим из них является так называемое условие регулярности Слейтера: Говорят, что функция gi(х), задающая ограничение в задаче, удовлетворяет условию регулярности Слейтера, если существует такая точка , принадлежащая области допустимых планов D, что , т. е. является внутренней точкой относительно ограничения gi(x).Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x1, х2,..., xn) на множестве D, определяемом системой ограничений где хотя бы одна из функций f или gi является нелинейной. По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f) и кратко может быть записана в следующем виде Как и в ЗЛП, вектор х* = (x1*,x2,...,xn*) D называется допустимым планом, а если для любого x D выполняется неравенство f(x*) ? f(x), то х* называют оптимальным планом. С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а gi(х) ? 0 как технологические ограничения на возможности выпуска продукции. Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например: или запись условий дискретности множеств: Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств: либо, добавив фиктивные переменные у, к системе уравнений: Свойства ЗНП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования: 1.Решение данного уравнения ищут в виде , тогда: В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова: С учетом этого функция определяется выражением: Эта функция в окрестности корня осуществляет сжимающее отображение, и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления: По теореме Банаха последовательность приближений стремится к корню уравнения . Иллюстрация метода Ньютона (синим изображена функция f(x), нуль которой необходимо найти, красным - касательная в точке очередного приближения xn). Основная идея метода заключается в следующем: задается начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Тогда формула итеративного исчисления приближений может быть выведена следующим образом: где - угол наклона касательной в точке xn. Следовательно искомое выражение для xn 1 имеет вид: Итерационный процесс начинается с некоего начального приближения (чем ближе к нулю, тем лучше, но если предположения о нахождении решения отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях).

Оглавление

1. Теоретическая часть

1.1 Теория математического программирования. Однокритериальная оптимизация. Необходимые и достаточные условия для локальных экстремумов гладких функций

1.2 Методы поиска глобального экстремума функции нескольких переменных. Условия Куна-Таккера. Условие Слейтера

1.3 Линейное программирование. Угловые точки допустимых множеств

1.4 Нелинейное программирование. Постановка общей задачи нелинейного программирования

2. Практическая часть

2.1 Метод Ньютона

Список литературы

1. Теоретическая часть

1.1 Теория математического программирования. Однокритериальная оптимизация. Необходимые и достаточные условия для локальных экстремумов гладких функций

1) Монографии, изданные в издательстве Российской Академии Естествознания [Электронный ресурс]. Режим доступа: http://www.rae.ru/monographs/57-2327

2) Планирование решений в экономике. Условие регулярности Слейтера[Электронный ресурс]. Режим доступа: http://ecosyn.ru/page0130.html

3) Бельков В.Н., Ланшаков В.Л. Автоматизированное проектирование технических систем: Учебное пособие-Москва: Академия Естествознания, 2009.

4) Акулич И. Л. Математическое программирование в примерах и задачах: Учеб.пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986.http://cyberfac.ru/publ/matematicheskie_metody_v_ehkonomike/kanonicheskaja_postanovka_zadachi_linejnogo_programmirovanija/45-1-0-1431

Размещено на