31
2-й шаг. Определяются платежи Qi и Wj из условий Ai+Bj=Cij. Один из
платежей( к примеру A1) полагаем равным 0.
3-й шаг. Считаются псевдостоимости Cij*=Ai+Bj для всех свободных
клеток. Если Cij*<=Cij для всех клеток, то план оптимален. Вычисляем
значение функции L на этом плане и прекращаем исследование.
4-й шаг. Если есть свободная клетка, для которой Cij*>Cij, то улучшается
план, перебрасывая перевозки по циклу этой свободной клетки.
5-й шаг. Происходит возврат к шагу 2 для пересчета платежей нового
опорного плана.
Следующей моделью, которая будет реализована в дипломной работе,
является модель сетевого (или календарного) планирования. Возможность ее
применения обусловливается тем, что логистический цикл состоит из
определенной последовательности работ – начиная от приема заказа и
заканчивая доставкой товара.
Сетевое планирование и управление – это совокупность расчетных
методов, контрольных и организационных мероприятий по планированию и
управлению комплексом работ с помощью сетевого графика. Под комплексом
работ в данном определении понимается всякая задача, для выполнения
которой необходимо совершить достаточно большое количество разнообразных
работ.
Основным понятием сетевого планирования является сетевая модель –
иначе, план выполнения взаимосвязанных работ, заданных в форме сети,
графическое отображение которой называется сетевым графиком. Ключевыми
понятиями сетевой модели являются понятия работы и события.
Термин работа в сетевом планировании имеет несколько значений:
32
- действительная работа, представляющая собой протяженный по
времени процесс и требующая существенных затрат материальных и трудовых
ресурсов;
- ожидание, представляющее собой процесс, требующий только
временных ресурсов, но не требующий материальных и трудовых ресурсов.
- фиктивная работа, представляющая процесс, не требующий затрат
временных и материальных ресурсов. Основной смысл фиктивной работы
состоит в следующем: она показывает, что возможность выполнения
определенной работы зависит от результатов выполнения другой.
Одним из важнейших понятий сетевой модели является понятие пути.
Путь представляет любую последовательность работ, в которой конечное
событие каждой работы совпадает с начальным событием следующей за ней
работы. Полный путь представляет любой путь, начало которого совпадает с
исходным событием сети, а конец – с завершающим. Наиболее
продолжительный полный путь называют критическим.
На стадии управления и контроля над ходом выполнения программы
основное внимание уделяется работам, находящимся на критическом пути или
в силу отставания попавшим на критический путь. Для сокращения
продолжительности проекта необходимо в первую очередь сокращать
продолжительность работ, лежащих на критическом пути.
Еще одним основным понятием сетевой модели является событие.
Различают следующие виды событий:
Ранний (или ожидаемый) срок свершения события определяется
продолжительностью максимального пути, предшествующего этому событию.
Задержка свершения события по отношению к своему раннему сроку не
отразится на сроке свершения завершающего события (а значит, и на сроке
выполнения комплекса работ) то тех пор, пока сумма срока свершения этого
33
события и продолжительности (длины) максимального из последующих за ним
путей не превысит длины критического пути.
Поэтому поздний (или предельный) срок свершения события равен
разности максимального времени наступления последующего за работой
события и времени работы до этого (будущего) события.
Основные параметры сетевой модели продемонстрированы в таблице 2
[28, С. 206]:
Таблица 2
Параметры сетевой модели
Элемент сети
Наименование параметра
Условное обозначение
параметра
Событие i
Ранний срок свершения работы
ТР(i)
Поздний срок свершения работы
ТП(i)
Резерв времени события
R(i)
Работа(i,j)
Продолжительность работы
Т(i,j)
Ранний срок начала работы
ТРН(i,j)
Ранний срок окончания работы
ТРО(i,j)
Поздний срок начала работы
ТПН(i,j)
Поздний срок окончания работы
ТПО(i,j)
Полный резерв времени работы
R(i,j)
К основным задачам сетевой модели относят задачу расчета сроков
выполнения работ.
Для определения резервов времени по событиям сети рассчитывают
наиболее ранние ТР и наиболее поздние ТП сроки свершения событий. Любое
событие не может наступить прежде, чем свершаться все предшествующие ему
события и не будут выполнены все предшествующие работы. Поэтому ранний
(или ожидаемый) срок ТР(i) свершения i-ого события определяется
продолжительностью максимального пути, предшествующего этому событию
(3)[28, С. 207]:
34
ТРН(i,j)=max ТРО(l,i), при i>1, и ТРН(i,j)=0, при i=1,
где (l,i)-работы, предшествующие работе(i,j) (3)
Раннее окончание работы определяется как сумма раннего начала работы
и продолжительности этой работы (4):
ТРО(i,j)=ТРН(i,j)+T(i,j) (4)
Время позднего начала и позднего окончания работ рассчитывается
наоборот: от последнего к исходному событию и рассчитывают в начале время
позднего окончания работ, а затем время позднего начала работ (5-6):
ТПО(i,j)=min(ТПН[k,j])если i<n, и ТПО(i,j)=Ткр, если i=n, где n-общее
число событий, Ткр- критический путь (5)
ТПН(i,j)=ТПО(i,j)-T(i,j) (6)
Таким образом, в рамках сетевой модели моменты начала и окончания
работы тесно связаны с соседними событиями соответствующими
ограничениями. Обозначения, используемые в формулах (3)-(6) объяснены в
таблице 2.
Важнейшим показателем сетевого графика являются резервы времени.
Резервы времени каждого пути показывают, насколько может быть увеличена
продолжительность данного пути без ущерба для наступления завершающего
события. Поскольку каждый некритический путь сетевого графика имеет свой
полный резерв времени, то и каждое событие этого пути имеет свой резерв
времени.
Среди резервов времени работ выделяют четыре разновидности.
Полный резерв времени работы показывает, насколько можно увеличить
время выполнения данной работы при условии, что срок выполнения комплекса
работ не изменится.
35
Полный резерв времени работы равен резерву максимального из путей,
проходящего через данную работу. Этим резервом можно располагать при
выполнении данной работы, если её начальное событие свершится в самый
ранний срок, и можно допустить свершение конечного события в его самый
поздний срок.
Важным свойством полного резерва времени работы является то, что он
принадлежит не только этой работе, но и всем полным путям, проходящим
через неё. При использовании полного резерва времени только для одной
работы резервы времени остальных работ, лежащих на максимальном пути,
проходящем через неё, будут полностью исчерпаны. Резервы времени работ,
лежащих на других (не максимальных по длительности) путях, проходящих
через эту работу, сократятся соответственно на величину использованного
резерва (7) [28, С. 208].
R(i,j)=ТПН(i,j)-ТРН(i,j)=ТПО(i,j)-ТРО(i,j) (7)
Резервы времени работ, находящихся на критическом пути, равны 0.
Таким образом, найдя полные резервы времени, легко по нулевым резервам
проследить критический путь сетевого графика.
Остальные резервы времени работы являются частями её полного
резерва.
Частный резерв времени первого вида есть часть полного резерва
времени, на которую можно увеличить продолжительность работы, не изменив
при этом позднего срока её начального события. Этим резервом можно
располагать при выполнении данной работы в предположении, что её
начальное и конечное события свершаются в свои самые поздние сроки. Его
находят как разность позднего начала данной работы и позднего окончания
предшествующей, если она есть (8) [28, С. 208]:
r1(i,j)=ТПН(i,j),если i=1, и r1(i,j)=ТПН(i,j)-ТПО(i,j),если i>1 (8)
36
Частный резерв времени второго вида, или свободный резерв времени
работы представляет часть полного резерва времени, на которую можно
увеличить продолжительность работы, не изменив при этом раннего срока её
конечного события. Этим резервом можно располагать при выполнении данной
работы в предположении, что её начальное и конечное события свершатся в
свои самые ранние сроки. Он равен разности раннего начала следующей
работы (если она есть) и раннего окончания данной (9):
r2(i,j)= ТРН(j,k)-ТРО(i,j), если j<n, и Ткр-ТРО(i,j) если j=n (9)
Свободным резервом времени можно пользоваться для предотвращения
случайностей, которые могут возникнуть в ходе выполнения работ. Если
планировать выполнение работ по ранним срокам их начала и окончания, то
всегда будет возможность при необходимости перейти на поздние сроки начала
и окончания работ.
Независимый резерв времени работы — часть полного резерва времени,
получаемая для случая, когда все предшествующие работы заканчиваются в
поздние сроки, а все последующие работы начинаются в ранние сроки.
Результаты расчета сетевого графика наглядно отображаются на
ленточной диаграмме Ганта. Диаграмма Ганта- тип стобчатых диаграмм,
который используется для иллюстрации плана, графика работ по какому- либо
проекту. Является одним из методов планирования проектов. Первый формат
ленточной диаграммы был разработан в 1910 году Генри Л.Гантом [25, С. 33].
Диаграмма Ганта представляет собой графическое отображение модели
сетевого планирования. На ней последовательность работ (этапов) привязана к
временной оси абсцисс, а каждый столбик диаграммы показывает
продолжительность отдельно взятой работы. При этом критический путь,
полученный при решении модели сетевого планирования, выделяется другим
цветом, что придает диаграмме Ганта наглядность. Диаграмма Ганта при
проектировании доставки товаров из ЕС дает визуальное представление о
37
продолжительности поставки, а также о возможности сократить время работы
на каком-либо из этапов.
После нахождения критического пути и резервов времени работ и оценки
вероятности выполнения проекта в заданный срок должен быть проведён
всесторонний анализ сетевого графика и приняты меры по его оптимизации.
Этот весьма важный этап в разработке сетевых графиков раскрывает основную
идею сетевого планирования. Он заключается в приведении сетевого графика в
соответствие с заданными сроками и возможностями организации,
разрабатывающей проект. Основным показателем при оптимизации сетевого
графика является коэффициент напряженности работ.
Коэффициентом напряжённости работы называется отношение
продолжительности несовпадающих, но заключённых между одними и теми же
событиями, отрезков пути, одним из которых является путь максимальной
продолжительности, проходящий через данную работу, а другим —
критический путь.
Этот коэффициент может изменяться в пределах от 0 (для работ, у
которых отрезки максимального из путей, не совпадающие с критическим
путём, состоят из фиктивных работ нулевой продолжительности) до 1 (для
работ критического пути).
Вычисленные коэффициенты напряжённости позволяют дополнительно
классифицировать работы по зонам:
-критическая К > 0,8
-подкритическая 0,6 < К < 0,8,
-резервная К < 0,6.
С целью оптимизации календарного плана по критерию общих затрат
необходимо путем проведения расчетов параметров сетевых графиков для
38
различной интенсивности (и времени) операций получить зависимость прямых
затрат от времени (которые убывают), т.е. провести сжатие сетевого графика.
Расчет в формулах. В таблице 3 нам даны [28, С. 209]:
Таблица 3
Время и стоимость работ в нормальном и интенсивном режиме
Вид работы
Нормальный режим
Интенсивный режим
Время t0
Стоимость C0
Время t1
Стоимость C1
(i1,j1)
t0(i1,j1)
C0(i1,j1)
t1(i1,j1)
C1(i1,j1)
…
…
…
…
…
(ik,jk)
t0(ik,jk)
C0(ik,jk)
t1(ik,jk)
C1(ik,jk)
Сжатие необходимо начинать с того вида работы, у которой наблюдается
наименьший угол наклона линии время/стоимость. Поэтому справа от этой
таблицы находится тангенс угла наклона по формуле (10):
????
????
????
????
Для нахождения наименьшего отклонения и получения как можно
большего числа комбинаций между временем и стоимостью работ, выбирается
минимальное значение тангенса угла наклона. По соответствующему виду
работ проводится замена нормального времени выполнения на интенсивное.
Таким образом, когда по всем видам работ соответствующий им тангенс
угла наклона будет равен бесконечности (что означает совпадение времени
интенсивного и нормального выполнения), значит, все операции сжаты до
предела. Затраты на выполнение всего вида работ на этих этапах рассчитывают
по формуле (11):
????
????
????
????
????
????
39
В итоге получают набор взаимосвязанных значений t и С, которые
используют для построения зависимости между стоимостью и
продолжительностью работ.
Рассмотренные экономико-математические модели требуют серьезного
информационного обеспечения. В данной работе практическую реализацию
осуществляют с помощью продуктов компании «Microsoft»:
1) Распространенным, и в то же время необычайно функциональным,
являются электронные таблицы «Microsoft Excel». «Excel» позволяет
реализовать представленные методы и модели следующим образом:
а) при решении транспортной задачи линейного программирования
(именно линейного программирования) существенно упрощает процесс
решения надстройка «Excel» «Поиск решения». Остается только правильно
ввести ограничения и целевую функцию, при этом программа определит, какое
количество груза, и с какого склада необходимо отправить для удовлетворения
всех потребностей; пошагово:
- проверяют, является ли модель задачи сбалансированной. Если
представлена задача с неправильным балансом, то вводим фиктивного
поставщика (потребителя);
- формулируют ограничения, в том числе, ограничения на
неотрицательность переменных;
- в рабочие ячейки листа «Excel» вводят данные стоимости перевозки
единицы товара;
- вводят формулы-ограничения на суммарные потребности в товаре;
- вводят формулы-ограничения на суммарные запасы поставщиков;
- в других ячейках вводят известные значения запасов и потребностей в
товаре;
40
- вводzят формулу СУММПРОИЗВ, где первый массив – стоимость
перевозки единицы товара, а второй – значения транспортных расходов;
- вызывают надстройку «Поиск решения», которая позволяет решить
транспортную задачу линейного программирования. В качестве целевой
функции, стремящейся к минимуму – суммарная стоимость перевозок;
- после введения всех ограничений, программа при нажатии кнопки
«Выполнить» автоматически заполнит таблицу транспортной задачи,
отвечающей минимальному критерию стоимости.
2) Однако, при сетевом планировании искать критический путь в «Excel»
достаточно проблематично и трудоемко. Именно поэтому для календарного
планирования разработана среда «Microsoft Project», позволяющая находить
критический путь и строить диаграмму Ганта автоматически.
Этапы построения диаграммы в среде «MS Project».
В ячейке «Task Name» (имя задачи) вводят имя операции (пути).
В ячейке «Duration» (продолжительность) вводят время работ для
соответствующей операции.
Далее необходимо связать операции друг с другом. Для этого в ячейке
«Preccedors» (предшественник), вводят соответствующую данной задаче
предшествующую операцию по идентификационному номеру. Например, задача
(1,2)- продольная рубка получила идентификационный номер 1, вводят для
задачи (2,4) номер 1 и т. д.
Среда «MS Project» удобна при нахождении критического пути, особенно
для больших проектов. В «MS Project» стоит выбрать операцию «Critical Path»
(критический путь) и критический путь выделится на экране другим цветом.
Нахождение критического пути облегчается и тем, что программа сразу выдает
операции, в него входящие. Черная стрелка в приложении над операциями