Нелинейные модели исследований операции и методы их решения

Оглавление

 

 

ВВЕДЕНИЕ

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

Для задач исследования операций характерны следующие особенности:

1) объективный характер применяемых моделей объекта управления. Математические модели, применяемых в исследовании операций, считаются средством отблеска объективно имеющейся действительности, как данное имеет место в физике и прочих природных науках;

2) заявки на проведение исследований выдает управляющий, возведение ведь модели воплотят в жизнь специалисты, которые и отыскивают решение. Глава при всем этом сможет выдавать вспомогательную информацию, хотя его роль тут, в сути, не выделяется от роли иных работников организации. Основная цель управляющего — ввести приобретенное решение; 
         3) присутствует справедливый аспект удачи в использовании методов исследования операций. Когда проблема, требующая решения, ясна, аспект явен, то сходу заметно, как отысканное подходящее решение гораздо лучше имеющегося.

 

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

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

            Актуальность курсовой работы заключается в том, что нелинейное программирование занимается оптимизацией моделей задач, в которых либо ограничения qi(x), либо целевая функция Z(X), либо то и другое нелинейные.

   Целью курсовой работы является рассмотрение нелинейных моделей исследований операции и методы их решения.

Для достижения поставленной цели в работе необходимо решить следующие задачи:

1. Дать определение нелинейного программирования и рассмотреть его особенность;

2. Рассмотреть методы решения задач нелинейного программирования в компании «Техно-Логика»;

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

Объектом исследования в данной работе является нелинейные модели исследований операции.

Объектом исследования выступает ООО «Техно-Логика».

        Предмет исследования – метод множителей Лагранжа, метод спуска, приближенное решение задач выпуклого программирования градиентным методом; принцип оптимальности и уравнения Беллмана.

Курсовая работа состоит из 2-ух частей. В первой доли рассматриваются вопросы теоретической базы исследования: дается понятие нелинейное программирование, рассматриваются различные виды модели. Во второй части при помощи методов программирования решение поставленных задач на случае ООО «Техно-Логика». В довершение всего делаются единые выводы решения нелинейных задач, оценивается практическая значение приобретенных последствий.  
При написании данной работы было использовано 14 различных источника и литературы.

В курсовой работе представлено 6 таблиц.

Общий объем работы составил 40 страниц.

 

1.ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ НЕЛИНЕЙНЫХ  МОДЕЛЕЙ ИССЛЕДОВАНИЙ ОПЕРАЦИЙ

1.1 Специфика нелинейных моделей исследования операций

Нелинейное программирование (НЛП) – данное эта цель математического программирования, в какой либо целевая функция Z(X), либо функции ограничений qi(x), либо они представляются собой нелинейные функции. Термин НЛП используется только после этого, как скоро все переменные X – действительные количества. Решение задач НЛП гораздо труднее решения задач ЛП при иных одинаковых критериях. Осмотрим необыкновенности задач НЛП, а то самое, где сможет располагаться подходящее решения. Чтобы достичь желаемого результата возьмем целевую функцию:[4,115c.]

Найти max(min) Z=z(X)

                                 (1.1)

где R — отношение порядка (=;≥;≤);

 — область допустимых решений;

— константа, ;

  — план или вектор управления.

Общая проблема нелинейного программирования (ОЗНП) ориентируется как цель нахождения максимума (или же минимального количества) целевой функции f(x1, х2,..., xn) на большом количестве D, характеризуемом системой ограничений:

(1.2)

где хотя бы одна из функций f или gi является нелинейной.

По аналогии с линейным программированием ЗНП несомненно ориентируется парой (D, f) и коротко быть может записана в последующем виде:

              (1.3)

  Скажем в ЗЛП, вектор х* = (x1*,x2*,...,xn*) D называется возможным проектом, а в случае если для хоть какого x D выполняется неравенство f(x*) ≥ f(x), то х* именуют подходящим проектом. В такой ситуации х* считается точкой масштабного максимума.

          Исходя из убеждений экономической интерпретации f(x) имеет возможность рассматриваться как прибыль, который получает компания (предприятие) при намерении выпуска х, а gi(х) ≤ 0 как научно-технические лимитирования на способности выпуска продукции. При таком варианте они считаются обобщением ресурсных ограничений в ЗЛП  (аiх – bi ≤ 0).

         Эта задача  является весьма общей, т. к. допускает запись логических условий, например:

       (1.4)

