Diplom-177.ru
 

Рефераты, курсовые, контрольные для студента!

 

Астрономия

Литература, Лингвистика

Страховое право

Уголовный процесс

Международные экономические и валютно-кредитные отношения

Экскурсии и туризм

Менеджмент (Теория управления и организации)

Компьютеры и периферийные устройства

Философия

Микроэкономика, экономика предприятия, предпринимательство

История отечественного государства и права

Бухгалтерский учет

Искусство

Маркетинг, товароведение, реклама

Радиоэлектроника

Экономическая теория, политэкономия, макроэкономика

История государства и права зарубежных стран

Психология, Общение, Человек

Банковское дело и кредитование

Историческая личность

Теория государства и права

Физкультура и Спорт

Государственное регулирование, Таможня, Налоги

Социология

Программное обеспечение

Биология

Культурология

Педагогика

Геодезия

Программирование, Базы данных

Международное право

Промышленность и Производство

Биржевое дело

Хозяйственное право

Медицина

Гражданское право

Право

Сельское хозяйство

Химия

Транспорт

Уголовное и уголовно-исполнительное право

Охрана природы, Экология, Природопользование

Физика

Музыка

География, Экономическая география

Математика

История

Муниципальное право России

Экономико-математическое моделирование

Ценные бумаги

Технология

Семейное право

Административное право

Искусство, Культура, Литература

Пищевые продукты

Компьютерные сети

Геология

Трудовое право

Иностранные языки

Здоровье

Юридическая психология

Москвоведение

Экономика и Финансы

Римское право

Гражданская оборона

Техника

Криминалистика и криминология

Конституционное (государственное) право зарубежных стран

Охрана правопорядка

Ветеринария

Военное дело

Налоговое право

Политология, Политистория

Экологическое право

История экономических учений

Религия

Компьютеры, Программирование

Прокурорский надзор

Космонавтика

Уголовное право

Физкультура и Спорт, Здоровье

Авиация

Металлургия

Архитектура

Правоохранительные органы

Конституционное (государственное) право России


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

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

Перечень работ и их характеристики представлены в таблице 1.1. Таблица 1.1 Перечень работ и их характеристики

Работы Непосредственно предшествующие работы Продолжительность работы, недель Стоимость работы, тыс. $ при t(i,j)=t HB (I,j) Коэффициент затрат на ускорение работы
t min t max
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. Разработать математическую модель оптимизации процесса реализации проекта.

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

2
5
D A H
1
3
6
B F
4
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 2 , …, x 8 продолжительность работ A , B ,…, H соответственно. x 1 ³ 4 (1) x 2 ³ 7 (2) x 3 ³ 8 (3) x 4 ³ 9 (4) x 5 ³ 5 (5) x 6 ³ 4 (6) x 7 ³ 11 (7) x 8 ³ 4 (8) x 1 6 (9) x 2 9 (10) x 3 11 (11) x 4 12 (12) x 5 8 (13) x 6 6 (14) x 7 15 (15) x 8 6 (16) x 1 + x 4 + x 9 28,4 (17) x 2 + x 6 + x 8 + x 9 28,4 (18) x 3 + x 7 + x 8 + x 9 28,4 (19) x 3 + x 5 + x 6 + x 8 + x 9 28,4 (20) Функция цели: 22 x 1 + 28 x 2 + 18 x 3 + 35 x 4 + 28 x 5 + 25 x 6 + 55 x 7 + 15 x 8 + 100 x 9 max Исходная матрица Таблица 1.2

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 Знак Св. чл.
1 1 0 0 0 0 0 0 0 0 ³ 4
2 0 1 0 0 0 0 0 0 0 ³ 7
3 0 0 1 0 0 0 0 0 0 ³ 8
4 0 0 0 1 0 0 0 0 0 ³ 9
5 0 0 0 0 1 0 0 0 0 ³ 5
6 0 0 0 0 0 1 0 0 0 ³ 4
7 0 0 0 0 0 0 1 0 0 ³ 11
8 0 0 0 0 0 0 0 1 0 ³ 4
9 1 0 0 0 0 0 0 0 0 6
10 0 1 0 0 0 0 0 0 0 9
11 0 0 1 0 0 0 0 0 0 11
12 0 0 0 1 0 0 0 0 0 12
13 0 0 0 0 1 0 0 0 0 8
14 0 0 0 0 0 1 0 0 0 6
15 0 0 0 0 0 0 1 0 0 15
16 0 0 0 0 0 0 0 1 0 6
17 1 0 0 1 0 0 0 0 1 28,4
18 0 1 0 0 0 1 0 1 1 28,4
19 0 0 1 0 0 0 1 1 1 28,4
20 0 0 1 0 1 1 0 1 1 28,4
Ф . ц . 22 28 18 35 28 25 55 15 100 max
Решение x 1 = 6 x 2 = 9 x 3 = 8 x 4 = 12 x 5 = 7 x 6 = 4 x 7 = 11 x 8 = 4 x 9 = 5,4 Т. к. x 9 = 5,4, то длина критического пути уменьшится на эту величину.

