Задачи оптимизаци

                                                          

                                                       СОДЕРЖАНИЕ

Введение.................................................................................................................................2

1 ПОСТАНОВКА ЗАДАЧ ОПТИМИЗАЦИИ....................................................................6

2 ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.......................................................7

3 АНАЛИТИЧЕСКИЙ МЕТОД ОПТИМИЗАЦИИ..........................................................13

ЗАКЛЮЧЕНИЕ....................................................................................................................15

ЛИТЕРАТУРА.....................................................................................................................16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                         Введение

     Каждый человек время от времени оказывается в ситуации, когда достижение некоторого результата может быть осуществлено не единственным способом. В таких случаях приходится отыскивать наилучший способ. Однако в различных ситуациях наилучшими могут быть совершенно разные решения. Все зависит от выбранного или заданного критерия. На практике оказывается, что в большинстве случаев понятие «наилучший» может быть выражено количественными критериями – минимум затрат, минимум времени, максимум прибыли и т.д. Поэтому возможна постановка математических задач отыскания оптимального (optimum – наилучший) результата, так как принципиальных различий в отыскании наименьшего или наибольшего значения нет. Задачи на отыскание оптимального решения называются задачами оптимизации. Оптимальный результат, как правило, находится не сразу, а в результате процесса, называемого процессом оптимизации. Применяемые в процессе оптимизации методы получили название методов оптимизации. Чтобы решить практическую задачу надо перевести ее на математический язык, то есть составить ее математическую модель.

     Математическая модель представляет собой стройную и глубокую совокупность знаний о математических моделях со своими проблемами, с собственными путями развития, обусловленными внутренними и внешними причинами и задачами. Математика дает удобные и плодотворные способы описания самых разнообразных явлений реального мира и тем самым выполняет в этом смысле функцию языка. Эту роль математики прекрасно осознавал Галилей, сказавший: «Философия написана в грандиозной книге – Вселенной, которая открыта нашему пристальному взгляду. Но понять эту книгу может лишь тот, кто научился понимать ее язык и знаки, которыми она изложена. Написана же она на языке математики».

     Итак, математика – это область человеческого знания, в которой изучаются математические модели.

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

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

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

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

     В настоящее время для решения оптимальных задач применяют в основном следующие методы:

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                 

 

 

 

 

 

 

 

                                1. ПОСТАНОВКА ЗАДАЧ ОПТИМИЗАЦИИ

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

     Наилучшие в определенном смысле решения задач принято называть оптимальными. Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

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

Составной частью методов оптимизации  является линейное программирование.

                               2 ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

     Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок; позволяющего минимизировать суммарной километраж, была дана в работе советского экономиста А. Н. Толстого в 1930 году.

     Систематические исследования задач линейного программирования и разработка общих методов их решения получили дальнейшее развитие в работах российских математиков Л. В. Канторовича, В. С. Немчинова и других математиков и экономистов. Также методам  линейного программирования посвящено много работ зарубежных и прежде всего американских ученых.

Задача линейного программирования состоит в следующем: максимизировать (минимизировать) линейную функцию

, где 

при ограничениях

(*)

причем все 

Замечание. Неравенства могут быть и противоположного смысла. Умножением соответствующих неравенств на (-1) можно  всегда получить систему вида (*).

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

Итак, надо максимизировать функцию   и удовлетворяющей системе ограничений.

Обратимся к одному из неравенств системы ограничений.

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

Замечание 2. Если  , то проще взять точку (0;0).

Условия неотрицательности   также определяют полуплоскости соответственно с граничными прямыми . Будем считать, что система неравенств совместна, тогда полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты которых являются решением данной системы – это множество допустимых решений.                       Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, лучом, многоугольником, неограниченной многоугольной областью. Таким образом, задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху (снизу). При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим прямую  (где h – некоторая постоянная). Чаще всего берется прямая . Остается выяснить направление движения данной прямой. Это направление определяется градиентом (антиградиентом) целевой функции

Вектор   в каждой точке перпендикулярной прямой  , поэтому значение f будет возрастать при перемещении прямой в направлении градиента (убывать в направлении антиградиента). Для этого параллельно прямой   проводим прямые, смещаясь в направлении градиента (антиградиента).

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

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

1. Строят прямые, уравнения  которых получаются в результате  замены в ограничениях знаков  неравенств на знаки точных равенств.

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

3. Находят многоугольник  решений.

4. Строят вектор  .

5. Строят прямую  .

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