Алгоритм решения задачи минимизации затрат на проект

 

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

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

Особенность реализации алгоритма состоит в том, что количество дуг в сети удваивается и, чтобы различать их, вводится новый индекс k, принимающий значения 1 или 2. Соответственно метка получает четвёртую составляющую: k = 1, 2 . Первая дуга соответствует любой продолжительности работы, кроме минимальной: a_ij < t_ij £ b_ij. Для неё характерен угловой коэффициент с _ij1 = с _ij. Вторая дуга допустима, только если t_ij = a_ij , при этом с _ij2 = ¥. Вводится дополнительное условие мечения: узел j может быть помечен из узла i , если дуга ( ijk )ÎA принадлежит дереву максимальных путей из источника s до узла j, т. е. R_{ч2 ij} = t_рj - t_рi - t_ij = 0.

В качестве исходного на первой итерации принимается нулевой поток. Расчет начинается с t_ij = b_ij . Критерием окончания вычислений является прохождение по сети бесконечного потока. Это означает, что критический путь или пути состоят только из вторых дуг с t_ij = a_ij  и с _ij2 = ¥, т. е. предел сокращения достигнут.

Пример

На рис. 4.6 приведена сетевая модель для решения задачи минимизации затрат на проект. Число дуг в ней уже удвоено. Исходные данные задачи приведены в табл. 4.2.           

                                                    3        

                                                               0, 0

                              10, 29   6, ¥         0, ¥  

     b₁₂ = 2, c₁₂₁ = 8               9, 61                    3, 8   

1   a₁₂ = 1, c₁₂₂ = ¥ 2         8, ¥           5   2, ¥          6    

                               9, 11    3, ¥         0, 0  

                                                               0, ¥ 

                                                    4   

 

Рис. 4.6. Исходная сетевая модель для минимизации затрат на проект

 

                                                                                                                                 Таблица 4.2

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Нормальная стоимость	Стоимость при ускоренной длительности	Угловой коэффициент
1	1	2	2	1	23	31	8
2	2	3	10	6	7	123	29
3	2	4	9	3	51	107	11
4	2	5	9	8	10	71	61
5	3	5	0	0	0	0	0
6	4	5	0	0	0	0	0
7	5	6	3	2	6	14	8

 

Решение начинается с расчета ранних сроков свершения событий (табл. 4.3) и частных резервов второго рода для всех работ (табл. 4.4). Здесь следует помнить, что исходной является нормальная длительность всех работ.

    Таблица 4.3

Событие	1	2	3	4	5	6
Ранний срок свершения	0	2	12	11	12	15

        Таблица 4.4

Работа	1-2	2-3	2-4	2-5	3-5	4-5	5-6
Резерв при к=1	0	0	0	1	0	1	0
Резерв при к=2	1	4	6	2	0	1	1

 

Как видно, критический путь составляют работы нормальной длительности (к =1): 1-2, 2-3, 3-5, 5-6, Т_кр =15, а к дереву максимальных путей относятся все работы (к =1), кроме 2-5 и 4-5, и работа 3-5 (к = 2).

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

                  Таблица 4.5

Событие	1	2	3	4	5	6
Первичная метка	[*,*,*,µ]	[1,+,1,8]	[2,+,1,8]	[2,+,1,8]	[3,+,2,8]	[5,+,1,8]
Повторная метка	[*,*,*,µ]	[ - ]	[ - ]	[ - ]	[ - ]	[ - ]

Из таблицы видно, что на первой итерации поток увеличится на 8 единиц по единственному критическому пути и составит: f₁₂₁ = f₂₃₁ = f₃₅₂ = f₅₆₁ =8. Чтобы убедиться, максимален ли этот поток для первой итерации, повторим процедуру расстановки меток (табл. 4.5). Она показывает, что увеличение потока невозможно, так как дуга 1-2(1) насыщена, а дуга 1-2(2) недопустима для мечения (R₁₂₂ ¹ 0); в минимальный разрез входят дуги: 1-2(1) и 1-2(2).

Далее следует произвести сокращение длительностей работ, для чего:

1) отыскивается величина сокращения d, как наименьшее ненулевое значение R_ijk  (табл.4.4) для работ минимального разреза; здесь d =1;

2) ранние сроки всех непомеченных событий сокращаются на d; здесь это события {2,3,4,5,6};

3) критический путь также сокращается на d; здесь Т_кр = 15 - 1 = 14;

4) длительности работ пересчитываются из условия t_ij = min{t_ij; t_рj - t_рi}; практически изменения могут коснуться только работ минимального разреза; здесь t₁₂ = min{2; 1- 0}=1= а₁₂ .

Сокращение длительностей работ сопровождается приращением затрат на их выполнение, которое следует также отыскать. Поскольку сокращенной оказалась лишь одна работа, D Р⁽¹⁾ = D t₁₂ с₁₂₁ = 1´ 8=8.

Аналогичным образом выполняются все остальные итерации, а ход решения задачи отражается в пяти таблицах (табл. 4.6, 4.7, 4.8, 4.9, 4.10).

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

  Таблица 4.6

Событие	Ранние сроки событий по итерациям
	1	2	3	4	5
1	0	0	0	0	0
2	2	1	1	1	1
3	12	11	11	10	9
4	11	10	10	10	9
5	12	11	11	10	9
6	15	14	13	12	11

  Таблица 4.7

Работа	Резервы работ по итерациям
	1		2		3		4		5
	к=1	к=2	к=1	к=2	к=1	к=2	к=1	к=2	к=1	к=2
1-2	0	1	0	0	0	0	0	0	0	0
2-3	0	4	0	4	0	4	0	3	0	2
2-4	0	6	0	6	0	6	0	6	0	5
2-5	1	2	1	2	1	2	0	1	0	0
3-5	0	0	0	0	0	0	0	0	0	0
4-5	1	1	1	1	1	1	0	0	0	0
5-6	0	1	0	1	0	0	0	0	0	0

 

             Таблица 4.8

Собы-тие	Метки событий по итерациям
	1		2	3		4			5
1	*,*,*,µ	*,*,*,µ	*,*,*,µ	*,*,*,µ	*,*,*,µ	*,*,*,µ	*,*,*,µ	*,*,*,µ	*,*,*,µ
2	1,+,1,8	–	1,+,2,µ	1,+,2,µ	1,+,2,µ	1,+,2,µ	1,+,2,µ	1,+,2,µ	1,+,2,µ
3	2,+,1,8	–	2,+,1,21	2,+,1,21	–	–	–	–	–
4	2,+,1,8	–	2,+,1,11	2,+,1,11	2,+,1,11	2,+,1,11	2,+,1,11	–	–
5	3,+,2,8	–	3,+.2,21	3,+.2,21	–	2,+,1,61	4,+,2,11	–	2,+,2,µ
6	5,+,1,8	–	–	5,+,2,21	–	5,+,2,61	5,+,2,11	–	5,+,2,µ
DV	8		0	21		61	11
V	0+8=8		8	29		90	101
d		1	1		1			1
Tкр		15–1=14	13		12			11
DРS		8	8		29			101
РS		97+8=105	113		142			243

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

              Таблица 4.9

Работа	Дуговые потоки по итерациям
	исходные		после 1-й		после 2-й		после 3-й		в ходе 4-й		после 4-й
	к=1	к=2	к=1	к=2	к=1	к=2	к=1	к=2	к=1	к=2	к=1	к=2
1-2	0	0	8	0	8	0	8	21	8	82	8	93
2-3	0	0	8	0	8	0	29	0	29	0	29	0
2-4	0	0	0	0	0	0	0	0	0	0	11	0
2-5	0	0	0	0	0	0	0	0	61	0	61	0
3-5	0	0	0	8	0	8	0	29	0	29	0	29
4-5	0	0	0	0	0	0	0	0	0	0	0	11
5-6	0	0	8	0	8	0	8	21	8	82	8	93

Таблица 4.10

Работа	Длительности работ по итерациям
	исходные	после 1-й	после 2-й	после 3-й	после 4-й
1-2	2	1	1	1	1
2-3	10	10	10	9	8
2-4	9	9	9	9	8
2-5	9	9	9	9	8
3-5	0	0	0	0	0
4-5	0	0	0	0	0
5-6	3	3	2	2	2

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

 

 

 

Рис. 4.7. График оптимального вложения средств в проект

 

4.5. Задачи для самоконтроля

 

1. На рис. 4.8 показана модель транспортной сети. Около дуг проставлены их пропускные способности. Требуется найти величину максимального потока груза, который можно пропустить по сети, и указать минимальный разрез, лимитирующий увеличение потока. Начальный поток задан: f₁₄ = f₄₅ = f₅₆ = 5.

 

                  7                                                     31                    46              

  1                            4 10                    1              3                              6 18            

     2 6 12                9                   7   16        8        11                       23        

                                    11          5                     14                5       19                 7        

          2              3                   5         2              5      

                 4                  3   6                       9        4               20                                 

 

Рис. 4.8. Исходная модель                         Рис. 4.9. Исходная модель

транспортной сети к задаче 1                  транспортной сети к задаче 2

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

3. Решить задачу 1 с исходными данными, приведенными на рис. 4.10. В качестве исходного принять поток: f₁₂ = f₂₃ = f₃₄ = f₄₅ = 2.

                  9                        4   7        5    

         1

          2        4                   3          1

                    2

                                5        3

Рис. 4.10. Исходная модель транспортной сети к задаче 3

 

4. Составьте задачу размерностью n = 8, k = 16 самостоятельно и решите ее. Учтите, что распределение дуговых потоков в окончательном решении задачи может быть неоднозначным.

5. Исходные данные для решения задачи оптимизации затрат на проект представлены в табл. 4.11÷4.14. Решить задачи и построить «кривую затрат на проект». Стоимости выполнения работ при нормальной длительности считать равными нулю.

                 Таблица 4.11

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Стоимость при ускоренной длительности
1	1	2	3	2	8
2	1	3	5	1	28
3	2	3	9	1	40
4	3	4	2	1	8

 

  Таблица 4.12

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Стоимость при ускоренной длительности
1	1	2	6	5	45
2	1	3	6	2	124
3	2	3	0	0	0
4	3	4	4	2	20
5	3	5	9	5	192
6	4	5	3	1	32
7	5	6	8	7	48

 

 

Таблица 4.13

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Стоимость при ускоренной длительности
1	1	2	8	4	136
2	1	3	7	3	48
3	2	3	0	0	0
4	1	4	8	6	6
5	3	5	12	4	320
6	4	5	8	5	9

 

Таблица 4.14

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Стоимость при ускоренной длительности
1	1	2	8	4	128
2	1	3	7	5	24
3	1	4	5	3	20
4	2	4	0	0	0
5	3	4	3	1	6
6	3	5	11	10	8
7	4	5	12	9	24

 

9. Построить «кривую затрат на проект» по данным табл. 4.15 – 4.16.

 

Таблица 4.15

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Нормальная стоимость	Стоимость при ускоренной длительности
1	1	2	5	2	42	45
2	1	5	7	4	27	30
3	2	3	4	2	17	21
4	2	4	4	1	38	41
5	2	5	5	2	10	25
6	3	5	0	0	0	0
7	4	5	0	0	0	0
8	5	6	6	4	35	39
9	6	7	7	3	11	19

 

Таблица 4.16

№ п/п	Начальное событие	Конечное событие	Нормальная длительность	Ускоренная длительность	Нормальная стоимость	Стоимость при ускоренной длительности
1	1	2	6	3	12	48
2	1	3	4	1	7	79
3	1	4	3	2	19	31
4	1	5	8	3	57	252
5	2	3	0	0	0	0
6	3	6	10	5	56	376
7	4	5	0	0	0	0
8	5	6	11	8	105	312
9	6	7	12	10	71	273
10	7	8	30	20	251	1261

 

 

 

Тема 5. СЕТЕВОЙ  АНАЛИЗ  С  ИСПОЛЬЗОВАНИЕМ ПРОГРАММНОГО  ПАКЕТА Win QSB

5.1. Общая характеристика пакета Win QSB

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: