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

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

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

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

Подготовила студентка 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<sub/>+tНВ D<sub/>=5,2+ 10,8 = 16

II.     1– 3 – 6 – 5. Длина: tНВ B<sub/>+ tНВ F<sub/>+ tНВ H<sub/>= 8,2 + 5,2 +5,2 =18,6

III.     1 – 4 – 6 – 5.Длина: tНВ C<sub/>+ tНВ G<sub/>+ tНВ H<sub/>= 9,8 + 13,4 + 5,2= 28,4

IV.    1 – 4 – 3 – 6 – 5.Длина: tНВ C<sub/>+ tНВ E<sub/>+ tНВ F<sub/>+ tНВ H<sub/>= 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№

x1

x2

x3

x4

x5

x6

x7

x8

x9

Знак Св. чл. 1 1 ³ 4 2 1 ³ 7 3 1 ³ 8 4 1 ³ 9 5 1 ³ 5 6 1 ³ 4 7 1 ³ 11 8 1 ³ 4 9 1 £ 6 10 1 £ 9 11 1 £ 11 12 1 £ 12 13 1 £ 8 14 1 £ 6 15 1 £ 15 16 1 £ 6 17 1 1 1 £ 28,4 18 1 1 1 1 £ 28,4 19 1 1 1 1 £ 28,4 20 1 1 1 1 1 £ 28,4 Ф. ц. 22 28 18 35 28 25 55 15 100 max Решение

x1 = 6

x2 = 9

x3 = 8

x4 = 12

x5 = 7

x6 = 4

x7 = 11

x8 = 4

x9 =5,4

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

x3 + x7 + x8 = 8+ 11 + 4 = 23

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

Таблица 1.3

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

Работа х

tHB

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 8 8 6 2 4 6 12 3 10 12 18 4 8 10 4

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

/>

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

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

Обозначимза 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

№

x1

x2

x3

x4

x5

x6

x7

x8

x9

х10

x11

x12

Св.чл. Зн 1 1 1 1 1 = 2 1 1 1 1 = 3 1 1 1 1 = 4 1 1 1 1 = 5 1 1 1 1 = 6 1 1 1 1 = 7 1 1 1 1 = 8 1 1 1 1 = Фц. 8 8 6 4 6 12 10 12 18 8 10 4 min Исходная матрицаРешение

x3 = 1

x5 = 1

x7 = 1

x8 = 0

x11 = 1

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

/>

Задание №3

Тема: Графы

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

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

/>

a/>/>/>/>исток                                                                                                                                             a/>/>/>/>сток

/>

Пропускнаяспособность  Sij<sub/>, тыс. тонн

S12= 4

S13= 7

S14= 8

S23= 3

S25= 5

S34= 8

S35 = 9

S45 = 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 1 = 2 1 -1 -1 = 3 1 1 -1 -1 = 4 1 1 -1 = 5 1 1 1 -1 = 6 1 £ 4 7 1 £ 7 8 1 £ 8 9 1 £ 3 10 1 £ 5 11 1 £ 8 12 1 £ 9 13 1 £ 9 Ф. ц. 1 max Решение

х1= 4

х2= 7

х3= 8

х5= 4

х7= 7

х8= 8

х9= 19

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

/>

Задание №4

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

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

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

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

/>

Таблица 4.1

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

Интенсивность потоков (переходов)

l12

l13

l21

l32

l34

l45

l53

l54

3 2 1 3 2 2 3 1

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

Примемза х1, х2, …, х5 предельные вероятностисостояний в стационарном режиме пунктов S1, S2, …,S5 соответственно.Произведение вероятности состояния на интенсивность исходящих из этого пунктапотоков равна произведению интенсивностей входящих потоков на вероятность состоянияв стационарном режиме пунктов их отправления. Система уравнений Колмогорова дляданной задачи в общем виде выглядит следующим образом:

(l13 + l12 )* х1= l21 * х2(1)

l21 * х2= l12 * х1+l32 * х3(2)

(l32 + l34 )* х3= l13 * х1+ l53 * х5(3)

l45 * х4= l34 * х3+l54 * х5(4)

 (l54 + l53 )* х5= l45 * х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 1 = 2 -3 1 -3 1 = 3 -2 5 -3 1 = 4 -2 2 -1 1 = 5 -2 4 1 = 6 1 1 1 1 1 1 1 = Ф.ц. М 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 1 4 26 Изделие 2 1 2 4 14 Изделие 3 1 6 4 25 Изделие 4 1 3 4 12 Изделие 5 1 3 4 25 Изделие 6 1 2 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 Время запуска 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 Пролеживание 6 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 2 1 3 2 1

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

График Ганта

Задание №6

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

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

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

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

Таблица 6.1.

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

Производящие цехи Потребляющие цехи (коэф. прямых затрат) Конечная продукция №1 №2 №3 №1 0,15 0,10 0,30 100 №2 0,25 0,15 0,25 280 №3 0,30 0,25 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 Ф. ц. -М 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 320 596 Итого

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