рефератырефератырефератырефератырефератырефератырефератырефераты

рефераты, скачать реферат, современные рефераты, реферат на тему, рефераты бесплатно, банк рефератов, реферат культура, виды рефератов, бесплатные рефераты, экономический реферат

"САМЫЙ БОЛЬШОЙ БАНК РЕФЕРАТОВ"

Портал Рефератов

рефераты
рефераты
рефераты

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

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

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

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

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

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

|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, по которой

наблюдается наибольшее сокращение времени в сочетании с наивысшим

коэффициентом затрат на выполнение работы.

Из-за сокращения критического пути проект будет введен в эксплуатацию

на 5,4 недели раньше. Т. к. прибыль за неделю составляет 100 тыс. $, то за

этот срок она составит 100 тыс. $ * 5,4 = 540 тыс. $.

В результате дополнительная прибыль с учетом возрастания затрат на

проведение работ составит 540 тыс. $ - 124,8 тыс. $ = 415,2 тыс. $

Задание №2

Тема: Графы

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

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

таблице 2.1.

Таблица 2.1

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

|Из пункта i |В пункт j |

| |1 |2 |3 |4 |

|1 |0 |8 |8 |6 |

|2 |4 |0 |6 |12 |

|3 |10 |12 |0 |18 |

|4 |8 |10 |4 |0 |

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

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

отсутствующие маршруты.

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

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

Таблица 2.2

Обозначения

|xi |Пункт |Пункт |Время |

| |отправления |назначения |переезда |

|x1 |1 |2 |8 |

|x2 |1 |3 |8 |

|Продолжение |

|x3 |1 |4 |6 |

|x4 |2 |1 |4 |

|x5 |2 |3 |6 |

|x6 |2 |4 |12 |

|x7 |3 |1 |10 |

|x8 |3 |2 |12 |

|x9 |3 |4 |18 |

|x10 |4 |1 |8 |

|x11 |4 |2 |10 |

|x12 |4 |3 |4 |

Сумма входящих и исходящих маршрутов в каждом пункте равна 1.

Следовательно, система условий-ограничений выглядит следующим образом:

x1 + x2 + x3 = 1 (1)

x4 + x5 + x6 = 1 (2)

x7 + x8 + x9 = 1 (3)

x10 + x11 + x12 = 1 (4)

x4 + x7 + x10 = 1 (5)

x1 + x8 + x11 = 1 (6)

x2 + x5 + x12 = 1 (7)

x3 + x6 + x9 = 1 (8)

Функция цели: 8x1 + 8x2 + 6x3 + 4x4 + 6x5 + 12x6 + 10x7 + 12x8 + 18x9

+ 8x10 + 10x11 + 4x12 min

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

Таблица 2.3

