ЗЛП. Суть симплексного метода решения задачи.



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

ЗЛП. Суть симплексного метода решения задачи.



Симплекс – выпуклый многоугольник в трехмерном пространстве с N+1 вершиной. С не лежащими в одной гиперплоскости.

Алгоритм решения следующий:

-Определить ведущий столбец

-Определить ведущий элемент

-Определить ведущую строку

-Составить уравнение пересчета матриц

-Выполнить пересчет матриц

-Проверить результаты пересчета матрицы на оптимальность

-Если найденное решение оптимально, то вычисление прекратить и сформулировать ответ. Если найденное решение не оптимально, то перейти к пункту 1.

Признакам оптимальности решения наличие в векторе решения только отрицательных или нулевых значений коэффициентов как для фактических переменных, так и для фиктивных (при решении задачи на поиск максимума).

Столбец канонической задачи ЛП называется правильным если все его элементы = 0

Кроме единственного положительного и равного 1. Вся матрица в канонической задаче ЛП называется правильной если она содержит минимум m - правильных столбцов (где m = числу строк в матрице).

Все правильные столбцы должны содержать 1 в разных строках матрицы. Ответ записывается:

Каждому отрицательному коэффициенту в векторе решений ставится соответствие нулевой коэффициент для соответствующей переменной в ответе. Для каждого нулевого коэффициента в векторе решений (то есть для правильного столбца) ставится в соответствие значения свободного члена (из вектора b) из строки, содержащей 1 в столбце данной переменной. Фиктивные переменные в ответе не учитываются.

Ведущим столбцом может быть назначен любой столбец t матрицы удовлетворяющий одному из условий:

-Первый столбец содержащий положительный элемент в строке (векторе) решения

Определение ведущего элемента матрицы А приводит к самому которкому решению задачи. Так как первые два способа носят формальный характер. Выполняются только для положительных и больших 0 элементах столбца. Критерием останова алгоритма поиска решения будет:

Для поиска максимума целевой функции – все коэффициенты вектора решений или равны 0 или отрицательны. Для поиска минимума целевой функции – все коэффициенты вектора решений или равны нулю или положительны.

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

 

21. Двойственная задача. Интерпретация двойственных задач с экономической точки зрения.

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

Двойственная задача имеет 4 переменные так как прямая содержит 4 ограничения. 3 и 5 ограничение двойственной задачи записанные в виде равенств на переменные X3, X5 в исходной задаче не наложено условие не отрицательности. На переменные Y1, Y3, Y4 наложено условие не отрицательности т.к. по исходной задаче им соответствуют ограничения в виде неравенств.

 

 

19. ЗЛП. Базисные и свободные переменные симплекс-метода, разрешающий элемент. Симплексная таблица.

В симплекс-методе вводится понятие базисных переменных, или базиса. Базисом называется любой набор из m таких переменных, что определитель, составленный из коэффициентов при этих переменных в m-ограничениях, отличен от нуля. Остальные N-m переменных называются небазисными, или свободными переменными. Если принять, что все небазисные переменные равны нулю, и решать систему ограничений относительно базисных переменных, то получим базисное решение.

Разрешающий(ведущий) элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки.

Ведущим столбцом может быть назначен любой столбец t матрицы удовлетворяющий одному из условий:

-Первый столбец содержащий положительный элемент в строке (векторе) решений;

-столбец, содержащий наибольший положительный элемент в строке (векторе) решений;

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

СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к “канонической форме”; последовательное ее преобразование по т. н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции.

 

22. Правила составления двойственных задач.

Правила построения двойственной задачи:

-Упорядочиваем записи исходной задачи. Если целевая функция исходной задачи исследуется на max то ограничения неравенства должны быть вида <=. Выполнение этих условий умножением соответствующих ограничений на1

-Если исходная задача исследуется на max то двойственная исследуется на min при этом вектор образованный из коэффициентов при неизвестных целевой функции исходной задачи совпадает с вектором констант в правых частях системы ограничений двойственной задачи. Коэффициентами при неизвестных целевой функции двойственной задачи является соответствующие правые части системы ограничений исходной задачи.

-Каждой переменной Yi двойственной задачи соответствует i – ое ограничение исходной задачи и переменной Xj прямой задачи соответствует j - ое ограничение двойственной задачи

-Матрица из коэффициентов при неизвестных двойственной задачи образуется транспонированием матрицы А = (aij)m*n , составленной из коэффициентов при неизвестных системы ограничений исходной задачи

