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

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

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

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

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

Подготовила студентка 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

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

Таким образом, время выполнения работ A, B, D, E увеличилось по сравнению с наиболее вероятным; продолжительность остальных работ уменьшилась. Затраты на реализацию проекта возросли на 124,8 тыс. $. Увеличение затрат произошло, в основном, из-за работы G, по которой наблюдается наибольшее сокращение времени в сочетании с наивысшим коэффициентом затрат на выполнение работы.

Из-за сокращения критического пути проект будет введен в эксплуатацию на 5,4 недели раньше. Т. к. прибыль за неделю составляет 100 тыс. $, то за этот срок она составит 100 тыс. $ * 5,4 = 540 тыс. $.

В результате дополнительная прибыль с учетом возрастания затрат на проведение работ составит 540 тыс. $ - 124,8 тыс. $ = 415,2 тыс. $

Задание №2

Тема: Графы

Задача о коммивояжере

Имеется 4 пункта. Время переезда из пункта I в пункт j представлено в таблице 2.1.

Таблица 2.1

Исходные данные

График представлен на рисунке.

Требуется найти оптимальный маршрут, вычеркнув из таблицы отсутствующие маршруты.

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

Обозначим за x маршруты, приведенные в таблице 2.2.

Таблица 2.2

Обозначения

Сумма входящих и исходящих маршрутов в каждом пункте равна 1. Следовательно, система условий-ограничений выглядит следующим образом:

x₁ + x₂ + x₃ = 1 ⁽¹⁾

x₄ + x₅ + x₆ = 1 ⁽²⁾

x₇ + x₈ + x₉ = 1 ⁽³⁾

x₁₀ + x₁₁ + x₁₂ = 1 ⁽⁴⁾

x₄ + x₇ + x₁₀ = 1 ⁽⁵⁾

x₁ + x₈ + x₁₁ = 1 ⁽⁶⁾

x₂ + x₅ + x₁₂ = 1 ⁽⁷⁾

x₃ + x₆ + x₉ = 1 ⁽⁸⁾

Функция цели: 8x₁ + 8x₂ + 6x₃ + 4x₄ + 6x₅ + 12x₆ + 10x₇ + 12x₈ + 18x₉ + 8x₁₀ + 10x₁₁ + 4x₁₂ min

Исходная матрица условий задачи представлена в таблице 2.3.

Таблица 2.3

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

Решение

x₃ = 1

x₅ = 1

x₇ = 1

x₈ = 0

x₁₁ = 1

Это означает, что на графике остаются только пути, соответствующие переменным х₃, х₅, х₇, х₁₁ (1 4, 2 3, 3 1, 4 2). Функционал равен 12, т. е. время пути будет равно 12 единицам. График при этом выглядит следующим образом.

Задание №3

Тема: Графы

Задача о максимальном потоке

Имеется трубопроводная сеть с заданной S_ij пропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел.

a_исток a_сток

Пропускная способность S_ij , тыс. тонн

S₁₂ = 4

S₁₃ = 7

S₁₄ = 8

S₂₃ = 3

S₂₅ = 5

S₃₄ = 8

S₃₅ = 9

S₄₅ = 9

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

Обозначим за х_{1, 2, …, 8} перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х₉ – пропускную способность конечного узла сети.

Сумма входящих в каждый узел потоков равна сумме выходящих, причем интенсивность каждого потока не может превышать пропускную способность своего участка сети. Поэтому система условий-ограничений выглядит следующим образом.

х₉ - х₁ – х₂ – х₃ = 0 ⁽¹⁾

х₁ – х₄ – х₅ = 0 ⁽²⁾

х₂ + х₄ – х₆ – х₇ = 0 ⁽³⁾

х₃ + х₆ – х₈ = 0 ⁽⁴⁾

х₅ + х₇ + х₈ – х₉ = 0 ⁽⁵⁾

х₁ £ 4 ⁽⁶⁾

х₂ £ 7 ⁽⁷⁾

х₃ £ 8 ⁽⁸⁾

х₄ £ 3 ⁽⁹⁾

х₅ £ 5 ⁽¹⁰⁾

х₆ £ 8 ⁽¹¹⁾

х₇ £ 9 ⁽¹²⁾

х₈ £ 9 ⁽¹³⁾

Функция цели: х₉ max

Таблица 3.1

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

Решение

х₁ = 4

х₂ = 7

х₃ = 8

х₅ = 4

х₇ = 7

х₈ = 8

х₉ = 19

Функционал в данной задаче равен –481, что не имеет смысла при заданных условиях. Однако, исходя из математической модели, функционал в данной задаче равен значению х₉ . Таким образом, максимальная пропускная способность сети составит 19 тыс. тонн. При этом некоторые маршруты окажутся незадействованными (х₄ и х₆). График будет выглядеть следующим образом.

Задание №4

Тема: Системы массового обслуживания

Задача: Рационализация функционирования системы управления аэропортом на базе анализа марковских процессов

Различные аэропорты имеют отделы системы управления, функциональная связь которых и интенсивность потоков информации представлены на рисунке и в таблице 4.1.

Требуется вычислить вероятности состояний в стационарном режиме по значениям интенсивности перехода.

Таблица 4.1

Исходные данные

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

