АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Классификация задач оптимизации

Читайте также:
  1. Data Mining и Business Intelligence. Многомерные представления Data Mining. Data Mining: общая классификация. Функциональные возможности Data Mining.
  2. FECONCL (ББ. Экономическая классификация)
  3. I Классификация кривых второго порядка
  4. I Психологические принципы, задачи и функции социальной работы
  5. I. 1.1. Пример разработки модели задачи технического контроля
  6. I. 1.2. Общая постановка задачи линейного программирования
  7. I. 2.1. Графический метод решения задачи ЛП
  8. I. 3.1. Двойственная задача линейного программирования
  9. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  10. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  11. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  12. I. Решение логических задач средствами алгебры логики

УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ

К изучению дисциплины «Методы оптимизации»

(конспект лекций)

Выполнил

студент гр. 10-21-2: ____________ И.В. Краснова

(подпись)

Руководитель: ____________ Г.Г. Тельнова

(подпись)

 

 

СОДЕРЖАНИЕ

 

1. Классификация задач оптимизации ……………………………………………  
2. Классификация математических методов и моделей в экономике ………….  
3. Линейное программирование ………………………………………………….  
3.1. Постановка задачи линейного программирования ……………………  
3.2. Экономическая интерпретация задач линейного программирования ……………………………………………………………  
3.3. Требования совместности условий ……………………………………..  
3.4. Графический метод решения задач линейного программирования ……………………………………………………………  
3.5. Симплекс-метод ………………………………………………………….  
3.6. Модифицированный симплекс-метод ………………………………….  
3.7. Построение опорных планов ……………………………………………  
3.8. Условия оптимальности …………………………………………………  
3.9. Метод искусственного базиса …………………………………………..  
3.10. Транспортная задача ……………………………………………………  
3.11. Двойственные задачи линейного программирования ………………..  
3.12. Устойчивость оптимизационного решения …………………………...  
4. Нелинейное программирование ……………………………………………….  
4.1. Классификация и общая постановка задач нелинейного программирования ……………………………………………………………  
4.2. Метод множителей Лагранжа …………………………………………...  
4.3. Возможные обобщения метода множителей. Седловая точка функции Лагранжа ……………………………………………………….  
4.4. Оптимальные решения при ограничениях-неравенствах. Теорема Куна – Таккера …………………………………………………………  
4.5. Выпуклое программирование. Задача выпуклого программирования ……………………………………………………………  
4.6. Квадратичное программирование …………………………………………..  
4.7. Градиентные методы …………………………………………………….  
5. Оптимизация на графах ………………………………………………………………...  
5.1. Основные понятия теории графов ………………………………………  
5.2. Связность …………………………………………………………………  
5.3. Подграфы …………………………………………………………………  
5.4. Матрица графов ………………………………………………………….  
5.5. Потоки в сетях ……………………………………………………………  
5.6. Задача о максимальном потоке сети ……………………………………  
5.7. Задача о кратчайшем пути ………………………………………………  
5.8. Задача коммивояжера ……………………………………………………  
5.9. Оптимизация сетевого графика …………………………………………  
5.10. Методы оптимизации производственной программы ……………….  
6. Динамическое программирование ……………………………………………..  
6.1. Общая постановка задачи динамического программирования ……….  
6.2. Принцип оптимальности. Уравнение Беллмана ……………………….  
6.3. Простейшие экономические задачи, решаемые методом динамического программирования ………………………………………….  
7. Математические модели потребительского поведения и спроса ……………  
7.1. Отношение предпочтения и функция полезности ……………………..  
7.2. Решение задачи об оптимальном выборе потребителя ………………..  
7.3. Функции спроса. Коэффициент эластичности …………………………  
Список литературы ………………………………………………………………...  

 

Классификация задач оптимизации

 

Во всех сферах человеческой деятельности большое ме­сто занимает принятие решений. Для постановки задачи принятия решения необходимо выполнение двух условий: 1) должно быть много решений; 2) вариант должен быть выбран по определенному принципу.

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

Известны два принципа выбора: волевой и критери­альный.

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

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

Решение не может быть оптимальным вообще, во всех смыслах, а только в одном, единственном смысле, опреде­ляемом выбранным критерием.

Критерий оптимизации называют целевой функцией, функцией цели, функционалом и др.

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

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

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

Таблица 1

Функция управления Задачи оптимизации Класс экономико-математических моделей
Техническая и органи­зационная подготовка производства Моделирование состава изде­лий. Оптимизация состава марок, шихты, смесей. Опти­мизация раскроя листового материала, проката. Оптими­зация распределения ресурсов в сетевых моделях комплексов работ. Оптимизация, планиро­вок предприятий, производств и оборудования. Оптимизация маршрута изготовления изде­лий. Оптимизация технологий и технологических режимов Дискретное (целочис­ленное) программиро­вание. Линейное про­граммирование. Сете­вое планирование и управление. Имита­ционное моделирова­ние. Динамическое программирование. Нелинейное про­граммирование. Теория графов
Технико-экономиче­ское плани­рование Построение сводного плана и прогнозирование показателей развития предприятия. Опти­мизация портфеля заказов и производственной программы. Оптимизация распределения производственной программы по плановым периодам Балансовые (матричные) модели «затраты - выпуск». Корреляционно-регрессионный ана­лиз. Экстраполяция тенденций. Линейное программирование
Оперативное управление основным производст­вом Оптимизация календарно-плановых нормативов. Кален­дарные задачи. Оптимизация стандарт-планов. Оптимиза­ция краткосрочных планов производств Нелинейное про­граммирование. Ими­тационное моделиро­вание. Линейное про­граммирование. Це­лочисленное про­граммирование

 

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

В зависимости от исходных данных выделяют 3 типа ма­тематического описания задач управления: детерминирован­ные, вероятностные и задачи в условиях неопределенности.

Исходные данные, которые заданы определенными ве­личинами, называют детерминированными.

 

 


Рис. 1

 

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

В детерминированной задаче всегда известно, что стра­тегия действий А приведет к результату a, а стратегия действий В - к результату b. Остается только определить, какой результат имеет большую полезность, чтобы выбрать лучшую из двух стратегий.

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

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

Оценки вероятностей бывают объективными и субъек­тивными. Объективные вероятности получаются путем оп­ределения отношения числа интересующих нас событий к общему числу наблюдаемых событий.

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

Переменные величины могут быть непрерывными и дис­кретными. Непрерывные величины могут принимать в за­данном интервале любые значения (например, процентное содержание элементов в марке материала). Дискретные, или целочисленные, принимают только целые значения (например, нельзя ввести в эксплуатацию 1,5 здания).

Зависимости между элементами могут быть линейными и нелинейными. Линейными называют зависимости, в которые входят переменные в первой степени и нет их произведения. Если входят переменные не в первой степени или есть произве­дение переменных, то зависимости называют нелинейными.

Сочетание различных элементов модели приводит к раз­личным классам задач оптимизации, которые требуют раз­ных методов решения, следовательно, и разных программ­ных средств (табл. 2).

Таблица 2

 

 

Исходные данные Переменные Зависимости Задача
Детермини­рованные Непрерывные Линейные Линейного программирования
Целочисленные (дискретные) Линейные Целочисленного программирования
Непрерывные, целочисленные Нелинейные Нелинейного программирования
Случайные Непрерывные Линейные Стохастического программирования  

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.018 сек.)