-Если на j переменную исходной задачи наложено условие не отрицательности то j ограничения двойственной задачи будет неравенством, в противном случае j ограничение будет равенством. Аналогично связаны между собой ограничения исходной задачи и переменная двойственной.

 

23. Транспортная задача. Общие понятия, определения, математическая формулировка.

Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям.

При решении транспортной задачи необходимо:

-обеспечить всех потребителей ресурсами;

-распределить все произведенные ресурсы;

-переместить ресурсы от производителей к потребителям с наименьшими затратами;

Сбалансированная(закрытая) задача - задача при которой количество произведенного ресурса равно количеству потребленного ресурса.

Допустимое решение - любое решение которое удовлетворяет условиям ... ... .

Опорное решение - решение которое имеет m+n-1 перевозок, отличных от нуля.

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

Для построения опорного плана разработаны три метода:

-метод "северо-заподного угла";

-метод наименьшего элемента;

-метод добротностей;

Для опреденления оптимального плана перевозок разработаны методы:

-распределительный;

-потенциалов;

-дельта-метод;

 

24. Общий алгоритм решения ТЗ. Метод "северо-западного угла"

Общий алгоритм решения ТЗ:

1.Формализация задачи (составление матрицы стоимостей перевозок)

2.Приведение задачи к сбаланированному виду (количество произведенного ресурса равно количеству потребленного ресурса).

3.Построение опорного плана.

4.Построение оптимального плана.

Метод "северо-западного угла"

1.При использовании этого метода опорный план перевозок начинают строить с левого верхнего угла матрицы перевозок по след. алгоритму:

-запрос первого потребителя удовлетворен не полностью, тогда недостающий ресуос первому потребителю добавляют от второго производителя и при необходимлсти от третьего производителя, до тех пор пока потребности первого потребителя не будут полностью обеспечены;

-запрос первого потребителя удовлетворен полностью. Остаток ресурса от первого производителя назначают второму потребителю, а при необходимости третьему и т.д.;

-запрос первого потребителя обеспечен полностью ресурсом первого производителя и есурс первого производителя израсходован полностью. Далее переходят к обеспечению запроса второго потребителя;

2. Затем обеспечивают потребности второго потребителя по образцу первого потребителя. И так далее пока не будут обеспечены запросы всех потребителей.

 

30.Построение остового дерева. Алгоритм Прима.

Алгоритм Прима предназначен для нахождения минимального охватывающего дерева.Минимальное охватывающее дерево- охватывающее дерево минимального веса.Дерево- связный граф без цикла.

Алгоритм:

-Делим все вершины графа на множество оставных (исходная вершина)и множество оставшихся (все вершины, за исключением исходной)

-Исчем ребро, соединяющее множество оставных и множество оставшихся, имеющее наименьший вес

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

 

 

25.ТЗ с нарушенным балансом. Метод минимальных элементов.

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

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

 

26. ТЗ. Метод потенциалов.

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

Метод потенциалов используется для нахождения оптимального решения ТЗ.Решение транспортной задачи будет оптимальным, если найдутся такие числа Ui (i=1..m) и Vj (j=1..n), называемые соответственно потенциалами поставщиков и потребителей, которые будут удовлетворять условиям Ui*+Vj*=Cij, xij*>0,Ui*+Vj*<=Cij,xij*=0.

Алгоритм решения начинается с того, что находится опорный план перевозки, затем этот план проверяетя на оптимальность.Для всех базисных (заполненных) клеток находим потенциалы поставщиков Ui и потребителей Vj по формуле Ui*+Vj*=Cij,xij*>0.Для свободных клеток вычисляются оценки по формуле Cij-(Ui+Vj).Если все оценки положительны или равны нулю, то план является оптимальным.Если хотя бы одна оценка меньше нуля, то строим цикл и выполняем перераспределение ресурсов.Цикл строится к перспективной клетке, в нее ставится знак плюс, остальные знаки чередуются и определяется величина перераспределения груза Q=min(xij).Осуществляется перераспределение груза по циклу на величину Q.Затем повторяем алгоритм.

 

 

27.Применение ИТ EXCEL,для решение ТЗ.

Для решения классической транспортной задачи с помощью программы Ms Excel необходимо задать конкретные значения параметрам исходной задачи.Т.е. необходимо внести значения коэффициентов целевой функции;формулу,которая представляет целевую функцию;значения ограничений и формулу для них и т.д.Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис->Поиск решения…

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1.В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки, которая представляет целевую функцию.

