Содержание
Введение. 2
1.Постановка задачи. 3
2.Метод решения. 4
3.Язык программирования. 11
4.Описание алгоритма. 12
5.Контрольный пример. 15
6.Описание интерфейса с пользователем. 19
Заключение. 20
Литература. 21
Листингпрограммы… 22
Введение
Сетевой график –необходимый элемент сложного производства, состоящего из нескольких связанных изависящих друг от друга этапов. Выявление критического пути и временныхрезервов производства – основная задача, решаемая построением сетевого графика.Такие задачи могут быть представлены в виде графа и в виде отображающей еготаблицы. Для нахождения критического пути (последовательности этапов работы,определяющих длительность всего проекта и не имеющих резерва по времени)применяются вычислительные методы. Одним из таких методов является табличный методи применяется для данных, представленных в виде таблицы.
Проблема автоматизации расчётасетевого графика является достаточно актуальной и важной. Вычислениекритического пути с помощью ЭВМ поможет в несколько раз ускорить этот процесс,а при больших графиках – во много раз. Поэтому автоматизация расчёта сетевогографика может иметь большую практическую пользу.
1.Постановказадачи
Мы рассматриваем задачу,представленную в виде графа.
/>Рис. 1
Вершины графа – этапыработ.
Рёбра графа – выполнениеработы. Рёбра имеют длину, обозначающую продолжительность работы и направление,обозначающее последовательность выполнение работы.
Требуется найти такойпуть на графе, который бы имел максимальную длину по сравнению со всемивозможными путями для данного графа.
Данные задачи также могутбыть представлены в виде таблицыВиды работ Продолжительность 1-2 2 1-4 1 1-5 4 2-3 3 4-3 5 4-6 3 4-7 1 4-9 3 5-6 2 6-10 5 7-8 6 7-9 2
Целью решения такжеявляется:
· Вычисление времени раннего началаработ каждого вида – минимального срока начала работы, считая от началапроекта.
· Вычисление времени раннего завершенияработ каждого вида – минимального срока завершения работы, считая от началапроекта.
· Вычисление времени позднего началаработ каждого вида – максимального срока начала работы, считая от началапроекта.
· Вычисление времени позднегозавершения работ каждого вида – максимального срока завершения работы, считаяот начала проекта.
· Вычисление полного резерва работкаждого вида – максимального запаса времени на которое можно отсрочить началоработы.
3.Язык программирования
Для написания программыбыл выбран язык VBA по следующимпричинам:
1. Visual Basic for Applications позволяет удобно работать с большимитаблицами, считывая из них данные, производя над ними преобразования и строяновые.
2. Использование VBA под оболочкой Excel позволяет использовать функцииданной оболочки, облегчающие ввод данных и работу с ними.
3. Этот языкпозволяет автоматизировать некоторые этапы написания программы средствамимакрорекордера.
4. Я хорошо знаком сэтим языком и мне удобнее всего будет писать программу именно с помощью VBA.
5. Простота восвоении языка и доступность исходных кодов программы позволит последующимпользователям усовершенствовать её, или изменить под свои требования.
4.Описаниеалгоритма
1. При запуске окна вводаначальных данных пользователю предлагается ввести количество этапов работ:
А) Выполняется проверкана правильность ввода. Количество выражается числом, оно должно быть целым(если число дробное, то происходит усечение дробной части) и не должнопревышать 254.
Б) Если условия вводавыполнены, то происходит проверка на наличие информации в листе, о чёмвыводится сообщение.
В) Строится таблицаисходных данных
2. После прорисовкитаблицы пользователь должен заполнить ее значениями:
А) После подтвержденияпользователем заполнения таблицы :
3. Пользователь переходитк другому рабочему окну, где он имеет возможность активировать расчёткритического пути и сетевого графика, либо перевести единицы времени из одних вдругие (например, дни в часы), если в таблице имеются дробные числа, посколькув конкретной задаче под оболочкой VBA вычисления с использованием дробных чисел дают погрешность.
А) Если пользовательвыбрал перевод единиц времени, то числа в таблице исходных данных преобразуютсяпо выбранной схеме.
Б) Если пользовательвыбрал построение сетевого графика, то строится таблица, имеющая данные овремени раннего и позднего начала работы, раннего и позднего завершения работы,а также резерв по времени для каждого этапа и последовательность этаповкритического пути.
4. Нажав кнопку расчётасетевого графика, пользователь запускает алгоритм поиска критического пути исопутствующих данных, который работает следующим образом:
4.1. В таблицу решениязаносится информация из таблицы исходных данных и подсчитывается количествозаписей (число видов работ).
4.2. Определяютсяначальные этапы. Если в таблице исходных данных столбец не содержит данныедлительности, значит, этим этапом не завершается ни один вид работ, то есть он начальный.
4.3. Для всех начальныхэтапов, найденных по исходной таблице заносятся значения раннего начала работравные 0 и время раннего окончания работ 0+продолжительность вида работ.
4.4. Для каждойзаполненной таким образом строки определяется этап окончания вида работ и егообозначение запоминается. Из всех видов работ, заканчивающихся на такой этап,выявляется вид, имеющий максимальное значение времени раннего окончания работы.Это значение также запоминается. Далее в таблице отыскиваются виды работ, начинающиесяна ранее запомненный этап и для всех записей, удовлетворяющих условию в графувремя раннего начала заносится запомненное максимальное значение временираннего окончания работы. Алгоритм повторяется, пока не останется ни однойпустой строки.
4.5. В таблицерезультатов, где для каждого вида работ определено время раннего начала изавершения, определяется максимальное значение времени раннего окончанияработы, которое является длительностью всего проекта.
4.6. Определяютсяконечные этапы. Если в таблице исходных данных строка не содержит данныедлительности, значит, этим этапом не начинается ни один вид работ, то есть он конечный.
4.7. Для всех конечныхэтапов, найденных по исходной таблице заносятся значения позднего завершенияработ равные длительности проекта и время позднего начала работ, равноеразнице длительности проекта и длительности вида работ. Вычисляется полныйрезерв равный разнице между поздним и ранним временем окончания (начала) работ.
4.8. Для каждойзаполненной таким образом строки определяется этап начала вида работ и егообозначение запоминается. Из всех видов работ, начинающихся на такой этап,выявляется вид, имеющий минимальное значение времени позднего начала работы.Это значение также запоминается. Далее в таблице отыскиваются виды работ,заканчивающиеся на ранее запомненный этап и для всех записей, удовлетворяющихусловию в графу времени позднего завершения заносится запомненное минимальноезначение времени позднего начала работы. Вычисляется полный резерв. Алгоритмповторяется, пока не останется ни одной пустой строки.
4.9. Выделяютсязаписи, имеющие значение полного резерва равное 0. Такие виды работ входят вкритический путь.
4.10. Для отыскания критического пути изпервой встретившейся записи с полным резервом равным нулю берутся значенияначала и завершения вида работ. Для всех последующих записей берётся толькообозначение этапа завершения вида работ. Работоспособность такому алгоритму обеспечиваетструктура расчётной таблицы, где виды работ упорядочены по этапам их начала.Однако если пользователь пронумерует этапы в обратном порядке, может случитьсятак, что какой-нибудь этап встретится в критическом пути два раза, а другой ниразу. Для этого предусмотрен алгоритм поиска повторяющихся значений вкритическом пути. Если повторения обнаружены, то программа строит критическийпуть в обратном порядке. Из последней встретившейся записи с полным резервомравным нулю берутся значения завершения и начала вида работ. Для всехпоследующих записей берётся только обозначение этапа начала вида работ.
5. Результатывычислений выводятся на экран. Пользователь может перевести единицы времени вобратном порядке (п. 3).5.Примеррешения задачи на ЭВМ
Определим критическийпуть на основе данных о связях между этапами работ и длительности выполненияработ.
Пусть задан граф.
/>
На основе данных графастроится таблицаВиды работ
Продол-
житель-
ность Время раннего начала Время раннего конца Время позднего начала Время позднего конца Полный резерв 1-2 2 1-4 1 1-5 4 2-3 3 4-3 5 4-6 3 4-7 1 4-9 3 5-6 2 6-10 5 7-8 6 7-9 2
Сначала вводится числоэтапов работ (в данном примере 10)
Исходя из данных таблицызаполняется электронная таблица исходных данных, где номер строки – этап началаработы, а номер столбца – этап завершения работы.
После нажатия на кнопку«ОК» откроется меню решения
В конкретном примереперевод единиц времени не требуется, но для наглядности можно осуществитьперевод. Допустим имеются данные о длительности в днях, но есть необходимостьпредставить их в часах.