Сетевое моделювання у разі планування. 
Завдання про коммивояжере

Московський міської інститут управління Уряди Москвы.

Лабораторні работы.

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

«Економіко-математичні методи лікування й модели».

Підготувала студентка V курсу Євдокимова Є. Д.

Викладач — Новикова Р. М.

Москва.

Завдання № 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 | |З |- |8 |11 |160 |18 | |D |A |9 |12 |190 |35 | |E |З |5 |8 |150 |28 | |F |B, E |4 |6 |130 |25 | |G |З |11 |15 |260 |55 | |H |F, G |4 |6 |90 |15 |.

Задание:

1. Зобразити проект з допомогою мережевий модели.

2. Визначити найбільш ймовірну тривалість кожної работы.

3. Знайти все повні шляху мережного графіка, визначити критичний шлях, очікувану тривалість виконання проекту й повну вартість всіх работ.

4. Розробити математичну модель оптимізації процесу реалізації проекта.

Мережний график.

D.

A.

H.

B F.

З 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НВ З= (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НВ З + tНВ G + tНВ H = 9,8 + 13,4 + 5,2 =.

28,4.

IV. 1 — 4 — 3 — 6 — 5. Довжина: tНВ З + tНВ E + tНВ F + tНВ H = 9,8 +.

6,8 + 5,2 + 5,2= = 27.

Максимальна довжина шляху, рівна 28,4 тижня відповідає шляху III, на якому лежать роботи З, 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).

Функція мети: 22×1 + 28×2 + 18×3 + 35×4 + 28×5+ 25×6 + 55×7 + 15×8 + 100×9 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 | |З |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.

Вихідні данные.

|Из пункту і |У пункт 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).

Функція мети: 8×1 + 8×2 + 6×3 + 4×4 + 6×5 + 12×6 + 10×7 + 12×8 + 18×9 + 8×10 + 10×11 + 4×12 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.

S1.

S4.

S3.

S2.

S5.