2.Для группы выбрать вариант поиска решения- минимальному или максисальному значению.(в зависимости от условия задачи)

3. В поле с именем "Изменяя ячейки": ввести абсолютный адрес диапазона ячеек со значениями коэффициентов целевой функции.

4.Добавить необходимые ограничения.С этой целью выполнить следующие действия:

· для задания первого ограничения в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· выбрать знак ограничений;

· выбрать значения правой и левой частей ограничения;

5.Добавить последнее ограничение на неотрицательность значений переменных.

6.В дополнительном окне параметров поиска решения следует выбрать отметки Линейная модель и Неотрицательные значения.

 

28.Графовые модели. Основные понятия и определения.

Графом G(V,E) называется совокупность двух множеств - непустого множества V- множества вершин и множества E-двухэлементных подмножеств множества V.

Маршрут- чередующаяся последовательность вершин и ребер графа V0,L1,V1,L2....Lk,Vk, в которой любые два соседних элемента инцидентны.

Дуга - упорядоченная пара вершин графа.(Ei,Ej)

Дуга вида (Ei,Ei) называется петлей.

Ребро- неупорядоченная пара вершин графа.

Два ребра (дуги) наз-ся смежными, если они имеют хотябы одну общую вершину.

Ориентированный граф- граф, связи между вершинами которого заданы дугами.

Неориентированный граф- граф, связи между вершинами которого заданы ребрами.

Смешанный граф- граф, связи между вершинами которого заданы дугами и ребрами.

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

Цепь наз-ся циклом, если начальная вершина совпадает с конечной.

Вершина наз-ся висячей если число ребер, инцидентных ей равно 1, если 0- вершина изолорована.

Степень вершины- кол-во ребер, инцидентных этой вершине.

Полустепень исхода- кол-во дуг, исходящих из вершины Ei.

Полустепень захода- кол-во дуг, входящих в вершину Ei.

Дерево- связный граф без цикла.

Остов- дерево, содержащее все вершины графа.

Минимальное охватывающее дерево- охватывающее дерево минимального веса.

 

31.Построение остового дерева. Алгоритм Краскала.

Алгоритм Краскала предназначен для нахождения мнимального охватывающего дерева.Минимальное охватывающее дерево- охватывающее дерево минимального веса.Дерево- связный граф без цикла.

Вначале текущее множество ребер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех ребер, добавление которых к уже имеющемуся множеству не вызовет появления в нем цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству, когда таких ребер нет- алгоритм завершен.До начала работы алгоритма необходимо отсортировать ребра по весу.

 

29. Графовые модели. Способы задания графа.

Графом G(V,E) называется совокупность двух множеств - непустого множества V- множества вершин и множества E-двухэлементных подмножеств множества V.

Степень вершины- кол-во ребер, инцидентных этой вершине.

Маршрут- чередующаяся последовательность вершин и ребер графа V0,L1,V1,L2....Lk,Vk, в которой любые два соседних элемента инцидентны.

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

Цепь наз-ся циклом, если начальная вершина совпадает с конечной.

Полустепень исхода- кол-во дуг, исходящих из вершины Ei.

Полустепень захода- кол-во дуг, входящих в вершину Ei.

Дерево- связный граф без цикла.

Остов- дерево, содержащее все вершины графа.

Минимальное охватывающее дерево- охватывающее дерево минимального веса.Способы задания графов:

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

Форма дуг несущественна, важен только сам факт соединения вершин. Дуги могут пересекаться, но точки пересечения не являются вершинами графа.

Если дуги имеют направление (ориентацию), отмеченное стрелкой, то такие графы называются ориентированными или орграфами. Дуга в орграфе, имеющая направление от вершины vi к вершине vј , называется выходящейиз вершины vi и заходящей в вершину vj. При этом вершина vi называется началом дуги, а vj – ее концом.

Дуга, выходящая из вершины и входящая в нее, называется петлей.

Дуги орграфа называются параллельными, если они соединяют две одинаковые вершины графа и имеют одно направление.

Дуги орграфа называются противоположными, если они соединяют две одинаковые вершины графа и противоположно направлены.

 

32.Задачи о нахождении кратчайших путей в графе. Алгоритм Дейкстры.

С помощью алгоритма Дейкстры мы ищем минимальное расстояние от одной вершины графа ко всем остальным.

