Планирование проектирования АСУ

1. ПЛАНИРОВАНИЕ ПРОЕКТИРОВАНИЯ АСУ

Лекция 10

2. Содержательная постановка задачи

Задано:
Множество подсистем АСУ, которые следует
разработать
Множество исполнителей, для каждого из
которых известны время и стоимость
разработки каждой подсистемы АСУ.
Время Т, выделенное на создание эскизного
проекта.
Средства, выделенные разработчику на
создание проекта.
Цель: минимизировать время разработки либо
затраты на создание проекта.

3. Обозначения и определения

Х – множество подсистем.
У – множество исполнителей.
Z(i,j) – булева переменная, равная единице,
если i-й исполнитель проектирует j-ю
подсистему, и равная нулю в противном случае.
t(i,j) – прогнозируемое время проектирования iм исполнителем j-й подсистемы.
с(i,j) – прогнозируемая стоимость
проектирования i-м исполнителем j-й
подсистемы.
Т – время, выделенное на создание проекта.
С – финансовые ресурсы, выделенные на
создание проекта.

4. Графическая иллюстрация

Исполнители
1
Подсистемы
1
Безработный
2
3
2
3
Безработный
4
4

5. Минимизация времени разработки проекта – формальная постановка

Допущения:
а) один исполнитель может разрабатывать несколько
подсистем;
б) допускаются безработные исполнители;
в) каждую подсистему проектирует один исполнитель.
max t (i, j ) z (i, j ) min;
i j
c(i, j ) z (i, j ) C ;
i j
j : z (i, j ) 1;
i
i, j : z (i, j ) 1,0.
(1)

6. Пример 1

Решить задачу (1) методом динамического
программирования при условии, что число
подсистем равно 4, а число исполнителей равно
трем, С=25.
С
1
Т
2
3
4
1
2
3
4
1 10
8
5
3
1
2
4
7
9
2 11
7
2
9
2
1
5
9
3
3
1
4
7
3
6
10
9
6
6

7. Решение задачи (1)

s
2,15
1,14
1
6,7
1
6,19
2
5,8
2,5
2
4,6
3
3
9,10
1
10,13
2
3
10,8 1
1
2
9,3
3
14,1 9,4
1
2
3
9,0 9,3
Ответ: π = {2,3,2,1}; R=10.
1
11,1
2
6,11
6,12
1
10,11 19,8
2
3
2
3
1
11,1 10,4 9,2
1
2
3
2
16,18
3
25,14
3
1
2
3
7,7 15,11 15,8 16,13 16,16
1
10,8 13,3 16,4 16,4
2
3
1
2
3
12,0 16,13 16,7 22,9

8. Самостоятельно 1

Решить задачу (1) методом динамического
программирования при условии, что число
подсистем равно 4, а число исполнителей равно
трем, С = 23.
С
1
Т
2
3
4
1
2
3
4
7
8
5
13
1
2
4
7
9
2 11
7
12
9
2
3
5
9
2
3
10
4
7
3
6
10
9
6
1
6

9. Самостоятельно 2

Решить задачу (1) методом динамического
программирования при условии, что число
подсистем равно 4, а число исполнителей равно
трем, С= 22.
С
1
Т
2
3
4
1
2
3
4
1 10
8
5
3
1
2
4
7
9
2 11
7
5
9
2
1
5
6
3
3
4
4
7
3
6
8
9
6
6

10. Самостоятельно 3

Решить задачу (1) методом динамического
программирования при условии, что число
подсистем равно 4, а число исполнителей равно
трем, С = 21.
С
1
Т
2
3
4
1
2
3
4
1 10
2
5
3
1
2
9
7
9
2 11
7
2
9
2
1
5
9
3
3
3
4
7
3
6
8
9
6
6

11. Минимизация стоимости разработки проекта при ограниченном времени

Допущения:
а) один исполнитель может разрабатывать несколько
подсистем;
б) допускаются безработные исполнители;
в) каждую подсистему проектирует один исполнитель.
c(i, j ) z (i, j ) min;
i j
j t (i, j ) z (i, j ) T ;
max
i
j : z (i, j ) 1;
i
i, j : z (i, j ) 1,0.
(2)

12. Самостоятельно

Решить задачу (2) методом динамического
программирования при условии, что число
подсистем равно 4, а число исполнителей
равно трем, Т<12.
С
1
Т
2
3
4
1
2
3
4
1 10
8
5
3
1
2
4
7
9
2 11
7
5
9
2
1
5
6
3
3
4
4
7
3
6
8
9
6
6