|(12 |(13 |(21 |(32 |(34 |(45 |(53 |(54 |

|3 |2 |1 |3 |2 |2 |3 |1 |

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

Примем за х1, х2, …, х5 предельные вероятности состояний в

стационарном режиме пунктов S1, S2, …, S5 соответственно. Произведение

вероятности состояния на интенсивность исходящих из этого пункта потоков

равна произведению интенсивностей входящих потоков на вероятность состояния

в стационарном режиме пунктов их отправления. Система уравнений Колмогорова

для данной задачи в общем виде выглядит следующим образом:

((13 + (12 )* х1 = (21 * х2 (1)

(21 * х2 = (12 * х1+ (32 * х3 (2)

((32 + (34 )* х3 = (13 * х1 + (53 * х5 (3)

(45 * х4 = (34 * х3+ (54 * х5 (4)

((54 + (53 )* х5 = (45 * х4 (5)

Кроме того, сумма всех вероятностей равна 1. При подстановке данных

таблицы 4.1 и добавлении переменной х6 получаем:

5 х1 - х2 + х6 = 0 (1)

х2 - 3х1 - 3х3 + х6 = 0 (2)

5 х3 - 2х1 - 3х5 + х6 = 0 (3)

2 х4 - 2х3 – х3 + х6 = 0 (4)

4 х5 - 2х4 + х6 = 0 (5)

х1 + х2 + х3 + х4 + х5 + х6 = 1 (6)

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

Таблица 4.2.

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

|№ |х1 |х2 |х3 |х4 |х5 |х6 |Св.чл. |Знак |

|1 |5 |-1 |0 |0 |0 |1 |0 |= |

|2 |-3 |1 |-3 |0 |0 |1 |0 |= |

|3 |-2 |0 |5 |0 |-3 |1 |0 |= |

|4 |0 |0 |-2 |2 |-1 |1 |0 |= |

|5 |0 |0 |0 |-2 |4 |1 |0 |= |

|6 |1 |1 |1 |1 |1 |1 |1 |= |

|Ф.ц. |0 |0 |0 |0 |0 |М |max | |

Решение

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

х1 = 0,125

х2 = 0,625

х3 = 0,083

х4 = 0,111

х5 = 0,055

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

полученная при расчетах, крайне незначительна.

Задание №5

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

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

мелкосерийного производства

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

различных видов продукции, а также директивное время исполнения заказов (в

условных единицах) и нормы затрат времени на обработку одной партии

продукции на каждом из типов оборудования.

Общая масса заказа по каждому виду продукции разбивается на N партий

так, что для каждого вида продукции выполняется условие:

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

Нормы затрат времени в каждом эксперименте имитационного моделирования

обратно пропорциональны числу партий.

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

Таблица 5.1

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

| Продукция|Эксперимент №1 |Эксперимент №2 |Эксперимент №3 |

| | | | |

| | | | |

|Оборудование | | | |

|Изделие 1 |1 |6 |0 |0 |0 |1 |4 |26 |

|Изделие 2 |1 |0 |0 |0 |0 |2 |4 |14 |

|Изделие 3 |1 |0 |6 |0 |0 |0 |4 |25 |

|Изделие 4 |1 |0 |0 |0 |0 |3 |4 |12 |

|Изделие 5 |1 |0 |0 |3 |0 |0 |4 |25 |

|Изделие 6 |1 |0 |0 |0 |2 |0 |4 |24 |

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

Таблица 5.3.

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

| |№1 |№2 |№3 | |

|№1 |0,15 |0,10 |0,30 |100 |

|№2 |0,25 |0,15 |0,25 |280 |

|№3 |0,30 |0,25 |0 |320 |

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

х1 = 0,15х1 + 0,1х2 + 0,3х3 + 100

х2 = 0,25х1 + 0,15х2 + 0,25х3 + 280

х3 = 0,3х1 + 0,25х2 + 0х3 + 320

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

ограничений:

0,85х1 - 0,1х2 - 0,3х3 - х4 = 100 (1)

-0,25х1 + 0,85х2 - 0,25х3 - х4 = 280 (2)

-0,3х1 + 0,25х2 + х3 - х4 = +320 (3)

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

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

Таблица 6.2.

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

|№ |х1 |х2 |х3 |х4 |Знак |Св. чл. |

|1 |0,85 |-0,1 |-0,3 |-1 |= |100 |

|2 |-0,25 |0,85 |-0,25 |-1 |= |280 |

|3 |-0,3 |-0,25 |1 |-1 |= |320 |

|Ф. ц. |0 |0 |0 |-М |max | |

Решение

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

х1 = 401,292

х2 = 622,756

х3 = 596,077

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

затрат, получим решение, представленное в таблице 6.3.

Таблица 6.3.

Решение

|Производящие цехи |Потребляющие цехи |Конечный |Валовой |

| | |продукт |продукт |

| |1 |2 |3 | | |

|1 |60,15 |40,1 |120,3 |100 |401 |

|2 |155,75 |93,45 |155,75 |280 |623 |

|3 |178,8 |149,0 |0 |320 |596 |

|Итого | | | | | |

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

выражении.

-----------------------

1

2

3

4

5

6

1

2

3

4

1

2

3

4

1

2

3

4

5

S1

S4

S3

S2

S5

1

3

5

2

4

рефераты
РЕФЕРАТЫ © 2010