Классы
Предметы

Логистика

Дополнительный материал: «Искусственные реки - каналы» - https://goo.gl/gioDjG

На этом уроке мы поговорим про коммуникации. И про задачу их организации, которая ещё называется логистикой.

Исторические сведения

Историю можно рассматривать с разных ракурсов. Например, с точки зрения развития коммуникаций племена объединялись в нации из-за общения друг с другом. Первые цивилизации (см. рис. 1) возникали именно там, где существовали дороги или их можно было построить. Под существованием дорог можно подразумевать наличие воды. Именно реки были системами связи между различными общностями. Для того чтобы общаться друг с другом, мы придумали язык, письмо и т.ьд. Но для того чтобы перевозить товары, нужны были коммуникации.

Рис. 1. Первые цивилизации

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

Одна из первых цивилизаций, с которой ученики знакомятся в школе, – Римская империя (см. рис. 2). Это круг около большого водного канала – Средиземного моря, название которого образовано от слов «среди земель». Всегда, когда говорят про Рим, у историков возникает образ строителей, так как, помимо великих войн, римляне были отличными строителями и в первую очередь строили дороги. В основном эти дороги связывали провинции с Римом (первым так называемым хабом): «все дороги ведут в Рим».

Рис. 2. Римская империя

Может возникнуть вопрос: почему цивилизации возникали именно вдоль рек? Понятно, что реки в то время являлись удобным способом транспортировки. Но всё равно возникают вопросы: ведь можно было в каком-то месте Нила начать развиваться, а затем уходить дальше от реки. Решив простую математическую задачу, можно интуитивно понять, почему развитие происходило именно вдоль рек, а не вглубь суши.

Грубая формулировка данной задачи будет звучать следующим образом (см. рис. 3): по реке скорость передвижения в несколько раз больше, чем по суше (или, например, стоимость транспортировки по реке будет в несколько раз дешевле):

 – время, за которое необходимо доставить товар из любой точки до окраины поселения. Тогда понятно, что расстояние, которое мы можем пройти по реке за это время, будет равняться: , а по суше – . Очевидно, что .

Рис. 3. Математическая модель

Вычислим, в какую точку мы сможем переместить товар от начала координат за время . Пусть по реке мы будем двигаться , а по суше, соответственно, . Выпишем систему уравнений для определения координат точки, в которой мы окажемся:

 –уравнение прямой

 –точка

 –точка

Получим, что данная фигура будет являться ромбом (см. рис. 4). За время  товар можно доставить в любую точку в пределах данного ромба.

Рис. 4. Геометрическим решением полученного уравнения будет ромб

При большом значении параметра  ромб будет вытянутым, а значит, есть смысл строить поселения только вдоль реки. Или, наоборот, при малом значении параметра ромб будет сжиматься, а значит, можно уходить дальше от реки (см. рис. 5).

Рис. 5. Вид ромба в зависимости от параметра

Очень часто мы измеряем расстояние временем, например « минут до магазина», « дня пути» и т. д. В такой метрике, где расстояние – это время, ромб примет форму окружности (см. рис. 6).

Рис. 6. В метрике, где расстояние – это время, ромб примет форму окружности

Возникновение городов

Рассмотрим, почему коммуникации связаны с дорогами, расстоянием и способом его преодоления. Посмотрим, как происходило возникновение городов. Представим, что на каком-то пространстве живут люди. Им нужно обмениваться товарами, а значит, они будут тянуться друг к другу (см. рис. 7).

Рис. 7. «Притяжение» людей для обмена товарами

Аналогично как глина трескается при высушивании (см. рис. 8), так и силы притяжения будут приводить к разрывам и возникновению границ. Одним выгоднее везти свой товар в точку А, а другим – в В. Так и возникают города (см. рис. 9).

 

Рис. 8. Трещины на глиняном поле

Рис. 9. Возникновение границ

Сила гравитационного притяжения обратно пропорциональна квадрату расстояния между объектами. Естественно, что после возникновения города людям из его окрестностей выгоднее возить свой товар именно туда, а не в соседний город. Тем, кто находится далеко от «рынка», выгоднее создать свой собственный город. Так появляются границы.

Рис. 10. Новгород в XVII веке

 

Понятно, что если территория не является плоской (присутствуют горы), то границы могут сдвигаться, а городов, которые занимают малую площадь, очень много (см. рис. 11).

Рис. 11. Возникновение городов в гористой местности

Например, на Кавказе более десятка языков, так как из одного горного района добраться до другого сложно, общение между ними затруднено, а значит, возникает множество наций (см. рис. 12). С другой стороны, на равнинах возникают большие нации, например Россия, Франция и т. д. Всё это фактически связано с задачей коммуникации.

Рис. 12. Нации, живущие на территории Кавказских гор

Раз появились города и границы, возникла необходимость организовать сообщение между этими городами. Город – это некая общность, но она тоже не может быть самодостаточной. Или, например, в одном из городов начали производить качественный товар в большом объеме, поэтому нужно было искать другие рынки сбыта. Происходит разделение труда между городами, появляется необходимость строительства дорог между ними для обмена товарами. Причем возникает вопрос, как передвигаться, чтобы затратить наименьшее количество времени, усилий и т. д. Возникает классическая задача коммивояжёра.

Задача коммивояжёра

Есть N городов, между ними дороги, у каждой дороги есть своя «цена» (например, время на её преодоление, экономические затраты и т. д). Нужно побывать в каждом городе хотя бы по одному разу. Задача – составить маршрут, удовлетворяющий условию задачи и имеющий наименьшую возможную «цену» (см. рис. 13).

Рис. 13. Иллюстрация к задаче коммивояжёра

Задача кажется не очень сложной для малого количества городов. Например, если  города, можно просто перебрать варианты (см. рис. 14). Но для большого значения N подобрать ответ практически невозможно.

Рис. 14. Решение задачи коммивояжёра для  городов


Трансвычислительные задачи

Почему такие задачи возникают? На самом деле, есть физическое обоснование того, что компьютер на килограмм своей массы не может произвести больше определенного количества операций в секунду. Это следует из уравнения Эйнштейна.

Компьютер массой  килограмм не может произвести больше чем  операций в секунду. Соответственно, понятно, что если мы берем компьютер даже массы, равной массе Земли, он не  может произвести больше чем  операций в секунду.

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

Сколько же операций нужно сделать для решения задачи коммивояжёра? Сложность задачи пропорциональна  (см. рис. 15, 16). Добавление каждого следующего города увеличивает количество маршрутов или переборов в разы. Таким образом, разница сложности решения задачи для  и для  городов – колоссальная!

Рис. 15. График  для небольшого значения

Рис. 16. График  при увеличении значения n

С другой стороны, сложность комбинаторных задач мы используем при нумерации машин или телефонов: добавление всего одного разряда добавляет колоссальное количество абонентов. А вот в задаче с поиском оптимального маршрута это, конечно, мешает.


Решение данной задачи будет полезно также, например, для организации торговли в магазинах. Если в городе есть  супермаркетов, то между ними нужно организовать оптимальную доставку товаров со склада. Иначе затраты на транспортировку будут высокими и стоимость товара будет выше, чем у конкурентов. Тот, кто первый оптимизирует маршрут, сможет снизить цену и окажется в выигрыше.

Рис. 17. Пример задачи коммивояжёра для доставки товаров

Для  городов задача решается с помощью компьютера, даже простым перебором. Можно построить все варианты, вычислить стоимость каждого маршрута и выбрать оптимальный вариант. Но оказывается, что уже даже для  городов эта задача не просто не может быть решена персональным компьютером, она в принципе не может быть решена никаким мыслимым компьютером, который мы можем построить в обозримом будущем.

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

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

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

Рис. 18. Декомпозиция


Декомпозиция

Декомпозиция кажется каким-то изобретением, придуманным учеными, но на самом деле, мы все время её используем для решения повседневных задач. Например, когда пробуем распланировать месяц своей жизни. Это абсолютно нерешаемая задача, если требуется сделать это оптимальным способом. Мы разбиваем месяц на части (дни) и т. д. Решая физическую задачу, мы тоже отвлекаемся от исходной формулировки, говорим, что важно, а что нет.

Рис. 19. Сила притяжения к соседней полке с книгами не принципиально влияет на математический маятник

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

Но главная сложность всегда состоит как раз в том, чтобы выделить, построить эту идеальную модель, которую потом можно будет точно рассчитать. В транспортной и логистической задачах этот вопрос стоит особенно остро, потому что математическая постановка вроде бы ясная, но даже в четкой математической модели задача точно не может быть решена. Именно тогда возникает такой приём, как декомпозиция.

Каждый сталкивался со сложностью планирования. Если бы мы могли выделить замкнутую систему, то тогда планирование дня в принципе было бы возможно и каждый мог бы более или менее за ограниченное время спланировать перебором свой идеальный день. Но каждый понимает, что возможны два исхода. Когда все идеально совпадает без какой либо задержки, ты всё успеваешь и кажется, что за день ты сделал все дела на год вперёд. А на следующий день совсем наоборот, потому что кто-то задержался, кто-то не пришёл и т. д. Если мы захотим учесть всех тех, с кем мы сотрудничаем, включить их в нашу задачу планирования или тот же транспорт, от которого наши планы тоже зависят, то нужно будет включить и всё то, что на них в свою очередь будет влиять. Таким образом, система расширится до планеты Земля, активности Солнца и притяжения каких-то далеких звёзд (см. рис. 20).

Рис. 20. Иллюстрация примера

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


 

Хабы

Хаб (анг. hub, буквально «ступица колеса», «центр») – узел какой-то сети.

Рис. 21. Возникновение хаба

Самый простой пример хаба – это рынок в торговле, доска объявлений – информационный хаб.

Рис. 22. Рынок как пример хаба

Рис. 23. Доска объявлений – информационный хаб


Примеры хабов

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

Рис. 24. Ходы муравейника (заливка цементом) флоридского муравья жнеца

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

Что же делают муравьи? Они создают колонии (ветки) от основного муравейника, поэтому есть опасность, что они станут чужими – будут войны, полосы отчуждения, а значит, они потеряют много земли. Для того чтобы этого не произошло, муравьи перетаскивают друг другу личинки, чтобы быть похожими друг на друга (см. рис. 25).

Рис. 25. Муравьи перетаскивают друг другу личинки, чтобы быть похожими друг на друга

Носят личинки они в большой хаб, где те перемешиваются и дальше разносятся по другим колониям (см. рис. 26).

Рис. 26. Хаб с личинками внутри муравейника

Еще один пример хаба – это деньги. Фактически деньги – это некий общий инструмент для оценки того, сколько стоит произведённый товар. Мы обмениваемся не товарами, а именно деньгами (см. рис. 27).

Рис. 27. Деньги – один из примеров хаба

Хабы присутствуют не только в логистике, но и в реальной жизни. Эта идея используется повсеместно. Подводя итог, хабы – это место (возможно, виртуальное), куда все привозят свои товары или информацию, и таким образом обмен происходит быстрее.


Примеры хабов – склады

Склады – это тоже примеры хабов. Со всех концов свозятся туда товары, которые нужны данному городу. Уже там они перераспределяются, подъезжают машины и развозят их по нужным точкам.

Рис. 28. Склады – один из примеров хаба

Рис. 29. Склады – один из примеров хаба

Рис. 30. Склады – один из примеров хаба

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


Рис. 31. Иллюстрация формулировки задачи

Рассмотрим конкретную задачу. Я, как перевозчик, хочу доставить товар в каждый город самым выгодным образом. Я могу организовать поставку из одного города в другой ежедневно, тогда для  городов мне понадобится  рейсов. А можно поступить по-другому – выбрать один город и назначить его хабом (см. рис. 32), то есть в город будут свозиться посылки из остальных  городов и потом из него же развозиться.

Рис. 32. Назначим один из городов хабом

По такому принципу работает почта Overnight – доставка посылок за ночь. Грубо говоря, вечером вы отдаете посылку, ночью её доставляют в центр (хаб), и утром посылки перераспределяются и отправляются в пункт назначения. Выгода такой доставки в том, что из одного города в другой может быть слабый поток посылок, тогда отправлять машину (или самолёт) каждый день просто не выгодно. Другое дело, когда со всех городов набирается нужное количество товара для загрузки машины или самолёта.

Рис. 33. Круглосуточный почтовый киоск-автомат (Техас, США)

Если посчитать количество рейсов с наличием хаба, то их будет существенно меньше: . Если рассмотреть эту зависимость в общем виде, то получим следующий график (см. рис. 34) для большего количества точек (городов).

Рис. 34. Зависимость количества рейсов от числа городов при отсутствии и наличии хаба

Идея хаба позволяет существенно уменьшить затраты и решать задачу с организацией передвижения. Конечно, решая её таким образом, мы выходим за рамки задачи коммивояжёра, так как, по условию, мы должны были побывать в каждом городе один раз, а в хаб мы будем каждый раз возвращаться из города. Однако именно расширение задачи позволяет её решить, причём достаточно просто и выгодно.

Идея хабов также близка к идее решения транспортной задачи.


Транспортная задача

Транспортная задача (задача Монжа-Канторовича) – математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приёмникам с минимизацией затрат на перемещение.

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

Рис. 35. Транспортная задача

Для математической модели мы считаем, что количество произведённого товара совпадает с количеством, которое потребляют, то есть нет недостатков или излишков товара. Также мы знаем стоимость доставки из произвольной точки в любую другую.

Задача: как оптимально развести товар по точкам сбыта и потратить при этом наименьшее количество денег?

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

Транспортная задача решаема. В этом огромная заслуга нашего соотечественника, математика Л.В. Канторовича, который придумал симплекс-метод.

Рис. 36. Л.В. Канторович (1912–1986)

Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Рис. 37. Иллюстрация к определению симплекс-метода

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

Муравьи начинают своё движение от муравейника и хотят найти источник пищи. Когда муравей находит этот источник, на обратном пути он оставляет след из феромонов. Тогда следующие муравьи, которые идут искать пищу, с большой долей вероятности попадут на дорожку с этим запахом, пойдут по ней же и найдут пищу.

Рис. 38. Дорожки из феромонов

Тогда понятно, что если первые муравьи нашли несколько дорожек, то рано или поздно почти все муравьи буду двигаться по этим дорожкам. Но феромон имеет такое свойство, как испарение. И, соответственно, если путь был длинным, то, поскольку плотность движения по нему будет, очевидно, меньше, чем по короткому пути, запах будет ослабевать, а на коротких путях, наоборот, будет усиливаться. Таким образом, через некоторое время все муравьи будут двигаться по самому короткому пути (см. рис. 39). Таким образом муравьи находят самый короткий путь к источнику пищи.

Рис. 39. Оптимальный путь от муравейника до источника пищи

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


 

Декомпозиция

Вернёмся к такому методу решения, как декомпозиция. Данный метод также подходит для приближённого решения задачи коммивояжёра. Если у нас есть, например,  городов, тогда мы можем разбить их на  групп по  городов. Решить задачу для каждой группы, а дальше подумать, как соединить маршруты каждой из групп между собой.

Рис. 40. Декомпозиция

Сложность задачи заключается в том, что непонятно, каким именно образом необходимо разбить города на группы. Вариантов таких разбиений очень много, поэтому, если все их перебрать, получится опять-таки исходная задача. Нужно понимать, что в данном случае мы говорим уже не об оптимальном решении, а о достаточно хорошем. Это решение будет эффективным, но, возможно, не самым оптимальным.

Поэтому если смягчить условие задачи коммивояжёра поиском пути, который будет отличаться от оптимального не больше чем на 5–10 %, то такую задачу уже можно решить с помощью компьютера.

Как тогда понять, с чем сравнивать полученное решение, если точно решить задачу мы не можем? Однако можно достаточно точно выполнить оценку снизу. Всё-таки это большая разница, когда мы говорим, что стоимость перевозки будет не меньше  рублей, или же когда утверждаем, что стоимость оптимального пути будет  рубля.

Рис. 41. Путешествие с одной вершины на другую

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

Например, Госплан при социализме в нашей стране, который решал, что будет произведено в ближайшие  лет, вплоть до гвоздя и зонтика. Казалось, что всё это можно вычислять и так удобнее. Такая кажущаяся ясность многих увлекала, и многие считают до сих пор, что для построения социализма не хватило только мощности вычислительных машин.

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

Рис. 42. Пример декомпозиции – сеть магазинов

Не всегда декомпозиция является лучшим решением. Например, на рисунке 43 показан пример расположения аптек, которые торгуют одними товарами и приблизительно по одной цене. Так происходит из-за того, что решает задачу каждая группа отдельно, не учитывая интересы других. Однако конкуренция чаще всего заставляет убирать с рынка такие неэффективные решения. Фактически экономику и бизнесменов (аналитиков) можно считать деталями большой вычислительной машины, которой руководит государство. Именно оно ставит сложные задачи и руководит крупными проектами.

Рис. 43. Расположение аптек

Заключение

Сегодня мы говорили о логистической задаче, её математическом проявлении и влиянии на развитие общества. Мы увидели, что некоторые задачи имеют простые и точные формулировки, но решить их абсолютно точно невозможно, только в некотором приближении.