Метод фора и мальгранжа

Метод фора и мальгранжа

Пусть дан граф G=(X, A), где X=< хi >, i =1, 2, . , n – множество вершин, а A=< ai >, i =1, 2, . m – где множество дуг, описанных матрицей смежности. Алгоритм разбиения заключается в следующем [4].

Для произвольной вершины хi X находим прямое T + (хi) и обратное T — (хi) транзитивные замыкания.

Находим T + (хi) T — (хi). Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G1 = (Х1, A1).

Из исходного графа вычитаем подграф G1:G ‘=GG1, Х’=XХ1 .

Граф G ‘принимаем за исходный граф и пока X ‘ Ø пункты 1, 2, 3 алгоритма повторяются.

Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на рис. 7.1,a, матрица смежности которого показана на рис. 7.1,б.

Начальной вершиной первого разбиения выберем х1 . Построим прямое и обратное транзитивные замыкания. T + (х1)– столбец, показанный справа от матрицы А, а T — (х1) – строка, находящаяся ниже матрицы смежности.

Находим T + (х1) T — (х1) = <х1, х7, х11>. Эти вершины и составляют первый выделенный, максимальный сильно связный подграф G1 = (Х1, A1), где Х1 = <х1, х7, х11>, а матрица смежности A1 подграфа G1 показана на таблица 7.1.

Из исходного графа G вычитаем подграф G1 G ‘ = G G1 ;

Так как X ‘ не пустое множество, то G’ принимаем за G и переходим ко второму разбиению.

Выбираем любую вершину, принадлежащую X, например, х2 , и находим T + (х2) и T — (х2). Это показано в таблице 7.2. T + (х2) = < х2, х8 >; T — (х2) = < х2 >.

T + (х2) T — (х2) = < х2 >. Следовательно, второй выделенный подграф G2 состоит из одной вершины х2 .

Так как X ‘ не пустое множество, то G ‘ принимаем за G и процесс разбиения продолжается.

7. Лекция: Методы разбиения графа на максимальные сильно связные подграфы

Пути и маршруты

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

Например, для графа на рис. 8.1 последовательности дуг

являются путями. Пути могут быть различными.

Орцепью (или простым путем) называется такой путь, в котором каждая дуга используется не более одного раза.

Так пути M1 и M2 являются орцепями, а M3 нет, поскольку дуга a6 используется дважды.

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

Простой орцепью является путь M2 .

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

Путь или маршрут можно изображать также последовательностью вершин. Так путь M1 можно представить последовательностью вершин х2, х5, х4, х3, х5, х6 , и такое представление часто оказывается более полезным.

Вес и длина пути

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

Граф G, описываемый тройкой вида

где Х = < хi >, i =1, 2, 3, . n – множество вершин,

А = < ai >, i = 1, 2, 3, . m – множество дуг,

С = i>, i = 1, 2, 3, . m – множество характеристик дуг, называется графом со взвешенными дугами.

Пример такого графа приведен на рис. 8.2,а. При рассмотрении пути M, представленного последовательностью дуг(a1, a2, . aq), за его вес (или длину, или стоимость) принимается число L(M), равное сумме весов всех дуг, входящих в путь, т. е. L(M)=(ci) для всех ai M.

Читайте также:  Зачем на стилусе кнопка

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

Рис. 8.2. Взвешенные графы: а – граф со взвешенными дугами; б – граф со взвешенными вершинами; в – взвешенный граф

Граф со взвешенными вершинами – это граф, описываемый тройкой G = ( X, А, V ), где Х = < хi >, i = 1, 2, . n – множество вершин графа;

А = < ai >, i = 1, 2, . m – множество дуг графа;

V =< vi >, i = 1, 2, . n – множество характеристик вершин.

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

И наконец, взвешенный граф определяется четверкой вида G = (Х, А, V, С), т. е. и дуги, и вершины этого графа имеют некоторые характеристики.

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

Орциклы и циклы

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

Пути М1 и М3 являются замкнутыми простыми орцепями, называемыми контурами или простыми орциклами, поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной). Путь М2 не является контуром, так как вершина х1 используется в нем дважды.

Контур, проходящий через все вершины графа, имеет особое название – гамильтонов контур. Путь М3 является гамильтоновым контуром. Он показан штриховой линией на рис. 8.3.

Рис. 8.3. Орциклы в графе

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

Для неориентированного графа понятия цикла и гамильтонова цикла аналогичны понятиям орцикла и гамильтонова контура в орграфе.

Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, содержащий эйлеров цикл, называется эйлеровым графом.

Основная теорема о существовании эйлерова цикла формулируется так.

ТЕОРЕМА. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю 0 или 2.

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

На реке Преголя в Кенигсберге было два острова. Они соединялись между собой и с берегами реки семью мостами, как схематично показано на рис. 8.4. Задача заключалась в том, чтобы за одну прогулку обойти все семь мостов, проходя по каждому мосту только один раз, и вернуться в исходное место.

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

Читайте также:  Can t initialize game блицкриг что делать

Рис. 8.4. а – схема Кенигсбергских мостов; б – эквивалентный граф

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

Рубрика Маркетинг, реклама и торговля
Вид статья
Язык русский
Дата добавления 30.07.2017
Размер файла 1,3 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

Л.Н. Клянина 1 , А.А. Рощупкина 1 , И.В. Левичев 2 , Академия строительства и архитектуры ДГТУ, Ростов-на-Дону, ІРоссийский экономический университет имени Г.В. Плеханова, Москва.

Ключевые слова: стимулирование сбыта, виды рекламы, продажи, социально-демографические предпочтения, эффективное планирование, максимизация прибыли, метод Фора Мальгранжа.

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

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

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

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

Общее стимулирование, используемое в зоне продажи, необходимо для оживления торговли. Этот вид включает в себя сразу продажи со скидками, демонстрации товаров, дегустации, оформление залов, рекламные щиты, вывески с объяснениями, а также рекламная кампания в СМИ.

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

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

Если внимание покупателя будет акцентированно на определенных марках или типах товара, то можно существенно увеличить свои продажи. Этот эффект послужил основой для одной из областей — "мерчендайзинг". Это комплекс мероприятий, проводимых в торговом зале и направленных на продвижение товара, марки, вида или упаковки. Результатом мерчандайзинга является стимулирование желания потребителей выбрать и купить продвигаемый товар.

Проводя стимулирование продаж, следует помнить, что:

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

2. Более эффективным является относительно короткий период стимулирования сбыта. Непродолжительность мероприятий призывает покупателя скорее воспользоваться предложением.

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

Читайте также:  Как создать аккаунт в телевизоре сони бравиа

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

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

Общее количество людей, которых можно назвать потенциальными слушателями, в возрасте от 12 до 59 лет, составляет около 117009 тыс. человек. Доля радиослушателей показана на рис. 1.

Рис. 1 — Соотношение радиослушателей

Около 93,015 млн. (117,009 млн. * 0,795) человек являются слушателями FM-радиостанций. Для расчета слушателей радио FM в Ростовской области воспользуемся данными Росстата. На территории области проживает 1170 тыс. человек в возрасте от 12 до 59 лет, которые потенциально могут быть клиентами развлекательного центра. Слушателями радио являются 0,93 млн. человек.

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

Распределение социально-демографических характеристик среди слушателей в сравнении с тем, кто не слушает FM-станции представлено на рис. 2. эффективность реклама стимулирование мальгранж

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

Рис. 2 — Описательные характеристики аудитории

Уровень дохода в ходе исследования определялся на человека в семье. В результате были получены данные, представленные на рис. 3.

Рис. 3 — Описательные характеристики аудитории: обеспеченность

Рис. 4 — Поведенческие характеристики аудитории

В результате была получена информация, представленная на рис. 4 о предпочтениях слушателей и не слушателей радио.

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

Рис. 5 — Предпочтения радиослушателей

Рис. 6 — Музыкальные вкусы всех респондентов

Рассмотрим эффективность рекламы в стимулировании сбыта на примере проведения рекламной компании строительной организации ООО "Спектр-металл".

Определим оптимальное распределение финансовых средств на виды рекламы в г. Ростов-на-Дону, укладываясь в затраты на реализацию проекта в целом (при объеме финансирования в размере 900000 рублей), с целью максимизации прибыли.

Расчетный срок проведения рекламной компании — 1 месяц. Реклама осуществляется по следующим направлениям:

1. Реклама на телеканале "Россия 24" (3 раза в сутки по 4500 рублей);

2. Радио — реклама (6 раз в стуки на радиостанциях города в среднем по 2000 рублей);

3. Реклама на остановках общественного транспорта (40 банеров, в среднем по 6050 рублей);

4. Реклама в бизнес — центрах (в 36 лифтах по 4500 рублей);

5. Реклама в лифтах жилых домов (на 200 стендах по 500 рублей);

6. Реклама в газетах и журналах ("аргументы и факты на Дону 72000 рублей);

7. Автобусы и маршрутки (по 3 рекламы в каждой из 50 единиц техники по 387 рублей).

Решение поставленной задачи основывается на данных таблицы 1.

Ссылка на основную публикацию
Лексический разбор текста образец
1. Найти многозначные слова (2-3), определить их значение в данном тексте, привести (для доказательства) другие значения 2. Найти слова в...
Компьютер не видит рутокен что делать
1. Возможно, на токене перегорел светодиод (лампочка). Для проверки следует: Открыть «Пуск» > «Панель управления» > «Панель управления Рутокен» (если...
Критическая ошибка 40 с сервера что делать
Ошибка "не удается завершить защищенную транзакцию" у пользователей браузера Opera 12.16 - 12.17 может возникать при попытке авторизоваться на некоторых...
Лучшие приложения для samsung gear s3 frontier
Samsung Galaxy Watch – это одни из самых ожидаемых смарт-часов этого года. О возможностях и характеристиках этих часов ходило множество...
Adblock detector