Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Экономико-математические модели и методы в решении задач сетевого планирования и управления - файл 1.doc


Лекции - Экономико-математические модели и методы в решении задач сетевого планирования и управления
скачать (494.5 kb.)

Доступные файлы (1):

1.doc495kb.13.12.2011 00:08скачать

содержание

1.doc

  1   2   3   4


ПРАКТИКУМ ПО УЧЕБНОЙ ДИСЦИПЛИНЕ

«МАТЕМАТИЧЕСКИЕ МОДЕЛИ В ТЕОРИИ УПРАВЛЕНИЯ

И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ»
ТЕМА «ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ,

ИСПОЛЬЗУЕМЫЕ ПРИ РЕШЕНИИ КОМПЛЕКСА ЗАДАЧ

СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ»
Домашнее задание № 1

Используя исходные данные, представленные в таблице 1, выполнить следующие виды работ:

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

2. Рассчитать временные параметры сетевого графика на графе и в табличной форме.

3. Выполнить привязку сетевого графика к календарю.

4. Распределить ресурсы в сетевой модели и сформировать расписание выполнения работ сетевого графика, а также построить график загрузки (использования) ресурсов.

5. Оценить эффективность полученных решений.
Таблица 1 - Исходные данные для расчета параметров сетевого графика


Работа, непосредственно предшествующая данной (i-j)-й работе

Работа процесса

(проекта)

Трудоемкость

(продолжительность)

данной работы, рабочий день

Потребность в ресурсе

для выполнения

данной работы, человек

h-i

i-j

Tij

Pij

-

а

7

3

-

б

3

5

а

в

4

2

а

г

8

2

а, б

д

5

1

а, б

е

5

4

в

ж

2

4

г, д

з

6

2

Ежедневно располагаемый фонд ресурса s-го вида равен 6 единицам, то есть S=6 человек



^

Методические рекомендации к выполнению домашнего задания № 1



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

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

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

Отображение процесса разработки, принятия и реализации управленческого решения; экономического процесса; строительства большого объекта; процесса разработки сложной научной проблемы, элементов экономической системы, экономического проекта; процесса выполнения задания (проекта) и т.д. в виде сетевых графов - достаточно распространенный прием моделирования систем такого рода.

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

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

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

Методы СПУ позволяют формировать оптимальные по выбранным критериям планы и осуществлять оптимальное управление.

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

Данная глава содержит компактное изложение основных вопросов, относящихся к построению и анализу детерминированных сетевых моделей.
^ 1 Основные понятия сетевых графов, графиков и моделей

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

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

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

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

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

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

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

Сетевые модели разделяются (классифицируются) по характеру и количеству поставленных целей на одноцелевые и многоцелевые, по степени определенности тех или иных параметров - на детерминированные и стохастические (вероятностные), по количеству учитываемых критериев оптимальности - на однокритериальные и многокритериальные, по виду управляемых ресурсов - на временные, стоимостные и ресурсные (материальные), по количеству сетей, из которых строятся модели, - на односетевые и многосетевые, по степени огрубления структуры объекта исследования - на детализированные и агрегированные, по характеру функционирования - на модели единичного и постоянного действия, по степени формализации и автоматизации - на неавтоматизированные и автоматизированные, по типу объединения работ - на построенные по схеме “И”, по схеме “ИЛИ” и на комбинированные - по схеме “И-ИЛИ”.

^ Основными элементами сетевого графика являются работа (изображается стрелкой - квазивектором), событие (изображается кружком) и путь.

Работа - это любой трудовой процесс, характеризующийся затратами времени и ресурсов (например, сборка узла, изготовление детали, проектирование машины, какого-либо из ее узлов, разработка плана производства и т.п.) или только времени - старение, то есть процесс или действие, которое нужно совершить, чтобы перейти от одного события к другому. Работа на графике изображается сплошной линией со стрелкой (). К этому понятию примыкает понятие “зависимость” или “фиктивная работа”. Оно выражает только связь, зависимость отдельных работ и характеризует тот случай, когда для начала данной работы требуется завершение одной или нескольких работ (непосредственно предшествующих данной), причем эту связь работ нельзя выразить ни через временные, ни через какие-либо другие ресурсные затраты, так как этих затрат нет. На графике эта связь изображается пунктирной линией со стрелкой (  ). Фиктивная работа представляет собой логическую связь между событиями и показывает зависимость начала выполнения какой-либо работы или совокупности работ от результатов выполнения другой или других и выполняется мгновенно.

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

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

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

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

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

^ Код работы определяется как номер ее начального и номер ее конечного события. Номер начального события работы должен быть меньше номера ее конечного события.

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

