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

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

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

Математическая модель Примем за 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 3 + x 7 + x 8 = 8 + 11 + 4 = 23 Уменьшение времени выполнения работы, как правило, связано с увеличением затрат. В таблице 1.3 определим прирост затрат при уменьшении времени реализации проекта.

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

Затраты на реализацию проекта возросли на 124,8 тыс. $. Увеличение затрат произошло, в основном, из-за работы G , по которой наблюдается наибольшее сокращение времени в сочетании с наивысшим коэффициентом затрат на выполнение работы. Из-за сокращения критического пути проект будет введен в эксплуатацию на 5,4 недели раньше. Т. к. прибыль за неделю составляет 100 тыс. $, то за этот срок она составит 100 тыс. $ * 5,4 = 540 тыс. $ . В результате дополнительная прибыль с учетом возрастания затрат на проведение работ составит 540 тыс. $ - 124,8 тыс. $ = 415,2 тыс. $ Задание №2 Тема: Графы Задача о коммивояжере Имеется 4 пункта. Время переезда из пункта I в пункт j представлено в таблице 2.1. Таблица 2.1 Исходные данные

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

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

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

Поэтому система условий-ограничений выглядит следующим образом. х 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 Исходная матрица

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

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

Система уравнений Колмогорова для данной задачи в общем виде выглядит следующим образом: ( 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. Исходная матрица

Задание №5 Тема: Имитационное моделирование Задача: Расчет и анализ графика запуска-выпуска продукции в цехе мелкосерийного производства В таблице 5.1 представлены технологические маршруты изготовления различных видов продукции, а также директивное время исполнения заказов (в условных единицах) и нормы затрат времени на обработку одной партии продукции на каждом из типов оборудования. Общая масса заказа по каждому виду продукции разбивается на N партий так, что для каждого вида продукции выполняется условие: Общая масса заказа = (масса партий)*(число партий) Нормы затрат времени в каждом эксперименте имитационного моделирования обратно пропорциональны числу партий.

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

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

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

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

Таблица 5.3. График запуска-выпуска продукции