Конспект лекций по дисциплине «Математическая теория оптимизационных процессов»



бет1/7
Дата24.04.2020
өлшемі338.56 Kb.
түріКонспект лекций
  1   2   3   4   5   6   7
Министерство образования и науки республики казахстан

АЛМАТИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ


Факультет «Инжиниринга и информационных технологий»

Кафедра «Механизация и автоматизация производственных процессов»


ЛЕКЦИОННЫЕ ЗАНЯТИЯ


по дисциплине

«Математическая теория оптимизационных процессов»

для специальности 6М070200 – Автоматизация и управление

Алматы,2019г.


Конспект лекций по дисциплине «Математическая теория оптимизационных процессов»

Лекция 1 Раздел 1. Общая методология математической теории оптимизационных процессов
Тема. Принципы и средства исследования оптимизационных процессов

Введение. Основные понятия

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

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

При решении конкретной задачи управления применение методов математической теории оптимизации предполагает:

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

2.Изучение взаимосвязей, определяющих в последствии принятия решений, и

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

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

Операция - любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа её проведения, организации, иначе – выбора некоторых параметров.

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

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

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

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

Концептуальные модели и составляют фундамент математических моделей.

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

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

Математические модели и методы стали необходимым элементом современной теории управления. Использование математического моделирования позволяет:

Формально описать наиболее важные связи переменных и объектов,

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

Использовать методы математики и статистики для получения новых знаний об объекте,

Излагать точно и компактно на языке математики положения теории управления.

Любое исследование предполагает объединение теории (модели) и практики (статистических данных). Теоретические модели используются для описания и объяснения наблюдаемых процессов. Эмпирическое построение и обоснование модели происходит на базе статистических данных.

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

Построение математическая модель операции происходит по этапам:

Формулировка предмета и цели исследования;

Выявление структурных и функциональных элементов, их качественных характеристик;

Словесное описание взаимосвязей между элементами модели;

Формализация описательной модели;

Расчеты математической модели на ЭВМ;

Анализ полученного результата, выводы и прогноз.

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

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

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

Всякий опорный (определенный) выбор, зависящий от начальных параметров, называется решением.

Оптимальное решение – это выбранное по какому-либо критерию оптимизации наиболее эффективное из всех альтернативных вариантов решение.

Оптимизация решения – это процесс перебора множества факторов, влияющих на результат.

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

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


Общая постановка задачи исследования операций.

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

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

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

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

Критерий эффективности – целевую функцию Z запишем в виде:

Z= f(х1, х2 , …, а1 , а2 , …)

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

Рассмотрим класс моделей. Такие задачи возникают при оптимизации планирования и управления экономическими системами.

Оптимизационную задачу можно сформулировать в общем, виде:

Найти переменные х1, х2 , …, хn , обращающие в максимум ( или минимум) целевую функцию

Z= f(х1, х2 , …, хn ) → max (min) (1)



и удовлетворяющие системе неравенств (уравнений)

φi 1, х2 , …, хn ) ≤ bi , i=1,2,…m, (2)

xj ≥0

для получения оптимального решения этой задачи Х* = (х1* , … , хn*) применим методы математического программирования.


Прикладные аспекты исследования операций

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

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

Применение методологии и методов оптимизации при разработке информационных систем.

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

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

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

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

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

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

При принятии решений современный менеджер должен: широко использовать различные методы науки управления; оценивать среду принятия решений и риски; знать и уметь применять различные модели и методы прогнозирования для принятия решений.
Выводы.
Тестовые задания для самоконтроля

1. Цель исследования операций это:

А) количественное обоснование принимаемых решений по организации управления

Б) качественное обоснование принимаемых решений по организации управления

В) эффективное управление определенными системами

Г) адаптивное управление определенными системами

Д) оптимальное решение по организации управления

2. Этапы математического моделирования состоят из:

А) 8 этапов

Б) 6 этапов

В) 7 этапов

Г) 5 этапов

Д) 3 этапов

3. Метод математического моделирования основывается:

А) на принципе аналогии

Б) на возможности изучения реального объекта

В) на рассмотрение подобного ему доступного объекта

Г) на описании социально-экономических систем моделью

Д) на формализации

4. Под математической моделью понимают:

A) образ реального объекта

Б) образ реального объекта в материальной форме

В) образ реального объекта, описанный с помощью математического аппарата

Г) образ реального объекта в идеальной форме

Д) образ реального объекта в физической форме

5. Какой процесс представляет собой моделирование:

A) линейный

Б) разветвляющийся

В) циклический

Г) сложный

Д) комбинированный
11.1.2. Лекция 2. Тема. Теоретические основы математической теории оптимизации
Математическое программирование.

Математическое программирование изучает экстремальные задачи

Типичные постановки задач

1. Определение наилучшего состава смеси О диете»).

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


Задача 2. Задача об оптимальном плане выпуска продукции.

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



Задача 3. Планирование перевозок металлопродукции (транспортная задача).

