Щербаков Б.Г., Попов А.А. Информационные технологии
Подождите немного. Документ загружается.
1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ
(образована в 1953 году)
Кафедра информационных технологий
Дистанционное
обучение
Информ-19.22.2202.очн.плн Информ-19.22.2102.зчн.скр
Информ-19.22.2102.зчн.плн Информ-19.22.2102.очн.плн
Информ-19.22.2102.вчр.плн
Щербаков Б.Г., Попов А.А.
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
Учебно-практическое пособие для студентов
всех специальностей и всех форм обучения
www.msta.ru
Москва – 2004
2
УДК
© Щербаков Б.Г, Попов А.А.. Учебно-практическое пособие по
информационным технологиям. – М., МГУТУ, 2004 г.
Рекомендовано Институтом информатизации образования РАО
В учебно-практическом пособии в краткой и систематической форме
изложено основное содержание курса «Информационные технологии».
Значительное внимание уделено исследованию операций, как системному
инструменту, позволяющему поставить задачу, оценить и выбрать
рациональный метод ее решения. Рассмотрены обратные задачи, поскольку они
доминируют в операционных исследованиях. Приведенная классификация
задач содержит также и конкретные рекомендации по методам их решения. В
последующих главах рассмотрены постановка и численные решения основных
типов задач с использованием, как традиционных математических методов, так
и современной широко распространенной программы имитационного
математического моделирования Mathcad. В пособии даны тесты и вопросы по
темам для самоконтроля.
Пособие предназначено для студентов специальностей 2202 и 2102 всех форм
обучения.
Авторы: Щербаков Б.Г., Попов А.А.
Рецензент: проф МГУПБТ Бородин А.В., проф МГУПБТ Сапфиров С.Г.
Редактор: Свешникова Н.И.
© Московский государственный университет технологий и управления, 2004
109004, Москва, Земляной вал, 73
3
Содержание
Цели и задачи изучения курса………………………………………………….. …4
Глава 1 Основные понятия и определения. Прямые и обратные задачи
информационных технологий…………………………………………………….5
§1.1 Основные понятия и определения…………………………………………….5
§1.2 Прямые и обратные задачи информационных технологий………………...10
Глава 2 Решение задач в условиях неопределенности……………………….11
§2.1 Детерминированные задачи…………………………………………………..11
§2.2 Стохастические задачи………………………………………………………..11
§2.3 Нерегулярные задачи…………………………………………………………13
Глава 3 Исследование и решение распределительных задач……………….15
§3.1 Общие задачи линейного программирования (ОЗЛП)……………………..16
§3.2 Задачи о назначении…………………………………………………………..19
§3.3 Распределение однородных и неоднородных ресурсов…………………….27
§3.3.1 Однородные ресурсы………………………………………………………..27
§3.3.2 Неоднородные ресурсы…………………………………………………….36
Глава 4 Задачи управления запасами………………………………………….43
§4.1 Управление при удовлетворительном спросе……………………………….45
§4.2 Управление при неудовлетворительном спросе…………………………….49
§4.3 Общая задача управления запасами…………………………………………54
Глава 5 Задачи массового обслуживания (ЗМО). Задачи
функционирования и оптимизации структур…………………………………60
§5.1 Функционирование системы массового обслуживания в
установившемся режиме…………………………………………..……………….63
§5.2 Функционирование системы массового обслуживания в
неустановившемся режиме……………………………………………...…………68
Ответы на тестовые задания……………………………………………………….74
Тестовые задания по дисциплине…………………………...……………. ……..75
Литература………………………………………………………………………..…76
4
Цели и задачи изучения курса
Целью изучения курса информационных технологий является освоение
студентами основы методов постановки и решения различных задач
функционирования (управления) с использованием принципов исследования
операций, информационных технологий и возможностей локальных
информационных систем, функционирующих на базе операционной системы
Windows: популярных офисных пакетов (электронные таблицы Microsoft Excel
и системы управления базами данных (СУБД) Microsoft Accesses) из
программного комплекса Microsoft Office; а также широко распространенной
программы имитационного математического моделирования MathCad.
Изучаемый курс является базой для освоения основ т.н. интегрированных
пакетов, изучаемых в последующих дисциплинах и позволяющих комплексно
решать ряд профессиональных задач. Это необходимо как для подготовки
конкурентоспособного на рынке труда специалиста, так и для дальнейшего
развития навыков использования студентами ЭВМ в процессе выполнения
контрольных, курсовых работ и дипломного проектирования.
При изучении дисциплины предполагается, что студенты освоили
предусмотренные учебным планом курсы: «Теория вероятностей»,
«Математическая статистика и случайные процессы», «Методы оптимизации»,
«Информатика», «Курс компьютерной подготовки».
В итоге изучения студент должен:
ИМЕТЬ ПРЕДСТАВЛЕНИЕ
о современных методах информационных
технологий.
ЗНАТЬ
возможности современных методов исследования операций,
методов информационных технологий и основы их алгоритмизации.
УМЕТЬ
поставить инженерную или производственную задачу
практической сложности для решения на ЭВМ
Построить алгоритм решения этой задачи. По разработанному алгоритму
составить программу.
Самостоятельно отладить программу и правильно интерпретировать
результат счета.
Разработать удобный Windows-интерфейс программы.
Инсталлировать свою работу на другие машины.
ПРИОБРЕСТИ НАВЫКИ
самостоятельной работы на компьютере по созданию
полноценных продуктов информационных технологий.
В учебно-практическом пособии изложены общие принципы и основы
современных методов исследования операций и соответствующих
информационных технологий с использованием классических и численных
методов математики, постановки, разработки и поиска оптимальных решений
ряда основных практических, технических и организационных задач отрасли*.
* - информационные технологии в экономике изучаются в отдельной дисциплине,
предусмотренной учебным планом специальности 2202
5
В частности рассмотрены:
Основные понятия и определения
Принципы анализа и синтеза систем, в том числе целевые функции,
критерии и показатели эффективности.
Основы их функционального представления. Практические структуры,
используемые в современной практике исследований. Их преимущества и
недостатки.
Физические и математические постановки задач, их модели, решения,
принципы исследования больших (сложных) систем, иерархические структуры,
их элементы, блоки, основные виды связей, фиксированные, с дискретным
изменением и аналитическим представлением, а также другие методические и
практические вопросы.
Глава 1. Основные понятия и определения
Прямые и обратные задачи информационных технологий
§1.1 Основные понятия и определения
Операция – последовательность действий, объединенных единым
замыслом и общей целью.
Показатель эффективности – количественный критерий-мера
эффективности операции и ее этапов. Поиск его максимума будем обозначать
W => max, минимума W => min. Если при исследовании операции учитываются
случайные факторы, то часто за показатель эффективности принимают его
математическое ожидание (МО), при релейной («да-нет» постановке задачи) за
показатель эффективности принимается вероятность достижения цели Р(А).
Выбор показателя эффективности в общем случае достаточно сложная
задача, так как возникает необходимость учета групп факторов. Обычно
функция W является функцией нескольких переменных.
Если переменные или их часть имеют различную меру, то задача еще
более осложняется. Так что в настоящее время нет достаточно удобных и
общих методов ее решения. В частных случаях исследуются альтернативные
варианты, строятся ранжированные последовательности, бинарные отношения,
логики предпочтения и выбора доминантных вариантов (методы «Макбет»,
«Electre») и др.
Физическая и математическая модель операций Для получения в
конечном итоге конечных оценок решаемых задач в начале строится
физическая модель операции. Далее на ее основе разрабатывается физическая и
в последующем математическая модели, для этого операция схематизируется и
разрабатывается алгоритм решения. Физическая модель заключается в
описании с использованием неформальных терминов закономерностей
операции или ее частей, которые в последующем подлежат последующей
формализации и в итоге составят математическую модель. В конечном итоге
разрабатывается алгоритм решения.
6
Следует заметить, что универсальных и общих схем построения в
настоящее время также не существует.
Часто качественное решение во многом зависит от автора.
При построении модели необходимо соизмерять потребную точность
ожидаемых результатов с точностью исходной информации и, соответственно,
с глубиной функционального представления рассматриваемых зависимостей.
При этом проводится предварительная экспертная оценка возможных
методов решения и выбор наиболее предпочтительного из них.
В конечном итоге исследователи, используя схематизацию задачи и вводя
упрощающие предположения, практически всегда с той или иной точностью
«выходят» на получение конечного результата.
Следует заметить, что при решении сложных задач весьма продуктивна
разработка системы моделей (системы имитационных модулей) различающихся
глубиной отражения реальных ситуаций в модели, а, следовательно, простотой,
точностью и «прозрачностью» алгоритмов решения.
В этих условиях весьма эффективно совместное творчество
специалистов-практиков, в совершенстве владеющих информацией,
особенностями и точностями рассматриваемой операции и математиков.
Оптимальным вариантом является сочетание этих знаний в одном лице
или в группе разработчиков-универсалов.
Фазовые координаты – переменные, которые составляют вектор
х (х(1), х(2),… х(n)), определяющий многомерное с размерностью n поле
переменных, на котором изучается функционирование исследуемой системы.
Управления – u(j) удобно также рассматривать, как вектор размерности m.
m – число управлений.
Система ограничений и упрощений – определяет граничное значение
рассматриваемых переменных, а также принятые упрощающие предположения.
Области определения и существования Первая, как правило, определяет
рассматриваемые границы изменения переменных. Вторая – область
существования границы изменения показателя эффективности.
Область решений – множество всех решений и задач. Она включает
область оптимальных решений – искомый результат (цель), экстремальные
значения показателя эффективности, которые определяют решение задачи.
В практике исследований нередки случаи, когда в «чистом виде»
аналитический образ операции создать не удается и приходится привлекать
методы «линейного», «нелинейного» и «динамического» программирования, а
также теорию вероятностей, теорию игр и статистических решений, теории
массового обслуживания, нечетких множеств и другие разделы математики и
их программное обеспечение.
При невозможности получить нужные алгоритмы привлекают «тяжелую
артиллерию» - метод статистических решений (метод Монте-Карло). Он
особенно эффективен в сочетании с современными методами оптимизации* и
часто используется в практике исследований нелинейных систем. Остановимся
кратко на классификации задач моделей и алгоритмов, а также используемых в
них принципах.
7
Аналитические и статистические модели информационных технологий -
рассмотренные выше подходы основаны на моделях составляющих два класса:
1. Аналитические модели
2. Статистические модели
Особенности первых - они требуют серьезных упрощений, а
преимуществом является обзорность результатов и возможность использования
математических методов оптимизации.
Вторые - статистические модели дают большую точность, поскольку
практически не требуют упрощающих предположений. Их недостаток в том,
что они имеют меньшую «обзорность» и требуют дополнительных, часто
весьма громоздких, алгоритмов поиска оптимальных решений.
Пролонгирование результатов требует дополнительных, часто весьма
объемных, расчетов на ЭВМ.
Имитационное моделирование. Деловые игры. Разработанные алгоритмы
позволяют проводить необходимые расчеты и исследования поставленных
задач и в итоге получать нужные результаты. При этом существенную помощь
в исследованиях могут оказать получившие широкое распространение методы
«имитационного моделирования» и «деловые игры». Их сущность заключается
в следующем.
Метод «имитационного моделирования» – предусматривает
вмешательство оператора или лица, принимающего решение (ЛПР), в процесс
счета, для определения отдельных частных решений и на их основе дает
возможность оперативно корректировать развитие операции в нужном
направлении. Таким образом, создается своего рода «пакет» («наработка»)
оптимальных локальных действий ЛПР, который упрощает поиск оптимальных
решений, параллельно происходит обучение ЛПР, дающее возможность «на
ходу» принимать правильные решения в зависимости от складывающейся
ситуации.
Если условия операции изменяются (осложняются) намеренно, то
складывается «деловая игра», при которой необходимо принимать решения в
инатые строки практически без проведения дополнительных расчетов. В этих
условиях «запас» готовых решений существенно упрощает получение
желаемого результата.
Такие подходы также весьма полезны при непосредственном управлении
операциями и в деле подготовки управляющих кадров.
* -
для специальности 2202 читается спецкурс, посвященный вопросам оптимизации.
8
Многокритериальные задачи в информационных технологиях.
При исследовании сложных задач поиска оптимальных решений,
возникает необходимость одновременного учета многих факторов,
определяющих результат. Те факторы, которые оказывают существенное
влияние, желательно вводить непосредственно в выражение показателя
эффективности.
Простейшее решение этой проблемы, широко используемое в настоящее
время состоит в том, что задается структура эффективности (РЭ).
Например, в виде дроби W=A(x
i
)/B(x
j
)
В числитель входят переменные x
i
,рост которых увеличивает W, а в
знаменатель x
j
, которые снижают W.
Распространена также запись W в виде линейной функции по х.
W=Σαх
к
С весовыми коэффициентами α=α
к
, или, что расширяет возможности, но
осложняет поиск решения, с весовыми функциями. Тогда W запишется так:
W=Σf
к
х
к
Перспективным подходом является использование нелинейных
f
к
,
зависящих от нескольких переменных, а также использование рядов,
записанных в удобном ортонормированном базисе.
Все эти проблемы достаточно сложны и в настоящее время нет простых и
отработанных алгоритмов их решения. Имеющиеся отдельные результаты
достаточно уязвимы, т.к. в используемых структурах W нет достаточной
адекватности решаемой задачи.
В заключение следует отметить, что при поиске оптимальных решений,
положительный результат дает решение прямых задач информационных
технологий и наработка опытным путем множества возможных решений.
Например, в поле показателей эффективности W
1
,W
2
(«плоская задача»).
Среди них выделяются эффективные решения – такие, которые являются
доминирующими (не улучшаемыми для пар каких- либо частных ПЭ: W
1
,W
2
)
см.рис*
Они образуют множество Парэто, так называемое «переговорное
множество», которое существенно сокращает число возможных решений и
упрощает выбор оптимального из них лицом, принимающим окончательное
(«замыкающее») решение (ЛПР).
Основные принципы исследования сложных систем (системного подхода)
В настоящее время в связи с ростом масштабов и сложности операций все
чаще приходится решать задачи оптимального управления так называемыми
«сложными системами», включающими большое количество элементов и
подсистем и организованными обычно по иерархическому принципу.
Например, какая-то отрасль народного хозяйства включает относительно
9
самостоятельные специализированные управления, которые, в свою очередь,
имеют в своем подчинении предприятия (фабрики, заводы); каждое
предприятие включает подразделения, цеха и проч. Оптимизируя (с точки
зрения какого-либо критерия) работу одного звена сложной системы, нельзя
забывать о связях, имеющихся между различными звеньями системы, между
разными уровнями иерархии. Нельзя вырывать из цепи одно звено и
рассматривать его, забывая об остальных.
Простейший пример: пусть, оптимизируя работу заводского цеха, мы
добились резкого увеличения объема продукции – это хорошо. Но готовые
изделия скапливаются (в лучшем случае – на складах, а в худшем – во дворе), а
транспортные средства не готовы к вывозу всей этой продукции. Такая
ситуация может привести к материальным потерям, сводящим на нет выигрыш
за счет увеличения продукции.
Другой пример: стремясь к перевыполнению плана по «валу», фабрика в
огромном количестве выпускает изделия, не пользующиеся спросом, быстро
переходящие в разряд «уцененных», что, разумеется, тоже ведет к потерям. Все
это – результат «несистемного», «локального» планирования.
Какой из этого выход? Разумеется, не в жестком планировании работы
всей системы в целом, при котором верхнее звено управления планирует работу
всех без исключения своих звеньев (элементов). Это не только невозможно – к
этому не надо и стремиться. Главный принцип управления сложной
иерархической системой состоит в том, чтобы каждое вышестоящее звено
давало задания (управляло) нижестоящим уровнем в соответствии с
примыкающими к нему связями, которые определяются иерархической
структурой: «вниз по вертикали» («по этажам») и «согласовывало» свои
действия по линиям связи своего уровня («этажа»).
При этом если возможно, желательно функциональное («эластичное»)
представление связей.
Это, разумеется, легче сказать, чем сделать. Математическая теория
больших иерархических систем в настоящее время еще только разрабатывается.
Создается математический аппарат, пригодный для описания таких систем,
разрабатываются приемы «декомпозиции» больших систем на более удобные в
рассмотрении «небольшие» блоки, но действенных методов управления такими
системами пока не создано. На практике «системный подход» в исследовании
операций сводится пока к тому, что каждое звено, работа которого
оптимизируется, необходимо рассматривать как часть всей системы, и
учитывать его влияние на работу последней.
10
§1.2 Прямые и обратные задачи информационных технологий
Все разнообразие решаемых задач можно разделить на два типа:
1. Прямые, когда для выбранного из множества решений (действий)
х € Х, определяется показатель его эффективности W=W(х)
2. Обратные задачи – основной тип задач исследования операций
информационных технологий. В этом случае, ищется такое
решение, которое обращает W в max: W=max [W(x)] на
множестве х. Их решение сложнее поэтому часто поиск
оптимального решения сводится к решению ряда прямых задач,
т.е. к определению для ряда х: х(1), х(2),..., х(к) значений W:
W(1), W(2),…, W(к). После чего строится графическая
зависимость W=W(x) и в итоге находится оптимальное решение.
Тесты
Что такое обратная задача?
1. Задается х, определяется W 2. Определяется х, ищется W
3.Определяется х, ищется W
max
Что такое прямая задача?:
В функции y=f(x) задается:
1. х 2. у 3. поочередно х и у
В какой форме выражается критерий?
1. Постоянная величина 2.Переменная величина 3.Функция
Что характеризуют фазовые координаты?
1. Положения объекта 2.Его состояние 3.Его геометрию
Что такое системный подход?
Рассмотрение задачи: 1. Последовательно (по этапам) 2. Параллельно
(по нескольким этапам) 3. В целом
Вопросы:
1. Какие показатели эффективности вы знаете?
2. Что такое математическая модель?
3. В чем сущность имитационного моделирования?