БОЛЬШАЯ НАУЧНАЯ БИБЛИОТЕКА  
рефераты
Добро пожаловать на сайт Большой Научной Библиотеки! рефераты
рефераты
Меню
Главная
Налоги
Начертательная геометрия
Оккультизм и уфология
Педагогика
Полиграфия
Политология
Право
Предпринимательство
Программирование и комп-ры
Радиоэлектроника
Региональная экономика
Режущий инструмент
Реклама и PR
Ресторанно-гостиничный бизнес бытовое обслуживан
Римское право
Русский язык культура речи
РЦБ ценные бумаги
САПР
Сексология
Семейное право
Социология
Страховое право
Строительство архитектура
Таможенное право
Теория государства и права
Технология
Таможенная система
Транспорт
Физика и энергетика
Философия
Финансы деньги и налоги
Физкультура и спорт
Фотография
Химия
Хозяйственное право
Цифровые устройства
Экологическое право
Экология
Экономика
Экономико-математическое моделирование
Экономическая география
Экономическая теория
Эргономика
Этика и эстетика
Сочинения по литературе и русскому языку
Рефераты по теории государства и права
Рефераты по теории организации
Рефераты по теплотехнике
Рефераты по товароведению
Рефераты по трудовому праву
Рефераты по туризму
Рефераты по уголовному праву и процессу
Рефераты по управлению
Рефераты по менеджменту
Рефераты по металлургии
Рефераты по муниципальному праву
Биографии
Рефераты по психологии
Рефераты по риторике
Рефераты по статистике
Рефераты по страхованию
Рефераты по схемотехнике
Рефераты по науке и технике
Рефераты по кулинарии
Рефераты по культурологии
Рефераты по зарубежной литературе
Рефераты по логике
Рефераты по логистике
Рефераты по маркетингу
Рефераты по международному публичному праву
Рефераты по международному частному праву
Рефераты по международным отношениям
Рефераты по культуре и искусству
Рефераты по кредитованию
Рефераты по естествознанию
Рефераты по истории техники
Рефераты по журналистике
Рефераты по зоологии
Рефераты по инвестициям
Рефераты по информатике
Исторические личности
Рефераты по кибернетике
Рефераты по коммуникации и связи
Рефераты по косметологии
Рефераты по криминалистике
Рефераты по криминологии
Новые или неперечисленные
Без категории

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

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

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

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

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

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

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





17.06.2012
Большое обновление Большой Научной Библиотеки  рефераты
12.06.2012
Конкурс в самом разгаре не пропустите Новости  рефераты
08.06.2012
Мы проводим опрос, а также небольшой конкурс  рефераты
05.06.2012
Сена дизайна и структуры сайта научной библиотеки  рефераты
04.06.2012
Переезд на новый хостинг  рефераты
30.05.2012
Работа над улучшением структуры сайта научной библиотеки  рефераты
27.05.2012
Работа над новым дизайном сайта библиотеки  рефераты

рефераты
©2011