Курсовая работа: Применение методов дискретной математики в экономике
P(x, y, z)=b0×1Åb1×xÅb2×yÅb3×zÅb4×x×yÅb5×x×zÅb6y×zÅb7x×y×z
Метод неопределенных коэффициентов заключается в том, что путем последовательной подстановки переменных x, y, z и соответственно значений функции при этих переменных, из таблицы 1 в данный полином (4), строится система уравнений:
0=b0×1Åb1×0Åb2×0Åb3×0Åb4×0×0Åb5×0×0Åb60×0Åb70×0×0
0=b0×1Åb1×0Åb2×0Åb3×1Åb4×0×0Åb5×0×1Åb60×1Åb70×0×1
1=b0×1Åb1×0Åb2×1Åb3×0Åb4×0×1Åb5×0×0Åb61×0Åb70×1×0
0=b0×1Åb1×0Åb2×1Åb3×1Åb4×0×1Åb5×0×1Åb61×1Åb70×1×1
0=b0×1Åb1×1Åb2×0Åb3×0Åb4×1×0Åb5×1×0Åb60×0Åb71×0×0
0=b0×1Åb1×1Åb2×0Åb3×1Åb4×1×0Åb5×1×1Åb60×1Åb71×0×1
0=b0×1Åb1×1Åb2×1Åb3×0Åb4×1×1Åb5×1×0Åb61×0Åb71×1×0
0=b0×1Åb1×1Åb2×1Åb3×1Åb4×1×1Åb5×1×1Åb61×1Åb71×1×1
По свойству суммы по модулю два находится b:
b0=0, b1=0, b2=1, b3=0, b4=1, b5=0, b6=1, b7=1
Полином Жегалкина будет иметь вид:
¦(x, y, z) = y Å x×y Å y×z Å x×y×z
Правильность построения полинома проверяется таблицей истинности:
Таблица 4 - Таблица истинности для полинома Жегалкина
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| x | y | z | x&y | Å | y&z | Å | x&y&z | Å |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Дифференцирование функции нескольких переменных.
Производной булевой
функции ¦(xn) по совокупности
переменных 
называется функция:
На основе данной формулы (5) находится производная по одной переменной x
Для данной функции (1) производная по формуле (6) принимает вид:
Таблица 5 - Производная ∂¦⁄∂x для формулы(7)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| x | y | z |
|
& |
|
|
|
|
|
|
|
|
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
Вектор значений функции (7) имеет вид:
Производная по двум переменным находится также по формуле (5):
Для данной функции (1) производная принимает вид:
Таблица 6 - Производная ∂2¦⁄∂(x;y) для формулы(9)
1 |
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| x |
|
|
& |
|
|
|
|
|
|
|
|
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
Вектор значений функции (6) имеет вид:
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 у.е. Необходимо, чтобы коммуникации связали все объекты, затраты на прокладку данных коммуникаций должны быть минимальны.
Для удобства записи вводятся следующие обозначения:
V1 – завод №1, V2 – магазин №1, V3 – хлебозавод, V4 –завод №2, V5 – магазин №2 V6 –продуктовый магазин, V7 – обувная фабрика, V8 –кафе, V9 – магазин №3, V10 – аптека, V11 –завод №3, V12 – торговый центр.
Если создать графическую интерпретацию данной модели, то видно что получился граф с 12 вершинами и 18 ребрами.
