Для реализации метода ветвей и границ применительно к задаче о коммивояжере необходимо конкретизировать правила ветвления, вычисления оценок и нахождения решений. [c.212]
Чтобы проиллюстрировать алгоритм метода ветвей и границ для решения задачи о коммивояжере приведем численный пример. [c.215]
Пример решения задачи о коммивояжере [c.215]
Дискретными являются задача о коммивояжере, задача о назначениях, задачи теории расписаний и т.д. [c.88]
См. также Задача о коммивояжере, Оперативно-календарное планирование. [c.360]
Задача о коммивояжере, о бродячем торговце 100 [c.465]
На втором этапе (80-е гг.) к согласованию процессов транспортировки, переработки, складирования и хранения материальных ресурсов подключается планирование и оперативное управление материальными и информационными потоками в основном производстве. Это способствовало повышению качества обслуживания покупателей за счет своевременности выполнения заказов и улучшения использования оборудования. На данном этапе развития логистики большую роль сыграло накопление и распространение опыта японских промышленных предприятий, в первую очередь в области автомобилестроения. Этому послужила тенденция развития автомобильной промышленности, ориентированная на изготовление автомобилей по индивидуальному заказу. Воздействие на конъюнктуру рынка через удовлетворение индивидуальных потребностей вынудило японские фирмы радикально изменить свою концепцию производственно-сбытовой политики. В первую очередь необходимо было разработать механизм доставки потребителю продукции, основным критерием эффективности которого было бы соблюдение принципов от двери к двери и точно в срок . Для этого потребовалось организовать производство таким образом, чтобы детали и узлы на сборочный конвейер подавались синхронно с производственным циклом. Партии поступающих деталей и собираемой конечной продукции рассчитываются таким образом, чтобы оперативно заданный объем товарной продукции выпускался с минимальными затратами. Кроме того, наконец успешно была решена задача о коммивояжере. [c.19]
Задача о коммивояжере. Здесь требуется отыскать наилучший маршрут, с тем чтобы объехать все порученные коммивояжеру пункты и вернуться назад либо в кратчайший срок, либо с наименьшими затратами на проезд. В общем виде эту задачу можно сформулировать следующим образом. [c.533]
Таким образом, задача о коммивояжере состоит в минимизации [c.534]
Рассмотрим третью проблему, возникающую в связи с переналадкой переменно-поточной линии. Пусть на МПЛ в плановом периоде должно быть изготовлено Кл различных партий изделий. Время переналадки линии / зависит от чередования снимаемой (/ ). и запускаемой (/) партий, а время изготовления каждой партии от этого не зависит. Тогда для минимизации времени изготовления на МПЛ всей запланированной продукции необходимо отыскать такую последовательность запуска партий в обработку, при которой суммарное время переналадки будет наименьшим, т. е. 2 на/ => min. Эта задача носит название задачи о переналадке поточной линии. Она сводится к постановке известной с конца XIX в. задачи, называемой задачей о коммивояжере. [c.296]
В случае планирования работы поточной линии правила приоритетов работают, лишь когда близки значения времени переналадки линии на любую новую партию с любой прежней. В противном случае задачу определения последовательности запуска партий в обработку более целесообразно сводить к задаче о коммивояжере (см. главу 12). Правил приоритетов достаточно много, рассмотрим лишь наиболее значимые и применимые. [c.547]
ЗАДАЧА О КОММИВОЯЖЕРЕ состоит в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города за кратчайший срок или с наименьшими затратами на проезд. Казалось бы, странно головоломка любопытна, но причем здесь экономика, какое это может иметь для нее значение [c.119]
Алгоритмы, позволяющие решать на электронных вычислительных машинах задачу о коммивояжере, используются не только при выборе маршрутов автотранспорта при кольцевой доставке товаров (например, в торговую сеть), но и пр-и решении таких задач, которые на первый взгляд никакого отношения к задаче коммивояжера не имеют, например, в планировании производства на конвейерах, выпускающих машины различных моделей. На ЭВМ с помощью таких алгоритмов рассчитывают оптимальные партии, позволяющие выпускать заданный объем продукции с минимумом затрат на переналадку конвейера. [c.119]
Интересная задача очередности размещения в полосе разных заготовок, приводящая к задаче о коммивояжере , рассмотрена в работе [284]. [c.251]
Классическим представителем математических проблем такого рода стала задача о коммивояжере. Она состоит в составлении маршрута посещения торговым агентом, находящимся в некотором начальном пункте, п других городов при условии, что задана матрица стоимостей переездов из города в город [c.139]
Какие экономико-математические модели могут быть сведены к задаче о коммивояжере [c.157]
Если допустимое множество целочисленной задачи линейного программировании является конечным множеством, то это комбинаторная оптимизационная задача. Классическим примером комбинаторной оптимизационной задачи наряду с задачами о загрузке корабля и о распределении капиталовложений между проектами является задача о коммивояжере. [c.218]
Задача о коммивояжере. Имеется п городов А А2,. ... . . , Л . и задана матрица С = (с у) расстояний между этими городами. Выезжая из исходного города Лг, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в At- Определить, в каком порядке следует объезжать город.а, чтобы суммарное пройденное расстояние было наименьшим. [c.218]
| Рис. 6,9. Схема оперативного решения задачи коммивояжера (задача о двух вертолетах) |  |
Конечная цель контроля состоит не в том, чтобы собрать информацию, установить стандарты и выявить проблемы, а в том, чтобы решить задачи, стоящие перед организацией. Проведение измерений и оповещение об их результатах важно только как средство достижения этой цели. Если вы хотите сделать контроль эффективным, вы должны тщательно следить з.а тем, чтобы эти самоочевидные средства контроля не заняли более важного места, чем подлинные цели организации. Например, было бы глупо увольнять лучших коммивояжеров фирмы только потому, что они никогда не представляют отчеты о расходах вовремя. Более того, бессмысленно провозглашать, что ваша система направлена на получение конкретных результатов, если фактически она не может их достичь. Бесполезно иметь обширную и точную информацию о различных отклонениях от намеченных целей, если эта информация не используется для осуществления необходимых корректирующих действий. Это означает, что информация о результатах контроля важна только тогда, когда доходит до тех лиц, которые обладают правом произвести на ее основании соответствующие изменения. Когда контрольный механизм не срабатывает, то чаще всего причина кроется в том, что необходимо усовершенствовать структуру прав и обязанностей, а не процедуру измерений. Таким образом, чтобы быть эффективным, контроль должен быть интегрирован с другими функциями управления. [c.410]
Коммивояжеры информируют свою фирму о требованиях местного рынка, вкусах и обычаях населения, условиях торговли и расчетов за поставленный товар, таможенных правилах и т.д. Для успешного выполнения своей задачи коммивояжер должен владеть местным языком и знать местные условия. На коммивояжеров могут быть возложены и обязанности инкассации причитающихся с покупателей платежей. Коммивояжеры выступают от имени фирмы и за ее счет. Оплачиваются коммивояжеры по-разному твердый оклад, сдельная оплата или определенный процент с суммы принятых заказов. [c.470]
И наконец, для производителя средств производства исключительно важно оценить перспективную стратегию конкурентов в области маркетинга. Главная задача состоит здесь в том, чтобы определить, намерен ли конкурент взять на себя лидерство в освоении новой продукции или же он ограничится ролью последователя , закупая лицензии и т.п. Учитывая такую важную особенность (и даже принципиальное требование) маркетинга средств производства, как постоянный и тесный контакт с потребителем, надо проводить всесторонний анализ практики деловых отношений конкурентов с наиболее важными потенциальными клиентами. Это необходимо для более правильной оценки выявленных тенденций спроса, определения границ (зон) влияния фирмы. Той же цели служит получение сведений о дислокации коммивояжеров и сбытовых агентов конкурентов. [c.299]
Личная продажа. В стимулировании сбыта товаров большое значение придается личным продажам, т.е. общению продавцов (торговых агентов) с одним или несколькими потенциальными покупателями с целью купли-продажи товара. Формирование эффективно работающего торгового персонала — одна из важнейших задач и проблем для современных фирм. На торговых агентов, коммивояжеров возлагаются задачи по поиску новых покупателей, распространению информации о товарах или услугах, продаже товара, исследованию рынка, сбору информации о товарах и т.п. [c.161]
Аналогично, если при оценке деятельности коммивояжеров исходить только из достигнутого ими объема продаж и не учитывать степени удовлетворения ими потребностей покупателя и уровень его обслуживания, то коммивояжеры могут и проигнорировать решение этих жизненно важных задач. Они, например, могут не позвонить клиенту после исполнения его заказа и не спросить, не возникло ли у него каких-либо проблем, не реагировать на возникновение таких проблем и даже не информировать покупателей о новых товарах, представляющих для них потенциальный интерес. Кроме того, если не оценивать коммивояжеров по количеству и качеству информации, нужной их организации и передаваемой ими в отдел маркетинга, то они такую информацию или вообще предоставлять не станут, или будут делать это от случая к случаю. При этом организации значительно труднее достичь важных целей, связанных с разработкой и внедрением новой привлекательной продукции в ответ на изменение потребностей покупателей. В итоге можно заключить, что односторонний контроль может обеспечить эффективное достижение какой-либо одной цели организации, но в долгосрочном плане он будет препятствовать достижению интегральных целей организации во многих важных областях. [c.451]
Конечная цель контроля состоит не в том, чтобы собрать информацию, установить стандарты и выявить проблемы, а в том, чтобы решить задачи, стоящие перед организацией. Проведение измерений и оповещение об их результатах важно только как средство достижения этой цели. Если вы хотите сделать контроль эффективным, вы должны тщательно следить за тем, чтобы эти самоочевидные средства контроля не заняли более важного места, чем подлинные цели организации. Например, было бы глупо увольнять лучших коммивояжеров фирмы только потому, что они никогда не представляют отчеты о расходах вовремя. [c.454]
Полученная матрица С" называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С", называется приведением. Сумма вычитаемых в процессе приведения элементов называется приводящими константами и обозначается п . Оптимальный план задачи о коммивояжере с матрицей С" явля- ется оптимальным и для задачи о коммивояжере с матрицей С. Длина цикла l (t) на приведенной матрице будет меньше длины цикла /(/) на исходной матрице на сумму приводящих констант [c.213]
ЗАДАЧА О КОММИВОЯЖЕРЕ (travelling salesman problem) — задача программирования математического, состоит в отыскании оптим маршрута для коммивояжера, который должен объехать все порученные ему пункты и вернуться назад за кратчайший срок или с наименьшими затратами на проезд Алгоритмы 3 о к используются при разработке маршрутов автотранспорта (при кольцевых рейсах), для расчета оптимальной партии изделий, [c.69]
КОММИВОЯЖЕР (travelling salesman) -разъездной представитель торгового предприятия или пром фирмы, посредник, который, перемещаясь по рынку, ищет покупателей К, как правило, снабжен образцами товаров и рекламными материалами, получает вознаграждение от своего работодателя пропорционально объему и эффективности продаж См также Бесплатный образец, Демонстрационный образец, Задача о коммивояжере, Канвассер [c.95]
МАРШРУТ СБОРНЫЙ (multi-pi k route) -способ орг-ции автомобильных мелкопартионных перевозок, сбор автомобилем грузов нескольких грузоотправителей и доставка этих грузов одному грузополучателю См также Задача о коммивояжере [c.129]
Как и генетическая оптимизация, моделирование отжига — очень мощная стохастическая методика, основанная на естественном явлении, которое может находить глобально оптимальные решения и работать с неупорядоченными функциями эффективности. Моделирование отжига эффективно решает комбинаторные проблемы, включая известную задачу о коммивояжере или проблему оптимального расположения миллионов элементов современных интегральных микросхем, например компьютерных процессоров. Методы, основанные на моделировании отжига, не следует ограничивать комбинаторной оптимизацией они могут бытьлегко применены для оптимизации параметров с реальными значениями. Следовательно, оптимизаторы, основанные на моделировании отжига, применимы к широчайшему кругу задач, включая задачи, интересующие трейдеров. [c.57]
О Рассмотрим задачу о коммивояжере с матрицей расстояний С = (с ) порядка п. Обозначим через И множество всех маршрутов, при когорых коммивояжер, выезжая из города Л1( побывает во всех остальных городах по одному разу и вернется в А+. Пусть QI, lt,, -,. .... t, 2 .k n — 1, — подмножество множества Q, состоящее из всех маршрутов, при которых коммивояжер, выезжая из А , последовательно посещает города А,-. . ., А . [c.223]
Многие коммивояжеры просто-напросто не умеют продавать (см. врезку 39). Одна из основных задач учебного курса-дать им знания об искусстве продажи. Фирмы тратят сотни миллионов долларов на проведение семинаров, подготовку книг, кассет и прочих учебных материалов. Ежегодно раскупается около миллиона экземпляров книг о коммерции с захватывающими заглавиями типа Как опередить прирожденного коммивояжера , Как продать что угодно кому угодно , Возможности вдохновенной коммерции , Как я добился успеха за шесть часов благодаря напористой продаже , Куда идти дальше, став первым , Тысяча способов увеличения продаж коммивояжером . Одним из самых живучих произведений подобного типа является книга Дейла Кар-неги Как приобретать друзей и оказывать влияние на людей . [c.560]
ПРЕДВАРИТЕЛЬНАЯ ПОДГОТОВКА К ВИЗИТУ. Коммивояжер должен как можно больше узнать и о компании - потенциальном клиенте (ее нуждах и потребностях, круге лиц, задействованных в принятии решений о закупках), и о самих покупателях (о чертах их характера и стиле покупательского поведения). Чтобы узнать как можно больше о компании-потенциальном заказчике, коммивояжер может воспользоваться официальными источниками информации (справочники Мудис , Стандард энд Пур , Дан энд Брэд-стрит ), информацией, полученной от знакомых и прочих лиц. Перед каждым визитом коммивояжер должен поставить себе определенные задачи либо квалифицировать (т. е. оценить) потенциального клиента, либо получить информацию, либо совершить немедленную запродажу. Следующей задачей является принятие решения о способе наилучшего подхода к клиенту личный визит, звонок по телефону или написание письм... Следует подумать и о наиболее удобном времени контакта, ибо в определенные периоды времени многие потенциальные клиенты бывают заняты. И наконец, коммивояжер должен продумать общий стратегический подход к организации торговых отношений с клиентом. [c.563]
Очередь с пространственно-зависимыми приоритетами имеет наименование dynam. Транзакты, попадающие в такую очередь, привязаны к точкам пространства. Очередь обслуживается специальным узлом ргос, работающим в режиме пространственных перемещений. Смысл обслуживания транзактов заключается в том, чтобы посетить все точки пространства, с которыми связаны (или из которых поступили) транзакты. При поступлении каждого нового транзакта, если он не единственный в очереди, происходит переупорядочение очереди таким образом, чтобы суммарный путь посещения точек был минимальным. Не следует считать, что при этом решается задача коммивояжера для решения такой задачи в нулевой момент времени имеется вся информация о точках пространства. В данном же случае информация о новых точках поступает во время движения, когда некоторые точки уже посещены. Рассмотренное правило работы узла dynam в литературе называется алгоритмом скорой помощи . [c.68]
Торгующие широким ассортиментом стандартных товаров, таких, как конторское оборудование, время от времени могут рассчитывать на совершение запродажи прямо со страницы , но только своим устоявшимся клиентам, которые знают поставщика и верят ему. Первейшая задача каталога может заключаться в оказании содействия коммивояжеру во время его визита к клиенту, или в завлечении покупателей в демонстрационные залы, или в предоставлении розничному торговцу подробной информации о товарном ассортименте оптовика. В последнем случае каталог может переиз- [c.119]