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

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

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

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

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

Подготовила студентка V курса Евдокимова Е. Д.

Преподаватель – Новикова Г. М.

Москва

2004

Содержание

Задание №1……………………………………………………………….3

Задание №2……………………………………………………………….8

Задание №3……………………………………………………………...11

Задание №4……………………………………………………………...14

Задание №5……………………………………………………………...16

Задание №6……………………………………………………………...20

Задание №1

Тема: Сетевое моделирование при планировании

Задача: Разработка, анализ и оптимизация сетевого графика при календарном планировании проекта

Компания «АВС» реализует проекты серийного производства различных видов продукции. Каждый проект обеспечивает получение в неделю 100 тыс. $ дополнительной прибыли. Перечень работ и их характеристики представлены в таблице 1.1.

Таблица 1.1

Перечень работ и их характеристики

Задание:

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

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

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

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

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

D

A H

B F

C E

G

Наиболее вероятная продолжительность работ

t_НВ = (2t_min + 3t_max)/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. Следовательно, он является критическим.

Математическая модель

Примем за x_1, x₂ , …, x₈ продолжительность работ A, B,…, H соответственно.

x₁ ³ 4 ⁽¹⁾

x₂ ³ 7 ⁽²⁾

x₃ ³ 8 ⁽³⁾

x₄ ³ 9 ⁽⁴⁾

x₅ ³ 5 ⁽⁵⁾

x₆ ³ 4 ⁽⁶⁾

x₇ ³ 11 ⁽⁷⁾

x₈ ³ 4 ⁽⁸⁾

x₁ £ 6 ⁽⁹⁾

x₂ £ 9 ⁽¹⁰⁾

x₃ £ 11 ⁽¹¹⁾

x₄ £ 12 ⁽¹²⁾

x₅ £ 8 ⁽¹³⁾

x₆ £ 6 ⁽¹⁴⁾

x₇ £ 15 ⁽¹⁵⁾

x₈ £ 6 ⁽¹⁶⁾

x₁ + x₄ + x₉ £ 28,4 ⁽¹⁷⁾

x₂ + x₆ + x₈ + x₉ £ 28,4 ⁽¹⁸⁾

x₃ + x₇ + x₈ + x₉ £ 28,4 ⁽¹⁹⁾

x₃ + x₅ + x₆ + x₈ + x₉ £ 28,4 ⁽²⁰⁾

Функция цели: 22x₁ + 28x₂ + 18x₃ + 35x₄ + 28x₅+ 25x₆ + 55x₇ + 15x₈ + 100x₉ max

Исходная матрица

Таблица 1.2

Решение

x₁ = 6

x₂ = 9

x₃ = 8

x₄ = 12

x₅ = 7

x₆ = 4

x₇ = 11

x₈ = 4

x₉ = 5,4

Т. к. x₉ = 5,4, то длина критического пути уменьшится на эту величину. Проверим это утверждение:

x₃ + x₇ + x₈ = 8 + 11 + 4 = 23

Уменьшение времени выполнения работы, как правило, связано с увеличением затрат. В таблице 1.3 определим прирост затрат при уменьшении времени реализации проекта.

Таблица 1.3

Изменение затрат при уменьшении времени реализации проекта