Реферат: Сетевое моделирование при планировании. Задача о коммивояжере...
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 | 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
| № |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
х10 |
x11 |
x12 |
Св.чл. | Зн |
| 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 |
