АльфаОмега

база знаний!

Приветствую Вас, Гость | RSS
...
Форма входа
Логин:
Пароль:


1с бухгалтерия [12]Английский язык [6]
Банковское дело [22]Безопасность жизнедеятельности [12]
Биология [3]Бухгалтерское дело [166]
Бухгалтерский учет [129]Информатика [91]
Инновационный менеджмент [12]История экономики [80]
История экономических учений [162]Концепции современного естествознания [54]
Конфликтология [18]Культурология [45]
Линейная алгебра [72]Линейное программирование [7]
Макроэкономика [43]Маркетинг и реклама [68]
Математическая статистика [21]Математический анализ [50]
Менеджмент [141]Микроэкономика [39]
Мировая экономика [85]Моделирование портфеля ценных бумаг [19]
Основы предпринимательства [44]Отечественная история [39]
Политология [27]Правоведение [74]
Прикладные программы [21]Психология и педагогика [159]
Региональная экономика [81]Социология [57]
Теория вероятностей [53]Теория оптимального управления [3]
Управление организацией [35]Физическая культура [42]
Философия [157]Финансовый анализ [99]
Финансы и кредит [236]Численные методы [8]
Эконометрика [15]Экономика предприятия [70]
Экономико математическое моделирование [48]Экономическая география [69]
Экономическая теория [99]Экономическая политика [23]
Юриспруденция [20]Другие предметы [39]

Сроки выполнения работ



Задача о сетевом графике возникает при планировании сроков выполнения комплекса работ. При выполнении сложного проекта - строительстве завода, запуске космического корабля и т. д. - необходимо за наименьшее время выполнить много разных работ. При планировании сроков выполнения комплекса работ будем считать известным, какие работы надо выполнить, и время, необходимое для выполнения каждой работы. Пример . Необходимо выполнить 16 работ. Данные о затратах времени, необходи­мых для выполнения каждой работы, заданы в виде матрицы. Каждая работа может начи­наться только после окончания работ, расположенных выше и левее данной. Надо найти минимальное время выполнения всего комплекса, свободный и полный резерв каждой ра­боты, критический путь и все критические работы.                                                                              
Самый главный вопрос, который студент должен понимать - какую задачу мы решаем? Что означают данные нам числа? Что мы ищем? В данном примере надо запланировать выполнение 16 работ. Будем считать, что они пронумерованы слева направо и сверху вниз. Так время выполнения 8 работы равно 5 (это 4-я работа во втором ряду), а время выполнения 11 работы равно 4 (это 3-я работа в третьем ряду). Что мы еще знаем об этих работах? Есть ограничения на порядок выполнения работ. Что можно сказать, например, о работе 7? Ее время выполнения равно 4, ее нельзя начинать, пока не закончены работа 3 (сосед сверху) и работа 6 (сосед слева). Что мы еще знаем об этой работе? Пока мы ее не закончим, нельзя начинать работу 8 ( сосед справа) и работу 11 (сосед снизу).

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

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

Работу 1 начнем в момент 0. Ее длительность равна 6, поэтому мы закончим ее вы­полнение в момент 6. Работу 2 можно начинать сразу после окончания работы 1. Поэтому самое раннее начало работы 2 равно времени самого раннего окончания работы 1, т.е. 6. Так как время выполнения равно 5, то самое раннее окончание работы 2 равно 6+5=11. Для работы 3 самые ранние сроки выполнения 11 - 18. Работу 4 можно начать после выполне­ния работы 3. Поэтому самые ранние сроки ее выполнения 18-24. Работу 5 можно начать после выполнения работы 1. Поэтому самые ранние сроки ее выполнения 6-11.У работы 6 два предшественника. Ее можно начинать сразу, как закончится работа 2 и работа 5. В дан­ном случае сроки окончания этих работ случайно совпали. Поэтому, самые ранние сроки выполнения работы 6 это 11-13. У работы 7 тоже два предшественника - работы 3 и 6. Ра­бота 3 может закончиться в 18, работа 6 - в 13. Так как должны закончиться обе работы, то из моментов их окончания надо взять максимум. mах(13,18)=18. Это и есть самое раннее время начало работы 7. Поэтому, самые ранние сроки выполнения работы 7 это 18-22. У работы 8 самые ранние сроки 24-29. Аналогично надо подсчитать ранние сроки выполне­ния остальных работ. Результаты удобно записать в виде таблицы.

Ранний срок выполнения работ.    

Мы нашли ранние сроки выполнения каждой работы и, тем самым, минимальное вре­мя выполнения всего комплекса. Данные нам 16 работ можно выполнить за 38 единиц вре­мени и нельзя сделать быстрее.

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

Работу 16 необходимо закончить к 38. Поэтому самый поздний срок ее окончания ра­вен 38. Ее длительность равна 2. Поэтому самый поздний срок начала равен 38 - 2 = 36.

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

Работу 15 необходимо закончить до начала работы 16. Поэтому самый поздний срок ее окончания равен самому позднему сроку начала работы 16, т.е. 36. Самый поздний срок ее начала равен 36-3 =33.

Работу 12 необходимо закончить до начала работы 16. Поэтому самый поздний срок ее окончания равен самому позднему сроку начала работы 16, т.е. 36. Самый поздний срок ее начала равен 36-7 =29.

Без работы 11 не могут начаться работы 12 и 15. Работу 15 надо начать не позднее 33, а работу 12 надо начать не позднее 29. Из этих сроков надо выбрать минимальный. Работу 11 необходимо закончить к 29. Поэтому самый поздний срок окончания равен 29. Самый поздний срок начала равен 29 -4 = 25.

Аналогично надо подсчитать поздние сроки выполнения остальных работ. Результа­ты удобно записать в виде таблицы.

Поздние сроки выполнения работ.

22-28    28-33  33-36 36-38 При этом мы обязательно должны выйти на ноль. У самой первой работы самое позднее время начала должно получиться равным 0. Если у Вас получилось по-другому, то Вы где-то ошиблись.

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

Определим два вида резервов.

Полный резерв- время, на которое можно задержать выполнение работы i без изменения времени окончания всего комплекса работ:

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

Найдем полные резервы для всех работ в нашем примере: Результаты удобно записать в виде таблицы.

Например, для 13 работы (первой в нижнем ряду) ранние сроки 13-19, а поздние сроки 22-28. Мы можем подсчитать полный резерв по срокам начала. Самый ранний 13, а самый поздний 22. Между ними интервал в (22-13) 9единиц времени. Можно подсчитать полный резерв по срокам окончания. Самый ранний 19, а самый поздний 28. Между ними интервал в (28-19) 9 единиц времени. Как и следовало ожидать, результат совпал. При расхождении надо проверять арифметику.

Свободный резерв  - время, на которое можно задержать выполнение i-й работы без изменения самых ранних сроков начала последующих работ: . Здесь минимум берется по всем тем работам к, для которых работа / является предше­ственником.

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

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

Например, для работы 6. Ранние сроки выполнения - 11-13. Без окончания работы 6 не могут начаться работы 7 и 10. Работа 7 не может начаться ранее 18 ин возражает против задержки работы 6. Но работа 10 собирается начинаться именно в 13, поэтому свободный резерв работы 6 равен 0.

Работы, полный резерв которых равен нулю, называются критическими. У этих Ра бот ранние сроки совпадают с поздними. В данном примере критическими работами являются работы 1,2,3,4,8,12,16. Последовательность критических работ образует один или не­сколько критических путей, т.е. последовательностей вершин, соединяющих начало ком­плекса с его окончанием. В рассматриваемом примере критический путь состоит из всех критических работ 1-2-3-4-8-12-16. Если бы нам нужно было бы выполнить только эти 7 работ, образующих критический путь, то на них мы бы затратили то же время, что и на весь. наш комплекс. Мы бы с 0 до 6 выполнили бы работу 1, затем с 6 до 11 работу 2, затем с 11 до 18 работу 3, затем с 18 до 24 работу 4, затем с 24 до 29 работу 8, затем с 29 до 36 работу 12, затем с 36 до 38 работу 16.

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

Условие наличия решения.

Можно ли выполнить комплекс работ, заданный произвольной таблицей или графом' Если, например, у каждой работы есть хотя бы один предшественник, то весь комплекс не­выполним. Мы не можем начать ни одной работы. Если, например, у работы 5 предшественник работа 3, а у работы 3 предшественник работа 5, то весь комплекс невыполним. Мы не можем начать работу 3, пока не закончим работу 5, и не можем начать работу 5, iiok;i не закончим работу 3. Обычно такие ситуации возникают из-за ошибок в начальных данных. Сетевой график не должен содержать ориентированных циклов, т. е. в нем не должно быть такого множества вершин, в котором в каждую последующую  вершину идет ориентиро­ванная дуга из предыдущей.

Такого фрагмента не должно быть в сетевом графике.

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

Как проверить, есть ли в ориентированном графе циклы?

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

Доказательство очевидно.

Для проверки отсутствия циклов и нахождения такой нумерации вершин можно вос­пользоваться следующим алгоритмом:

1) Найти в графе вершину, в которую не входит ни одна дуга. Присвоить ей номер I.

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

Этот шаг повторяется пока это возможно.

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

 




Похожие материалы
Негосударственные пенсионные фонды (НПФ)
Сельское хозяйство России в 2004 году(Статистический обзор)
Этапы трансформация общей региональной экономической структуры России
Сравнительная оценка существующих методик анализа финансового состояния промышленного предприятия
Определение цены и объема производства в условиях олигополии. Индекс Херфиндаля. Роль неценовой конкуренции

Категория: Экономико математическое моделирование | Добавил: irish-lu
Просмотров:1765 | Загрузок: 434 | Рейтинг: 0.0/0
  
Всего комментариев: 0
 
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Меню сайта
Шпаргалки

>Шпаргалки

ПОДЕЛИТЬСЯ