дом робіт цеху. Умовно будемо вважати це вимога задоволеним.
Перерахуємо основні економічні показники, пов'язані з роботою робота:
1. Прямі витрати
1.1 Одноразові - По доставці машин.
1.2 Амортизаційні суми.
2. Накладні витрати. Заробітна плата робітників.
3. Умовно-постійні витрати.
Зміст службових приміщень.
Пожежної і сторожової охорони.
Побутове благоустрій цеху і підсобних приміщень.
Витрати, пов'язані з технікою безпеки.
4. Непрямі витрати.
Витрати на утримання обслуговуючого персоналу.
Ремонтних майстерень. Витрати на ремонт.
Аналізуючи роботу робота, можна сказати, що основний економічний показник, який можна регулювати (і за рахунок цього домогтися більшого економічного ефекту) - це амортизаційні суми, пов'язані з переміщенням машин по цеху, будівельної майданчику і т.п.
Таким чином, слід по можливості скоротити шлях, прохідний роботом.
Отже, задачу зменшення грошових витрат ми звели до задачі пошуку шляху мінімальної довжини. Маємо задачу комівояжера.
5.2 Виявлення основних особливостей розглянутого об'єкта
Будемо вважати, що у нас є зібрані статистичні дані, що показують час руху робота між агрегатами цеху (Див. табл. 1). Тут - номери агрегатів. - Відповідає часу руху вираженому в деяких умовних одиницях. Таблиця симетрична. Незаповнені поля говорять про неможливість даного маршруту з якихось причин.
Таблиця 1.
1
2
3
4
5
1
*
4
2
5
2
*
1
9
3
*
3
4
4
*
11
5
*
5.3 Приклад рішення задачі комівояжера
Маємо В«чистоВ» математичну задачу, яку вирішимо, використовуючи метод гілок і меж.
У симетричному графі, зображеного на рис. 3, визначити найкоротший шлях з вершини 1 у вершину 2, що проходить через усі вершини графа тільки по одному разу.
Крок 0. Значення. Пометим вершину 1 ознакою
Крок 1. Пометим вершину 3 ознаками
Рис. 3. Крок З. Маємо.
Крок 1. Пометим наступні вершини: вершину 4 - ознаками вершину 5 - ознаками
Крок 3. Маємо.
Крок 1. Пометим вершину 5 ознаками
Крок 3. Маємо.
Крок 1. Пометим вершину 3 ознаками
Крок 3. Маємо.
Крок 1. Пометим вершину 4 ознаками
Крок 1. Пометим вершину 2 - ознаками так як, то шуканий шлях побудований.
Крок 2. Шуканий шлях складає послідовність вершин 1, 5, 3, 4, 2.
Загальне витрачається час в дорозі складе 13.
Висновки
У даній роботі ми познайомили читача з основними поняттями теорії графів, дали уявлення про задачі комівояжера, описали метод гілок і меж. Також привели приклад використання методу гілок і меж для розв'язування задачі комівояжера.
Ще раз відзначимо, що завдання комівояжера є однією з найбільш найважливіших завдань у теорії графів. Можливість подання (записи) різних виробничих
Список літератури
1. М. 1998.
2.
3. М. 1969.
4. ім.
5.
