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

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

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

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

Введём обозначения:– фабрика одежды, – магазин обуви, – кондитерская фабрика, – мебельный завод, – магазин продуктов, – хозяйственный магазин,– обувной завод, – ресторан, – овощной магазин, – аптека, - металлургический завод, – торговый центр. При создании графической интерпретации данной модели нам становится понятно, что получился граф, который содержит 12 вершин и 18 ребер. Для решения задачи необходимо дерево покрытия минимального веса. Эта задача решается алгоритмом «краскала» – разновидностью «жадного» алгоритма.

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

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

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

, где

, где

, где

, где

, где

, где

, где

, где

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

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

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

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

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

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

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

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

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

k₂₃= 2, k₃₄= 1 + 2 = 3, k₄₅= 5, k₆₁= 2, k₅₆= 2 + 4 = 6.

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

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

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

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

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

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

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

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

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

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

.

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

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

Список литературы

1. Долгополова А.Ф., Гулай Т.А., Литвин Д.Б. Финансовая математика в инвестиционном проектировании (учебное пособие) // Международный журнал прикладных и фундаментальных исследований. 2014. № 8-2. С. 178-179.

2. Долгополова А.Ф., Колодяжная Т.А. Руководство к решению задач по математическому анализу. Часть 1//Международный журнал экспериментального образования. -2011. -№ 12. -С. 62-63.

3. Долгополова А.Ф., Гулай Т.А., Литвин Д.Б. Руководство к решению задач по математическому анализу. Часть 2//Международный журнал экспериментального образования.-2012. № 2. С. 81-82.

4. Долгополова А.Ф., Шмалько С.П. Пути повышения качества образования студентов экономических направлений // Политематический сетевой электронный научный журнал КубГАУ №02(116). Краснодар, 2016. С. 228-238.

5. Грушевский С.П., Засядко О.В. Мороз О.В. Формирование профессиональных компетенций студентов экономических направлений подготовки бакалавров в процессе изучения математики // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. 2015. № 107. С.400-418.

6. Засядко О.В., Мороз О.В. Междисциплинарные связи в процессе обучения математике студентов экономических специальностей //Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. 2016. № 119. С. 349-359.

7. Долгополова А.Ф., Мелешко С.В., Цыплакова О.Н. Применение анализа чувствительности модели при восстановлении финансового равновесия предприятия // Аграрная наука Северо - Кавказскому федеральному округу. Сборник научных трудов по материалам 80-й Ежегодной научно-практической конференции. Ставропольский государственный аграрный университет. 2015. С. 98-103.

8. Шмалько С.П. Формирование профессионально ориентированного мышления у студентов экономических направлений. // Культурная жизнь Юга России. 2010. №1. С. 99-101.

9. Цысь Ю.В., Долгополова А.Ф., Элементы линейной алгебры и их применение при решении экономических задач // Современные наукоемкие технологии. 2013. № 6. С. 91-93

10. Литвин Д. Б., Гулай Т. А., Долгополова А. Ф. Применение операционного исчисления в моделировании экономических систем // Аграрная наука, творчество, рост. 2013. С. 263-265.

11. Литвин Д. Б., Гулай Т. А., Долгополова А. Ф. Коррекция динамического диапазона статистических данных // Статистика вчера, сегодня, завтра : сб. по материалам Междунар. науч.-практ. конф. 2013. С. 148-152.

12. Долгополова А.Ф. Моделирование стратегии управления в социально-экономических системах с использованием Марковских процессов/А.Ф. Долгополова//Вестник АПК Ставрополья. -2011. № 1. С. 67-69.

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