Пусть имеется m пунктов производства с объемами a1, a2, …, am и n пунктов потребления с объемами потребления b1, b2, …, bn. Известны cij – затраты по перевозке единицы продукции из i-го пункта производства в j-й пункт потребления. Необходимо составить такой план перевозок, при котором были бы удовлетворены потребности во всех n пунктах потребления и при этом суммарные затраты на перевозку были бы минимальными.



Задача 4. Задача о назначениях.

Пусть имеется n самолетов различных типов, которые требуется распределить между n авиалиниями. Известен ожидаемый эффект cij от использования i-го самолета на j-й авиалинии. Задача состоит в таком назначении самолетов на авиалинии (по одному на каждую авиалинию), чтобы суммарный эффект от использования всех самолетов был максимальный.

Разрешимость задачи оптимизации.

Решение задач оптимизации производится с помощью математических моделей и применения ЭВМ.

Основные этапы разрешимости задачи оптимизации, т.е принятия оптимального решения с помощью ЭВМ показаны на схеме рис.1.

Исходные

Данные



Объект→ Задача→Модель→Алгоритм→Программа→ЭВМ→Решение.


Рис.1.
Классификация задач математического программирования.

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

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

Наиболее часто встречавшиеся задачи оптимизации даны в таблице 1.

Таблица1

Область применения

Управления

Проектирование

Разработка технологических процессов

Основные задачи

Различные задачи распределения ресурсов

Оптимизация параметров объекта проектирования

Оптимизация маршрута изготовления изделий

Оптимизация структуры объекта проектирования

Оптимизация параметров технологических процессов

Оптимизация функционирования



Различные классы задач требуют различных методов решения. Часто встречающиеся классы задач оптимизации даны в таблице 2.

Таблица 2

Задача

Обозначение

Исходные данные

Переменные

Зависимости

Линейного программирования

ЛП

Детерминированные

Непрерывные

Линейные

Целочисленного программирования

ЦЧП




Целочисленные

Линейные

Нелинейного программирования

НЛП




Непрерывные, целочисленные

Нелинейные

Стохастического программирования

СТП

Случайные

Непрерывные

Линейные

Общая схема решения методов оптимизации.

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

Общая схема состоит из пяти шагов:

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

2. ( – оптимальная точка). Если очередная точка является оптимальной, то конец решения. Если нет, то переходим к следующему шагу.

3. Определяем направление в данной точке

.

4. Определение шага движения по данному направлению .

5. Определение новой точки . Переход к шагу 2.

Прямые, двойственные и комбинированные методы решения

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

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

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

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

Тестовые задания для самоконтроля

1. Критерий эффективности может принимать:

A) только максимальное значение

Б) только минимальное значение

В) только целочисленное значение

Г) только дискретное значение

Д) только экстремальное значение

2. Что мы понимаем под управляемым мероприятием, преследующем цель:

A) систему

Б) операцию

В) экономико-математическую модель

Г) кибернетику

Д) идентификацию

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

A) анализ экономических объектов и процессов

Б) экономическое прогнозирование, предвидение и развитие

В) выработка управленческих решений

Г) все выше перечисленные ответы верны.

Д) синтез математических методов

4. Для реализации математических моделей используются:

A) методы оптимизации

Б) методы планирования

В) планово- управленческие решения

Г) ЭВМ


Д) методы идентификации

5. Общая схема решения методов оптимизации состоит из

А) трех шагов

Б) пяти шагов

В) двух шагов

Г) четырех шагов

Д) шести шагов

6. Для производства трех видов изделий А, В, C завод должен использовать два вида сырья I и II, запасы которого на планируемый период 100 и 50 условных единиц. В приведенной таблице даны технологические коэффициенты и прибыль от реализации единицы продукции каждого вида.






A

B

C

Запас

I

5

1

2

100

II

4

2

1

50

Прибыль

6

2

4




Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль:

A) 6x(1)+2x(2)+4x(2)-->max, 5x(1)+x(2)+2x(3)<=100,

4x(1)+2x(2)+x(3)<=50, x(1),x(2),x(3)<=0

Б) 6x(1)+2x(2)+4x(2)-->max, 5x(1)+x(2)+2x(3)<=100,

4x(1)+2x(2)+x(3)<=50, x(1),x(2),x(3)>=0

В) 6x(1)+2x(2)+x(2)-->max, 5x(1)+x(2)+2x(3)<=100,

4x(1)+2x(2)+x(3)<=50, x(1),x(2),x(3)>=0

Г) 6x(1)+2x(2)+4x(2)-->max, 5x(1)+2x(2)+2x(3)<=100,

4x(1)+2x(2)+2x(3)<=50, x(1),x(2),x(3)>=0

Д) 6x(1)+2x(2)+4x(2)-->max, 5x(1)+x(2)+6x(3)<=100,

4x(1)+2x(2)+2x(3)<=50, x(1),x(2),x(3)>= 0
11.1.3. Лекция 3.



Достарыңызбен бөлісу:
  1   2   3   4   5   6   7


©netref.ru 2019
әкімшілігінің қараңыз

    Басты бет