Дискретная математика и математические методы экономики с применением VBA Excel

Дискретная математика 
и математические методы 
экономики с применением 
VBA Excel

Москва, 2023

О. А. Сдвижков

2-е издание, электронное

УДК 330.4:004.91MS Excel
ББК 65в631с515
C27

C27
Сдвижков, Олег Александрович.
Дискретная математика и математические методы экономики с применением 
VBA Excel / О. А. Сдвижков. — 2-е изд., эл. — 1 файл pdf : 213 с. — 
Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо 
Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-559-6

В книге приведены задачи по дискретной математике и математическим методам 
экономики, а также показано их решение на компьютере с помощью специально 
созданных программ (макросов) в среде VBA Excel. Материал книги охватывает 
булевы функции, конечные автоматы, машины Тьюринга и Поста, нормальные алгоритмы, 
графы, производство и потребление товаров, управление портфелем ценных 
бумаг и запасами, замкнутые системы массового обслуживания, методы кластеризации. 
Отдельная глава посвящена задаче коммивояжера.
Издание ориентировано на студентов технических, информационных и экономических 
специальностей вузов, а также будет полезно и более широкому кругу 
пользователей MS Excel.

УДК 330.4:004.91MS Excel 
ББК 65в631с515

Электронное издание на основе печатного издания: Дискретная математика и математические 
методы экономики с применением VBA Excel / О. А. Сдвижков. — Москва : ДМК Пресс, 2016. — 
212 с. — ISBN 978-5-97060-181-5. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами 
защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.


ISBN 978-5-89818-559-6
© Сдвижков О. А., 2012
© Оформление, ДМК Пресс, 2016

Содержание

Предисловие ................................................................................................6

 Часть I

Дискретная математика с применением VBA Excel ............................ 8

 Глава 1

Функции алгебры логики  ...........................................................................9
§1. Элементарные функции алгебры логики ...........................................9
§2. Разложение булевых функций по переменным ..............................15
§3. Классы Поста .....................................................................................23
§4. Частично определенные булевы функции ......................................30

 Глава 2

Машины Тьюринга, Поста и нормальные алгоритмы ........................37
§1. Понятие машины Тьюринга  ..............................................................37
§2. Программирование по Тьюрингу ....................................................39
§3. Макрос нахождения выходного слова  ...........................................43
§4. Нормальные алгоритмы ...................................................................45
§5. Машина Поста ...................................................................................50

 Глава 3

Конечные автоматы ................................................................................... 55
§1. Автоматы Мили .................................................................................. 55
§2. Минимизация автоматов алгоритмом Мили  ...................................59
§3. Автоматы Мура ..................................................................................63
§4. Частично определенные автоматы  .................................................67

Содержание
4

 Глава 4

Элементы теории графов .........................................................................74
§1. Основные понятия  ...........................................................................74
§2. Задача о минимальном дереве-остове  ..........................................79
§3. Задача о назначениях ........................................................................82
§4. Алгоритм Дейкстры  ......................................................................... 85
§5. Задача о гиперсфере минимального радиуса................................90
§6. Транспортная задача .........................................................................97

 Глава 5

Задача коммивояжера ........................................................................... 100
§1. Свойства оптимальных контуров  ................................................. 100
§2. Метод ветвей и границ .................................................................. 107
§3. Сведение к задаче линейного программирования ......................114
§4. Сведение к задаче квадратичного программирования ...............119
§5. Обобщения задачи коммивояжера  ..............................................124

 Часть II

Математические методы экономики с применением 
VBA Excel ...................................................................................................135

 Глава 1

Математические модели производства и потребления 
товаров  .....................................................................................................136
§1. Модель В. Леонтьева ......................................................................136
§2. Задачи с функцией полезности ......................................................144
§3. Задачи с производственной функцией .........................................150
§4. Характеристики производства ......................................................155

 Глава 2

Управление портфелем ценных бумаг ...............................................157
§1. Средние доходности и ковариационная матрица  ......................157
§2. Задачи оптимизации портфеля ......................................................159
§3. Эффективная граница ......................................................................164

Содержание

 Глава 3

Замкнутые системы массового обслуживания .................................168
§1. Одноканальные замкнутые СМО ....................................................168
§2. Многоканальные замкнутые СМО ..................................................171
§3. Макрос для замкнутых систем МО .................................................175

 Глава 4

Статические модели управления запасами .......................................184
§1. Макрос управления запасами ........................................................184
§2. Тестирование макроса ...................................................................192

 Глава 5

Методы кластеризации ...........................................................................198
§1. Кластеризация методом k-средних ...............................................198
§2. Иерархическая кластеризация (макрос Joining) ..........................201
§3. Иерархическая кластеризация (макрос Ward) .............................204
§4. Кластеризация с помощью циклов ............................................... 206

Литература ................................................................................................211

В настоящее время уже недостаточно знать математические методы, 
надо еще знать компьютерные технологии их применения, так 
как ими искомые результаты находятся быстрее. При этом особый 
интерес представляют такие технологии, на применение которых за-
трачивается минимум времени. Подобным технологиям и посвящена 
данная книга.
Дискретная математика и математические методы экономики – 
важнейшие, тесно связанные математические разделы, имеющие 
большое прикладное значение. Однако в информационных математических 
технологиях фактически нет инструментов для решения задач 
этих разделов, а эти решения отличаются большой трудоемкостью. 
Поэтому на процедурном языке VBA (Visual Basic for Applications) 
программного комплекса MS Excel 2003 автором были разработаны 
специальные программы (макросы), предназначенные для решения 
на компьютере типовых задач этих разделов, вообще говоря, по принципу «
ввод данных задачи → ответ», то есть автоматически. 
Согласно справочным сведениям MS Excel:
 •
макрос – последовательность команд и функций, хранящаяся 
в модуле VB, которую можно выполнить всякий раз, когда это 
необходимо;
 •
проект макроса – совокупность компонентов, в том числе 
форм, текста программы и модулей классов, которые составляют 
макрос.
В MS Excel имеется макрорекордер, но записать им разработанные 
макросы нельзя, в основном потому, что они поддерживают произвольные 
объемы начальных данных. Их можно создать только непосредственным 
программированием. К программным кодам большинства 
макросов даны подробные комментарии. 
В данной книге краткие сведения по дискретной математике и математическим 
методам экономики, необходимые для решения основ-

Предисловие

Предисловие

ных типов задач, дополнены сведениями по технологиям решения 
этих задач на компьютере с помощью созданных макросов. В ней на 
большом числе конкретных задач подробно показывается, как для 
каждого типа задач надо вводить начальные данные, запускать вычисления 
и считывать результаты. Большое число рисунков, демонстрирующих, 
что будет на экране монитора в процессе решения той или 
иной задачи, позволяет понять технологии применения макросов, не 
включая компьютера. Условия задач в основном взяты из наиболее 
популярных сборников задач и учебных пособий.
В частности, показывается, как макросами решаются такие трудоемкие 
задачи, как:
 •
минимизация ДНФ булевой функции алгоритмом Квайна;
 •
минимизация конечного полностью определенного автомата 
алгоритмом Мили;
 •
нахождение объемов ресурсов, обеспечивающих максимальную 
прибыль.
Отдельная глава посвящена задаче коммивояжера и компьютерным 
технологиям ее решения. Кроме известных методов (ветвей и 
границ, сведение к линейному программированию), в ней рассматриваются 
обобщения задачи коммивояжера и новые подходы (пронумерованные 
леммы и теоремы), с помощью которых можно получить 
оптимальный контур, в частности позволяющие:
 •
упростить задачу коммивояжера;
 •
свести ее к задаче квадратичного программирования.
Подробно рассмотрена ставшая популярной в последние годы задача 
о гиперсфере (окружности) минимального радиуса. Для нее найдены 
алгоритмы решения и разработаны соответствующие макросы.
Макросы, всего их около 50, находятся в отдельных рабочих книгах 
Excel, собранных в папке VBAcodes, ссылка для скачивания: 
http://www.oasdv.narod.ru. 
Макросы поддерживаются в MS Excel 2007 и 2010.
Книга ориентирована на студентов технических, информационных 
и экономических специальностей вузов, но будет полезна и более 
широкому кругу пользователей MS Excel.

ДИСКРЕТНАЯ 
МАТЕМАТИКА 
С ПРИМЕНЕНИЕМ 
VBA EXCEL
I

ЧАСТЬ

§1. Элементарные функции алгебры 
логики

Функция f = f(x1, x2, …, xn) называется функцией алгебры логики, или 
булевой функцией, если переменные f, x1, x2, …, xn, называемые логическими, 
двоичными или альтернативными, принимают значения из 
множества E2 = {0,1}. Число булевых функций от n переменных, обозначаемое 
p2(n), выражается формулой

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

Таблица 1.1.1

№
x1
x2
…
xn–1
xn
Зна чения f
1
0
0
…
0
0
0 или 1

2
0
0
…
0
1
0 или 1

3
0
0
…
1
0
0 или 1

4
0
0
…
1
1
0 или 1

2 n
1
1
…
1
1
0 или 1

Функции 
алгебры логики 
1

Часть I. Дискретная математика с применением VBA Excel
10

Указанный порядок получается следующим образом. В столбце x1 
первые p1 = 2n–1 клеток заполняются нулями, остальные p1 клеток – 
единицами. В столбце x2 первые p2 = 2n–2 клеток – нули, следующие 
p2 клеток – единицы, затем снова p2 нулей, затем снова p2 единиц. Аналогично, 
чередованием, с учетом pk = 2n–k, заполняются после дующие 
столбцы. В столбце xn значения 0 и 1 чередуются. При оговоренном 
порядке записи наборов значений независимых переменных каждая 
булева функция f задается значениями последнего столбца, что записывается 
в  виде f = (f1 f2 … f2n).
Таблицы истинности элементарных булевых функций сведены 
в табл. 1.1.2 и 1.1.3. 

Таблица 1.1.2

x
f1
f2
f3
f4
0
0
1
0
1
1
0
1
1
0

Таблица 1.1.3

x
y
f5
f6
f7
f8
f9
f10
f11
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
0
0

1)  f1(x) = 0 – константа 0;
2)  f2(x) = 1 – константа 1;
3)  f3(x) = x – тождественная функция;
4)  
 – отрицание (обозначается также 
);
5)  f5(x, y) = x ∧ y – конъюнкция (логическое умножение), обозначается 
также x&y и x·y, x ∧ y = min(x, y); 
6)  f6(x, y) = x ∨ y – дизъюнкция (логическое сложение), x ∨ y = 
max(x, y); 
7)  f7(x, y) = x ⊕ y  – сложение по модулю 2, значение равно остатку 
от деления x + y на 2;
8)  f8(x, y) = x ~ y – эквиваленция, обозначается также x ↔ y,

 
9)  f9(x, y) = x → y – импликация (логическое следствие),

 

Глава 1. Функции алгебры логики

10)  f10(x, y) = x | y – штрих Шеффера, отрицание конъюнкции;
11)  f11(x, y) = x ↓ y – стрелка Пирса, отрицание дизъюнкции.
Основные тождества алгебры логики:
1)  коммутативность:
 
x ° y = y ° x, 
 
символ ° обозначает один из символов ∧, ∨, ⊕, ~;
2)  ассоциативность:
 
(x ° y) ° z = x ° (y ° z); 
3)  дистрибутивность:
 
(x ∨ y) · z = x · z ∨ y · z),
 
(x · y) ∨ z = (x ∨ z) · (y ∨ z);
4)  закон двойного отрицания: 
 
5)  законы де Моргана:

 
6)  закон противоречия:
 
7)  закон исключения третьего:
 
8)  законы идемпотентности:
 
x ∨ x = x, 
 
x · x = x;
9)  законы поглощения:
 
x · (x ∨ y) = x, 
 
x ∨ (x · y) = x; 
10)  тождества с константами:
 
x · 0 = 0, x · 1 = x, x ∨ 0 = x, x ∨ 1 = 1; 
11)  свойство расщепления (при перестановке частей – свойство 
склеивания):
 

12)  
13)  
14)  
.
Аналитические выражения элементарных булевых функций и их 
суперпозиций, то есть функций, полученных подстановками одних 
функций в другие, называются формулами. Примеры формул:

Часть I. Дискретная математика с применением VBA Excel
12

При отсутствии скобок логические операции выполняются в порядке 
убывания приоритета: ¬, ∧, ∨, →, ~.
В Excel значения булевых функций вычисляются с помощью 
встроенных функций, приведенных в табл. 1.1.4.

Таблица 1.1.4

Наименование функции Стандартное обозначение Синтаксис функции
Конъюнкция
x ∧ y
И(х;у)
Дизъюнкция
x ∨ y 
ИЛИ(х;у)
Отрицание
x
_
НЕ(х)
Сложение по модулю 2
x ⊕ y
ОСТАТ(х+у;2)
Импликация
x → y 
ЕСЛИ (x <= y;1;0) 
Эквиваленция
x ~ y
ЕСЛИ(х=у;1;0)
Логическая единица
1
ИСТИНА()
Логический ноль
0
ЛОЖЬ()

Замечание 1. Вместо функции ЕСЛИ лучше пользоваться тождествами 
12 и 13.
Замечание 2. В функциях ИСТИНА, ЛОЖЬ круглые скобки 
можно опускать.

Задача 1.1.1. Составить таблицу истинности функции 

Технология решения. В диапазон A2:C9 вводятся значения независимых 
переменных, в ячейке D2, учитывая 
 (тождество 
12), записывается формула: 

=ОСТАТ(И(НЕ(A2);B2)+ИЛИ(НЕ(C2);НЕ(A2));2)

Копирование ее в ячейки D3:D9 приводит к таблице истинности 
заданной функции (рис. 1.1.1).

Рис. 1.1.1

Глава 1. Функции алгебры логики

Ответ: f = (11001010). 

Переменная xi называется существенной переменной функции f = 
f(x1, … xi, …, xn), если найдется такая пара наборов, что

В противном случае она называется несущественной, или фиктивной, 
переменной. 
Макрос Fictive, применяемый стандартно, во введенной на лист 
Excel таблице истинности булевой функции выделяет желтым цветом 
столбцы значений фиктивных переменных, если они имеются, 
иначе возвращает сообщение, что фиктивных переменных нет. 
Под стандартным применением макроса здесь и далее понимается:
1) вызов макроса (рабочей книги, содержащей макрос);
2) ввод m×n матрицы (таблицы) данных задачи в диапазон 
R1C1:RmCn;
3) выделение диапазона данных;
4) запуск макроса на исполнение (Сервис/Макрос/Макросы/
Имя/Выполнить).

Задача 1.1.2. Найти фиктивные переменные функции f =
= (11001100).
Технология решения. Вызывается макрос Fictive, таблица истинности 
функции f вводится на рабочий лист и выделяется (рис. 1.1.2).

Рис. 1.1.2

Запуск макроса на исполнение возвращает выделенные желтым 
цветом первый и третий столбцы (рис. 1.1.3).
Откуда следует, что переменные x1 и x3 являются фиктивными.
Ответ: x1, x3.