II. Пример.

Для решения транспортной задачи используют распределительный метод, реализуемый на основе алгоритма:

1. Формирование таблицы исходных данных в виде

Таблица 1

	В1	В2	В3	В4	В5	Наличие
А1
А2
А3
Потребность

 

А1, А2, А3 - пункты отправления груза, n = 3.

B1, B2, B3, B4, B5 - пункты назначения груза, m = 5.

В столбе "Наличие" - какое количесвто груза в каждом пункте отправления А1, А2, А3.

В строке "Потребность" - потребности в этом грузе каждого пункта назначения.

Модель задачи "Закрытая", так как суммы потребностей и возможностей (наличия) равны 1600.

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

2. Аналитическая форма модели имеет вид

(6)

 

х₁₁ + х₁₂ + х₁₃ + х₁₄ + х₁₅ = 300

х₂₁ + х₂₂ + х₂₃ + х₂₄ + х₂₅ = 400 (7)

х₃₁ + х₃₂ + х₃₃ + х₃₄ + х₃₅ = 900

 

х₁₁ + х₂₁ + х₃₁ = 250

х₁₂ + х₂₂ + х₃₂ = 300

х₁₃ + х₂₃ + х₃₃ = 350 (8)

х₁₄ + х₂₄ + х₃₄ = 500

х₁₅ + х₂₅ + х₃₅ = 200

 

 

3. Выполнение правила "Северо-Западного угла": Распределение груза начинается с левого верхнего угла и заканчивается правым нижним углом исходной (транспортной) таблицы.

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

- количество компонент не должно превосходить числа n + m - 1,

- должны соблюдаться ограничения (2) и (3).

3.2 Осуществление распределения груза между пунктами отправления и назначения:

- из А1 и В1 отправляется 250 единиц груза, то есть потребность В1 полностью удовлетворена,

- остаток груза в А1 (50 единиц) направляется в В2 и для полного удовлетворения его потребности из А2 отправляется 250 единиц груза из имеемых 400 (остаток в А2 150 единиц),

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

 

1 2 3 4 5 Таблица 2.

		В1	В2	В3	В4	В5	Наличие
	А1	2 250	4 50
	А2		6 250	3 150
	А3			2 200	1 500	10 200
	Потребность

 

3.3 Получение плана перевозок путем подсчета затрат на его реализацию:

- перемножение транспортных тарифов (верхний левый угол таблицы на объем перевозок

500 200 450

1500 400

500 2000

- найти сумму

Z = 500 + 200 + 1500 + 450 + 400 + 500 + 2000 = 5550

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

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

Таблица 3.

	В1	В2	В3	В4	В5	Наличие
А1		4 250			9 50
А2	1 250				4 150
А3		3 50	2 350	1 500
Потребность

 

4.2 Определение суммы

Z = 250 + 1000 + 150 + 700 + 500 + 450 + 600 = 3650 - это базисное решение (базисный план)

5 Проверка базисного решения на оптимальность, для чего вводятся два понятия:

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

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

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

5.2 Построение циклов пустых клеток для табл. 2, осуществляя движение против движения часовой стрелки (можно по движению)

- в табл. 2 восемь сводобных клеток с индексами (1,3), (1,4), (1,5), (2,1), (2,4) (2,5), (3,1), (3,2),

- циклы пустых клеток:

1.

2.

3.

4.

5.

6.

7.

8.

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

5.2. Определение сумм тарифов стоящих в клетках циклов со знаком "+" и знаком "-":

- со знаком "+" (5+6); (7+6+3); (9+6+2+10); (1+4); (5+2); (4+2+10); (6+3+1); (3+6)

- со знаком "-" (4+3); (4+3+1); (4+3+1); (6+2); (3+1); (3+1); (2+6+2); (2+6)

5.3. Определение разностей

V_1,3 = (5+6) - (4+3) = 4

V_1,4 = (7+6+3) - (4+3+1) = 16 - 8 = 8

V_1,5 = (9+6+2+10) - (4+3+1) = 19

V_2,1 = (1+4) - (6+2) = -3

V_2,4 = (5+2) - (3+1) = 7 - 4 = 3

V_2,5 = (4+2+10) - (3+1) = 16 - 4 = 12

V_3,1 = (6+3+1) - (2+6+2) = 10 - 10 = 0

V_3,2 = (3+6) - (2+6) = 9 - 8 = 1

Так как среди V_ij есть отрицательная V_2,1 = -3, то исходный план перевозок может быть улучшен.

6. Улучшение исходного плана:

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

- так как в 1,1 и 2,2 одинаковое количество груза по 250 единиц, то в свободную клетку 2,1 помещается 250 единиц груза;

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

то есть в клетке 1,2 будет 300 единиц груза, а клетки 1,1 и 2,2 окажутся пустыми;

- выполнение п.5 - проверка оптимальности нового плана

	В1	В2	В3	В4	В5	Наличие
А1		4 300
А2	1 250		3 150
А3			2 200	1 500	10 200
Потребность

 

путем подсчета оценок свободных клеток V_ij ;

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

 

 

Пример 5.

Сетевое планирование.

I.Пусть есть конечное множество X = {x_i}, x_i Î Х. Тогда можно получить граф G = {X, Г), где Г - закон соответствия множества Х графу G. Если X = {А, В, С, D, E) и ГА = {B, C, D}, ГB = {B}, ГC = {B, D, E}, ГD = {A, C} и ГЕ = О, то можно дать графическое и табличное представления графа

 

 

Основные понятия и определения:

Вершиной - графа называется элемент множества, образующего граф.

Дугой графа - ориентированная пара вершин графа.

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

в другую.

Контуром - путь, начальная вершина которого совпадает с конечной.

Петля - дуга, начало и конец которой совпадают.

Ребром - неориентированная дуга, т. е. дуга, у которой не указано направление движения.

Цепь - сцепленная последовательность ребер или дуг.

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

Предок вершины - вершина, из которой выходит дуга, входящая в данную вершину.

Потомок вершины - вершина, в которую входит дуга, исходящая из данной вершины.

Граф G - множество вершин V, соединенных множеством ребер R, то есть G={V, R}.

Ориентированный граф (орграф) G - множество вершин V, соединенных множеством дуг D, то есть G={V, D}.

II.Для связного графа без контуров решается задача декомпозиции его вершин на слои так, чтобы:

1). все элементы (вершины) данного слоя не имели предков в предыдущем слое, а элементы последнего слоя - потомков;

2). порядок вершин внутри одного и того же слоя безразличен.

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

Пусть имеется орграф без контуров вида (Рис.1):

	1. Вершина А не имеет предков - она образует 1-й слой. Вершину вычеркивают вместе с дугами, которые из неё выходят, и получают новый орграф вида Рис.2.
	3. Вершина G не имеет предков, то есть образует 3-й слой. Вершину G вычеркивают вместе с исходящими из неё дугами и получают новый орграф вида Рис.4

	2. На полученном орграфе вершины C, D, B не имеют предков, то есть они образуют 2-й слой. Вершины C, D, B вычеркивают вместе с дугами, изходящими из них и получают новый орграф вида Рис.3
	3. Вершина G не имеет предков, то есть образует 3-й слой. Вершину G вычеркивают вместе с исходящими из неё дугами и получают новый орграф вида Рис.4
		4. Вершины E, F не имеет предков, то есть образуют 4-й слой. Вершины E, F вычеркивают вместе с исходящими из них дугами и получают новый орграф вида Рис.5

	5. Вершины H, L не имеют предков, то есть образуют 5-й слой. Вершины H, L вычеркивают вместе с исходящими из них дугами и получатют новый орграф в виде Рис. 6
	6. Вершина К не имеет предков, то есть образует 6-й слой. Вершину К вычеркивают вместе с исходящей из неё дугой и остается вершина, не имеющая предков, то есть образующая 7-й слой. Рис. 7 - последний, так как у вершины М нет потоков.

 

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

 

 

С E H

А D G F L K M

B

 

Слои 1 2 3 4 5 6 7

Рис.8

 

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

Ход выполнения проекта иллюстрируют сетевым графиком, представляющим собой взвешенный орграф, в котором вершины - это события от Е₁ до Е_n, которые должны возникать по мере осуществления проекта, а дуги - это переходы от одного события Е_i к другому E_j, то есть процессы выполнения действий P_ij .Дугам приписывают продолжительности ваыполнения соответствующих действий (часы, дни, недели, месяцы и т.п.) - этим определяется взвешенность орграфа (сетевого графика осуществления проекта).

 

 

		На Рис.9 представлен фрагмент сетевого графика, который соответствует части проекта строительства объекта. Событие Е1 - "начало выполнения проекта". Событие Еn - "окончание выполнения проекта".

 

 

Рис.9

 

Например, событие Е8 - "начало закладки фундамента", а действия, предшествующие этому событию: (Р4,8) - "рытье котлована под фундамент" и (Р6,8) - "подвозка железнодетонных блоков для фундамента". Продолжительность Р4,8 10 временных единиц, а Р6,8 – пять.   .

 

 

Из сетевого графика проекта (Рис.10) видно:

1) от события Е₁ к событию Е_n можно пройти различными путями;

2) наступление каждого последующего события может произойти только тогда, когда будет завершено самое продолжительное действие, обуславливающее его наступление;

3) самый длинный путь в сетевом графике определяет кратчайшие сроки осуществления проекта - это критический путь;

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

 

IV.Пусть в результате декомпозиции полного сетевого графика на слои выделен некоторый k-й слои, взвешенный орграф которого представлен на Рис.10.

 

 

Рис. 10

 

Алгоритм определения времени насатупления событий Е₂…Е_12:

1. Событию Е₁ приписывается t₁ = 0.

2. Для каждой вершины Е₂…Е₁₂ рассматриваются дуги, которые из неё выходят.

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

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

Пример:

1.Из Е₁ выходят три дуги: Р_1,2 с весом 8, Р_1,3 с весом 13 и Р_1,4 с весом 9. Так как для Е₁ принято t₁ = 0, то 0+8=8, 0+13=13, 0+9=9 и, следовательно, событию Е₃ приписывается t₃ = 13, а дуга Р_1,3 входит в критический путь.

1. Из Е₃ входят четыре дуги: Р_3,4, Р_3,8, Р_3,9 и Р_3,6 , но Е₃ непосредственно связано с Е₄, следовательно, в критический путь входит дуга Р_3,4 с весом 7, а время наступления события Е₄ равно t₄ = 13+7=20, кроме того Р_1,3+Р_3,4 = 20, Р_3,8 = 6, Р_3,9 = 9 и Р_3,6 = 12, то есть выбирается Р_1,3 + Р_3,4 =20.

2. Из Е₄ выходят три дуги Р_4,7 с весом 8, Р_4,10 с весом 6 и Р_4,8 с весом 9. Так как t₄ = 20, то 20+8=28, 20+6=26, 20+9=29 и, следовательно, событию Е₈ приписывается t₈=29, а дуга Р_4,8 входит в критический путь.

3. Из Е₈ выходят три дуги Р_8,7 с весом 8, Р_8,10 с весом 13 и Р_8,11 с весом. Так как t₈=29, то 29+8=37, 29+13=42, 29+5=34 и, следовательно, событию Е₁₀ приписывается t₁₀=42, а дуга Р_8,10 входит в критический путь.

4. Из Е₁₀ выходят две дуги Р_10,11 с весом 6 и Р_10,12 с весом 17, но Е₁₀ непосредственно связано с Е₁₁, следовательно, в критический путь входит дуга Р_10,11 с весом 6, а время наступления события Е₁₁ равно t₁₁=42+6=48, кроме того Р_10,11+Р_11,12=19, а Р_10,12=17, то есть выбирается Р_10,11+Р_11,12=19.

5. Из Е₁₁выходит только одна дуга Р_11,12 с весом 13, она и входит в критический путь.

Следовательно, проект может быть реализован, то есть наступят все 12 событий, за 61 единицу времени. Действия, соответствующие дугам Р_1,3, Р_3,4, Р_4,8, Р_8,10, Р_10,11, Р_11,12, составляют критический путь : Е₁, Е₃, Е₄, Е₈, Е₁₀, Е₁₁, Е₁₂.

V. Следует обозначить t_i - ранний срок (ожидаемое время) наступления события Е_i. a t^*_i - предельный срок (предельное время) наступления события Е_i , превышение которого приведет к увеличению времени реализации всего проекта. При этом, следует учесть, что для критических событийц (Е₁, Е₃, Е₄, Е₈, Е₁₀, Е₁₁, Е₁₂ на Рис.10) должно выполняться условие t^*_i = t_i, так как такое событие не допускает никакого запаздывания в сроках его наступления, то есть критические действия (Р_1,3, Р_3,4, Р_4,8, Р_8,10, Р_10,11, Р_11,12 на Рис.10) не допускают никакой зедержки в их выполнении.

