Сетевое моделирование при планировании. Задача о коммивояжере...

Московский городской институт управления Правительства Москвы

Лабораторные работы

по дисциплине

«Экономико-математические методы и модели»

Подготовила студентка 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-4611022
B-7913028
C-81116018
DA91219035
EC5815028
FB, E4613025
GC111526055
HF, G469015

Задание:

1. Изобразить проект с помощью сетевой модели.

2. Определить наиболее вероятную продолжительность каждой работы.

3. Найти все полные пути сетевого графика, определить критический путь, ожидаемую продолжительность выполнения проекта и полную стоимость всех работ.

4. Разработать математическую модель оптимизации процесса реализации проекта.

Сетевой график

Овал: 2Овал: 5D

A H

Овал: 1Овал: 3Овал: 6B F


Овал: 4C 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

ЗнакСв. чл.
1100000000³4
2010000000³7
3001000000³8
4000100000³9
5000010000³5
6000001000³4
7000000100³11
8000000010³4
9100000000£6
10010000000£9
11001000000£11
12000100000£12
13000010000£8
14000001000£6
15000000100£15
16000000010£6
17100100001£28,4
18010001011£28,4
19001000111£28,4
20001011011£28,4
Ф. ц.2228183528255515100max

Решение

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 затратСтоимостьИтого затрат
A65,2-0,822-17,611092,4
B98,2-0,828-22,4130107,6
C89,81,81832,4160192,4
D1210,8-1,235-42190148
E76,8-0,228-5,6150144,4
F45,21,22530130160
G1113,42,455132260392
H45,21,2151890108
Всего затрат124,812201344,8
Актуально: