VII Международная студенческая научная конференция Студенческий научный форум - 2015

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

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

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

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

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

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

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

Пусть нам дана задача: в городе Невинномысске находятся заводы. Они поставляют свою продукцию в магазины, кафе и аптеки этого города. Специалисты определили возможные дорожные маршруты для того, чтобы проложить все коммуникации, и выяснили, сколько денежных средств потребуется для создания коммуникаций для каждой трассы. Итак, проложить коммуникаций для дороги между фабрикой одежды и магазином обуви составляет 15 у.е., между фабрикой одежды и мебельным заводом– 85 у.е., между фабрикой одежды и кондитерской фабрикой составляет 20 у.е., между магазином обуви и мебельным заводом - 25 у.е., между магазином обуви и обувным заводом – 65 у.е. Стоимость прокладки коммуникаций для трассы, которая соединяет кондитерскую фабрику и магазин продуктов - 5 у.е., между кондитерской фабрикой и рестораном - 50 у.е., между мебельным заводом и рестораном - 20 у.е., между магазином продуктов и хозяйственным магазином составляет 20 у.е., между хозяйственным магазином и обувным заводом - 25 у.е, между хозяйственным магазином и рестораном – 35 у.е., между обувным заводом и овощным магазином - 15 у.е, между обувным заводом и аптекой составляет 40 у.е., между рестораном и аптекой - 10 у.е., между овощным магазином и торговым центром - 20 у.е., между аптекой и металлургическим заводом составляет 30 у.е, между аптекой и торговым центром – 45 у.е., между металлургическим заводом и торговым центром, - 25 у.е. Необходимо найти такую структуру сети, при которой коммуникации связали бы все пункты, а затраты на прокладку этих коммуникаций были бы минимальны.

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

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

Для решения задачи необходимо дерево покрытия минимального веса. Эта задача решается алгоритмом Краскала - разновидностью «жадного» алгоритма.

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

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

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

, где.

, где .

, где .

, где .

, где .

, где.

, где .

, где .

Таким образом, мы нашли минимальное дерево покрытия взвешенного графа, а значит, определили оптимальную структуру сети, в которой денежные средства, которые необходимо потратить на прокладку коммуникаций, рассчитываются следующим образом: 5+10+15+15+20+20+20+20+25+25+25=200.

Из всех возможных затрат эта сумма является наименьшей.

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

Разберем задачу Коммивояжера как ещё один пример применения средств дискретной математики в экономике.

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

Расстояние между Ставрополем и Михайловском составляет 6 км, между Ставрополем и Пелагиадой - 7 км, между Ставрополем и Надеждой расстояние составляет 20 км, между Ставрополем и Татаркой - 12 км, между Ставрополем и Рождественским - 10 км. Между Михайловском и Пелагиадой расстояние составляет 5 км, между Михайловском и Надеждой - 7 км, между Михайловском и Татаркой - 9 км, между Михайловском и Рождественским - 16 км. Между Пелагиадой и Надеждой расстояние составляет 4 км, между Пелагиадой и Татаркой- 10 км, между Пелагиадой и Рождественским- 12 км. Между Надеждой и Татаркой расстояние - 3 км, между Надеждой и Рождественским - 15 км. Между Татаркой и Надеждой - 6 км, между Татаркой и Рождественским - 4 км, между Рождественским и Пелагиадой - 11 км, между Рождественским и Татаркой - 21 км. Представитель страховой фирмы должен объехать все порученные ему пункты по одному разу и вернуться назад за самый короткий срок или с наименьшими затратами на проезд.

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

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

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

.

Вычисляем коэффициенты значимости для каждого занулившегося элемента.

, , ,

, .

Теперь из матрицы нужно вычеркнуть строку и столбец, в которых находится элемент с наибольшим коэффициентом значимости. В нашем случае таким элементом является: коэффициент значимости равен 6. Для элемента установим значение1: .

После преобразований получим:

Опять вычисляем коэффициенты значимости:

, , ,

, , .

Матрица уменьшается в размере:

Для новой матрицы находим коэффициенты значимости:

, , ,

, .

Теперь матрица запишется в виде:

Коэффициенты значимости последней матрицы:

, , ,

, , .

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

Таким образом, в маршрут представителя страховой фирмы вошли ребра: {5,6}, {4,5}, {3,4}, {1,2}, {6,1}, {2,3}. Все вершины (пункты) соединились.

Длина маршрута составляет4 + 3 + 4 + 6 + 10 + 5 = 32.

Путь торговца включает расстояния между городами {Ставрополь, Михайловск}, {Михайловск,Пелагиада}, {Пелагиада, Надежда}, {Надежда, Татарка}, {Татарка, Рождественский}, {Рождественский, Ставрополь} и имеет длину, равную 32 километрам.

Список используемой литературы:

1.Соболева Т.С., Чечкин А.В. Дискретная математика. 2006 год. 255 стр.

2. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. — СПб.: Питер, 2007. — 364 с: ил. — (Серия «Учебник для вузов»).

3. Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. Исследование операций (учебное пособие) // Международный журнал экспериментального образования. 2014. № 11-1. С. 118-119.

4. Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. Линейная алгебра (учебное пособие) // Международный журнал экспериментального образования. 2014. № 11-1. С. 115.

5. Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. Математика (учебное пособие) // Международный журнал экспериментального образования. 2014. № 11-1. С. 114 - 115.

6. Попова С.В., Смирнова Н.Б., Долгих Е.В., Крон Р.В. Агроинженерия (электронный учебно-методический комплекс) // Международный журнал экспериментального образования. 2009. № S4. С. 6-7.

7. Морозова О.В., Долгополова А.Ф., Попова С.В., Крон Р.В., Смирнова Н.Б., Долгих Е.В., Тынянко Н.Н.Комплект рабочих тетрадей по курсу высшей математики для экономических специальностей // Международный журнал экспериментального образования. 2009. № S4. С. 22.

8. Немцова А.В., Попова С.В. Применение средств матричной алгебры для решения задач экономического содержания // Современные наукоемкие технологии. 2014. № 5-2. С. 171-172.

9. Смирнова Н.Б., Попова С.В. Проблемы создания математических моделей эколого-экономических систем в процессе взаимодействия человека и окружающей среды // Культура и общество: история и современность материалы III Всероссийской (с международным участием) науч.-практ.конф. Филиал РГСУ в г. Ставрополь; под редакцией О. Ю. Колосовой, Т. В. Вергун, Р. Ф. Гударенко. / Ставрополь, 2014. С. 185-190.

10. Смирнова Н.Б., Лубенцева Е.Ф. Роль математики в современном обществе // Культура и общество: история и современность материалы III Всероссийской (с международным участием) научно-практической конференции. Филиал РГСУ в г. Ставрополь; под редакцией О. Ю. Колосовой, Т. В. Вергун, Р. Ф. Гударенко. г. Ставрополь, 2014. С. 160-163.

11. Невидомская И.А., Копылова Е.П., Сотникова Ю.Д., Нивинская С.И. Применение дискретной математики при решении задач экономического содержания // Современные наукоемкие технологии. 2014. № 5-2. С. 169-171.

12. Коннова Д.А., Леликова Е.И., Мелешко С.В. Взаимодействие математики с экономикой // Современные наукоемкие технологии. 2014. № 5-2. С. 159-161.

Код для цитирования: Скопировать