3298

33

При решении задачи приходится удвоить некоторые ребра графа для того, чтобы обеспечит четность всех его вершин (рис. 7).

Рис. 7. Дополненный граф G*

Используя алгоритм Флери, находим найти эйлеров цикл графа G*, за-

писывая проходимые вершины в массив P[i] и соответствующий ему опти-

мальный цикл первоначального графа G.

P[i]={1,2,4,6,9,10,12,11,10,6,7,8,10,11,8,7,5,3,4,5,7,4,2,3,1}. Вес полученного цикла равен 281.

Маршрут коммивояжера

В транспортной логистике чрезвычайно часто возникают задачи, когда

прохождение транспорта по всем дорогам обслуживаемой сети вовсе не обя-

зательно, однако важен факт заезда в каждый из обслуживаемых объектов.

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

вана так называемая задача коммивояжера, поставленная еще в 1934 году и ставшая впоследствии весьма знаменитой.

Введем некоторые термины. Объекты пронумерованы числами j, j 1, N . Тур коммивояжера может быть описан циклической перестановкой t T , t ( j1, j2 ,..., jN , j1) , причем все j1, j2 ,..., jN – разные номера. Повторяющийся в начале и конце j1 показывает, что перестановка зациклена. Расстоя-

ния между парами вершин cik c ji , jk образуют матрицу С. Задача состоит в том, чтобы найти тур t T , минимизирующий функционал

В своей области (оптимизации дискретных задач) задача коммивояжера ЗК служит своеобразным полигоном, на котором испытываются все новые методы. При помощи алгоритмов, решающих эту задачу, находят решение большого количества родственных задач. К таким задачам относится задача сбора почтовых отправлений из ящиков, которая может в большинстве слу-

чаев быть поставлена не как задача китайского почтальона, а именно как за-

дача коммивояжера (тогда почтовые ящики принимаются за вершины сети обслуживаемых объектов). Составление графика движения школьного авто-

буса по заданным остановкам имеет ту же основу: необходимость заезда на каждую остановку и желательность минимизации суммарно проезжаемого расстояния.

В ряде отраслей промышленности, особенно фармацевтического и хи-

мического плана, возникает внешне совсем иная задача планирования произ-

водства. Допустим, нужно произвести ряд продуктов, используя единствен-

ный тип аппаратуры или реактор. Аппарат должен (или не должен) быть пе-

ренастроен (очищен) после того, как произведен продукт pi, но до того, как началось производство продукта pj. Допустим, стоимость перенастройки ап-

паратуры постоянна и не зависит от сочетания только что произведенного и готовящегося к производству продукта (или просто неизвестна и берется ка-

кое-то усредненное ее значение). Разумеется, не требуется никаких затрат,

если перенастройка аппаратуры не нужна. Пусть такие продукты по техноло-

гическим соображениям производятся в некотором цикле, т.е. после произ-

водства N продуктов снова возобновляется производство в том же фиксиро-

ванном порядке. Возможна внешне совсем иная ситуация, которая однако решается тем же самым методом. Возникает вопрос, может ли быть найдена циклическая последовательность производства продуктов pj, не требующая перенастройки аппаратуры? Если такой последовательности не существует,

35

то какова должна быть очередность производства продуктов с наименьшими затратами на перенастройку?

НЕОБХОДИМЫЕ УТОЧНЕНИЯ

Цикл, проходящий через все вершины неориентированного графа ров-

но по одному разу, называется гамильтоновым циклом. Цикл, проходящий через все вершины ориентированного графа ровно по одному разу, называет-

ся гамильтоновым контуром. Незамкнутый гамильтонов цикл (контур) назы-

вается "гамильтоновой цепью" ("гамильтоновым путем").

Обычно под понятием веса ребра подразумевают расстояние cij c i, j , откуда с точки зрения логики следует выполнение нескольких ус-

ловий:

1.Неотрицательность, т.е. для всех i, j V : cij 0 , cii 0 .

2.Симметричность, т.е. для всех i, j V : cij cji .

3. Соответствие неравенству треугольника, т.е. для всех i, j,k V :

cij cjk cik .

В математической постановке говорится о произвольной матрице С.

Сделано это потому, что имеется много прикладных задач, которые описы-

ваются основной моделью, но, всем условиям не удовлетворяют. Особенно часто нарушается условие симметричности (например, если cij – не расстоя-

ние, а плата за проезд, то стоимость железнодорожного билета Екатеринбург-

Москва отличается по цене от билета Москва-Екатеринбург). Поэтому, во-

обще говоря, различают два варианта задачи коммивояжера: симметричную задачу, когда условие симметричности выполнено (ей соответствует модель в виде неориентированного графа) и несимметричную в противном случае (она формализуется в терминах ориентированных графов). Условие неотрица-

тельности и правило треугольника будем считать выполненными по умолча-

нию.

ПОСТАНОВКА ЗАДАЧИ

1.Дан ориентированный граф G, требуется найти в нем гамильтонов

36

цикл или все существующие гамильтоновы циклы.

2.Дан полный ориентированный граф G, дугам которого приписаны произвольные веса C cij . Найти гамильтонов цикл с наименьшим сум-

марным весом (минисуммная постановка).

3.Дан полный ориентированный граф G, дугам которого приписаны произвольные веса C cij . Найти гамильтонов цикл, в котором самая длин-

ная дуга минимальна (минимаксная постановка).

Рис. 8. Решение задачи коммивояжера Естественно, если граф не полный, то при необходимости его можно

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

В общем случае, точное решение задачи коммивояжера – это перебор всех возможных гамильтоновых циклов. Его можно либо усовершенствовать для снижения размерности, либо заменить на приближенные или эвристиче-

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

Решение задачи коммивояжера для 40 точек приведено на рис. 8.

37

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1.Классификация моделей.

2.Математические модели.

3.Материальные модели.

4.Преимущества и недостатки математического моделирования.

5.Преимущества и недостатки имитационного моделирования.

6.Однокритериальная и многокритериальная оптимизация.

7.Методы многокритериальной оптимизации.

8.Экспертные методы оценки параметров.

9.Транспортная задача. Еѐ постановка.

10.Математическая модель транспортной задачи.

11.Методы построения начального плана.

12.Метод потенциалов в транспортной задаче.

13.Ориентированные и неориентированные графы.

14.Способы задания графов.

15.Взвешенные графы.

16.Путь и цикл в графе.

17.Элементы сетевого графика.

18.Временные параметры сетевого графика.

19.Критический путь в сетевом графике.

20.Линейный график работ.

21.Задача прокладки коммуникаций в постановке Прима.

22.Задача прокладки коммуникаций в постановке Краскала.

23.Задача Штейнера на плоскости.

24.Задача Штейнера на графах.

25.Поиск кратчайшего пути в графе.

26.Алгоритм Дейкстры.

27.Поиск пути в ориентированном графе.

28.Минимальное дерево.

29.Задача размещения регулярных пунктов обслуживания.

30.Медиана графа.

31.Задача размещения экстренных пунктов обслуживания.

32.Центр графа.

33.Задачи объезда.

34.Эйлеров и гамильтонов цикл в ориентированном и неориентированном графе.

35.Задача китайского почтальона.

36.Задача коммивояжера.

38

Библиографический список А) Основная литература

1 Логистика: модели и методы : [Электронный ресурс]учеб. пособие / П.В. Попов, И.Ю. Мирецкий, Р.Б. Ивуть, В.Е. Хартовский ; под общ. и науч. ред. П.В. Попова, И.Ю. Мирецкого. — М. : ИНФРА-М, 2017. — 272 с..- ЭБС "Знаниум".

2. Стерлигова А. Н. Управление запасами в цепях поставок: Учебник/Стерлигова А. Н. - М.: НИЦ ИНФРА-М, 2016. - 430 с.: ЭБС "Знаниум".

Б) Дополнительная литература 1 Логистика. Управление цепью поставок: Учебник / Уотерс Д. -

М.:ЮНИТИ-ДАНА, 2015. - 503 с.: – ЭБС "Знаниум".

40

Яковлев Андрей Васильевич

Логистика: модели и методы

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

38.04.02 - Менеджмент

Редактор

Воронежский государственный лесотехнический университет

_____________________________________________________________

РИО ВГЛТУ 394613 г. Воронеж, ул. Тимирязева, 8