Раскраска графов - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

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

Ставится задача раскраски вершин такого графа несовместимости при различных условиях (ограничениях, критериях), среди которых:

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

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

Похожие статьи

• Частотно-матричный метод, Близость (на практике) - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

  Подход к постановке задачи аналогичен предыдущему, но в качестве исходной модели рассматривается матрица инциденций Q = [ Q (i, j)]. Столбцам матрицы...

• Предметная интерпретация - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

  Система "Диспетчер" апробирована на реальных исходных данных двух регионов Нефтяной Компании "Юкос" (Липецкая и Воронежская области) и показала свою...

• Введение - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

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

• Общая постановка задачи - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

  Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...

• Заключение, Литература - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

  Основные результаты работы состоят в следующем: 1. Рассмотрены математические модели, лежащие в основе системы оптимизации доставки товаров...

• Задача маршрутизации - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

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

• Задача кластеризации, Аппарат нечетких множеств - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

  Задача кластеризации реализуется набором методов (алгоритмов), каждый из которых осуществляет разбиения региона на компактные зоны обслуживания. Аппарат...

• Нестационарная неопределенность, Нелинейная неопределенность, Неопределенность внешних условий - Математические модели неопределенностей систем управления и методы, используемые для их исследования

  Модель "вход - выход" для нестационарной системы управления можно представить в следующем виде [2] . Где коэффициенты матриц возмущения и ограничены...

• Непараметрическая неопределенность, Аддитивная неопределенность, Дробно-рациональная неопределенность, Мультипликативная неопределенность - Математические модели неопределенностей систем управления и методы, используемые для их исследования

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

• Неопределенность цели - Математические модели неопределенностей систем управления и методы, используемые для их исследования

  При управлении подвижными объектами (такими, например, как мобильные роботы, подводные аппараты и т. п.) часто имеет место неопределенность цели, когда...

• Введение, Параметрическая неопределенность - Математические модели неопределенностей систем управления и методы, используемые для их исследования

  В практике управления системами различного назначения (экономическими, финансовыми, техническими и др.) неизбежно приходится сталкиваться с различными...

• Реализация модели оптимизации графика занятости в MS Excel - Разработка математической модели оптимизации графиков занятости при многосменной организации труда и реализация ее в MS EXEL

  Реализуем математическую модель (2) (6) в MS Excel. Для этой цели построим таблицы исходных данных задачи по расчету оптимального графика занятости при...

• Классификационная схема характеристик сложности задачи выбора пути в условиях неопределенности - Модели и методы решения проблемы выбора в условиях неопределенности

  Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...

• Заключение, Список использованной литературы - Моделирование математической модели теплообменника

  В данной курсовой работе была получена математическая модель теплообменника в виде дифференциальных уравнений. Также была получена передаточная функция...

• Объединение двух ЭС - Расчетная модель оптимизации системы теплоснабжения региона

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

• Анализ конкурентоспособности ТЭЦ на рынке тепла - Расчетная модель оптимизации системы теплоснабжения региона

  Возможны две различных стратегии реструктуризации сферы централизованного теплоснабжения, и, как следствие, различные методики анализа возникающих...

• Расчет зон влияния ТЭЦ по программе CHPPLANT - Расчетная модель оптимизации системы теплоснабжения региона

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

• Моделирование рынка тепла - Расчетная модель оптимизации системы теплоснабжения региона

  Энергосистема теплоснабжение конкуренция регион В нашей предыдущей работе [1] была разработана методология анализа конкуренции ТЭЦ и/или котельных, а...

• Литература - Математические модели неопределенностей систем управления и методы, используемые для их исследования

  1. Цыпкин, Я. З. Частотные критерии робастной модальной линейных дискретных систем / Я. З. Цыпкин, Б. Т. Поляк // Автоматика.-1990. - № 5. - С.4-11. 2....