Примем за х₁, х₂, …, х₅ предельные вероятности состояний в стационарном режиме пунктов S₁, S₂, …, S₅ соответственно. Произведение вероятности состояния на интенсивность исходящих из этого пункта потоков равна произведению интенсивностей входящих потоков на вероятность состояния в стационарном режиме пунктов их отправления. Система уравнений Колмогорова для данной задачи в общем виде выглядит следующим образом:

(l₁₃ + l₁₂ )* х₁ = l₂₁ * х₂ ⁽¹⁾

l₂₁ * х₂ = l₁₂ * х₁+ l₃₂ * х₃ ⁽²⁾

(l₃₂ + l₃₄ )* х₃ = l₁₃ * х₁ + l₅₃ * х₅ ⁽³⁾

l₄₅ * х₄ = l₃₄ * х₃+ l₅₄ * х₅ ⁽⁴⁾

(l₅₄ + l₅₃ )* х₅ = l₄₅ * х₄ ⁽⁵⁾

Кроме того, сумма всех вероятностей равна 1. При подстановке данных таблицы 4.1 и добавлении переменной х₆ получаем:

5 х₁ - х₂ + х₆ = 0 ⁽¹⁾

х₂ - 3х₁ - 3х₃ + х₆ = 0 ⁽²⁾

5 х₃ - 2х₁ - 3х₅ + х₆ = 0 ⁽³⁾

2 х₄ - 2х₃ – х₃ + х₆ = 0 ⁽⁴⁾

4 х₅ - 2х₄ + х₆ = 0 ⁽⁵⁾

х₁ + х₂ + х₃ + х₄ + х₅ + х₆ = 1 ⁽⁶⁾

Функция цели: М х₆ max

Таблица 4.2.

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

Решение

Функционал = -500

х₁ = 0,125

х₂ = 0,625

х₃ = 0,083

х₄ = 0,111

х₅ = 0,055

Сумма данных вероятностей составляет 0,999, т. е. погрешность, полученная при расчетах, крайне незначительна.

Задание №5

Тема: Имитационное моделирование

Задача: Расчет и анализ графика запуска-выпуска продукции в цехе мелкосерийного производства

В таблице 5.1 представлены технологические маршруты изготовления различных видов продукции, а также директивное время исполнения заказов (в условных единицах) и нормы затрат времени на обработку одной партии продукции на каждом из типов оборудования.

Общая масса заказа по каждому виду продукции разбивается на N партий так, что для каждого вида продукции выполняется условие:

Общая масса заказа = (масса партий)*(число партий)

Нормы затрат времени в каждом эксперименте имитационного моделирования обратно пропорциональны числу партий.

Требуется определить оптимальный маршрут изготовления продукции.

Таблица 5.1

Технологические маршруты изготовления продукции

Т_д = 27

Решение

В результате применения программы «APOSUM» было получено 3 варианта решения. Время изготовления заказа в каждом из них составляет соответственно 41, 48 и 52 единицы. Ближе всего к нормативному времени находится вариант 1. Количество переналадок при этом равно 19, что больше, чем в других вариантах (10 и 5), однако решающее значение имеет время. Изменяя длительность обработки изделий, можно уменьшить время с 41 до 29 единиц. Измененная длительность обработки изделий представлена в таблице 5.2.

Таблица 5.2.

Длительность обработки изделий

В итоге получился следующий график запуска-выпуска продукции.

Таблица 5.3.

График запуска-выпуска продукции

Продолжение

Время и очередность запуска и выпуска каждой партии продукции, последовательность и время использования каждого оборудования проиллюстрированы далее графиком Ганта.

График Ганта

Задание №6

Тема: Матричные модели балансового метода планирования

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

В трех цехах приборостроительного завода изготовляются датчики, приборы и их узлы, основная часть которых идет на внутреннее потребление при сборке блоков АСУ, остальная является конечным продуктом и поставляется внешним приборостроительным и машиностроительным организациям, а также в ремонтные мастерские.

Требуется составить межпродуктовый баланс производства и распределения продукции, если известны коэффициенты прямых затрат и конечный продукт (таблица 6.1).

Таблица 6.1.

Исходные данные

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

х₁ = 0,15х₁ + 0,1х₂ + 0,3х₃ + 100

х₂ = 0,25х₁ + 0,15х₂ + 0,25х₃ + 280

х₃ = 0,3х₁ + 0,25х₂ + 0х₃ + 320

Отсюда, умножив уравнения на –1, получаем следующую систему уравнений ограничений:

0,85х₁ - 0,1х₂ - 0,3х₃ - х₄ = 100 ⁽¹⁾

-0,25х₁ + 0,85х₂ - 0,25х₃ - х₄ = 280 ⁽²⁾

-0,3х₁ + 0,25х₂ + х₃ - х₄ = +320 ⁽³⁾

Функция цели: -Мх₄ max

Исходная матрица условий задачи представлена в таблице 6.2.

Таблица 6.2.

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

Решение

Функционал = 0

х₁ = 401,292

х₂ = 622,756

х₃ = 596,077

Умножив полученные значения валового продукта на коэффициенты прямых затрат, получим решение, представленное в таблице 6.3.

Таблица 6.3.

Решение

В таблице показаны затраты на производство продукции в количественном выражении.