Применение методов дискретной математики в экономике

Курсовая работа содержит пояснительную записку на 33 листах формата А4, включающую 6 таблиц, 13 рисунков, 9 литературных источников.

БУЛЕВА ФУНКЦИЯ, ВЫСКАЗЫВАНИЯ, ЛОГИЧЕСКИЕ ОПЕРАЦИИ, ТАБЛИЦЫ ИСТИННОСТИ, ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА, КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА, ПОЛИНОМ ЖЕГАЛКИНА, ПРОИЗВОДНАЯ ЛОГИЧЕСКОЙ ФУНКЦИИ, ГРАФ, «ЖАДНЫЙ» АЛГОРИТМ, АЛГОРИТМ ДЕЙКСТРА, ЗАДАЧА КОММИВОЯЖЁРА, НЕЧЕТКОЕ МНОЖЕСТВО, КОНКУРЕНТОСПОСОБНОСТЬ, НЕЧЕТКОЕ ОТНОШЕНИЕ ПРЕДПОЧТЕНИЯ, АЛЬТЕРНАТИВА, СТЕПЕНЬ НЕДОМИНИРУЕМОСТИ

Объект исследования данной курсовой работы: дискретные системы, методы дискретной математики и их применение в области экономики.

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

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

Содержание

Введение

1 Применение логических функций

1.1 Применение методов дискретной математики в экономике

1.2 Практическое применение методов математической логики

2 Применение теории графов

2.1 Практическое применение жадного алгоритма

2.2 Применение алгоритма Дейкстры

2.3 Задача коммивояжера

3 Практическое применение теории нечетких множеств

Заключение

Список использованных источников

Введение

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

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

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

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

1.2 Практическое применение методов математической логики

Всякая логическая функция «n» переменных может быть задана таблицей, в левой части которой перечислены все 2ⁿ наборов значений переменных (то есть всевозможных наборов двоичных векторов длины «n»), а в правой части приведены значения функции на этих наборах. При любом фиксированном упорядочении наборов значений переменных логическая функция «n» переменных полностью определена вектор-столбцом своих значений, то есть вектором длины 2ⁿ. Поэтому число различных логических функций «n» переменных будет . В самом деле, для одного набора значений своих переменных (строка левой части таблицы) значение функции может быть либо 1, либо 0 (две возможности). Число же возможных различных наборов аргументов функции, как уже отмечалось равно 2ⁿ, поэтому число различных логических функций будет/1/.

Заданием в данном пункте является построение таблицы истинности для следующего высказывания:

,

Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. “Истинность” или “ложность” предложения - это истинностное значение высказывания. Каждому высказыванию сопоставляется переменная, равная 1, если высказывание истинно, и равная 0, если оно ложно. Эти высказывания будут считаться простыми. Из простых высказываний с помощью логических связок могут быть построены составные высказывания. В таблице 1 приведены некоторые логические связки, используемые при задании данной функции (1).

Таблица 1-Логические связки

Правильно построенные составные высказывания называются (пропозиционарными) формулами. Истинностное значение формулы определяется через истинностные значения её составляющих в соответствии с единой таблицей истинности (таблица 2).

Таблица 2-Истиностные значения формул высказывания

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

, (1)

После последовательного выполнения всех логических операций составляется таблица истинности для данной функции

Таблица 3- Таблица истинности функции (1)

Приведение функции к конъюнктивным и дизъюнктивным нормальным формам. Конъюнктивным (дизъюнктивным) одночленом от переменных а₁, а₂, а₃,…,а_n называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений (конъюнктивных одночленов), называется дизъюнктивной нормальной формой (ДНФ) данной формулы. Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений (дизъюнктивных одночленов), называется конъюнктивной нормальной формой (КНФ) данной формулы /2/. Справедливы следующие теоремы: любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде ДНФ по формуле:

V (2)

Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде КНФ.

(3).

Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание /2/.

Искомая ДНФ для функции (1) имеет вид:

Искомая КНФ для функции (1) будет иметь следующий вид:

В расчетах ДНФ и КНФ использована методика /2/.

Построение полинома Жегалкина.

Представление булевой функции над базисом {0,1,v,} называется полиномом Жегалкина.

Таким образом, всякая булева функция представима в виде:

где ? - сложение по модулю два, знак ? обозначает конъюнкцию/7/.

Для функции f(x,y,z)(1) полином Жегалкина имеет вид:

P(x, y, z)=₀1₁x₂y₃z₄xy₅xz₆yz₇xyz

Метод неопределенных коэффициентов заключается в том, что путем последовательной подстановки переменных x, y, z и соответственно значений функции при этих переменных, из таблицы 1 в данный полином (4), строится система уравнений:

0=₀1₁0₂0₃0₄00₅00₆00₇000

0=₀1₁0₂0₃1₄00₅01₆01₇001

1=₀1₁0₂1₃0₄01₅00₆10₇010

0=₀1₁0₂1₃1₄01₅01₆11₇011

0=₀1₁1₂0₃0₄10₅10₆00₇100

0=₀1₁1₂0₃1₄10₅11₆01₇101

0=₀1₁1₂1₃0₄11₅10₆10₇110

0=₀1₁1₂1₃1₄11₅11₆11₇111

По свойству суммы по модулю два находится :

₀=0, ₁=0, ₂=1, ₃=0, ₄=1, ₅=0, ₆=1, ₇=1

Полином Жегалкина будет иметь вид:

(x, y, z) = y xy yz xyz

Правильность построения полинома проверяется таблицей истинности:

Таблица 4 - Таблица истинности для полинома Жегалкина

Дифференцирование функции нескольких переменных.

Производной булевой функции (xⁿ) по совокупности переменных называется функция:

На основе данной формулы (5) находится производная по одной переменной x

Для данной функции (1) производная по формуле (6) принимает вид:

Таблица 5 - Производная ???x для формулы(7)

Вектор значений функции (7) имеет вид:

Производная по двум переменным находится также по формуле (5):

Для данной функции (1) производная принимает вид:

Таблица 6 - Производная ?²??(x;y) для формулы(9)

Вектор значений функции (6) имеет вид:

2. Применение теории графов

2.1 Практическое применение жадного алгоритма

На территории некого города N размещены заводы и магазины, в которые поставляется продукция с этих заводов. В результате разработки были определены возможные трассы для прокладки коммуникаций и оценена стоимость их создания для каждой трассы. Стоимость прокладки коммуникаций для трассы между заводом №1 и магазином удобрений составляет 15 у.е., между заводом №1 и заводом №3 - 85 у.е., между заводом №1 и хлебозаводом - 20 у.е. Между магазином №1 и заводом №2 составит 25 у.е., между магазином №1 и обувной фабрикой - 65 у.е. Стоимость прокладки коммуникаций для трассы, соединяющей хлебозавод и магазин №2 - 5 у.е., между хлебозаводом и кафе - 50 у.е., между заводом №2 и кафе - 20 у.е., между магазином №2 и продуктовым магазином - 20 у.е., между продуктовым магазином и обувной фабрикой - 25 у.е, между продуктовым магазином и кафе - 35 у.е., между обувной фабрикой и магазином №3 - 15 у.е, между обувной фабрикой и аптекой - 40 у.е., между кафе и аптекой - 10 у.е., между магазином №3 и торговым центром - 20 у.е., между аптекой и заводом №3 составит 30 у.е, между аптекой и торговым центром - 45 у.е., между заводом №3 и торговым центром, - 25 у.е. Необходимо, чтобы коммуникации связали все объекты, затраты на прокладку данных коммуникаций должны быть минимальны.

Для удобства записи вводятся следующие обозначения:

V₁ - завод №1, V₂ - магазин №1, V₃ - хлебозавод, V₄ -завод №2, V₅ - магазин №2 V₆ -продуктовый магазин, V₇ - обувная фабрика, V₈ -кафе, V₉ - магазин №3, V₁₀ - аптека, V₁₁ -завод №3, V₁₂ - торговый центр.

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

Рисунок 1- Графическая интерпретация задачи о оптимальной структуре сети

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

Пусть имеется конечное множество Е, |E|=18, весовая функция w: ER⁺ и семейство ?? 2^Е. Требуется найти ХЕ, такое что :

Пусть Е - непустое конечное множество, w: ER⁺ - функция, ставящая в соответствие каждому элементу е этого множества неотрицательное действительное число w(e) - вес элемента е. Для Х Е вес w(Х)определим как сумму весов всех элементов множества Х:

где

Другими словами, необходимо выбрать в данном семействе непустое подмножество наименьшего веса.

Сопоставим каждому пункту сети вершину графа G. А каждому ребру этого графа сопоставим число, равное стоимости строительства соответствующей коммуникации: (рисунок 1).

Примером жадного алгоритма служит алгоритм Краскала /3/.

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

Согласно алгоритму Краскала, выбирается ребро минимального веса. В данном случае это будет ребро е₁ = {3,5}, получаем граф Т₁.

Строится граф Т₂ = Т₁ + е₂, где е₂ - ребро, имеющее минимальный вес среди ребер, не входящих в Т₁ и не составляющий циклов с ребрами Т₁, е₂ {8,10}.

Т₃ = Т₂ + е₃, где е₃ = {7,9}.

Т₄ = Т₃ + е₄, где е₄ = {1,2}.

Т₅ = Т₄ + е₅, где е₅ = {1,3}.

Т₆ = Т₅ + е₆, где е₆ = {5,6}.

Т₇ = Т₆ + е₇, где е₇ = {4,8}.

Т₈ = Т₇ + е₈, где е₈ = {9,12}

Т₉ = Т₈ + е₉, где е₉ = {2,4}.

Т₁₀ = Т₉ +е₁₀, где е₁₀ = {6,7}.

Т₁₁ = Т₁₀ + е₁₁, где е₁₁ = {11,12}.

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

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

Рисунок 2 - Решение задачи о оптимальной структуре сети

Коммуникации проложат между следующими пунктами: аптека - кафе - завод №2 - магазин №1 - завод №1 - хлебозавод - магазин №2 - продуктовый магазин - обувная фабрика - магазин №3 - торговый центр.

2.2 Применение алгоритма Дейкстры