Начинается алгоритм с того, что каждой вершине мы присваиваем метки.Метка вершины, из которой мы ищем расстояние полагается равной нулю, метки остальных вершин- бесконечности.(это отражает, что расстояния от начальной до других вершин пока неизвестно)Все вершины графа помечаются как непосещенные. В метках используются два числа.(первое- номер вершины, из которой пришли в данную, второе- расстояние от начальной вершины до данной).

Если все вершины посещены- алгоритм завершает работу, в противном случае из его непосещенных вершин выбирается вершина U, имеющая минимальную метку.Рассматриваем всевозможные маршруты, в которых U является предпоследним пунктом.(т. е. рассматриваем соседей вершины U).Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки и длине ребра. Если полученная длина меньше, то заменяем в соседней вершине метку.Рассмотрев всех соседей, пометим вершину U как посещенную, повторим шаг.

 

49.Алгоритм выполнения условной оптимизации ,безусловной оптимизации.

Условная оптимизация :в каждой узловой точке известно направление движения и стоимость оставшегося пути.(от пункта Б к пункту А).

Безусловная оптимизация :определение пути от пункта А к пункту Б самым дешевым способом.

 

33.Задачи о нахождении кратчайших путей в графе. Алгоритм Флойда.

Алгоритм Флойда предназначен для нахождения кратчайшего пути между двумя любыми узлами сети.

Алгоритм: определяем начальную матрицу расстояния D0 и матрицу последовательностей узлов S0.Диагональные элементы обеих матриц помечаются знаком минус, показывающим, что эти элементы в вычислениях не учавствуют.

Полагаем k=1.Задаем строку k и столбец k как ведущую строку и ведущий столбец.Затем для всех элементов (за исключением элементов ведущей строки и столбца) находим сумму соответствующих элементов из ведущего столбца и ведущей строки. Если это сумма меньше самого элемента, то заменяем этот элемент на сумму.А в матрице последовательностей узлов заменяем элемент данной позиции на 1.

После реализованных n-шагов алгоритма определение кратчайшего пути выполняется по следующим правилам: расстояние между узлами равно элементу в матрице Dn, промежуточные узлы определяем по матрице Sn.

 

34.Потоки в сетях. Основные понятия и определения.

Транспортной сетью наз-ся пара T(G,C), где G- взвешенный орграф, удовлетворяющий следующим условиям:

а) нет петель

б)сущ. только одна вершина, не имеющая ни одного прообраза- исток

в)сущ. только одна вершина, не имеющая ни одного образа- сток

C- функция пропускных способностей дуг, которая явл-ся положительной вещественной функцией определенной на множестве дуг графа, т. е. каждой дуге V графа поставлено в соответствие положительное число C(V) называемое пропускной способностью дуги V.

Вершина, не имеющая ни одного прообраза наз-ся входом сети или истоком (V0 S).

Вершина, не имеющая ни одного образа наз-ся выходом сети или стоком (U0,T).

В транспортной сети существует один исток и один сток.

Потоком в транспортной сети наз-ся неотрицательная вещественная функция, определенная на множестве дуг и удовлетворяющая следующим условиям:

-ограниченности.Поток по любой дуге сети не превосходит пропускной способности этой дуги.

-сохранение.Суммарный поток, заходящий в любую вершину сети (кроме истока и стока)равен потоку, выходящему из этой вершины.

Дуга сети наз-ся насыщенной, если поток по этой дуге равен пропускной способности этой дуги.

Поток по пути наз-ся полным, если хотябы одна дуга насыщена.

Величина потока- сумма значений этой функции по всем выходным дугам сети.

Выходные дуги сети- дуги, инцидентные стоку.

Разрез- множество дуг, удаление которых разрывает все пути, соединяющие исток и сток.Примеры задач:

-задача об источниках и потребителях

-транспорт и грузоперевозки

-проектирование транспортных маршрутов без перечисления дорог в неузловых пунктах

-разработка структуры тайных организаций

 

43. Алгоритм нумерации событий.

Нумерацию событий рекомендуется выполнять по след. Алгоритму:

1.Определить начальное событие.Это событие А.

2.Условно вычеркнуть работы, выходящие из начального события А. Событиям Б,В и Г, которые имеют только входящие работы , присвоить ранг 1.

3.Условно вычеркиваем работы, выходящие из событий 1-го ранга. Событиям Д и Е присваиваем ранг 2 и т.д. Событиям 3 и Ж – ранг 3, событию И- 4.