Резервным интервалом события Е_i (интервалом свободы события) [t_i. t^*_i] называют интервал времени, в течении которого может наступить событие Е_i без изменения общего времени реализации проекта t_n . Определение резервных интервалов событий осуществляется по сетевому графику (Рис.10), идя от конечного события Е₁₂, то есть снизу вверх.

Пример:

1. Наступление события Е₇ отделено от наступления события Е₁₀ действием длительностью 4 единицы времени, то есть действие Р_7,10 может начатся за 4 единицы времени до наступления события Е₁₀. Следовательно, событие Е₇ должно произойти в интервале [37, 42-4=38].

2. Наступление события Е₉ отдельно от наступления события Е₁₁ на 5 единиц времени и поэтому событие Е₉ должно прроизойти в интервале [33, 48-5=43].

3.Событие Е₆ отделяет от события Е₉ действие Р_6,9, выполняемое за 8 единиц времени, от события Е₈ - 3 единицы времени, от события Е₇ - 5 единиц времени. Производится сравнение 33-8=25, 29-3=26, 37-5=32. Наименьшая из сравниваемых величин и есть верхняя граница интервала [23, 25].

4. Событие Е₅ отделяется от события Е₉ три единицы времени, то есть резервный интервал для события Е₅ равен [17, 33-3=30].

5. Событие Е₂ отделяет от Е₅ и Е₆ соответственно 9 и 6 единиц времени, тогда 17-8=9, 23-6=17 и, выбирая наименьшее значение, получают резервный интервал для Е₂ равный [8, 9].

Следовательно, моменты наступления событий Е₂, Е₅, Е₆, Е₇, Е₉ могут быть в следующих интервалах:

Е₁: 0,Е₂: [8, 9], Е₃: 13, Е₄:20, Е₅: [17, 30], Е₆: [23, 25],

Е₇: [37, 38], Е₈:29, Е₉: [33, 43], Е₁₀:42, Е₁₁48, Е₁₂:61,

а на критическом пути интервалы сводятся к точечным моментам времени.

VI.Для каждого действия Р_ij необходимо определить какая задержка модет быть допущена при его выполнении без того чтобы это привело к нарушению срока наступления события Е_j. Для каждого действия существует три резерва времени:

1) свободный резерв времени - это возможная отсрочка начала выполнения действия, обозначается R1_ij, то есть если t_i и t_j - ожидаемые сроки наступления событий Еi и Еj, между которыми происходит действие Р_ij длительнотью t_ij , то

R1_ij = t_j - t_i - t_ij;

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

2) полный резерв времени действия Р_ij определяется по формуле

R2_ij =t^*_j - t_i - t_ij;

3) независимый резерв времени действия Р_ij определяется по формуле

R3_ij = t_j - t^*_i - t_ij;

или, чтобы не получать отрицательныхз значений R3_ij = max (0, t_j - t^*_i - t_ij).

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

Существенное различие между резервным интервалом события Еi и свободным или полным резервом действия Р_ij состоит в том, что:

- резервный интервал события - это запаздывание, которое может быть допущено в наступлении события Еi без изменения фиксированных сроков наступления критических событий и, в частности, конечного, то есть без изменения t_n,

- свободный резерв действия - это отсрочка начала выполнения действия Р_ij без изменения ожидаемого срока наступления события Еj, а полный резерв действия - это максимально допустимая отсрочка начала выполнения действия Р_ij .

Пример:

1. В предыдущем примере определено, что интервал свободы события Е₆ есть [23, 25]. Тогда свободный резерв действия Р_6,9 равен

R1_6.9 = t₉ - t₆ - t_6.9 = 33 - 23 - 8 = 2 единицы времени.

Следовательно, действие Р_6,9 может начаться в момент 23+2=25 без изменения времени (срока) наступления события Е₉, который равен t₉ = 33 единицы времени.

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

2. Полный резерв действия Р_6,9 равен

R2_6.9 = t^*₉ - t₆ - t_6,9 = 43 - 23 - 8 = 12

 

Следовательно, действие Р_6,9 может начаться в момент 23+12=35, не вызывая задержку в реализации проекта.

3. Независимый резерв действия Р_6,9 равен

R3_6.9 = t₉ - t ^*₆ - t_6,9 = 33 - 25 - 8 = 0.

 

 

Пример 6.