Методы дискретной математики (методы формализованного представления) часто используются для анализа, исследования управленческих задач и их решения, а также для моделирования объектов исследования. В число этих методов входят методы, которые базируются на теоретико-множественных представлениях, математической логике, графах и других разделах математики.
Методы дискретной математики применяются в таких отраслях экономики, как математическое моделирование, логистика, эконометрика.
В эконометрике, например, используются булевские переменные для построения регрессионных моделей по неоднородным данным и для анализа регрессионных моделей с переменной структурой.
В данном случае исследуется только одно уравнение регрессии, в которое добавляются булевские переменные, характеризующие изучаемый фактор. Этим методом очень удобно пользоваться, если есть необходимость установить зависимость модели от какого-либо фактора.
Если в логистике требуется задать маршруты или описать потоки, то удобнее всего будет применить теорию графов. Здесь схему дорог мы можем изобразить, как ориентированный граф, и далее выбрать самый короткий маршрут.
Что же касается теории нечетких множеств, то с ее помощью можно правильно сделать выбор в пользу конкурентоспособного товара или услуги методом нечеткого предпочтения, поэтому эта теория используется в маркетологии, когда нужно проанализировать рынки экономических благ.
Рассмотрим практическое применение Жадного алгоритма, который заключается в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. В этом алгоритме пересеклись интересы дискретной математики и исследования операций.
Пусть нам дана задача: в городе Невинномысске находятся заводы. Они поставляют свою продукцию в магазины, кафе и аптеки этого города. Специалисты определили возможные дорожные маршруты для того, чтобы проложить все коммуникации, и выяснили, сколько денежных средств потребуется для создания коммуникаций для каждой трассы. Итак, проложить коммуникаций для дороги между фабрикой одежды и магазином обуви составляет 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 ребер.
Для решения задачи необходимо дерево покрытия минимального веса. Эта задача решается алгоритмом Краскала – разновидностью «жадного» алгоритма.
Пусть имеется конечное непустое множество
, 
– функция, которая ставит в соответствие каждому элементу 
этого множества неотрицательное действительное число, 
– вес элемента 
и семейство 
. Вес 
найдем сложением весов всех элементов множества 
. Нам нужно из данного семейства выбрать непустое подмножество с наименьшим весом.
Всем пунктам сети поставим в соответствие вершины графа 
, а всем ребрам графа поставим в соответствие число, которое равно сумме денежных средств, необходимых для строительства соответствующей коммуникации, связывающей объекты.
Из всех ребер выбирается ребро с наименьшим весом (исходя из алгоритма Краскала). В нашем случае таким ребром является ребро 
, получаем граф 
. Далее строится граф 
, равный сумме
, где 
– ребро, которое имеет самый маленький вес среди тех ребер, которые не входят в граф 
, и не составляющий циклов с ребрами 
, 
{8,10}. Граф 
находится сложением 
и 
, где 
. Аналогично находим графы 
– T11.
, где 
.
, где 
.
, где 
.
, где 
.
, где 
{9, 12}.
, где
.
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, при этом 
. Если 
, то ставим символ 
, так как такой дороги не существует. В нашем случае матрица примет вид:
Матрица A строится для того, чтобы в каждой строке и в каждом столбце получить не менее одного кратчайшего маршрута (нулевого приведенного значения). Для этого в каждой строке матрицы A от каждого элемента мы вычитаем значение минимального элемента этой строки. В результате получим:
Вычисляем теперь коэффициент приведения. Он равен сумме всех минимальных элементов матрицы 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.
После преобразований получим:
Опять вычисляем коэффициенты значимости:
k12 = 2, k23 = 2, k45 = 5, k61 = 2, а34 = 3, а45 = 1.
Матрица уменьшается в размере:
Для новой матрицы находим коэффициенты значимости:
k12 = 2, k23 = 2, а45 = 1, k61 = 2, k34 = 3.
Теперь матрица запишется в виде:
Коэффициенты значимости последней матрицы:
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 (дата обращения: 21.11.2024).