Сетевое моделирование при планировании. Задача о коммивояжере... (стр. 1 из 5)
Московский городской институт управления Правительства Москвы
Лабораторные работы
по дисциплине
«Экономико-математические методы и модели»
Подготовила студентка 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 EG
Наиболее вероятная продолжительность работ
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
x2 = 9
x3 = 8
x4 = 12
x5 = 7
x6 = 4
x7 = 11
x8 = 4
x9 = 5,4
Т. к. x9 = 5,4, то длина критического пути уменьшится на эту величину. Проверим это утверждение:
x3 + x7 + x8 = 8 + 11 + 4 = 23
Уменьшение времени выполнения работы, как правило, связано с увеличением затрат. В таблице 1.3 определим прирост затрат при уменьшении времени реализации проекта.
Таблица 1.3
Изменение затрат при уменьшении времени реализации проекта
| Работа | х | tHB | D x | Куск | D затрат | Стоимость | Итого затрат |
| A | 6 | 5,2 | -0,8 | 22 | -17,6 | 110 | 92,4 |
| B | 9 | 8,2 | -0,8 | 28 | -22,4 | 130 | 107,6 |
| C | 8 | 9,8 | 1,8 | 18 | 32,4 | 160 | 192,4 |
| D | 12 | 10,8 | -1,2 | 35 | -42 | 190 | 148 |
| E | 7 | 6,8 | -0,2 | 28 | -5,6 | 150 | 144,4 |
| F | 4 | 5,2 | 1,2 | 25 | 30 | 130 | 160 |
| G | 11 | 13,4 | 2,4 | 55 | 132 | 260 | 392 |
| H | 4 | 5,2 | 1,2 | 15 | 18 | 90 | 108 |
| Всего затрат | 124,8 | 1220 | 1344,8 |
Таким образом, время выполнения работ A, B, D, E увеличилось по сравнению с наиболее вероятным; продолжительность остальных работ уменьшилась. Затраты на реализацию проекта возросли на 124,8 тыс. $. Увеличение затрат произошло, в основном, из-за работы G, по которой наблюдается наибольшее сокращение времени в сочетании с наивысшим коэффициентом затрат на выполнение работы.