Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

ПРИМЕНЕНИЕ МЕТОДОВ ДИСКРЕТНОЙ МАТЕМАТИКИ В ЭКОНОМИКЕ

Одукалец А.А. 1 Хорошман П.А. 1
1 Ставропольский государственный аграрный университет
1. Соболева Т.С., Чечкин А.В. Дискретная математика. 2006.
2. Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. 2-е изд. – СПб.: Питер, 2007.
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.

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

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

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

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

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

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

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

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

Введём обозначения: V1 – фабрика одежды, V2 – магазин обуви, V3 – кондитерская фабрика, V4 – мебельный завод, V5 – магазин продуктов, V6 – хозяйственный магазин, V7 – обувной завод, V8 – ресторан, V9 – овощной магазин, V10 – аптека, V11 – металлургический завод, V12 – торговый центр.

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

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

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

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

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

missing image file, где missing image file.

missing image file, где missing image file.

missing image file, где missing image file.

missing image file, где missing image file.

missing image file, где missing image file{9, 12}.

missing image file, гдеmissing image file.

T10 = T9 + e10, где e10 = {6, 7}.

T11 = T10 + e11, где e11 = {11, 12}.

Таким образом, мы нашли минимальное дерево покрытия взвешенного графа, а значит, определили оптимальную структуру сети, в которой денежные средства, которые необходимо потратить на прокладку коммуникаций, рассчитываются следующим образом: 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 км. Представитель страховой фирмы должен объехать все порученные ему пункты по одному разу и вернуться назад за самый короткий срок или с наименьшими затратами на проезд.

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

missing image file

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

missing image file

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

kпр = 6 + 5 + 4 + 3 + 4 + 10 = 20.

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

k23 = 2, k34 = 1 + 2 = 3, k45 = 5, k61 = 2, k56 = 2 + 4 = 6.

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

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

missing image file

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

k12 = 2, k23 = 2, k45 = 5, k61 = 2, а34 = 3, а45 = 1.

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

missing image file

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

k12 = 2, k23 = 2, а45 = 1, k61 = 2, k34 = 3.

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

missing image file

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

k12 = 7, k61 = 7, k23 = 2, а12 = 1, а61 = 1, а23 = 1.

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

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

Длина маршрута составляет:

4 + 3 + 4 + 6 + 10 + 5 = 32.

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


Библиографическая ссылка

Одукалец А.А., Хорошман П.А. ПРИМЕНЕНИЕ МЕТОДОВ ДИСКРЕТНОЙ МАТЕМАТИКИ В ЭКОНОМИКЕ // Международный студенческий научный вестник. – 2015. – № 3-4. ;
URL: https://eduherald.ru/ru/article/view?id=14133 (дата обращения: 07.12.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074