Проверим это утверждение: x 3 + x 7 + x 8 = 8 + 11 + 4 = 23 Уменьшение времени выполнения работы, как правило, связано с увеличением затрат. В таблице 1.3 определим прирост затрат при уменьшении времени реализации проекта.

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

Работа х t HB D x К уск D затрат Стоимость Итого затрат
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
График представлен на рисунке.
1
2
3
4
Требуется найти оптимальный маршрут, вычеркнув из таблицы отсутствующие маршруты.

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

x i Пункт отправления Пункт назначения Время переезда
x 1 1 2 8
x 2 1 3 8
Продолжение
x 3 1 4 6
x 4 2 1 4
x 5 2 3 6
x 6 2 4 12
x 7 3 1 10
x 8 3 2 12
x 9 3 4 18
x 10 4 1 8
x 11 4 2 10
x 12 4 3 4
Сумма входящих и исходящих маршрутов в каждом пункте равна 1. Следовательно, система условий-ограничений выглядит следующим образом: x 1 + x 2 + x 3 = 1 (1) x 4 + x 5 + x 6 = 1 (2) x 7 + x 8 + x 9 = 1 (3) x 10 + x 11 + x 12 = 1 (4) x 4 + x 7 + x 10 = 1 (5) x 1 + x 8 + x 11 = 1 (6) x 2 + x 5 + x 12 = 1 (7) x 3 + x 6 + x 9 = 1 (8) Функция цели: 8 x 1 + 8 x 2 + 6 x 3 + 4 x 4 + 6 x 5 + 12 x 6 + 10 x 7 + 12 x 8 + 18 x 9 + 8 x 10 + 10 x 11 + 4 x 12 min Исходная матрица условий задачи представлена в таблице 2.3. Таблица 2.3
x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 х 10 x 11 x 12 Св.чл. Зн
1 1 1 1 0 0 0 0 0 0 0 0 0 1 =
2 0 0 0 1 1 1 0 0 0 0 0 0 1 =
3 0 0 0 0 0 0 1 1 1 0 0 0 1 =
4 0 0 0 0 0 0 0 0 0 1 1 1 1 =
5 0 0 0 1 0 0 1 0 0 1 0 0 1 =
6 1 0 0 0 0 0 0 1 0 0 1 0 1 =
7 0 1 0 0 1 0 0 0 0 0 0 1 1 =
8 0 0 1 0 0 1 0 0 1 0 0 0 1 =
Фц. 8 8 6 4 6 12 10 12 18 8 10 4 min
Исходная матрица Решение x 3 = 1 x 5 = 1 x 7 = 1 x 8 = 0 x 11 = 1 Это означает, что на графике остаются только пути, соответствующие переменным х 3 , х 5 , х 7 , х 11 (1 4, 2 3, 3 1, 4 2). Функционал равен 12, т. е. время пути будет равно 12 единицам.

График при этом выглядит следующим образом.

1
2
3
4
Задание №3 Тема: Графы Задача о максимальном потоке Имеется трубопроводная сеть с заданной S ij пропускной способностью каждого участка из i -го узла в j -й узел и мощностью насосной станции, расположенной в узле.

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

2
1
5
3
a исток a сток
4
Пропускная способность S ij , тыс. тонн S 12 = 4 S 13 = 7 S 14 = 8 S 23 = 3 S 25 = 5 S 34 = 8 S 35 = 9 S 45 = 9 Математическая модель Обозначим за х 1, 2, …, 8 перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х 9 – пропускную способность конечного узла сети. Сумма входящих в каждый узел потоков равна сумме выходящих, причем интенсивность каждого потока не может превышать пропускную способность своего участка сети.

Поэтому система условий-ограничений выглядит следующим образом. х 9 - х 1 – х 2 – х 3 = 0 (1) х 1 – х 4 – х 5 = 0 (2) х 2 + х 4 – х 6 – х 7 = 0 (3) х 3 + х 6 – х 8 = 0 (4) х 5 + х 7 + х 8 – х 9 = 0 (5) х 1 4 (6) х 2 7 (7) х 3 8 (8) х 4 3 (9) х 5 5 (10) х 6 8 (11) х 7 9 (12) х 8 9 (13) Функция цели: х 9 max Таблица 3.1 Исходная матрица

