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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение оригинальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.

Результат поиска


Наименование:


контрольная работа Оптимизация

Информация:

Тип работы: контрольная работа. Добавлен: 20.05.13. Год: 2012. Страниц: 19. Уникальность по antiplagiat.ru: < 30%

Описание (план):


     Оптимизация

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

     

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

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

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

     И структурный, и параметрический синтез объектов может осуществляться при помощи оптимизационных алгоритмов: структурный синтез – при помощи методов дискретного математического программирования; параметрический – непрерывного; структурно-параметрический – при помощи алгоритмов дискретно-непрерывного математического программирования.

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

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

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

     С теорией оптимизации тесно связаны  математическое программирование, теория исследования операций, теория принятия решений, динамическое программирование.

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

     Литература

  1. Батищев Д.И. Методы оптимального проектирования. М. Радио и связь 1984г.
  2. Батищев Д.И. Поисковые методы оптимального проектирования. М.: Сов. Радио, 1975.
  3. Химмельблау Д. Прикладное нелинейное программирование. Пер. с англ. Мир, М., 1975.
  4. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.
  5. Сушков Ю.А. Об одном способе организации случайного поиска. Автоматика и вычислительная техника, 1974, № 6, 41-48.
  6. Фиакко А., Мак-Кормик Г. Нелинейное прогаммирование. Методы последовательной безусловной минимизации. Пер. с англ. М.: Мир, 1972.
  7. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М.: Наука, 1981.
  8. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

     Математическое  программирование

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

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

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

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

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

     Наиболее  популярными локальными алгоритмами  нулевого порядка (поисковыми алгоритмами) являются Роземброка (вращающихся координат), деформируемого многогранника, Хука-Дживса.

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

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

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

5.1 Постановка задачи  векторной оптимизации

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

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

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

Многокритериальные задачи широко распространены в техническом проектировании, например, задача проектирования компьютера с максимальным быстродействием, максимальным объемом оперативной памяти и минимальным весом или задача проектирования электрического двигателя с максимальной мощностью, максимальным коэффициентом полезного действия, минимальным весом и минимальными затратами электротехнической стали (естественно, при ограничениях на необходимые параметры проектируемых устройств). Реальные многокритериальные управленческие задачи также широко распространены,  лозунг экономики СССР 80-х гг. - «максимум качества при минимуме затрат», несмотря на его одиозность, выражал сущность большинства проблем управления.

Под многокритериальной задачей зачастую понимают не собственно вербальное  описание задачи, а ее модель, а именно: «многокритериальная  задача – математическая модель принятия оптимального решения по нескольким критериям. Эти критерии могут отражать оценки различных качеств объекта или процесса, по поводу которых принимается решение».

Формально многокритериальная задача  как модель задается  в виде:           

                             

          ,                                                        (5.1)

где D - множество допустимых решений.  F(x) – векторная функция векторного аргумента x,  которую можно представить как F(x)={f1(x), f2(x), … , fk(x) },      где f1(x), f2(x), … , fk(x) – скалярные функции векторного аргумента x, каждая их которых является математическим выражением одного критерия оптимальности.   Так как в данной модели используется векторная целевая функция, ее зачастую называют задачей векторной оптимизации. Очевидно, что задача (5.1) не принадлежит классу задач математического программирования, т.к.модели      этого класса задач содержат всегда только одну целевую функцию векторного аргумента. 

 
 

 
Иначе задачу  (5.1) можно переписать в виде:   
 

Сущность поставленной задачи состоит в нахождеии такого ее допустимого решения, т.е. }, которое в том или ином смысле максимизирует (минимизирует) значения всех  целевых функций fi(x), i=1,k.  Существование решения, буквально максимизирующего все целевые функции, является редким исключением. (Если вспомнить пример о поиске одновременно очень качественной и очень дешевой покупки, то становится понятным, что нахождение такого решения – редкая удача, но, гораздо более часто,  это неразрешимая задача).

Отсюда следует, что принципиальным моментом при  решении такого рода задач является предварительная договоренность, а  что считать  самым предпочтительным решением, т.е. надо договориться об используемом принципе оптимальности. Ранее используемый принцип оптимальности «хорошо то, что доставляет наибольшее (наименьшее) значение имеющемуся единственному критерию оптимальности» в многокритериальных задачах очевидно «не работает».

Задача векторной  оптимизации в общем случае не имеет    строго математического математического   решения.  Для получения того или иного ее решения  необходимо использовать дополнительную субъективную информацию специалиста в данной предметной области, которого принято называть лицом принимающим решение (ЛПР), в английском языке - decision maker. Это означает, что при решении задачи разными специалистами с привлечением различных источников информации, скорей всего будут получены различные ответы.

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

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

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

Математическая  постановка (модель) задачи математического программирования (МП) выглядит следующим образом:

