Экономико-математическое моделирование /
←предыдущая следующая→
1 2 3 4 5
Реферат
Курсовой проект 43 с., 5 рис., 6 блок-схем, 1 таблица, 1 источник.
СЕТЕВОЙ ГРАФИК, АНАЛИЗ ОПТЕМАЛЬНОСТИ СЕТЕВЫХ ГРАФИКОВ, РАЦИОНАЛЬНЫЕ МЕТОДИКИ ПОИСКА ОСОБЫХ ПУТЕЙ СЕТЕВЫХ ГРАФИКОВ, АВТОМАТИЗАЦИЯ АНАЛИЗА СЕТЕВЫХ ГРАФИКОВ НА ЭВМ.
Направление работы – изучение математических и алгоритмических аспек¬тов анализа оптимальности сетевых графиков.
Основная цель работы – найти и доказать рациональные методики поиска особых путей сетевых графиков, легко поддающиеся автоматизации на ЭВМ и со¬кращающие затраты на сетевое планирование, за счёт уменьшения сроков разра¬ботки оптимальных сетевых графиков.
Используемый в работе метод исследований – аппарат формальной логики, позволяющий осуществлять математические доказательства с минимальным при¬влечением, для этого, формул.
В ходе работы получены блок-схемы алгоритмов расчёта параметров сете¬вых графиков и поиска их особых путей, которые предполагается использовать при создании конкретной программы анализа оптимальности сетевых графиков на любом из известных языках программирования.
Новизна работы состоит в том, что разработанные методы позволяют найти критический и наикратчайший пути сетевого графика без перебора всех возмож¬ных вариантов, что даёт: во-первых – высокую скорость разработки оптимальных сетевых графиков, а во-вторых – возможность точного ответа на вопрос об опти-мальности уже готового сетевого графика и высокую степень оптимизации сете-вых графиков по длительности в случае их неоптимальности.
Содержание
Введение 4
1 Постановка задачи 6
2 Теоретические основы сетевого планирования 9
3 Обоснование рациональных методик поиска особых путей сете¬вых графиков 15
4 Автоматизация анализа оптимальности сетевых графиков на ЭВМ 22
4.1 Представление сетевого графика в машинной форме 22
4.2 Автоматизация расчёта параметров сетевого графика 27
4.3 Автоматизация процесса поиска особых путей сетевого гра¬фика 40
Заключение 42
Список использованных источников 43
Введение
Одним из основных экономических показателей, определяющих себестои¬мость проведения проектных, научно-исследовательских, опытно-конструктор¬ских и других, поддающихся экономическому анализу, работ, связанных с раз¬ра¬боткой и внедрением на предприятие новой техники или с организацией и управ¬лением деятельности всего предприятия, является общая продолжительность их выполнения. Естественно, что в рамках некоторого рассматриваемого проекта, эта продолжительность существенно зависит от структуры упорядочивания отдель¬ных, входящих в него работ. Поэтому, построение оптимальной структуры упоря¬дочивания проектных работ является основной задачей сетевого планирования.
В основе решения указанной задачи лежит анализ смыслового содержания работ и ус¬тановление взаимо¬связей между ними, что позволяет выявить возмож¬ность их параллельного выполнения. Последнее, является основным фактором со¬кращения дли¬тельности всего проекта.
Распространены два метода оптимального планирования или упорядочива¬ния проектных работ. Один из методов, основан на построении ленточного гра¬фика, где каждой работе присваи¬ваются такие характеристики как время начала её выполнения, её длительность, которые затем, в виде параллельных от¬резков, на¬но¬сятся на шкалу времени. Другой из ме¬тодов, ос¬нован на построении сетевого графика, где структура упорядочивания работ изо¬бражается графически в виде сигнального графа.
Выбор того или иного метода планирования зависит от числа работ, входя¬щих в состав проекта. Принято, что если число работ превышает 25, то наиболее наглядный и удобный метод опти¬мального планирования – есть метод, основан¬ный на построении сетевого графика. На практике этот метод более употребите¬лен, в силу того, что число работ, входящих в некоторый рассматриваемый проект, как правило, достигает не¬скольких сотен.
Для сетевого графика, существует два понятия оптимальности: оп¬тималь¬ность по структуре и оптимальность по длительности. Оптимальность по струк¬туре характеризуется степенью параллельности исполнения отдельных ра¬бот. Оп¬тимальность по длительности характеризуется рациональным распре¬деле¬нием тру¬довых ресурсов между параллельными видами работами, которое обеспечивает при¬мерно равную их продолжительность.
На сегодняшний день нет, и не предвидится появление, строгих методов и алгоритмов построения оптимального сетевого графика, поддающихся автомати¬зации на ЭВМ. Это связано с тем, что процесс построения оптимального сетевого графика требует от экономиста-проектировщика опыта и интуитивных свойств мышления, реализовать которые на ЭВМ практически не возможно.
По другому обстоит дело с задачей анализа оптимальности уже готового се¬тевого графика. Надо сказать, что с этой задачей экономист-проектировщик стал¬кивается систематически при оптимизации сетевого графика по длительности, ко¬гда каждое очередное принятое решение о перераспределении трудовых ресурсов требует проверки на достижение оптимального варианта. Очевидно, что если ав¬томатизи¬ровать процесс решения рассматриваемой задачи, то это существенно снизит про¬должитель¬ность разработки сетевого графика, а значит и затраты на се¬тевое пла¬нирование в целом. Так вот, задача анализа оптимальности сетевого гра¬фика математиче¬ски формализуема и, с некоторыми трудностями, решаема на ЭВМ. В данном курсовом проекте, как раз и будут предложены и обоснованы ра¬циональные методики решения задачи анализа оптимальности сетевых графиков, легко автоматизируемые на ЭВМ.
1 Постановка задачи
Как правило, экономисту-проектировщику не представляется сложным, с первого раза, построить оптимальный по структуре сетевой график, когда будет обеспечена максимальная параллельность исполнения отдельных работ. Всё зави¬сит от понимания им сущности и содержания каждой работы, входящей в состав сетевого графика.
Труднее обстоит дело с распределением трудовых ресурсов по отдельным видам работ, от которого зависит оптимальность сетевого графика по длительно¬сти. Проблема в том, что практически невозможно предугадать, как от¬разится на длительности всего проекта и соотношении длительностей различных путей его сетевого графика, перенос трудовых ресурсов с одних работ на другие, в резуль¬тате которого, при неизменной трудоемкости работ, происходит увеличение дли¬тельности первых и уменьшение длительности вторых. В таких условиях, ос¬та¬ётся только один способ оптимизации сетевого графика по длительности. Этот способ основан на методе проб и ошибок, когда, первостепенную важность играет задача проверки и анализа оптимальности уже готового, полностью рассчитанного сете¬вого графика, с целью выявления ошибок в распределении трудовых ресурсов. Рассмотрим эту задачу и связанные с ней трудности подробнее.
Для сетевого графика существуют понятия пути и его продолжительности. Под путем понимается любая цепочка непрерывно следующих, друг за другом, последовательных во времени работ, от начала проекта до его завершения. Под длительностью пути понимается суммарная длительность всех, входящих в него, последовательных работ. Более понятными, данные определения станут при рас¬смотрении следующего раздела. Сейчас же, важно другое, что каждый сетевой график имеет в своём составе два особых пути: критиче¬ский и наикратчайший. Критическим путём является путь, имеющий наибольшую продолжительность среди других возможных путей сетевого графика. Наикрат¬чайшим путём является путь, который, в отличие от критического пути, имеет наименьшую продолжи¬тельность во всём сетевом графике. На понятиях этих двух путей основан наибо¬лее простой и распространенный критерий оптимальности сетевого графика, фор¬мализуемый следующим образом:
, (1.1)
где – коэффициент напряжённости наикратчайшего пути;
– длительность наикратчайшего пути, ;
– длительность критического пути, .
Из критерия (1.1) следует, что некоторый рассматриваемый сетевой график принимается оптимальным, если отношение длительности его наикратчайшего пути к длительности его критического пути не менее 0.7, или, что тоже самое, ес-ли длительность наикратчайшего пути отличается от длительности критиче¬ского пути не более чем на 30%.
Забегая вперёд, можно сказать, что длительность критического пути, легко найти путём расчёта некоторых, принятых параметров сетевого графика, которые будут подробно рассмотрены в следующем разделе. Длитель¬ность же наикрат¬чайшего пути, в общем случае неизвестна, и для её нахождения требуется сумми¬ровать длительности всех, входящих в него работ.
Теперь встаёт проблема, – а как найти работы, принадлежащие наикратчай¬шему пути, чтобы иметь возможность просуммировать их длительности? Решить данную проблему, для человека, интуитивно или простым перебором вариантов, очень проблематично, особенно при большой, сильно разветвленной структуре се¬тевого графика. Зачастую и ЭВМ справиться с этой задачей не может, в силу того, что её быстродействие ограничено, а число всех возможных вариантов путей сете¬вого графика, уже при стах событиях, может достигать миллионов или даже сотен миллионов.
Так вот, оказывается, эта проблема решаема, причём без перебора вариантов и срав¬нительно быстро даже для человека, не говоря уже об ЭВМ. Основной це¬лью дан¬ной курсового проекта, как раз и является цель показать, а точнее доказать рациональные ме¬тодики поиска особых путей сетевого графика, которые не только дают возмож¬ность проверки его оптимальности, но и позволяют рационально вы¬полнить его оптимизацию по длительности. Последнее заключается в том, что ес-ли экономист-проектировщик
←предыдущая следующая→
1 2 3 4 5
|
|