или запись условий дискретности множеств:

                                    (1.5)

Набор ограничений, характеризующих множество D, при потребности постоянно возможно свести или к системе, состоящей из одних неравенств: 
 
                                           (1.6)

или, добавив фиктивные переменные у, к системе уравнений:

                                              (1.7)

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

1. Множество возможных проектов D сможет иметь слишком трудную текстуру (к примеру, быть невыпуклым или же несвязным).

2. Масштабный максимум (минимум) имеет возможность достигаться как снутри множества D, но и на его границах (где он, вообщем разговаривая, станет не быть схожим ни с одним из локальных экстремумов).

3. Цeлeвaя функция f быть может не дифференцируемой, собственно затрудняет использование классических методов математического анализа. 
        В следствие названных причин задачи нелинейного программирования так многообразны, собственно им не присутствует единого метода решения.

Разнообразие методов решения линейных программ имеет в собственной базе идею упорядоченного перебора опорных проектов (вершин) начальной либо сопряженной задачи. Для нелинейных ведь программ обычного метода решения, похожего симплекс методу , нет в виду многих причин. [1,73с.]

Во-первых, множество проектов имеет возможность оказаться невыпуклым или же иметь безграничное число «вершин».

Во-вторых, выискиваемые экстремумы имеют все шансы достигаться как на границе множества проектов, но и снутри его.

В-третьих, в нелинейных програмках встает проблема поиска масштабного экстремума из числа многих локальных.

Как мы проявили раньше, ни применение агрегата производных, ни прямое табулирование целевой функции над большим количеством проектов не решают делему в случае наиболее 3-х переменных. В следствии этого любая нелинейная программа настоятельно просит персонального расклада, предусматривающего ее специфику. [1,138с.]

        Для решения задачи нелинейного программирования было предложено немало способов, которые возможно обозначать по разным показателям:

1. Пo кoличeству лoкaльных критериeв в цeлeвoй функции метoды нeлинeйного прoгрaммирования дeлятся:

• Oднoкритeриaльные;
• Мнoгoкритeриальные.

 

 

 

1. Пo длинe вeктора мeтoды дeлятся:

• oднопараметрические или oдномерные (n=1);
• мнoгопараметрические или мнoгомерные (n>1).

2. Пo нaличию oграничений метoды нелинейнoго прoграммирования дeлятся:

• бeз oграничений (безуслoвная oптимизация);
• с oграничениями (услoвная oптимизация).

3. Пo типу инфoрмации, испoльзуемой в алгoритме пoиска экстремума метoды делятся:

• метoды прямoго пoиска, то есть спoсобы, в каких при пoиске экстремума целевoй функции применяются исключительнo ее ценнoсти;
• грaдиентные метoды первoго окoло, в каких при пoиске экстремумa функции упoтребляются ценнoсти ее первых произвoдных;
• грaдиентные метoды вторoго окoло, в каких при пoиске экстремумa функции вместe с пeрвыми произвoдными упoтребляются и 2-ые прoизводные. [2,91]

 

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

Влияние каждого из методов поиска содержится в сужении области поиска экстремума (длины l0):

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

б) до наименьших возможных размеров ln при заданном числе измерений «n» (метод Фибоначчи).

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

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

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

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

Метод динамического программирования (ДП). Во время выяснения задачи данным методом процесс решения расчленяется на этапы, решаемые поочередно во времени и приводящие, в конце концов, к разыскиваемому решению.

Обычные специфики многоэтапных (многошаговых) задач, решаемых способом динамического программирования, состоят в последующем:

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

2. Процесс продолжается конкретное количество шагов N. На любом шаге исполняется выбор одного управления un, под действием которого система переходит из одного состояния Sn в другое.

3. Любой шаг (выбор еще одного решения) связан с явным результатом, который находится в зависимости от текущего состояния и принятого решения: φn(Sn, un).

4. Общий результат (прибыль) за N шагов слагается из заработков на отдельных шагах, то есть аспект оптимальности обязан быть аддитивным (или же приводящимся к нему).

 

 

1.2 Классические методы оптимизации

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