• Дополнительные примеры, Модель Мальтуса, Система хищник-жертва - МАтематическое моделирование в экономике

  Модель Мальтуса Скорость роста пропорциональна текущему размеру популяции. Она описывается дифференциальным уравнением Где б -- некоторый параметр,...

• Математическая модель задачи оптимизации графика занятости при многосменной организации труда - Разработка математической модели оптимизации графиков занятости при многосменной организации труда и реализация ее в MS EXEL

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

• Теоретическое обоснование математического моделирования - Математические методы и модели в экономике

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

• Математическая модель оценки состояния СЭС - Формирование стратегии развития социально-экономической системы в условиях ограниченности ресурсов

  Основные процессы СЭС представлены комплексом направлений деятельности, которые можно представить как EP(t)={EP1(t), EP2(t) ... EPN(t)},, где i=1..n, n -...

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

  Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...

• Введение, Графики занятости при многосменной организации труда. Задача оптимизации графиков занятости - Разработка математической модели оптимизации графиков занятости при многосменной организации труда и реализация ее в MS EXEL

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

• Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи

  Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...

• Универсальность моделей, Прямая и обратная задачи математического моделирования - Экономико-математическая детерминированная модель

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

• Экономико-математическая модель в форме линейных уравнений и неравенств - Оптимизация производственной структуры сельскохозяйственного предприятия на примере ОПХ "Боевое" Исилькульского района Омской области

  Ограничения по производственным ресурсам: 1.Ограничение по посевной площади : Х1+Х2+Х3+Х4+Х5+Х6+Х7+Х8+Х9+Х12 +Х13+Х14+...+Х23?14280 Ограничения по...

• Задание №4, Для трехотраслевой экономической системы заданы матрица коэффициентов - Математические модели в экономике

  Для трехотраслевой экономической системы заданы матрица коэффициентов Прямых материальных затрат И вектор конечной продукции Найти коэффициенты полных...

• Запись экономико-математической модели в математическом виде - Разработка экономико-математической модели по оптимизации отраслевой структуры производства в СХА "Горизонт"

  В данной задаче за основные неизвестные приняты площади посева сельскохозяйственных культур по их целевому назначению и площади сенокосов и пастбищ. Х1...

• Определение коэффициентов передаточной функции по заданным динамическим каналам методом площадей. Сравнение расчетной и аналитической функции (экспериментальной) - Моделирование математической модели теплообменника

  В основе метода площадей лежит предположение, что объект может быть описан линейным дифференциальным уравнением с постоянными коэффициентами, а его...

• Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы

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

• Разработка математической модели объекта в виде д. у. и их системы - Моделирование математической модели теплообменника

  Необходимо составить математическое описание теплообменника, в котором жидкий продукт нагревается насыщенным водяным паром (расход, кг/с), до температуры...

• Введение - Моделирование математической модели теплообменника

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

• Выводы, Список литературы - Разработка математической модели оптимизации графиков занятости при многосменной организации труда и реализация ее в MS EXEL

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

• Почасовой расчет работы энергетических систем - Расчетная модель оптимизации системы теплоснабжения региона

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

• Энергосистема г. Омска - Расчетная модель оптимизации системы теплоснабжения региона

  Крупные теплофикационные системы на базе ТЭЦ общего пользования построены и функционируют в основном в городах с расчетной тепловой нагрузкой более 500...

• Построение формализованной модели оценки издержек - Модель оценки издержек в системе складского комплекса

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

• Введение - Методика и модели оптимизации входных параметров технологической цепи хлебопродуктового объединения

  Рассмотрим наиболее типичные вертикально интегрированные структуры хлебопродуктовых объединений потребительской кооперации (рис. 1, 5 в [1]). Годовой...

• Решить графически задачу нелинейного программирования, Математическая модель задачи нелинейного программирования (ЗНП) - Методика решения двойственных задач линейного программирования

  Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...

Раскраска графов - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

Предыдущая | Следующая