необходимо определить значения вектора переменных x = (x1,x2,…, xn), которые удовлетворяют ограничениям вида

g i (x1,x2,…, xn)

 bi    , для всех i = 1,…, m

и доставляют максимум или минимум целевой функции

f (x1,x2,…, xn) > max (min).  

Решением (планом, вектором управления) задачи МП называется всякий вектор х из пространства En (En- n-мерное векторное пространство), в геометрической интерпретации – это точка векторного n-мерного пространства. Допустимым решением (планом)  задачи МП называется такое решение задачи, которое удовлетворяет ее ограничениям g i (x1,x2,…, xn)  bi    , для всех i = 1,…, m. 

Совокупность  допустимых решений задачи называют областью допустимых решений (ОДР) задачи МП, которую, как правило, обозначают как D. Оптимальным решением х* называется такое допустимое решение, при котором целевая функция достигает своего оптимального (в нашем случае — максимального) значения, т. е. решение, удовлетворяющее условию max f(x) = f(x*). Величина f* = f(x*) называется оптимальным значением целевой функции.

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

 Если хотя  бы одна из функций g i (x1,x2,…,  xn) или f (x1,x2,…, xn) нелинейная, то такая задача МП называется задачей нелинейного программирования.           

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

В общем виде задача линейного программирования (ЗЛП) может быть сформулирована как задача нахождения вектора x = (х1, х2, …, хn) En такого, что функция линейного вида z(x)=c1x1+ c2x2+ c3x3+ … + cnxn>max (или min), т.е. достигает своего максимального или минимального значения, при этом вектор x = (х1, х2, …, хn) должен удовлетворять системе линейных неравенств:  

                (1.1)  

Таким образом, модель задачи линейного программирования (ЛП) может быть записана в виде (1.2). Функцию z в задаче (1.2) является целевой функцией (ЦФ) задачи.   

                        (1.2)  

Линейные неравенства  в модели ЛП  вида   

  

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

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

Дополнительно следует заметить, что в математическом смысле задача поиска максимума функции эквивалентна задаче поиска минимума.

   ?   
.

Например, точка  максимума функции f(x) = x2  очевидно равна точке минимума функции  f'(x) = -x2.

Модель задачи  ЛП (1.2) можно представить в матричной форме:   

       (1.3)  

где c,x,b – векторы-столбцы из пространства En, А-матрица коэффициентов условий {aij} размерности m?n.   

,
,
,
 
 

Задачу линейного  программирования, записанную в форме (1.2-1.3), называют общей задачей линейного программирования[1].

Процесс решения  задачи ЛП заключается в отыскании  решений ЗЛП или получения  вывода о том, что задача ЛП по тем  или иным причинам не имеет решений.

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

1.2. Схема построения  оптимизационных  моделей  

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

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

1) Что является  искомыми величинами задачи? Как лучше обозначить эти величины?

2) Какова цель  решения? Что в задаче служит критерием эффективности (оптимальности) решения, например, прибыль, себестоимость, время и т.д. В каком направлении должно изменяться значение этого критерия (к max или к min) для достижения наилучших результатов?

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

Только после  ответа на все эти вопросы можно  приступать к записи математической модели.

В общем виде схема построения математической модели состоит из следующих этапов.

Этап 1. Выбор и обозначение переменных задачи.

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

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

Искомые величины являются переменными задачи, которые, как правило, обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде x = (x1, x2, ... ,xn). При этом переменные могут иметь и более чем один индекс, например, xij или xikl.

Этап 2. Представление целевой функции задачи.

Цель решения  записывается в виде ЦФ, обозначаемой, например, z. Математическая формула  ЦФ z отражает способ расчета значений критерия эффективности задачи.

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

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

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

1.3. Задачи к практикуму  

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

Задача 1.1. О производстве красок.

Фабрика производит два вида красок: первый - для наружных, а второй - для внутренних работ. Для производства красок используются два ингредиента: А и В. Максимально возможные суточные запасы этих ингредиентов составляют 6 и 8 тонны соответственно. Известны расходы ингредиентов А и В на производство 1 т соответствующих красок (табл. 1.1). Изучение рынка сбыта показало, что спрос на краску второго вида никогда не превышает 2 тонн в сутки. Оптовые цены одной тонны красок равны: 3 тыс. руб. за тонну краски первого вида; 2 тыс. руб. за тонну краски второго вида.

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

Таблица 1.1 Исходные данные к задаче о производстве красок

 
Ингредиенты    
Расход  ингредиентов,

т ингредиента/т  краски

Запас,

тонн ингр./

сутки   

Краска  первого вида Краска второго  вида
А 1 2 6
В 2 1 8

 

 

Решение

Построим модель задачи, используя описанную в 1.2 схему.

1. Переменные  задачи.

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

·    
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.