Экономико-математические модели и методы


Задачи для самостоятельного решения



страница7/7
Дата06.06.2016
Размер0.62 Mb.
1   2   3   4   5   6   7

Задачи для самостоятельного решения



3.1 3.9. Найти начальное опорное решение методом северо-западного угла

и методом минимального элемента.


3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9

3.10-3.24. По указанным ниже данным о ресурсах ai , потребностях bj и матрицы коэффициентов затрат с cоставить математические модели и решить соответствующие транспортные задачи.
3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24

  1. СЕТЕВЫЕ МОДЕЛИ




  1. Сетевой график комплекса операций и правила его построения

В практике управления большими системами широко применяется метод сетевого планирования и управления (СПУ).

Система СПУ позволяет:


  • формировать план выполнения некоторого комплекса работ, в частности план управления проектом;

  • выявлять трудовые, материальные и денежные ресурсы;

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

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

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

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

Различают следующие операции:



  1. действительная операция – процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов и т. д.);

  2. операция ожидания – процесс, требующий только затрат времени (затвердение бетона, рост растений и т. п.);

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



Правила построения сетевого графика


  1. В сети не должно быть событий (кроме исходного), в которое не входит ни одна дуга.

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

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

  4. Любая пара событий может быть соединена не более чем одной дугой.

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



Рис. 4. Наличие петли в сетевом графике

Пример 6.. Построить укрупненный сетевой график выполнения комплекса операций по реконструкции цеха. Список операций представлен в табл. 4.1.
Таблица 4.1

ОперацияШифр операцииНаименование операцииОпирается на операцииПродолжительность, дниа1(1,2)Подготовительные работы-5а2(1,3)Демонтаж старого оборудования-3а3(2,6)Ремонтные строительно-монтажные работыа1, а230а4(3,4)Подготовка фундамента под новое оборудованиеа116а5(2,4)Подготовка к монтажу нового оборудованияа110а6(2,5)Электротехнические работыа112а7(4,5)Монтаж нового оборудованияа4, а58а8(5,7)Подключение оборудования к электросетиа6, а72а9(7,8)Наладка и технические испытания оборудования а86а10(6,8)Отделочные работыа3, а6, а78а11(8,9)Приемка цеха в эксплуатациюа9, а101



Рис. 5. Сетевой график реконструкции цеха


  1. Расчет временных параметров сетевого графика

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

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

Предшествующий событию путь – это путь от исходного события до данного.

Следующий за событием путь есть путь от данного события до завершающего.

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

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

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

Определим, прежде всего, ожидаемые (ранние) сроки ti свершения событий (i) сетевого графика.



Рис. 6.
Ожидаемый (ранний) срок совершения данного события (j) сетевого графика равен продолжительности максимального пути, предшествующего этому событию. Расчет tj свершения j-го события ведется слева направо, начиная с исходного события и заканчивая событием j. Общая формула для нахождения ожидаемых сроков свершения событий:


;
где – подмножество дуг сети, входящих в событие (j).
Исходное событие означает момент начала выполнения комплекса операций, следовательно, t1 = 0. Событие (2) свершится спустя 2 единицы времени после свершения события (1), т.к. время выполнения операции (1,2) равно 2. Значит, Событию (3) предшествуют два пути и . Значит,

и т. д.

Расчеты приведены в табл. 4.2.

Значения ti , , приписаны соответствующим событиям на рис. 6.

Ожидаемый срок свершения события (7) t7=11 совпадает с критическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь от завершающего события к исходному, можно выделить операции, принадлежащие критическому пути. Критический путь в нашем примере выделен жирной линией. Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению выполнения комплекса операций. Для некритических операций есть резервы времени.

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

;
,

где – подмножество дуг сети, исходящих из события (i).

В нашем примере .

, т. к. из события (5) исходит одна операция.

.

Из события (4) исходят три операции, поэтому



и т. д. (см. табл. 4.2).

На рис. 6 предельные сроки свершения событий указаны в скобках. Для критических событий эти сроки совпадают с ожидаемыми.

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

.

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

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

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

.

Свободный резерв времени операции R показывает, на сколько можно увеличить продолжительность или отсрочить начало выполнения операции (i,j), при условии, что начальное и конечное события свершаются в ожидаемое время:

Частный резерв времени первого вида – это запас времени, которым можно располагать при выполнении операции (i,j) в предположении, что начальное и конечное события свершаются в предельные сроки:



.

Частный резерв времени второго вида – это запас времени, которым можно располагать при выполнении операции (i,j) в предположении, что ее начальное событие свершится в предельное, а конечное – в ожидаемое время. Для некоторых операций интервал времени между предельным сроком свершения начального события и ожидаемым сроком свершения конечного события может быть меньше их продолжительности. В этом случае принимается равным нулю. Определяется частный резерв времени второго вида по формуле:

.

Найдем резервы времени операции (4, 6) сетевого графика (рис. 6):









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

Для примера определим ранний и предельный сроки свершения всех событий, их резервы времени, критический путь. Расчеты поместим в табл. 4.2.
Таблица 4.2

N п/пСроки свершения событийРезерв времени, RiРанний, tiПредельный, 1 02 03 04 15 06 57 0

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

  1. Задачи для самостоятельного решения





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

а)

N Код операцииПродолжительность операции10 – 1 321 – 5 531 – 2 341 – 3452 – 4 364 – 5 273 – 5 585 – 7 495 – 6 5106 – 7 5112 – 7 4127 – 8 5138 – 9 3



б)

N Код операцииПродолжительность операции11 – 2 421 – 3 331 – 4 542 – 5 752 – 61063 – 6 874 – 6 1284 – 7 995 – 8 8106 – 8 10117 – 8 11



  1. Найти ранний и предельный сроки свершения всех операций, их резервы во времени, критический путь.

а)


б)

Список рекомендуемой литературы


  1. Кузнецов Б.Т. Математические методы и модели исследования операций / Б.Т.Кузнецов. – М., 2005.

  2. Костевич П.С. Математическое программирование. – Минск, 2003.

  3. Кузнецов А.В. Математическое программирование. – Минск, 1984.

  4. Пантелеев А.В. Методы оптимизации в примерах и задачах / А.В.Пантелеев, Т.А. Летова– М., 2002.

  5. Количественные методы в экономических исследованиях / [М.В.Грачева и др.]; под общ. ред. М.В.Грачевой – М., 2004.






Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница