Методические указания (стр. 4 )

Для сетевого графика, изображенного на рис. 4,  найти оптимальные значения  продолжительностей работ yij при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и продолжительности проекта T0 =15.

  Сетевой график для примера 5.

  Рис.4.

  Таблица 8.

Работа	Lij	Uij	aij
(0,1)	2	8	1
(0,2)	5	10	8
(1,2)	1	4	6
(1,3)	4	8	7
(2,3)	6	8	5

Полагая yij=Lij, находим Tнкр. При заданных значениях продолжительностей работ Tнкр=11. Так как T0 >Tнкр,  то задача разрешима. При yij= Uij, величины критического и предкритического путей равны  Tвкр =20 и Tпкр =18 соответственно. Это означает, что T0<Tпкр  и нельзя уменьшить время исполнения проекта только за счет сокращения продолжительности работ, лежащих на критическом пути. Таким образом, для определения продолжительности работ необходимо решить задачу (5), которая для данного примера при t0=0 имеет вид:

y0,1+8y0,2+6y1,2+7y1,3+5y2,3→ max

y0,1-t1  ≤0 

y0,2-t2  ≤0

y1,2+t1-t2≤0  (7)

y1,3+t1-t3≤0

y2,3+t1-t3≤0

  t3≤15

2≤y0,1≤8

5≤y0,2≤10

1≤y1,2≤4

4≤y1,3≤8

6≤y2,3≤8.

Сформулированная задача имеет слишком большую для ручного счета размерность (число ограничений m=16, число  переменных n=8,  а после приведения задачи к каноническому виду возрастет до n=29). Поэтому для решения задачи рекомендуем воспользоваться программой SIMPLEX, разработанной на кафедре исследования операций и предназначенной для решения задач линейного программирования. Описание программы SIMPLEX и пример ее использования  смотрите в приложении 1.  ●

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

Tкр=tn-t0  → min

  ti, yij

ti - tj +yij≤0  для всех (i, j)∈S,

  (8) 

Σ  (bij-aijyij) ≤ C0

(i, j)∈S 

Lij ≤ yij ≤ Uij для всех  (i, j)∈S.

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

Утверждение 5. Пусть Сн – затраты на выполнение проекта при yij=Uij.  Задача  (8) разрешима тогда и только тогда, когда  С 0≥Cн.  ●

       Задача (8) эквивалентна задаче линейного программирования  (9):

Tкр=tn-t0  → min

  ti, yij

  ti +yij  ≤tj  для всех (i, j)∈S,

  (9) 

  Σ  aijyij ≥ D0,  где D0=  Σ  bij - C0,

(i, j)∈S  (i, j)∈S

Lij ≤ yij ≤ Uij для всех  (i, j)∈S.

Задачу (9) как и задачу (4) можно решить симплекс-методом. Для этого  можно воспользоваться программой SIMPLEX. 

Пример 6.

Для сетевого графика изображенного на рис. 2  найти оптимальные значения  продолжительностей работ yij, минимизирующих время выполнения проекта в целом при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и  D0 =201.

       Задача (9)  для данного примера при t0=0 имеет вид:

       t3→ min

y0,1-t1  ≤0 

y0,2-t2  ≤0

y1,2+t1-t2≤0

y1,3+t1-t3≤0  (10)

y2,3+t1-t3≤0

y0,1+8y0,2+6y1,2+7y1,3+5y2,3≥201

2≤y0,1≤8

5≤y0,2≤10

1≤y1,2≤4

4≤y1,3≤8

6≤y2,3≤8.

Входной файл для программы SIMPLEX с информацией о данной задаче проведен в приложении 2. В результате работы программы было получено следующее оптимальное решение  y0,1=6, y0,2=10, y1,2=4, y1,3=8, y2,3=7,  t 1=6, t2=10, Tкр=t 3=17.

Индивидуальные задания

В соответствии с номером индивидуального задания (см. таблицу 9) решить задачу  А:

  Σ  aijyij→ max

  (i, j)∈S  ti, yij

  ti  - tj+yij ≤ 0 для всех (i, j)∈S, 

  - t0+tn  ≤T0,

  Lij ≤ yij ≤ Uij для всех  (i, j)∈S,

или задачу  Б:

  Tкр=tn-t0  → min

  ti, yij

  ti +yij - tj ≤0 для всех (i, j)∈S, 

  Σ  aijyij ≥ D0

  (i, j)∈S

  Lij≤yij≤Uij для всех  (i, j)∈S.

Необходимые исходные данные взять из таблиц 10-12. Для  оптимальных продолжительностей работ yij, найденных в результате решения задачи, определить Ткр, λjр, λiп, rijп, rijс, rijн, используя метод критического пути. 

  Таблица 9.

Номерзада- ния	Номертаб- лицы	Номервари- анта	Зада -ча	Номерзада- ния	Номертаб- лицы	Номервари- анта	Зада -ча
1	10	1	А	13	11	1	Б
2	10	2	А	14	11	2	Б
3	10	3	А	15	11	3	Б
4	10	4	А	16	11	4	Б
5	10	1	Б	17	12	1	А
6	10	2	Б	18	12	2	А
7	10	3	Б	19	12	3	А
8	10	4	Б	20	12	4	А
9	11	1	А	21	12	1	Б
10	11	2	А	22	12	2	Б
11	11	3	А	23	12	3	Б
12	11	4	А	24	12	4	Б

  Таблица 10.

Ра- бо- та	Вариант 1	Вариант 2	Вариант 3	Вариант 4
aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij
0,1	5	5	13	4	4	14	3	6	15	5	8	10
0,2	3	3	14	2	6	15	8	9	14	1	7	18
1,2	2	5	7	3	8	10	9	2	6	9	3	6
1,3	4	1	12	6	6	15	6	7	19	2	7	13
2,3	8	1	3	5	11	12	7	3	7	6	3	12
2,4	7	6	10	8	5	16	7	11	17	4	5	10
3,5	8	9	12	7	9	17	4	13	20	7	9	16
4,5	9	4	13	9	6	10	5	12	15	5	7	14
T0	33	40	40	41
D0	392	573	530	416

  Таблица 11.

Ра- бо- та	Вариант 1	Вариант 2	Вариант 3	Вариант 4
aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij
0,1	18	14	20	7	8	16	4	7	15	5	4	7
0,2	27	15	18	6	3	19	8	9	13	4	2	12
1,3	16	10	23	3	8	20	5	5	13	7	3	8
2,3	8	5	15	2	4	7	9	3	12	6	2	6
2,4	9	12	16	5	5	22	9	7	12	2	4	11
3,4	12	5	12	7	2	4	2	3	6	9	4	8
3,5	18	7	29	9	9	19	7	7	18	1	2	9
4,5	14	10	15	8	4	20	6	8	10	5	6	11
T0	50	51	35	23
D0	2158	666	590	321

  Таблица 12.