Глава 2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ

Оглавление

ВВЕДЕНИЕ

ВВЕДЕНИЕ В МЕТОДЫ ОПТИМИЗАЦИИ

2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ
2.1 Параметры плана
2.2 Целевая функция (план)

3. ФУНКЦИЯ ОДНОЙ ПЕРЕМЕННОЙ
3.1 Определение функции одной переменной и ее свойства
3.2 Исследование функции в экономике. Нахождение максимума прибыли
3.3 Определение глобального экстремума
3.4 Выпуклость, вогнутость функции
3.5 Критерий оптимальности
3.6 Идентификация оптимумов

4. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ
4.1 Методы исключения интервалов
4.1.1 Метод сканирования
4.1.2 Метод деления отрезка пополам
4.1.3 Метод золотого сечения
4.1.4 Сравнительная характеристика методов исключения интервалов
4.2 Полиномиальная апроксимация и методы точечного оценивания
4.2.1 Метод параболической апроксимации
4.2.2 Метод Пуэлла
4.3 Сравнение методов одномерного поиска

5. ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ
5.1 Функции многих переменных, их обозначение и область определения
5.2 Некоторые многомерные функции, используемые в экономике
5.3 Частные производные функции многих переменных
5.4 Экономический смысл частных производных
5.5 Частные производные высших порядков
5.6 Свойства функции нескольких переменных
5.7 Производная по направлению. Градиент. Линии уровня функции
5.8 Экстремум функции многих переменных

6. МНОГОМЕРНАЯ БЕЗУСЛОВНАЯ ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ
6.1 Концепция методов
6.2 Метод градиентного спуска
6.3 Метод наискорейшего спуска

7. КРИТЕРИИ ОПТИМАЛЬНОСТИ В ЗАДАЧАХ С ОГРАНИЧЕНИЯМИ
7.1 Задачи с ограничениями в виде равенств
7.2 Множители Лагранжа
7.3 Экономическая интерпретация множителей Лагранжа
7.4 Условия Куна-Таккера
7.4.1 Условия Куна-Таккера и задача Куна-Таккера
7.5 Теоремы Куна-Таккера
7.6 Условия существования седловой точки

8. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
8.1 Предмет динамического программирования
8.2 Постановка задачи динамического программирования
8.3 Принцып оптимальности и математическое описание динамического процесса управления
8.4 Общая схема применения метода динамического программирования
8.5 Двумерная модель распределения ресурсов
8.6 Дискретная динамическая модель оптимального распределения ресурсов
8.7 Выбор оптимальной стратегии обновления оборудования
8.8 выбор оптимального маршрута перевозки грузов
8.9 Построение оптимальной последовательности операций в коммерческой деятельности

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ РАСЧЕТНО-ГРАФИЧЕСКОГО ЗАДАНИЯ

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 1

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 2

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 3

ЛИТЕРАТУРА

ВВЕДЕНИЕ

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

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

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

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

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

Учебно-практическое пособие для системы дистанционного образования по дисциплине «Методы оптимизации и теория управления» предназначено для самостоятельной работы студента при нестационарной форме контроля знаний.

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

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

Глава 1. ВВЕДЕНИЕ В МЕТОДЫ ОПТИМИЗАЦИИ

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

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

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

Методы оптимизации являются разделом математического моделирования.

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

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

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

· установить границы подлежащей оптимизации системы;

· определить количественный критерий, на основе которого можно произвести анализ вариантов с целью выявления «наилучшего»;

· осуществить выбор внутрисистемных переменных, которые используются для определения характеристик и идентификации вариантов;

· построить модель, отражающую взаимосвязи между переменными.

Эта последовательность действий составляет содержание процесса постановки задачи оптимизации.

Рассмотрим некоторые встречающиеся в практической деятельности задачи математического моделирования в содержательной, а не в формальной математической трактовке.

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

