Реферат: Сетевое моделирование при планировании. Задача о коммивояжере...
Реферат: Сетевое моделирование при планировании. Задача о коммивояжере...
Московский городской институт управления Правительства Москвы
Лабораторные работы
по дисциплине
«Экономико-математические методы и модели»
Подготовила студентка V курса Евдокимова Е. Д.
Преподаватель – Новикова Г. М.
Москва
2004
Содержание
Задание №1……………………………………………………………….3
Задание №2……………………………………………………………….8
Задание №3……………………………………………………………...11
Задание №4……………………………………………………………...14
Задание №5……………………………………………………………...16
Задание №6……………………………………………………………...20
Задание №1
Тема: Сетевое моделирование при планировании
Задача: Разработка, анализ и оптимизация сетевого графика при календарном планировании проекта
Компания «АВС» реализует проекты серийного производства различных видов продукции. Каждый проект обеспечивает получение в неделю 100 тыс. $ дополнительной прибыли. Перечень работ и их характеристики представлены в таблице 1.1.
Таблица 1.1
Перечень работ и их характеристики
| Работы | Непосредственно предшествующие работы | Продолжительность работы, недель |
Стоимость работы, тыс. $ при t(i,j)=tHB(I,j) |
Коэффициент затрат на ускорение работы | |
|
tmin |
tmax |
||||
| A | - | 4 | 6 | 110 | 22 |
| B | - | 7 | 9 | 130 | 28 |
| C | - | 8 | 11 | 160 | 18 |
| D | A | 9 | 12 | 190 | 35 |
| E | C | 5 | 8 | 150 | 28 |
| F | B, E | 4 | 6 | 130 | 25 |
| G | C | 11 | 15 | 260 | 55 |
| H | F, G | 4 | 6 | 90 | 15 |
Задание:
1. Изобразить проект с помощью сетевой модели.
2. Определить наиболее вероятную продолжительность каждой работы.
3. Найти все полные пути сетевого графика, определить критический путь, ожидаемую продолжительность выполнения проекта и полную стоимость всех работ.
4. Разработать математическую модель оптимизации процесса реализации проекта.
Сетевой график
D
A H
B
F
 |
|||||
 |
|||||
 |
|||||
C
E
G
Наиболее вероятная продолжительность работ
tНВ = (2tmin + 3tmax)/5
tНВ A = (2*4 + 3*6)/5 = 5,2
tНВ B= (2*7 + 3*9)/5 = 8,2
tНВ C= (2*8 + 3*11)/5 = 9,8
tНВ D= (2*9 + 3*12)/5 = 10,8
tНВ E= (2*5 + 3*8)/5 = 6,8
tНВ F= (2*4 + 3*6)/5 = 5,2
tНВ G= (2*11 + 3*15)/5 = 13,4
tНВ H= (2*4 + 3*6)/5 = 5,2
Возможные полные пути
I. 1 – 2 – 5. Длина: tНВ A + tНВ D =5,2 + 10,8 = 16
II. 1 – 3 – 6 – 5. Длина: tНВ B + tНВ F + tНВ H = 8,2 + 5,2 +5,2 = 18,6
III. 1 – 4 – 6 – 5. Длина: tНВ C + tНВ G + tНВ H = 9,8 + 13,4 + 5,2 = 28,4
IV. 1 – 4 – 3 – 6 – 5. Длина: tНВ C + tНВ E + tНВ F + tНВ H = 9,8 + 6,8 + 5,2 + 5,2= = 27
Максимальная длина пути, равная 28,4 недели соответствует пути III, на котором лежат работы C, G, H. Следовательно, он является критическим.
Математическая модель
Примем за x1, x2 , …, x8 продолжительность работ A, B,…, H соответственно.
x1 ³ 4 (1)
x2 ³ 7 (2)
x3 ³ 8 (3)
x4 ³ 9 (4)
x5 ³ 5 (5)
x6 ³ 4 (6)
x7 ³ 11 (7)
x8 ³ 4 (8)
x1 £ 6 (9)
x2 £ 9 (10)
x3 £ 11 (11)
x4 £ 12 (12)
x5 £ 8 (13)
x6 £ 6 (14)
x7 £ 15 (15)
x8 £ 6 (16)
x1 + x4 + x9 £ 28,4 (17)
x2 + x6 + x8 + x9 £ 28,4 (18)
x3 + x7 + x8 + x9 £ 28,4 (19)
x3 + x5 + x6 + x8 + x9 £ 28,4 (20)
Функция цели: 22x1 +
28x2 + 18x3 +
35x4 + 28x5+ 25x6 +
55x7 + 15x8 +
100x9 max
Исходная матрица
Таблица 1.2
| № |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
Знак | Св. чл. |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ³ | 4 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ³ | 7 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | ³ | 8 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | ³ | 9 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | ³ | 5 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | ³ | 4 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ³ | 11 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | ³ | 4 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | £ | 6 |
| 10 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | £ | 9 |
| 11 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | £ | 11 |
| 12 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | £ | 12 |
| 13 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | £ | 8 |
| 14 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | £ | 6 |
| 15 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | £ | 15 |
| 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | £ | 6 |
| 17 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | £ | 28,4 |
| 18 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | £ | 28,4 |
| 19 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | £ | 28,4 |
| 20 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | £ | 28,4 |
| Ф. ц. | 22 | 28 | 18 | 35 | 28 | 25 | 55 | 15 | 100 | max |
Решение
x1 = 6
