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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

« ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Реферат

ПО ДИСЦИПЛИНЕ «ОПТИМИЗАЦИЯ И ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ»

на тему Метод симплексный нелинейного программированиия

Томск 2019

Содержание

Введение

1. Методы оптимизации

2. Классификация методов оптимизации

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

3.1 Общая задача нелинейного программирования

3.2 Симплексный метод

Заключение

Список использованных источников

Введение

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

Также было известно, что из всех многоугольников с заданным числом сторон и заданным периметром наибольшую площадь имеет правильный многоугольник и что сфера - это замкнутая поверхность заданной площади, ограничивающая максимальный объём. Оптимизационные особенности геометрических фигур исследовали Архимед и Зенодор (II век до н.э.). В трактате «Об изопериметрических фигурах» Зенодор исследует плоские фигуры, которые при данном периметре имеет наибольшую площадь, и тела, которые при данной поверхности имеет наибольший объём. Одной из теорем, которую доказал Зенодор, является следующая: если круг и правильный многоугольник имеют одинаковый периметр, то круг будет больше. Можно показать, что площадь любого правильного многоугольника всегда меньше площади круга с таким же периметром. Причём площадь правильного многоугольника с увеличением числа его сторон при постоянстве периметра асимптотически стремится к площади круга.

В средневековой Европе изопериметрическими задачами занимались И. Сакробоско (XIII век) и Т. Брадвардин (XIV век). Изопериметрические свойства окружности и сферы были строго доказаны только в 1884 году Германом Шварцем.

Научное становление теории оптимизации началось в XVII-XVIII веках. Пьер Ферма (1601-1665) сформулировал необходимый признак экстремума: в точках экстремума производная функции равна нулю. Имя Ферма носит основной принцип геометрической оптики, в силу которого свет в неоднородной среде выбирает путь, занимающий наименьшее время. В 1746 году Мопертюи обобщил это правило, введя в науку - принцип наименьшего действия.

Ньютон в «Математических началах натуральной философии» (1687) решает задачу: найти форму тела вращения, обеспечивающую наименьшее сопротивление при движении в газе или жидкости (при заданных размерах). Важной исторической задачей, давшей толчок к развитию современного варианта вариационного исчисления, стала задача о брахистохроне, которую сформулировал в 1696 году Иоганн Бернулли. Эта задача также называется задачей о наискорейшем спуске. Первым эту задачу решил Исаак Ньютон.

Эта задача положила начало одному из важнейших методов теории оптимизации - вариационному исчислению. Правда, первый вариационный принцип сформуировал ещё в I век н. э. для траекторий отражённых световых лучей Герон Александрийский в работе «Катоптрика».

Решающий вклад в развитие вариационного исчисления внесли Леонард Эйлер, Якоб и Иоганн Бернулли, Жозеф Луи Лагранж. Первое систематическое изложение вариационного исчисления и сам термин (1766 год) принадлежит Эйлеру.

Лагранж независимо получил (с 1755 года) многие основополагающие результаты и ввёл понятие вариации. Позже в XIX веке вариационное исчисление развивалось трудами Карла Вейерштрасса, Карла Якоби и других.

Основные достижения в области методов решения оптимизационных задач были получены в XX веке[1].

1. Методы оптимизации

В 1939 году советский математик Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой заложил основы нового математического аппарата поиска оптимума, названного впоследствии линейным программированием. Толчком к разработке метода стала практическая задача раскроя листового материала. В 1949 году Канторович стал лауреатом Сталинской премии «за работы по функциональному анализу» в рамках проекта по разработке ядерного оружия. За разработку метода линейного программирования и экономических моделей Канторович был удостоен в 1965 году Ленинской премии вместе с академиком В.С.Немчиновым и профессором В.В.Новожиловым, а в 1975 году стал лауреатом Нобелевской премии по экономике (совместно с Тьяллингом Купмансом «за вклад в теорию оптимального распределения ресурсов»).

Дальнейшее развитие линейного программирования связано с именем Д.Данцига, разработавшего в 1947 году метод решения задач линейного программирования - симплекс-метод. Многие практические задачи, экономические и технические, могут быть представлены как задачи линейного программирования, а появление вычислительных машин позволило решать задачи большой размерности.

В области задач оптимального управления следует назвать два значимых метода: принцип максимума, разработанный Львом Семёновичем Понтрягиным в 1958 году (Ленинская премия 1962 года), и динамическое программирование, разработанное Ричардом Беллманом. Кроме этих методов для решения оптимизационных задач разработано множество методов так называемого нелинейного программирования. [1]

Методы оптимизации занимаются построением оптимальных решений для математических моделей. В эту дисциплину не входит само построение математических моделей. Но именно вид модели определяет метод или методы, используемые для построения оптимального решения. В большинстве случаев математическую модель объекта можно представить в виде целевой функции f (x) или критерия оптимальности (иногда без ограничений), которую нужно максимизировать или минимизировать. Т.е. необходимо найти максимум или минимум поставленной задачи, причем x D - области возможных значений . Как правило, область допустимых значений D задается. Тогда задача формулируется следующим образом:

оптимальный управление оптимизационный задача

или по другому

при

Область допустимых значений D определяется системой линейных или нелинейных ограничений, накладываемых на x

В реальных задачах ограничения на область возможных значений переменных модели отсутствуют чрезвычайно редко, потому что, как правило, переменные бывают связаны с некоторым ограниченным ресурсом. Но все-таки с задачами без ограничений сталкиваются. Это бывает в условиях “неограниченных” ресурсов или при наличии условий, не накладывающих ограничений на переменные задачи. В таком случае мы имеем безусловную задачу, задачу без ограничений:

Сложность задачи зависит от вида критерия f (x) и функций , определяющих допустимую область. Функции могут быть линейными и нелинейными, быть непрерывнми или принимать дискретные значения. Область возможных значений может быть выпуклой и невыпуклой, несвязной, представлять собой дискретное множество точек. В зависимости от этого задачи могут быть одноэкстремальными или многоэкстремальными, могут использоваться одни или другие методы поиска решения.

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

Если функции нелинейны, используем методы нелинейного программирования. Если при этом минимизируем выпуклую f (x) при выпуклых функциях , то знаем, что задача одноэкстремальна (выпуклое нелинейное программирование).

Если ( ) линейны, а минимизируемая f (x) представляет собой квадратичную выпуклую функцию, можем использовать алгоритмы квадратичного программирования [2].

2. Классификация методов оптимизации

Существуют различные виды классификации методов. Рассмотрим некоторые из них.

Что касается систематизации известных задач оптимизации человекомашинных систем и методов их решения, то ее обычно проводят исходя из природы целевой функции f(x_i), ограничений g_i(x_i) и входящих в них переменных x_i. Одна из часто встречающихся классификаций, построенная с учетом указанных признаков, проиллюстрирована на рис. 1 [3].

Рисунок 1 Классификация методов и задач оптимизации

На рисунке 1 мы видим что классификация строиться исходя из наличия ограничений.

В общем виде классификацию методов оптимизации мы можем рассмотреть на рисунке 2.

Рисунок 2 Классификация непрерывных методов оптимизации [4]

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

В том случае, если в задаче оптимизации отсутствуют ограничения, т.е. экстремум ищется в пределе неограниченного пространства варьируемых внутренних параметров X, задача носит название безусловной оптимизации, а найденный экстремум -- безусловного экстремума.

Наличие ограничений приводит к задаче условной оптимизации, а решением ее является условный экстремум [4].

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

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

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

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

Методы первого порядка при поиске решения используют не только информацию о самой функции, но и о её производных первого порядка. К таким методам относятся различные градиентные алгоритмы.

Методы второго порядка при поиске решения используют информацию о самой функции и о её производных первого и второго порядка. Сюда относятся метод Ньютона и его модификации [2].

Помимо того, оптимизационные методы делятся на следующие группы:

- аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

- численные методы;

- графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

- задачи дискретного программирования (или комбинаторной оптимизации) -- если X конечно или счётно;

- задачи целочисленного программирования -- если X является подмножеством множества целых чисел;

- задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства. [5]

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

Рисунок 3 Классификация задач математического программирования

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

3.1 Общая задача нелинейного программирования (НЛП)

Под общей задачей НЛП понимается задача нахождения максимального F(X) или минимального F(X), т.е. максимизации или минимизации скалярной функции F(X) при условиях:

и

где g_i(X) -- функциональные и критериальные ограничения;

D_x -- некоторая область n-мерного евклидова пространства Rⁿ, в пределах которой допустимо варьирование векторов внутренних параметров X.

Область, определяемая совместно условиями (4) и (5) обозначается G(X) и называется областью допустимых решений или областью работоспособности.

F(X) -- целевая функция [7].

3.2 Симплексный метод

Заключение

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

Список использованных источников

1. Дадаян, Л. Г. Оптимизация и оптимальное управление: Уфа: Изд-во УГНТУ, 2016.

2. Лемешко, Б.Ю. Методы оптимизации: Новосибирск: Изд-во НГТУ, 2009. 126 с.

3. Белов П.Г. Системный анализ и моделирование опасных процессов в техносфереURL:http://www.nashaucheba.ru/v7643/белов_п.г._системный_анализ_и_моделирование_опасных_процессов_в_техносфере?page=14(дата обращения 28.01.2019).

4. Классификация непрерывных методов оптимизации http://bigpo.ru/potra/Классификация+параметров+и+задач+проектированияa/part-5.html (дата обращения 28.01.2019).

5. Классификация методов оптимизации https://studopedia.ru/10_300159_optimizatsiya.html(дата обращения 28.01.2019).

6. Гладких Б. А. Методы оптимизации и исследование операций для бакалавров информатики. Ч. II. Нелинейное и динамическое программирование: Томск: Изд-во НТЛ, 2011. 264 с.

7. Методы непрерывной параметрической оптимизации. URL: http://uchebana5.ru/cont/1387569-p11.html (дата обращения: 3.06.2018).

8. Бояринов А.И. Методы оптимизации в химической промышленности.

Размещено на Allbest.ru