АльфаОмега

база знаний!

Приветствую Вас, Гость | 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) Среди вершин, не имеющих номера, найти такую, в которую либо не входит ни од­
на дуга, либо входят дуги только из уже пронумерованных вершин. Найденная вершина получает следующий свободный номер.

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

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

 




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

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

>Шпаргалки

ПОДЕЛИТЬСЯ