Имеется начальное количество средств Р₀, которое необходи­мо распределить в течение п лет между S предприятиями. Сред­ства и_ki (k = 1,..., n; i = 1,..., S), выделенные в k-м году i-му пред­приятию, приносят доход в размере f_ki(u_ki) и к концу года возвращаются в количестве j_ki(u_ki). В последующем распределе­нии доход может либо участвовать (частично или полностью), ли­бо не участвовать.

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

(1)

Количество ресурсов в начале k-го года будем характеризовать величиной P_n1 (параметр состояния). Управление на k-том шаге состоит в выборе переменных u_k1, u_k2, …, u_ks, обозначающих ресурсы, выделяемые в k-том году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид

(2)

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

Требуется определить п_s неотрицательных переменных и_ki, удовлетворяющих условиям (2) и максимизирующих функ­цию (1).

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

Проблема управления запасами является одной из важнейших областей практического приложения экономико-математических методов, в том числе методов математического программирова­ния.

При формулировке задач управления запасами используют следующие понятия.

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

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

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

Под запасами можно понимать запасы сырья или других мате­риалов, поставляемых дискретными партиями (пополнение), ко­торые должны обеспечить непрерывное потребление в процессе производства (расход). Критерием оптимальности могут служить суммарные затраты на хранение запасов, замораживание оборот­ных средств и поставки запасов.

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

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

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

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

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

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

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

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

Существует достаточно большое количество численных методов оптимизации. Основные из них можно классифицировать следующим образом:

· по размерности решаемой задачи: одномерные и многомерные;

· по способу формирования шага многомерные методы делятся на следующие виды:

q градиентные:

o по способу вычислений градиента: с парной пробой и с центральной пробой;

o по алгоритму коррекции шага;

o по алгоритму вычисления новой точки: одношаговые и многошаговые;

q безградиентные: с поочередным изменением переменных и с одновременным изменением переменных;

q случайного поиска: с чисто случайной стратегией и со смешанной стратегией;

· по наличию активных ограничений;

· без ограничений (безусловные);

· с ограничениями (условные);

· с ограничениями типа равенств;

· с ограничениями типа неравенств;

· смешанные.

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

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

Вопросы к главе 1

1. Почему необходимо использование математики в экономике?

2. Что такое математическая модель?

3. Как строится математическая модель экономического явления и объекта? Приведите пример построения модели.

4. Что такое оптимизация?

5. Какие существуют методы оптимизации?

6. Какие экономические задачи решаются методами оптимизации?

Глава 2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ

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

Рассматривая некоторую произвольную систему, описываемую m уравнениями с n неизвестными, можно выделить три основных типа задач:

· если m = n, то задачу называют алгебраической. Такая задача обычно имеет единственное решение;

· если m > n, то задача переопределена, как правило, не имеет решений;

· если m < n, то задача недоопределена, имеет бесконечно много решений.

В практике чаще всего приходится иметь дело с задачами третьего типа.

Введем ряд определений.

2.1. Параметры плана

Определение. Параметры плана – это независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу.

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

Например, в качестве параметров могут рассматриваться значения длины, массы, времени, температуры.

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

Обозначения. Обычно число проектных параметров обозначают через n, х – сами проектные параметры с соответствующими индексами

х₁, х₂, …, х_n – n проектных параметров задачи.

2.2. Целевая функция (план)

Определение. Целевая функция – выражение, значение которого стремимся сделать максимальным или минимальным.

Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (n+1)-мерную поверхность.

1) Если имеется только один проектный параметр, то целевую функцию можно представить кривой на плоскости (рис. 1).

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

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

Целевая функция в ряде случаев может быть представлена:

· кусочно-гладкой функцией;

· таблицей;

· только целыми значениями;

· двумя значениями – да или нет (дискретная функция).

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

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

Вопросы к главе 2

1. Что такое параметры плана?

2. Приведите пример параметров плана.

3. Дайте определение целевой функции.

4. Как изображается целевая функция?

Не нашли, что искали? Воспользуйтесь поиском по сайту: