Логистика
Видео и статья на тему «Основы рационального поведения»
На этом уроке мы поговорим о коммуникациях и про задаче их организации, которая ещё называется логистикой.
Исторические сведения (00:00)
К изучению истории можно подходить с разных сторон. Например, с точки зрения развития коммуникаций. Первые цивилизации (см. рис. 1) возникали именно там, где существовали дороги или их можно было построить. Речь идёт не только о сухопутном, но и о водном сообщении. Именно реки были основными системами связи между различными обществами. Для того чтобы общаться друг с другом, мы придумали язык, письмо и т. д. Но для того чтобы перевозить товары, нужны были коммуникации.
Рис. 1. Первые цивилизации [МТ1]
История цивилизации – это, по сути, история разделения труда. Если мы производим для себя всё, что необходимо, то нам не нужно ничем и ни с кем обмениваться, а значит, и дороги нам не нужны. Но развитие требует новых материалов или товаров, которые можно получить только в результате обмена.
Одна из первых цивилизаций, с которой ученики знакомятся в школе, – Римская империя (см. рис. 2). Это «круг» около большого водного канала – Средиземного моря, название которого образовано от слов «среди земель». Всегда, когда историки говорят про Рим, то используют образ строителей, так как римляне были не только великими завоевателями, но и отличными строителями. И в первую очередь строили дороги. В основном эти дороги связывали провинции с Римом (первым так называемым хабом), отсюда и поговорка: «Все дороги ведут в Рим».
Одна из первых цивилизаций, с которой ученики знакомятся в школе, – Римская империя (см. рис. 2). Это «круг» около большого водного канала – Средиземного моря, название которого образовано от слов «среди земель». Всегда, когда историки говорят про Рим, то используют образ строителей, так как римляне были не только великими завоевателями, но и отличными строителями. И в первую очередь строили дороги. В основном эти дороги связывали провинции с Римом (первым так называемым хабом), отсюда и поговорка: «Все дороги ведут в Рим».
Рис. 2. Римская империя
Может возникнуть вопрос: почему цивилизации возникали именно вдоль рек? Понятно, что реки в то время являлись удобным способом транспортировки. Но это лишь часть объяснения. Действительно, почему развитие, начавшись, например, в каком-то месте Нила, не продолжалось вглубь суши. Решив простую математическую задачу, можно интуитивно понять, почему развитие происходило именно вдоль рек.
Грубая формулировка данной задачи будет звучать следующим образом (см. рис. 3): по реке скорость передвижения в несколько раз больше, чем по суше (или, например, стоимость транспортировки по реке будет в несколько раз дешевле):
vпо реке = kvпо суше
t – время, за которое необходимо доставлять товар из любой точки до окраины поселения. Тогда понятно, что расстояние, которое мы можем пройти вдоль реки за это время, будет равняться: S₁ = kvt, а по суше – S₂ = vt. Очевидно, что S₂ < S₁.
Грубая формулировка данной задачи будет звучать следующим образом (см. рис. 3): по реке скорость передвижения в несколько раз больше, чем по суше (или, например, стоимость транспортировки по реке будет в несколько раз дешевле):
vпо реке = kvпо суше
t – время, за которое необходимо доставлять товар из любой точки до окраины поселения. Тогда понятно, что расстояние, которое мы можем пройти вдоль реки за это время, будет равняться: S₁ = kvt, а по суше – S₂ = vt. Очевидно, что S₂ < S₁.
Рис. 3. Математическая модель
Вычислим, в какую точку мы сможем переместить товар от начала координат за время t. Пусть по реке мы будем двигаться время t₁, а по суше, соответственно, t - t₁. Выпишем систему уравнений для определения координат точки, в которой мы окажемся:
Получим, что данная фигура будет являться ромбом (см. рис. 4). За время t товар можно доставить в любую точку в пределах данного ромба.
Рис. 4. Геометрическим решением полученного уравнения будет ромб
При большом значении параметра k ромб будет вытянутым, а значит, есть смысл строить поселения только вдоль реки. Или, наоборот, при малом значении параметра ромб будет сжиматься, а значит, можно уходить дальше от реки (см. рис. 5).
Рис. 5. Вид ромба в зависимости от параметра
Часто мы измеряем расстояние при помощи времени, например: «5 минут до магазина», «2 дня пути» и т. д. В такой метрике, где расстояние – это время, ромб примет форму окружности – в любую точку границы мы добираемся за одно и то же время t (см. рис. 6).
Рис. 6. В метрике, где расстояние – это время, ромб примет форму окружности
Возникновение городов (06:00)
Рассмотрим, почему коммуникации связаны с дорогами, расстоянием и способом его преодоления. Посмотрим, как происходило возникновение городов. Представим, что на каком-то пространстве живут люди. Им нужно обмениваться товарами, а значит, они будут тянуться друг к другу (см. рис. 7).
Рис. 7. «Притяжение» людей для обмена товарами
Как глина трескается при высушивании (см. рис. 8), так и силы притяжения будут приводить к разрывам и возникновению границ. Одним выгоднее везти свой товар в точку А, а другим – в В. Так и возникают города (см. рис. 9).
Рис. 8. Трещины на глиняном поле
Рис. 9. Возникновение границ
Естественно, что после возникновения города людям из его окрестностей выгоднее возить свой товар именно туда, а не в соседний город. Тем, кто находится далеко от «рынка», выгоднее создать свой собственный город. Так появляются границы (см. рис. 10).
Рис. 10. Новгород в XVII веке
Понятно, что если территория не является плоской (присутствуют горы), то границы могут сдвигаться, а городов, которые занимают малую площадь, очень много (см. рис. 11).
Рис. 11. Возникновение городов в гористой местности
Например, на Кавказе более десятка языков, так как из одного горного района добраться до другого было сложно, общение между ними было затруднено, а значит, были условия для изолированного развития и возникновения большого количества наций (см. рис. 12). С другой стороны, на равнинах есть предпосылки для возникновения больших наций: Россия, Франция и т. д.
Рис. 12. Народы, живущие на территории Кавказских гор
Раз появились города и границы, возникла необходимость организовать сообщение между этими городами. Город – это некая общность, но она тоже не может быть самодостаточной. К примеру, в одном из городов начали производить качественный товар в большом объеме, поэтому нужно было искать другие рынки сбыта. Происходит разделение труда между городами, появляется необходимость строительства дорог между ними для обмена товарами. Причем возникает вопрос, как передвигаться, чтобы затратить наименьшее количество времени, усилий и т. д. Возникает классическая задача коммивояжёра.
Задача коммивояжёра (09:35)
Есть N городов, между ними дороги, у каждой дороги есть своя «цена» (например, время на её преодоление, экономические затраты и т. д). Нужно побывать в каждом городе хотя бы по одному разу. Задача – составить маршрут, удовлетворяющий условию задачи и имеющий наименьшую возможную «цену» (см. рис. 13).
Рис. 13. Иллюстрация к задаче коммивояжёра
Задача кажется не очень сложной для малого количества городов. Например, если 3 города, можно просто перебрать варианты (см. рис. 14). Но для большого значения N подобрать ответ практически невозможно.
Рис. 14. Решение задачи коммивояжёра для 3 городов
Трансвычислительные задачи
Почему такие задачи возникают? На самом деле, есть физическое обоснование того, что компьютер на килограмм своей массы не может произвести больше определенного количества операций в секунду. Это следует из уравнения Эйнштейна: E = mc².
Компьютер массой 1 килограмм не может произвести больше чем 1,36 · 10⁵⁰ операций в секунду. Соответственно, даже если взять гипотетический компьютер, масса которого равна массе Земли, он не сможет произвести больше чем 10⁹³ операций в секунду.
Число 10⁹³ представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю за период времени, равный общему времени существования Земли.
Сколько же операций нужно сделать для решения задачи коммивояжёра? Сложность задачи пропорциональна n! (см. рис. 15, 16). Добавление каждого следующего города увеличивает количество маршрутов или переборов в разы. Таким образом, разница сложности решения задачи для 10 и для 100 городов колоссальная!
С другой стороны, возрастание сложности решения комбинаторных задач мы используем при нумерации машин или телефонов: добавление всего одного разряда колоссально увеличивает возможное количество абонентов. А вот в задаче с поиском оптимального маршрута это, конечно, мешает.
Компьютер массой 1 килограмм не может произвести больше чем 1,36 · 10⁵⁰ операций в секунду. Соответственно, даже если взять гипотетический компьютер, масса которого равна массе Земли, он не сможет произвести больше чем 10⁹³ операций в секунду.
Число 10⁹³ представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю за период времени, равный общему времени существования Земли.
Сколько же операций нужно сделать для решения задачи коммивояжёра? Сложность задачи пропорциональна n! (см. рис. 15, 16). Добавление каждого следующего города увеличивает количество маршрутов или переборов в разы. Таким образом, разница сложности решения задачи для 10 и для 100 городов колоссальная!
С другой стороны, возрастание сложности решения комбинаторных задач мы используем при нумерации машин или телефонов: добавление всего одного разряда колоссально увеличивает возможное количество абонентов. А вот в задаче с поиском оптимального маршрута это, конечно, мешает.
Рис. 15. График n! для небольшого значения n
Рис. 16. График n! при увеличении значения n
Решение данной задачи будет полезно также, например, для организации торговли в магазинах. Если в городе есть 30 супермаркетов, то между ними нужно организовать оптимальную доставку товаров со склада (см. рис. 17). Иначе затраты на транспортировку будут высокими и стоимость товара будет выше, чем у конкурентов. Тот, кто первый оптимизирует маршрут, сможет снизить цену и окажется в выигрыше.
Рис. 17. Пример задачи коммивояжёра для доставки товаров
Для 10 городов задача решается с помощью компьютера, даже простым перебором. Можно построить все варианты, вычислить стоимость каждого маршрута и выбрать оптимальный вариант. Но оказывается, что уже даже для 100 городов эта задача не просто не может быть решена персональным компьютером, она в принципе не может быть решена никаким мыслимым компьютером, который мы можем построить в обозримом будущем.
Например, если в городе 100 аптек, то найти оптимальный маршрут между ними и доказать, что он таковым является, невозможно.
Такие задачи, которые мы не можем вычислить даже с помощью компьютера, называются трансвычислительными. Есть два глобальных способа решения таких задач: разбить задачу на части (декомпозиция) или расширить задачу (мы уже приводили пример – появление хабов).
Например, если в городе 100 аптек, то найти оптимальный маршрут между ними и доказать, что он таковым является, невозможно.
Такие задачи, которые мы не можем вычислить даже с помощью компьютера, называются трансвычислительными. Есть два глобальных способа решения таких задач: разбить задачу на части (декомпозиция) или расширить задачу (мы уже приводили пример – появление хабов).
Декомпозиция (разделение целого на части) – научный метод, использующий структуру задачи и позволяющий заменить решение одной большой задачи решением серии меньших, более простых задач, но при этом взаимосвязанных (см. рис. 18).
Рис. 18. Декомпозиция
Декомпозиция
Декомпозиция кажется каким-то изобретением, придуманным учеными, но на самом деле мы все время её используем для решения повседневных задач. Например, когда пробуем распланировать следующий месяц. Это абсолютно нерешаемая задача, если требуется сделать это оптимальным способом. Мы разбиваем месяц на части (дни) и т. д. Решая физическую задачу, мы тоже отвлекаемся от исходной формулировки, говорим, что важно, а что нет (см. рис. 19).
При решении задачи с маятником мы говорим, что сила притяжения к соседней полке с книгами не принципиально на него влияет (рис. 19). Любую задачу мы на каком-то этапе ограничиваем, выделяем модель. В школьных учебниках по физике часто предлагаются уже готовые задачи, которые выделены из реальной жизни, составлены так, чтобы их можно было решить.
Но главная сложность всегда состоит как раз в том, чтобы выделить, построить эту идеальную модель, которую потом можно будет точно рассчитать. В транспортной и логистической задачах этот вопрос стоит особенно остро, потому что математическая постановка вроде бы ясная, но даже в четкой математической модели задача точно не может быть решена. Именно в таких ситуациях полезен такой приём, как декомпозиция.
Каждый сталкивался со сложностью планирования. Если бы мы могли выделить замкнутую систему, то тогда планирование дня в принципе было бы возможно и каждый мог бы более или менее за ограниченное время перебором составить план своего идеального дня. Но мы понимаем, что возможны два исхода. Когда все идеально совпадает без какой-либо задержки, мы всё успеваем и кажется, что за день сделали все дела на год вперёд. А на следующий день совсем наоборот, потому что кто-то задержался, кто-то не пришёл и т. д. Чтобы учесть всё, в задачу планирования нужно включить всех, с кем мы сотрудничаем, транспорт, от которого зависит наше перемещение, и т. д. Но тогда нужно включить в неё и всё то, что влияет на этих людей и на транспорт, и т. д. Таким образом, система расширится до планеты Земля, активности Солнца и притяжения каких-то далеких звёзд (см. рис. 20).
Вот поэтому мы всегда строим модель, ограничиваем задачу, включаем здравый смысл. Так появляется модель, которую мы уже можем решить точно.
При решении задачи с маятником мы говорим, что сила притяжения к соседней полке с книгами не принципиально на него влияет (рис. 19). Любую задачу мы на каком-то этапе ограничиваем, выделяем модель. В школьных учебниках по физике часто предлагаются уже готовые задачи, которые выделены из реальной жизни, составлены так, чтобы их можно было решить.
Но главная сложность всегда состоит как раз в том, чтобы выделить, построить эту идеальную модель, которую потом можно будет точно рассчитать. В транспортной и логистической задачах этот вопрос стоит особенно остро, потому что математическая постановка вроде бы ясная, но даже в четкой математической модели задача точно не может быть решена. Именно в таких ситуациях полезен такой приём, как декомпозиция.
Каждый сталкивался со сложностью планирования. Если бы мы могли выделить замкнутую систему, то тогда планирование дня в принципе было бы возможно и каждый мог бы более или менее за ограниченное время перебором составить план своего идеального дня. Но мы понимаем, что возможны два исхода. Когда все идеально совпадает без какой-либо задержки, мы всё успеваем и кажется, что за день сделали все дела на год вперёд. А на следующий день совсем наоборот, потому что кто-то задержался, кто-то не пришёл и т. д. Чтобы учесть всё, в задачу планирования нужно включить всех, с кем мы сотрудничаем, транспорт, от которого зависит наше перемещение, и т. д. Но тогда нужно включить в неё и всё то, что влияет на этих людей и на транспорт, и т. д. Таким образом, система расширится до планеты Земля, активности Солнца и притяжения каких-то далеких звёзд (см. рис. 20).
Вот поэтому мы всегда строим модель, ограничиваем задачу, включаем здравый смысл. Так появляется модель, которую мы уже можем решить точно.
Рис. 19. Сила притяжения к соседней полке с книгами не принципиально влияет на математический маятник
Рис. 20. Иллюстрация примера
Хабы (14:00)
Хаб (анг. hub, буквально «ступица колеса», «центр») – узел какой-то сети.
Рис. 21. Возникновение хаба
Самый простой пример хаба – это рынок в торговле (см. рис. 22). Доска объявлений – информационный хаб (см. рис. 23).
Рис. 22. Рынок как пример хаба
Рис. 23. Доска объявлений – информационный хаб
Примеры хабов
Важно понимать, что большинство из тех задач, которые мы решаем, уже каким-то образом решены природой. Например, логистическую задачу решают муравьи (см. рис. 24).
Задача, которую решают муравьи, схожа с той, которую у людей решает культура. Культура делает нас близкими, с её помощью мы образуем нацию, общность.
Что же делают муравьи? Они создают колонии (ветки) отдельно от основного муравейника, поэтому есть опасность, что эти колонии станут чужими – будут войны, полосы отчуждения, а значит, муравьи потеряют много земли. Для того чтобы этого не произошло, муравьи таскают друг другу личинки, чтобы быть похожими друг на друга (см. рис. 25).
Они носят личинки в большой хаб, где те перемешиваются и дальше разносятся по другим колониям (см. рис. 26).
Еще один пример хаба – это деньги. Фактически деньги – это некий общий инструмент для оценки того, сколько стоит произведённый товар. Мы обмениваемся не товарами, а именно деньгами (см. рис. 27).
Хабы присутствуют не только в логистике, но и в реальной жизни. Эта идея используется повсеместно. Подводя итог, хабы – это место (возможно, виртуальное), куда все привозят свои товары или информацию, и где все могут их приобрести (получить). В результате обмен происходит быстрее.
Задача, которую решают муравьи, схожа с той, которую у людей решает культура. Культура делает нас близкими, с её помощью мы образуем нацию, общность.
Что же делают муравьи? Они создают колонии (ветки) отдельно от основного муравейника, поэтому есть опасность, что эти колонии станут чужими – будут войны, полосы отчуждения, а значит, муравьи потеряют много земли. Для того чтобы этого не произошло, муравьи таскают друг другу личинки, чтобы быть похожими друг на друга (см. рис. 25).
Они носят личинки в большой хаб, где те перемешиваются и дальше разносятся по другим колониям (см. рис. 26).
Еще один пример хаба – это деньги. Фактически деньги – это некий общий инструмент для оценки того, сколько стоит произведённый товар. Мы обмениваемся не товарами, а именно деньгами (см. рис. 27).
Хабы присутствуют не только в логистике, но и в реальной жизни. Эта идея используется повсеместно. Подводя итог, хабы – это место (возможно, виртуальное), куда все привозят свои товары или информацию, и где все могут их приобрести (получить). В результате обмен происходит быстрее.
Рис. 24. Ходы муравейника (заливка цементом) флоридского муравья-жнеца
Рис. 25. Муравьи перетаскивают друг другу личинки, чтобы быть похожими друг на друга
Рис. 26. Хаб с личинками внутри муравейника
Рис. 27. Деньги – один из примеров хаба
Примеры хабов – склады
Склады – это тоже примеры хабов (см. рис. 28, 29, 30). Со всех концов туда свозятся товары, которые нужны данному городу. На складах они перераспределяются, подъезжают машины и развозят их по нужным точкам.
Если бы со всех предприятий товары везли не на склад, а сразу в точки его сбыта, то моментально наступил бы транспортный коллапс и, соответственно, стоимость товара была бы гораздо дороже.
Если бы со всех предприятий товары везли не на склад, а сразу в точки его сбыта, то моментально наступил бы транспортный коллапс и, соответственно, стоимость товара была бы гораздо дороже.
Рис. 28. Склады – один из примеров хаба
Рис. 29. Склады – один из примеров хаба
Рис. 30. Склады – один из примеров хаба
Рис. 20. Иллюстрация формулировки задачи
Рассмотрим конкретную задачу. Мы, как перевозчики, хотим доставить товар в каждый город самым выгодным образом. Мы можем организовать поставку из одного города в другой ежедневно, тогда для 10 городов понадобится 90 рейсов (см. рис. 31). А можно поступить по-другому – выбрать один город и назначить его хабом (см. рис. 32), то есть в город будут свозить посылки из остальных 9 городов и потом их из него же развозить.
Рис. 32. Назначение одного из городов хабом
По такому принципу работает почта Overnight – доставка посылок за ночь (см. рис. 33). Грубо говоря, вечером вы отдаете посылку, ночью её доставляют в центр (хаб), и утром посылки перераспределяют и отправляют в пункт назначения. Выгода такой доставки в том, что между двумя городами может быть слабый поток посылок, из-за чего отправлять машину или самолёт ежедневно из одного города в другой экономически нецелесообразно. Другое дело, когда со всех городов набирается нужное количество товара или корреспонденции для загрузки машины или самолёта.
Рис. 33. Круглосуточный почтовый киоск-автомат (Техас, США)
Если посчитать количество рейсов с наличием хаба, то их будет существенно меньше: 2 · 9 = 18. Если рассмотреть эту зависимость в общем виде, то получим следующий график (см. рис. 34) для большего количества точек (городов).
Рис. 34. Зависимость количества рейсов от числа городов при отсутствии и наличии хаба
Идея хаба позволяет существенно уменьшить затраты и решать задачу с организацией передвижения.
Конечно, решая её таким образом, мы выходим за рамки задачи коммивояжёра, так как, по условию, мы должны были побывать в каждом городе один раз, а в хаб мы будем каждый раз возвращаться из любого города. Однако именно расширение задачи позволяет её решить, причём достаточно просто и выгодно.
Идея хабов также близка к идее решения транспортной задачи.
Идея хабов также близка к идее решения транспортной задачи.
Транспортная задача
Транспортная задача (задача Монжа-Канторовича) – математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приёмникам с минимизацией затрат на перемещение.
Иными словами, у нас есть n мест, где производят товар, и есть m мест, куда этот товар нужно поставить (см. рис. 35).
Для математической модели мы считаем, что количество произведённого товара совпадает с количеством товаров, которые потребляют люди, то есть нет недостатков или излишков товара. Также мы знаем стоимость доставки между любыми двумя точками.
Задача: как оптимально развести товар по точкам сбыта и потратить при этом наименьшее количество денег?
Отличие данной задачи от задачи коммивояжёра в том, что там у нас один объект должен был проложить путь, оптимальный для него, а здесь мы можем использовать несколько машин из каждой точки, но так, чтобы суммарная стоимость была наименьшей.
Транспортная задача решаема. В этом огромная заслуга нашего соотечественника, математика Л.В. Канторовича (см. рис. 36), который придумал симплекс-метод.
Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве (см. рис. 37).
Как мы уже говорили, многие задачи, с которыми мы сталкиваемся, уже решены природой задолго до нас. Оказывается, один из методов оптимизации решения транспортной задачи в каком-то смысле подсмотрен у природы и у тех самых муравьев, о которых мы уже упоминали, когда говорили о хабах. Это алгоритм подражания муравьиной колонии, и его очень удобно применять не только при решении транспортной задачи.
Муравьи начинают своё движение от муравейника и хотят найти источник пищи. Когда муравей находит этот источник, на обратном пути он оставляет след из феромонов (см. рис. 38). Тогда следующие муравьи, которые идут искать пищу, с большой долей вероятности попадут на дорожку с этим запахом, пойдут по ней же и найдут пищу.
Тогда понятно, что если первые муравьи нашли несколько дорожек, то рано или поздно почти все муравьи буду двигаться по этим дорожкам. Но феромон имеет такое свойство, как испарение. И, соответственно, если путь был длинным, то, поскольку плотность движения по нему будет, очевидно, меньше, чем по короткому пути, запах будет ослабевать, а на коротких путях, наоборот, будет усиливаться. Таким образом, через некоторое время все муравьи будут двигаться по самому короткому пути (см. рис. 39). Таким образом, муравьи находят самый короткий путь к источнику пищи.
Идея этого алгоритма лежит в основе решения, в частности, и транспортной задачи. Математика позволяет в некотором приближении находить оптимальные или почти оптимальные пути решения наших повседневных задач. Насколько сложна эта задача, каждый может понять, просто представив, какое количество товаров в течение дня, недели он использует. Ведь все эти товары были кем-то произведены, откуда-то доставлены, затем распределены и развезены по точкам продаж.
Иными словами, у нас есть n мест, где производят товар, и есть m мест, куда этот товар нужно поставить (см. рис. 35).
Для математической модели мы считаем, что количество произведённого товара совпадает с количеством товаров, которые потребляют люди, то есть нет недостатков или излишков товара. Также мы знаем стоимость доставки между любыми двумя точками.
Задача: как оптимально развести товар по точкам сбыта и потратить при этом наименьшее количество денег?
Отличие данной задачи от задачи коммивояжёра в том, что там у нас один объект должен был проложить путь, оптимальный для него, а здесь мы можем использовать несколько машин из каждой точки, но так, чтобы суммарная стоимость была наименьшей.
Транспортная задача решаема. В этом огромная заслуга нашего соотечественника, математика Л.В. Канторовича (см. рис. 36), который придумал симплекс-метод.
Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве (см. рис. 37).
Как мы уже говорили, многие задачи, с которыми мы сталкиваемся, уже решены природой задолго до нас. Оказывается, один из методов оптимизации решения транспортной задачи в каком-то смысле подсмотрен у природы и у тех самых муравьев, о которых мы уже упоминали, когда говорили о хабах. Это алгоритм подражания муравьиной колонии, и его очень удобно применять не только при решении транспортной задачи.
Муравьи начинают своё движение от муравейника и хотят найти источник пищи. Когда муравей находит этот источник, на обратном пути он оставляет след из феромонов (см. рис. 38). Тогда следующие муравьи, которые идут искать пищу, с большой долей вероятности попадут на дорожку с этим запахом, пойдут по ней же и найдут пищу.
Тогда понятно, что если первые муравьи нашли несколько дорожек, то рано или поздно почти все муравьи буду двигаться по этим дорожкам. Но феромон имеет такое свойство, как испарение. И, соответственно, если путь был длинным, то, поскольку плотность движения по нему будет, очевидно, меньше, чем по короткому пути, запах будет ослабевать, а на коротких путях, наоборот, будет усиливаться. Таким образом, через некоторое время все муравьи будут двигаться по самому короткому пути (см. рис. 39). Таким образом, муравьи находят самый короткий путь к источнику пищи.
Идея этого алгоритма лежит в основе решения, в частности, и транспортной задачи. Математика позволяет в некотором приближении находить оптимальные или почти оптимальные пути решения наших повседневных задач. Насколько сложна эта задача, каждый может понять, просто представив, какое количество товаров в течение дня, недели он использует. Ведь все эти товары были кем-то произведены, откуда-то доставлены, затем распределены и развезены по точкам продаж.
Рис. 35. Транспортная задача
Рис. 36. Л.В. Канторович (1912–1986)
Рис. 37. Иллюстрация к определению симплекс-метода
Рис. 38. Дорожки из феромонов
Рис. 39. Оптимальный путь от муравейника до источника пищи
Декомпозиция (18:02)
Вернёмся к такому методу решения, как декомпозиция. Данный метод также подходит для приближённого решения задачи коммивояжёра. Если у нас есть, например, 100 городов, тогда мы можем разбить их на 10 групп по 10 городов. Решить задачу для каждой группы, а дальше подумать, как соединить маршруты каждой из групп между собой (см. рис. 40).
Рис. 40. Декомпозиция
Сложность задачи заключается в том, что непонятно, каким именно образом необходимо разбить города на группы. Вариантов таких разбиений очень много, поэтому, если все их перебрать, получится опять-таки исходная задача. Нужно понимать, что в данном случае мы говорим уже не об оптимальном решении, а о достаточно хорошем. Это решение будет эффективным, но, возможно, не оптимальным.
Поэтому если смягчить условие задачи коммивояжёра поиском пути, который будет отличаться от оптимального не больше чем на 5–10 %, то такую задачу уже можно решить с помощью компьютера.
Как тогда понять, с чем сравнивать полученное решение, если точно решить задачу мы не можем? Однако можно достаточно точно выполнить оценку снизу. Всё-таки это большая разница, когда мы говорим, что стоимость перевозки будет не меньше 1000 рублей, или же когда утверждаем, что стоимость оптимального пути будет 1003 рубля.
Поэтому если смягчить условие задачи коммивояжёра поиском пути, который будет отличаться от оптимального не больше чем на 5–10 %, то такую задачу уже можно решить с помощью компьютера.
Как тогда понять, с чем сравнивать полученное решение, если точно решить задачу мы не можем? Однако можно достаточно точно выполнить оценку снизу. Всё-таки это большая разница, когда мы говорим, что стоимость перевозки будет не меньше 1000 рублей, или же когда утверждаем, что стоимость оптимального пути будет 1003 рубля.
Рис. 41. Путешествие с одной вершины на другую
В жизни мы также достаточно часто пользуемся оценками, а не точными решениями. Например, стоя на одной вершине, в походе мы оцениваем, каким путем удобнее добираться до другой вершины (см. рис. 41). Понятно, что мы выберем более ровную дорогу и постараемся избежать восхождений на холмы. Не зная местности и оптимальной дороги, мы выбираем какой-то путь, приближенный к оптимальному. Аналогичным образом живёт всё человечество.
Раньше Госплан в нашей стране решал, что будет произведено в ближайшие 5 лет, вплоть до гвоздя и зонтика. Казалось, что всё это можно просчитать и так будет удобнее. Такая кажущаяся ясность многих увлекала, и многие до сих пор считают, что для построения социализма не хватило только мощности вычислительных машин.
Таким образом, мы перешли к экономической составляющей решения логистических задач. На самом деле, люди решают эти задачи интуитивно с помощью простых моделей. Например, при покупке еды. Каждая сеть магазинов представляет собой декомпозицию (см. рис. 42). Аналитик такой сети должен решить задачу организации доставки товаров и попытаться оптимизировать собственное решение.
Раньше Госплан в нашей стране решал, что будет произведено в ближайшие 5 лет, вплоть до гвоздя и зонтика. Казалось, что всё это можно просчитать и так будет удобнее. Такая кажущаяся ясность многих увлекала, и многие до сих пор считают, что для построения социализма не хватило только мощности вычислительных машин.
Таким образом, мы перешли к экономической составляющей решения логистических задач. На самом деле, люди решают эти задачи интуитивно с помощью простых моделей. Например, при покупке еды. Каждая сеть магазинов представляет собой декомпозицию (см. рис. 42). Аналитик такой сети должен решить задачу организации доставки товаров и попытаться оптимизировать собственное решение.
Рис. 42. Пример декомпозиции – сеть магазинов
Не всегда декомпозиция является лучшим решением.
Например, на рисунке 43 показан пример расположения аптек, которые торгуют одними товарами и приблизительно по одной цене. Так происходит из-за того, что решает задачу каждая группа отдельно, не учитывая интересы других. Однако конкуренция чаще всего заставляет убирать с рынка такие неэффективные решения. Фактически экономику и бизнесменов (аналитиков) можно считать деталями большой вычислительной машины, которой руководит государство. Именно оно ставит сложные задачи и руководит крупными проектами.
Рис. 43. Расположение аптек
Заключение (23:54)
Сегодня мы говорили о задачах логистики, их математической интерпретации и влиянии на развитие общества. Мы увидели, что некоторые задачи имеют простые и точные формулировки, но решить их абсолютно точно невозможно, только в некотором приближении.
Ссылки на дополнительные ресурсы сети Интернет:
[МТ1] Евфрат
- «Искусственные реки - каналы» - https://goo.gl/gioDjG
[МТ1] Евфрат
Другие материалы
Copyright © 2009-2021
Made by