х 1 х 2 х 3 х 4 х 5 х 6 х 7 х 8 х 9 Знак Св.чл.
1 -1 -1 -1 0 0 0 0 0 1 = 0
2 1 0 0 -1 -1 0 0 0 0 = 0
3 0 1 0 1 0 -1 -1 0 0 = 0
4 0 0 1 0 0 1 0 -1 0 = 0
5 0 0 0 0 1 0 1 1 -1 = 0
6 1 0 0 0 0 0 0 0 0 4
7 0 1 0 0 0 0 0 0 0 7
8 0 0 1 0 0 0 0 0 0 8
9 0 0 0 1 0 0 0 0 0 3
10 0 0 0 0 1 0 0 0 0 5
11 0 0 0 0 0 1 0 0 0 8
12 0 0 0 0 0 0 1 0 0 9
13 0 0 0 0 0 0 0 1 0 9
Ф . ц . 0 0 0 0 0 0 0 0 1 max
Решение х 1 = 4 х 2 = 7 х 3 = 8 х 5 = 4 х 7 = 7 х 8 = 8 х 9 = 19 Функционал в данной задаче равен –481, что не имеет смысла при заданных условиях.

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

1
3
5
2
4
Задание №4 Тема: Системы массового обслуживания Задача: Рационализация функционирования системы управления аэропортом на базе анализа марковских процессов Различные аэропорты имеют отделы системы управления, функциональная связь которых и интенсивность потоков информации представлены на рисунке и в таблице 4.1. Требуется вычислить вероятности состояний в стационарном режиме по значениям интенсивности перехода.
S 4
S 1
S 3
S 5
S 2
Таблица 4.1 Исходные данные
Интенсивность потоков (переходов)
l 12 l 13 l 21 l 32 l 34 l 45 l 53 l 54
3 2 1 3 2 2 3 1
Математическая модель Примем за х 1 , х 2 , …, х 5 предельные вероятности состояний в стационарном режиме пунктов S 1 , S 2 , …, S 5 соответственно.

Произведение вероятности состояния на интенсивность исходящих из этого пункта потоков равна произведению интенсивностей входящих потоков на вероятность состояния в стационарном режиме пунктов их отправления.

Система уравнений Колмогорова для данной задачи в общем виде выглядит следующим образом: ( l 13 + l 12 )* х 1 = l 21 * х 2 (1) l 21 * х 2 = l 12 * х 1 + l 32 * х 3 (2) ( l 32 + l 34 )* х 3 = l 13 * х 1 + l 53 * х 5 (3) l 45 * х 4 = l 34 * х 3 + l 54 * х 5 (4) ( l 54 + l 53 )* х 5 = l 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 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 2 2 2 2 2 2 4 4 4 4 4 4
2 6 - - - - - 12 - - - - - 24 - - - - -
3 - - 6 - - - - - 12 - - - - - 24 - - -
4 - - - - 3 - - - - - 6 - - - - - 12 -
5 - - - - - 2 - - - - - 4 - - - - - 8
6 1 2 - 2 - - 2 4 - 6 - - 4 8 - 12 - -
Количество партий 4 4 4 4 4 4 2 2 2 2 2 2 1 1 1 1 1 1
Т д = 27 Решение В результате применения программы « APOSUM » было получено 3 варианта решения. Время изготовления заказа в каждом из них составляет соответственно 41, 48 и 52 единицы. Ближе всего к нормативному времени находится вариант 1. Количество переналадок при этом равно 19, что больше, чем в других вариантах (10 и 5), однако решающее значение имеет время.

Изменяя длительность обработки изделий, можно уменьшить время с 41 до 29 единиц.

Измененная длительность обработки изделий представлена в таблице 5.2. Таблица 5.2. Длительность обработки изделий

Ст. 1 Ст. 2 Ст. 3 Ст. 4 Ст. 5 Ст. 6 Объем заказа Длит. обраб.
Изделие 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 4 5 6 7 8 9 10 11
Продукция 4 1 4 3 4 2 1 3 2 4 2
Время запуска 0 1 2 3 4 5 6 7 8 9 10
Время выпуска 4 9 12 10 15 17 18 16 20 23 25
Длительность обработки 4 8 10 7 11 12 12 9 12 14 15
Пролеживание 0 0 6 0 7 9 4 2 9 10 12
Продолжение
№ п/п 12 13 14 15 16 17 18 19 20 21 22 23 24
Продукция 2 1 3 5 5 6 6 1 3 5 6 6 5
Время запуска 11 12 13 14 15 16 17 18 19 20 21 22 23
Время выпуска 27 28 22 18 21 19 21 29 28 24 24 26 27
Длительность обработки 16 16 9 4 6 3 4 11 9 4 3 4 4
Пролеживание 13 8 2 0 2 0 1 3 2 0 0 1 0
Время и очередность запуска и выпуска каждой партии продукции, последовательность и время использования каждого оборудования проиллюстрированы далее графиком Ганта.

оценка стоимости склада в Твери
оценка станка в Орле
оценка машин для наследства в Брянске

Подобные работы

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

echo "Перечень работ и их характеристики представлены в таблице 1.1. Таблица 1.1 Перечень работ и их характеристики Работы Непосредственно предшествующие работы Продолжительность работы, недель

 
© 2011-2012, e