4.После назначения ранга событиям выполняется нумерация событий по след. Правилам:

-Собыитя нумеруются слева направо, т.е. от начального события к конечному

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

 

35.Потоки в сетях. Задача о максимальном потоке и минимальном разрезе.

Транспортной сетью наз-ся пара T(G,C), где G- взвешенный орграф, удовлетворяющий следующим условиям:

а) нет петель

б)сущ. только одна вершина, не имеющая ни одного прообраза- исток

в)сущ. только одна вершина, не имеющая ни одного образа- сток

C- функция пропускных способностей дуг, которая явл-ся положительной вещественной функцией определенной на множестве дуг графа, т. е. каждой дуге V графа поставлено в соответствие положительное число C(V) называемое пропускной способностью дуги V.

Вершина, не имеющая ни одного прообраза наз-ся входом сети или истоком (V0 S).

Вершина, не имеющая ни одного образа наз-ся выходом сети или стоком (U0,T).

Разрез- множество дуг, удаление которых разрывает все пути, соединяющие исток и сток.

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

Разрез наз-ся минимальным, если имеет наименьшую пропускную способность.

Отыскание минимального разреза- одна из основных задач анализа транспортных сетей.

 

36.Потоки в сетях. Алгоритм Форда-Фалкерсона.

Теорема Форда-Фалкерсона:в любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

С помощью алгоритма Форда-Фалкерсна мы находим максимальный поток и минимальный разрез транспортной сети.Алгоритм начинается с того, что мы пронумеровываем все вершины произвольным образом.Затем вершинам сети присваиваем целочисленные метки:истоку присваивается метка *, затем вершинам, для которых исток является прообразом присваеваем номер вершины-истока и т. д.,пока не пометим все возможные вершины. Если вершину-сток удалось пометить, то рассматриваем последовательность вершин, пометив которые мы пришли к стоку.Если дуга принадлежит множеству рассмотренных вершин и имеет знак +, то новый поток по этой дуге=старый поток + k,если знак -, то новый поток= старый поток - k.k- минимальный поток дуг, имеющих знак "-".После этого начинаем заново расставлять метки.Если же вершина-сток метки не получила, задача решена

 

37.Потоки в сетях. Задачи с множеством истоков и стоков.

Потоком в транспортной сети наз-ся неотрицательная вещественная функция, определенная на множестве дуг и удовлетворяющая следующим условиям:

-ограниченности.Поток по любой дуге сети не превосходит пропускной способности этой дуги.

-сохранение.Суммарный поток, заходящий в любую вершину сети (кроме истока и стока)равен потоку, выходящему из этой вершины.

Величина потока- сумма значений этой функции по всем выходным дугам сети.

Выходные дуги сети- дуги, инцидентные стоку.

Разрез- множество дуг, удаление которых разрывает все пути, соединяющие исток и сток.

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

Разрез наз-ся минимальным, если имеет наименьшую пропускную способность.

Отыскание минимального разреза- одна из основных задач анализа транспортных сетей.

 

47.Динамическое программированиематематический метод оптимизации, суть которого состоит в отыскании оптимального решения путем выполнения вычислений в несколько этапов (шагов).

 

 

38. Сетевая модель. Основные понятия и определения.

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

1.Событие – фиксируемых момент времени завершения i-ой работы и начало выполнения (i+1)-й работы. На сетевом графике события обозначается кружком с порядковым номером.

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

-Действительная работа, определение дано выше.

-Ожидание – вид работы, который требует для своей реализации только затрат времени: просушка окрашенных изделий, затвердение бетона и т.д.

-Фиктивная работа – логическая связь между событиями, не требующая затрат каких-либо ресурсов, т.е. какая-либо работа не может начаться до тех пор пока, другая работа (или работы) не будет окончена.

3.Путь - непрерывная последовательность событий и работ, которые включаются только 1 раз. Форма пути может быть произвольной. Длина пути рассчитывается как сумма времени выролнения работ.

4.Критический путь – путь, который содержит напряженные работы. Напряженная работа не имеет резервов по времени для своей реализации. Работы, имеющие резервы по времени, называются Некретическими.

5.Исходное событие – откуда вытекает событие.

6.Завершающее событие – на том котором заканчивается работа.

 

39. Сетевая модель. Сферы применения, использования.

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



Последнее изменение этой страницы: 2016-04-23; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.235.179.79 (0.027 с.)