1 шаг. Просматривается весь сетевой граф и выбирается событие, в которое не входит ни одна работа. Следовательно, это событие является исходным событием сетевого графа и ему присваивается номер 1.

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

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

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

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

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

^ Комплекс задач сетевого планирования и управления включает в себя следующие подкомплексы задач:

- построение сетевого графа, нумерация событий и кодировка его работ;

- расчет временных параметров сетевого графика;

- установление возможности выполнения задания (проекта) в определенный срок, то есть оценка реализуемости проекта в течение фиксированного отрезка времени (директивный срок);

- оптимизация сетевого графика по временным параметрам;

- оптимизация сетевого графика по стоимости работ;

- оптимизация сетевого графика по ресурсам;

- привязка сетевого графика к календарю;

- формирование расписаний выполнения работ сетевого графика (рассматриваемого комплекса работ - проекта);

- формирование графиков загрузки ресурсов для рассматриваемого комплекса работ (проекта);

- анализ состояния процесса в каждый заданный момент времени;

- другие задачи.
^ 2 Построение сетевых моделей и расчет

их основных параметров
Построение сетевой модели предусматривает выполнение следующих четырех этапов:

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

определение перечня (совокупности) работ, входящих в проект, и оценку (прогнозирование, расчет) длительности каждой работы (операции);

установление и анализ отношений очередности работ и формирование сетевого графа, отражающего эти отношения;

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

Экономико-математическая модель задачи СПУ имеет следующий вид:

1. Условные обозначения (исходные данные):

h, i, j, k, m - номера событий СГ;

i - номер начального события данной работы, i=1,2,...,m-1;

j - номер конечного события данной работы, j=2,3,...,m;

m - номер завершающего события СГ;

i-j - данная работа СГ;

h-i - работа, непосредственно предшествующая данной (i-j)-й работе;

j-k - работа, непосредственно следующая за данной (i-j)-й работой;

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

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

^ S - располагаемый фонд ресурса s-го вида;

Pijs - количество единиц ресурса s-го вида, необходимого для выполнения

(i-j)-й работы;

Tk - k-й момент времени;

Tнач.ij, Tок.ij - момент времени соответственно начала и окончания данной (i-j)-й работы;

Pijsk - количество единиц ресурса s-го вида, необходимого для выполнения

(i-j)-й работы в k-й момент времени (если Tнач.ijTkTок.ij, то k Pijsk=Pijs);

Sk - располагаемый в k-й момент времени фонд ресурса s-го вида;

Sост.k - остаток фонда ресурса s-го вида, располагаемого в k-й момент времени;

{A} - множество работ СГ, ожидающих выполнения;

{Ak} - множество работ СГ, ожидающих выполнения в k-й момент времени;

{By} - совокупность работ, принадлежащих множеству работ {Ak};

TРНij, TРОij - соответственно моменты времени самого раннего начала и окончания данной (i-j)-й работы;

TПНij, TПОij - соответственно моменты времени самого позднего начала и окончания данной (i-j)-й работы;

Tкр. - длина критического пути СГ;

r1ij, r2ij - частный резерв времени данной (i-j)-й работы соответственно первого и второго вида;

Rij - полный (общий) резерв времени данной (i-j)-й работы;

T - продолжительность выполнения всего комплекса работ данного сетевого графика;

Tдир. - директивный срок выполнения всего комплекса работ данного сетевого графика.

Пример исходных данных (о составе, взаимосвязи и трудоемкости работ некоторого комплекса) для расчета временных параметров сетевого графика и формирования расписания выполнения его работ приведены в таблице 1.
2. Основные расчетные формулы (для расчета временных параметров сетевого графика):









3. Критерии оптимальности.

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

3.1. Минимизация общего времени выполнения всего комплекса работ:



3.2. Максимизация загрузки ресурсов:



3.3. Равномерность загрузки или потребления ресурсов:



3.4. Минимизация потребности в ресурсах (потребности в располагаемом фонде ресурса s-го вида) при соблюдении директивного срока выполнения всего комплекса работ:



4. Ограничительные условия.

Для выполнения данной работы необходимыми условиями являются:

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



- наличие в каждый k-й момент времени (Tk) для выполняемых работ требуемого количества ресурсов всех видов, а следовательно, в каждый k-й момент времени суммарный расход ресурса s-го вида не может превысить некоторой заданной величины Sk, то есть



Количество работ рассматриваемого комплекса может быть любым (то есть нет ограничения на количество работ сетевого графика).

На рисунке 1 представлен сетевой график, построенный по исходным данным таблицы 1.


  1   2   3   4



Скачать файл (494.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации