6.2. Математическое обеспечение.

Теоретическую основу математического обеспечения АСОИУ составляет прикладная математика и связанные с ней дисциплины: математическая логика, теория множеств, реляционная алгебра, теория алгоритмов, теория графов, исследование операций, теория сложных систем и др.

6.2.1. Прикладная математика.

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

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

Не претендуя на полноту, укажем некоторые классы задач, решаемых средствами прикладной математики:

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

2. оптимальные задачи (управления);

3. имитационные задачи, результатами которых являются описания имитационных моделей;

4. задачи переработки текстовой информации (в том числе, переводы с одного языка на другой);

5. информационные задачи, связанные с выдачей ответов на вопросы;

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

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

6.2.2. Элементы математической логики.

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

6.2.2.1. Понятие логического значения и высказывания.

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

Определение. Логическими значениями называются два абстрактных объекта: истина и ложь.

Распространены три способа кодирования логических значений. См. таблицу 1.1.

Таблица 1.1. Коды логических значений.

Код1	Код 2	Код 3
ложь	Л	0
истина	И	1

Будем использовать код 3.

Определение. Элементарным высказыванием называется символ, которому поставлено в соответствие логическое значение.

Определение. Логическими связками называются знаки ¬, ,V, →, ~, ≂ читаемые соответственно как "не", "и", "или", "влечет", "эквивалентно", "неэквиваленто". С помощью логических связок осуществляют построение сложных высказываний. Знаки, которыми пользуются как логическими связками, применяют как условные обозначения операций над логическими значениями определены следующие операции:

операция отрицания; выполняется в соответствии табл.1.2.

Таблица 1.2. Таблица 1.3. Таблица 1.4.

Отрицание Логическое умножение Логическое сложение

Таблица 1.5. Таблица 1.6. Таблица 1.7.

Оценка импликации Оценка эквивалентности Оценка неэквивалентности

Определение. Если А и В – высказывания, то составленным высказыванием называется совокупность любой из нижеприведенных записей и их логических значений:

1. ¬ (А) – называется отрицанием А и читается "не А";

2. (А)  (В) – называется конъюнкцией А и В и читается "А и В";

3. (А) V (В) – называется дизъюнкцией А и В и читается "А или В";

4. (А) → (В) – называется импликацией А и В и читается "А влечет В";

5. (А) ~ (В) – называется эквивалентностью А и В и читается "А эквивалентно В";

6. (А) ≂ (В) – называется отрицанием эквивалентности А и В и читается "А не эквивалентно В".

Приведенные выше операции над логическими значениями известны под названием булевых операций.

Определение. Два высказывания называются равнозначными, если их логические значения равны (одинаковы).

Отношение равнозначности обозначают символом ≈. Отношение равнозначности является:

1. рефлексивным, так как для любого высказывания А справедливо А ≈ А;

2. симметричным – из А ≈ В следует В ≈ А;

3. транзитивным – из А ≈ В и В ≈ С следует А ≈ С.

3. Элементы теории множеств.

6.2.3.1. Понятие предмета и множества.

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

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

Если предмет "а" входит в множество "М", то говорят: "а" является элементом "М", и пишут:

а  М.

Знак  называют знаком включения. Если о каком-либо предмете "b" известно, что он не является элементом множества "М", то пишут:

b  М.

Удобно считать, что возможны:

а) множество, не содержащее ни одного элемента, называемое пустым, его обозначают символом Φ;

б) множество, состоящее из одного элемента, называют одноэлементным.

6.2.3.2. Подмножества. Равенство множеств.

Пусть А и В – два множества. Если каждый элемент множества А является также элементов множества В, то А называют подмножеством множества В и пишут:

А ⊆ В.

Очевидно, что всякое множество является своим подмножеством. Пустое множество является подмножеством любого множества. Если А ⊆ В и существует такой элемент множества В, который не является элементом множества А, то А называют правильной частью В. при этом пишут:

А ⊂ В.

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

6.2.3.3. Теоретико-множественные операции.

Пусть А и В множества. Множество С тех элементов, которое принадлежат и А и В, называют пересечением или теоретико-множественным произведением множеств А и В. при этом пишут:

С = А ∩ В.

Знак ∩ называется знаком теоретико-множественного умножения. Операция построения А ∩ В по заданным А и В называется теоретико-множественным умножением. Для этой операции справедлив перестановочный закон:

А ∩ В = В ∩ А, а также – сочетательный закон:

(А ∩ В) ∩ С = А ∩(В ∩ С).

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

А ∩ В ∩ С.

Множества D всех элементов, каждый из которых принадлежит хотя бы одному из множеств А и В, называют теоретико-множественной суммой или объединением множеств А и В. при этом пишут:

D = А ∪ В.

Знак ∪ называют знаком теоретико-множественного (т-м) сложения. Операция, дающая А ∪ В по заданным А и В, называется (т-м) сложением. Для нее справедливы:

1. Перестановочный закон: А ∪ В = В ∪ А;

2. Сочетательный закон: (А ∪ В) ∪ С = А ∪ (В ∪ С), что позволяет делать такие записи:

А ∪ В ∪ С.

В теории множеств существует два распределительных закона:

Умножения относительно сложения

А ∩ (В ∪ С) = (А ∩ В) ∪ (А ∩ С)

и сложения относительно умножения

А ∪ (В ∩ С) = (А ∪ В) ∩ (А ∪ С).

Множество Е тех элементов, принадлежащих А, которые не принадлежат В, называют теоретико-множественной разностью А и В. при этом пишут:

Е = А \ В.

Операция, позволяющая получать А \ В по заданным А и В, называется (т-н) вычитанием.

6.2.3.4. Декартово (геометрическое) произведений множеств.

Образуем все возможные пары, в которые первая компонента является элементом множества А, а вторая – элементом множества В.

Множество этих пар называется декартовым или геометрическим произведением множеств А и В и обозначается (А x В).

Очевидно, что А x В ≠ В x А, однако (А x В) x С = А x (В x С), т.е. сочетательный закон справедлив.

Пары, являющиеся элементами А x В, будем обозначать (a, b), где а  А, b  B. При этом скобки (a, b) обозначают факт рассмотрения (a) и (b) в совокупности. Образуя декартово произведение множеств А x В и С, его элементами будем считать (если с  С) пары вида:

((a, b), с) = (a, b, с), т.е. тройки, образованные в определенном порядке из элементов множеств А, В, С.

Если число множеств сомножителей равно "n", то элементами их декартова произведения будут кортеджи (упорядоченные наборы) по "n" элементов. В силу сочетательного закона в много численных декартовых произведениях можно писать :

А x В x С.

Если члены декартова произведения между собой равны, то декартово произведение называют декартовой ступенью и обозначают:

А x А x … x А = Аⁿ

6.2.3.5. Понятие предиката.

Слова или тексты, являющиеся собирательными (групповыми) именами предметов, обозначим x₁ y₁, … z. Групповое имя – это произвольный предмет, принадлежащий некоторой группе предметов. Например, текст "житель Москвы" является групповым именем людей, каждый из которых является конкретным предметом и имеет свое собственное имя. Пусть (x, y…, z) означает текст, содержащий в своем составе групповые имена x, y…, z и обладающий следующими свойством: если в этом тексте каждое групповое имя заменить собственным (индивидуальным) именем, то данный текст превратиться в символьную часть некоторого высказывания.

Текст Р (x, y…, z) называется предикатом, входящие в него групповые имена называются предметными переменными. О предметах, соответствующих групповому имени, говорят, что они принадлежат предметной области данной переменной, собственные имена указанных предметов называются значениями предметной переменной; логические значения получаемых высказываний называют значением предиката.

Пусть Р (x) - одноместный предикат, предметной областью которого является множество А. [ f (x) одного переменного, определенная для каждого значения х, являющегося элементом множества А ]. Те элементы множества А, для которых указанный предмет принимает значение "истина", образуют подмножества А. Получение подмножества с помощью предиката называют выделением подмножества (предикатом Р). мощность конечного множества равна числу его элементов.

Обозначения.

Если А – одноэлементное множество и а  А, то пишут:

А = {а}

Если А состоит из конечного числа элементов а₁, а₂, …, а_n, то пишут:

Если А является множеством всех х, а х - ???, групповое имя, то пишут:

А = {х}.

Если В является подмножеством, выделенным из множества А с помощью предиката Р (х), то пишут:

В = {х Р | (х)}

Если В получено из А = {х} с помощью функции f (x) и является образом множества А, то пишут:

B = {f (x) | x  А}.

3. Элементы алгебры отношений (реляционной алгебры).

[исключительно важный материал для организации БнД, БД, без знаний]

6.2.4.1. Понятие отношения.

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

Описание каждой области связанных между собой предметов требует не только перечисления предметов, но и описания связей между ними. Теория множеств дает некоторые возможности такого описания. Пусть А₁, А₂, …, А_n - множества (не обязательно различные). Рассмотрим их декартово произведение

D = А₁ х А₂ х … х А_n

Предположим, что а₁, а₂, а₃, …, а_n – элементы соответственно множеств А₁, А₂, …, А_n. Кортеж (а₁, а₂, а₃, …, а_n) является элементом множества D. Предположим, что F является подмножеством множества D, т.е. F ⊆ D. Если выше указанный кортеж удовлетворяет условию (а₁, а₂, …, а_n)  F, то говорят, что его элементы находятся в отношении F и пишут:

(а₁, а₂, а₃, …, а_n; F) или F (а₁, а₂, а₃, …, а_n)

При этом символ F называют и отношение и множество (кортежей, члены которых связаны отношением). Последнее множество иногда называют графиком отношения или множеством отношения. Иногда вместо слов "находятся в отношении F" говорят "удовлетворяют условию F".

Два символа, обозначающий один и тот же элемент рассматриваемого множества, называются равными. Если символы x и y равны, то будем писать:

x = y

Определение. Отношение F называется функциональным относительно i –го аргумента, если для любых двух наборов его графика

(

а₁, а₂, а₃, …, а_n) и из того, что следует, что

Функциональное отношение задает некоторую функцию от (n-1) переменных, значения которой можно получить так. Если задан набор значений исходных данных х₁, х₂, х₃,…, х_i-1, х_i+1,…, х_n, то находят кортеж данного отношения, имеющего вид: (х₁, х₂, х₃,…, х_i-1, а, х_i+1,…, х_n-1) и значением функции считают "а".

В частном случае может оказаться, что А₁ = А₂ =…= А_n = А. В этом случае D = Аⁿ; отношение F, имеющие график F, удовлетворяет условию F ⊆ D, называют заданным на множестве А. Если F – функциональное отношение, то оно определяет некоторую функцию от (n-1) переменных на множестве А.

Пример.

Предположим, что А₁ = А₂ = А₃ = N = (1, 2, 3, 4, 5, …). В данном случае множество предметов бесконечно. Будет бесконечным и множество D = А₁ х А₂ х А₃ = N³, его элементами будут всевозможные тройки целых чисел. Иногда удается указать признак, по которому можно определить принадлежность тройки натуральных чисел множеству F.

Допустим, что такой признак гласит: "Третий элемент кортежа равен сумме первого его элемента и квадрата второго его элемента". Тогда тройка (1, 2, 5) принадлежит множеству F, а тройка (1, 2, 6) – не принадлежит, т.к. числа (1, 2, 6) не удовлетворяют указанному отношению. Это отношение является функциональным и соответствует функции Z = x + y².

Число элементов в кортежах множества – отношения называются рангом отношения. Отношение n-го ранга называют n-местным (или n-арным). на практике часто используют отношения 2-го ранга (бинарные, двухместные). В последнем пример приведено отношение 3-го ранга (трехместные, тернарные). Иногда удобно пользоваться отношением 1-го ранга (унарного, одноместного). Отношению первого ранга соответствует некоторое подмножество множества предметов, т.к. А' = А.

Остановимся подробнее на бинарных отношениях φ ⊆ А х А, заданных на множестве А. Такое отношение часто обозначают а₁ φ а₂ вместо (а₁, а₂; φ), или φ (а₁, а₂).

1. Отношение φ называют рефлексивным, если для любого а  А, справедливо а φ а ;

2. Отношение φ называют симметричным, если из а₁ φ а₂ следует а₂ φ а₁;

3. Отношение φ называют антисимметричным, если из а₁ φ а₂ следует невозможность а₂ φ а₁;

4. Отношение φ называют транзитивным, если из а₁ φ а₂ и а₂ φ а₃ следует а₁ φ а₃.

Про всякие бинарные отношения, заданные на А, говорят, что оно имеет ??? эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Рассмотрим бинарное отношение, которое обладает тем свойством, что для любых а₁  А и а₂  А имеет место либо а₁ φ а₂, либо а₂ φ а₁, но не сразу оба условия. Если, кроме того, рассматриваемое бинарное отношение не рефлекторно не для одного а  А, антисимметрично и транзитивно, то говорят, что φ имеет тип срочного порядка. Отношение < между числами имеет тип строгого порядка, называется строго упорядоченным (этим отношением).

Если бинарное отношение φ, заданны на А, таково, что для любого а  А (кроме быть может а = а₀) всегда существует а'  А такое, что а' φ а и , кроме того φ не рефлексивно ни для одного а  А, антисимметрично и транзитивно, то отношение φ называют отношением типа древовидного порядка. Вместо типа "древовидный порядок" часто употребляют термин "иерархический порядок". (например, генеалогия по мужской линии царствующей династии).

В дальнейшем, под словами "порядок" и "иерархия" будем соответственно понимать соответственно строгий порядок и иерархический порядок. Если а φ а', то говорят, что а' следует за а.

6.2.4.2. Операции над отношениями.

Рассмотрим операцию над отношениями одинакового ранга. Пусть F и Ф отношение ранга "n" между элементами из А₁, А₂, …, А_n. Те же буквы пусть обозначают соответствующие отношениям множества кортежей.

1. Сложение отношений. Теоретико-множественная сумма F⋃Ф определяет новое множество и тем самым новое отношение, которое обозначают F⋃Ф и читают "F или Ф". Это отношение – сумма отношений F и Ф.

2. Умножение отношений. Пересечение множеств F⋂Ф определяет новое множество кортежей n-го порядка, которое называют произведением отношений F и Ф, обозначают F⋂ Ф и читают " F и Ф".

3. Вычитание отношений. С помощью теоретико-множественного вычитания множеств F / Ф получают новое множество кортежей "n-го" порядка, новое отношение, которое называют разностью отношений F и Ф, обозначают F / Ф и читают " F, но не Ф".

4. Обмен позициями. Пусть i и j – целые числа, причем 1 ≤ i < j ≤ n. Обменом позиций i и j называется операция над отношением, заключающегося в том, что в каждом кортеже множестве – отношения меняются местами элементы с номерами i и j. Если исходным отношением было F, то результат описанной операции обозначают (i ↔ j) F.

Пример.

Если описанием бинарного отношения F служит фраза "1-е число больше, чем 2-е", то после выполнения операции обменами позициями получается отношение (1 ↔ 2) F, описанием которого будет фраза "2-е число больше, чем 1-е".

5. Операция расширения отношения. Эти операции над множеством F заключается в том, что к каждому кортежу его множество – отношения слева добавляют один и тот же элемент "а". При этом номера позиций всех "старых" элементов каждого кортежа увеличиваются на "1" и вновь получаемое отношение имеет ранг(n+1). Результат описанной операции обозначают . Расширение отношения применяют, если нужно уравнять ранги двух отношений.

6. Операция исключения позиции (проекции отношения). Эта операция заключается в том, что из всех кортежей множества – отношения F исключают элемент, занимающий позицию номер "i". В результате возникает новое множество кортежей и соответственно новое отношение, которое обозначают (i) F. Операция может касаться случая исключения сразу нескольких позиций. При этом для ее обозначения употребляют запись (i, j, …, k) F. В скобках перечислены номера исключенных позиций.

7. Удвоение позиции. В некоторых случаях бывает полезной операция над отношением ранга "n", заключающиеся в том, что в каждый кортеж отношения включается дополнительный элемент (предположим, что он займет позицию с номером ), равный элементу, занимающему в этом кортеже позицию F, то результат выполнения над ним операции удвоения j-й позиции обозначают t_j F.

Пример. Пусть дано F = {(1, 2); (3, 7); (9, 2); (11, 5)}, тогда

D, F = {(1, 2, 1), (3, 7, 3), (9, 2, 9), (11, 5, 11)}.

Отношение D, F имеет ранг 3.

6.2.4.3. Реляционная алгебра.

Предположим, что задано конечное множество конечных множеств. С = {А', А", …}. Задавая число n, мы можем выбрать из множества С всевозможными способами некоторое количество (не превосходящее число n) входящих множеств образовать из них последовательность А₁, А₂,…, А_n, в которой могут быть и равные множества. Опираясь на такие последовательности множеств, можно построить конечное или счетное множество n-арных отношений. Заставляя "n" прибегать значения 1, 2, 3, …, мы можем получить счетное множество конечных или счетных множеств различных отношений. Обозначим совокупность всех полученных отношений через R. На множестве R определены операции (над отношениями), результаты которых тоже принадлежат R. В математической дисциплине, называемой абстрактной алгеброй, совокупность, образованная некоторым множеством объектов и множеством заданных на нем операций называется реляционной алгеброй. В нашем случае совокупность множества R отношений и множества операций, описанных в предыдущем разделе, называется реляционной алгеброй.

3. Понятия и термины теории графов.

Во многих работах по АСОИУ, в особенности тех из них, которые посвящены вопросам структуры информации и направленности ее потоков, в качестве математического аппарата применяется теория графов.

6.2.5.1. Понятие графа.

Приведем определение графа в терминах абстрактной алгебры (и теории множеств).

Пусть Х – некоторое множество, элементы которого условимся называть вершинами.

Образуем геометрический квадрат Х² и обозначим через D некоторое его подмножество, так что D⊆Х². Элементами множества D являются упорядоченные данные пары, члены которых являются элементами множества Х. Каждый элемент множества D условимся называть дугой; первый член дуги будем называть ее началом, а второй член – ее концом. С помощью каждой дуги d, принадлежащей D, образуем множество, элементами которого является начало и коней дуги d, и только они. Полученное множество назовем ребром. Очевидно, каждое ребро является либо одноэлементным, либо двухэлементным. Будем говорить, что каждое ребро имеет два конца, причем этими концами являются элементы множества Х (вершины), одновременно являющиеся элементами ребра. Множество всех полученных ребер обозначим через R.

Совокупность (Х, D) множества вершин и множества дуг называются ориентированным графом.

Совокупность (Х, R) множества вершин и множества ребер называется неориентированным графом.

Если х' и х" є Х, и х' ≠ х", то дуги (х' и х") и (х", х') между собой различны, т.к. имеют различную ориентацию.

Обеим этим дугам соответствует одно и то же ребро { х', х"}. Ориентированный и неориентированный графы называются "графами".

Ни одно из понятий "ориентированный граф" и "неориентированный граф" не является частным случаем другого. Каждому ориентированному графу отвечает только один неориентированный граф. Обратное неверно.

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

Х = {a, b, c, d, e, f};

D = {(a, b), (b, a), (b, c), (c, c), (c, d), (c, e), (f) f)}.

Обратим внимание на то, что в этом графе вершина f не соединена дугами с другими вершинами; некоторые пары вершин соединены двумя дугами, имеющими различную ориентацию.

На рис. 6.2. изображен неориентированный граф, соответствующий ориентированному, приведенному на рис. 6.1. При этом Х является прежним, а

R = { {a, b}, {b, c}, {c}, {c, d}, {c, e}, {f} }

Рис. 6.2.

Из самого определения графа следует, что геометрическая его интерпретация является только одной из возможных. На практике часто приходится иметь дело с объектами, более сложными, чем графы. Предположим, что задано множество M = {S₁, S₂, …, S_n}, в котором S₁, S₂, …, S_n, в качестве элементов имеют дуги (ребра), и множество так называемых имен E = e₁, e₂, …, e_n. Предположим, что имена поставлены во взаимоодназначное соответствие множествам S₁, S₂, …, S_n, и элемент каждого S_i рассматривается всегда только вместе с именем e_i, которое отвечает множеству S_i. В этом случае говорят, что задан ориентированный (неориентированный) размеченный мультиграф. Это определение можно упростить, если ввести понятие размеченных дуг (ребер), понимая под этим термином пару (e_i, d_i), пару (l_i, r_i). Тогда выше приведенное определение примет следующий вид.

Размеченным ориентированным (неориентированным) мультиграфом называется совокупность (Х, Т), где Х – множество вершин, а Т – множество размеченных дуг (ребер).

Пример. Пусть Х = {Пьер, Иван, Нина}; Е = {учит французскому языку, учит русскому языку, учит математике, учит танцевать}. Размеченный ориентированный мультиграф, описывающий схему взаимного обучения Пьера, Ивана, Нины, может иметь вид, показанный на рис. 6.3. На этом рисунке вершины мультиграфа изображены в виде так называемых блоков: прямоугольников, внутри которых написаны названия объектов, являющихся вершинами мультиграфа. Т.о. схема алгоритмов решения задач АСОИУ является размеченными ориентированными мультиграфами, рис. 6.4. Если множество вершин графа конечно, то граф (мультиграф) называют конечным.

Рис. 6.4. Простейшая блок-схема алгоритма.

6.2.5.2. Пути, контуры, цепи, циклы.

Две дуги графа называют смежными, если они различны и начало одной из них является концом другой. О дуге (a, b) говорят, что исходит из вершины "а" и входит в вершину "b" и что она ??? каждой из этих вершин.

Путем в ориентированном графе называется такая последовательность дуг (d1, d2, ..._,), что конец каждой предыдущей дуги является началом следующей. Путь называется простым, если ни одна дуга не присутствует в нем более одного раза. В противном случае путь называется составным. Конечный путь, начало первой дуги которого совпадает с концом последней, называется контуром. Контур, в котором нет различных между собой дуг, входящих в одну и ту же вершину, называется элементарным. Контур, состоящий из одной дуги, называется петлей.

Цепью в неориентированном графе называется такая последовательность графа называется такая последовательность ребер (r₁, r₂, …, r_k), что конец каждого ребра r_k, является также концом ребра r_k-1, а другой конец – концом ребра r_k-2. Указанное условие может ??? только для k = 1 и для k = n (если r_n – последнее ребро в указанной последовательности).

Цепь, которая конечна и в которой один из концов ребра r_i является концом ребра r_n, называется циклом. Цепь, состоящая из одного ребра, концы которого одинаковы, называют единичным циклом. Цепь называется простой, если все ее ребра различны. В противном случае, цепь составная.

Неориентированный граф называют связным, если любые две его вершины можно соединить цепью. Ориентированный граф связный, если соответствующий ему неориентированный граф связен. Неориентированный граф древовиден (или дерево), если он не имеет циклов.

Ориентированный граф древовиден, если ему соответствует древовидный неориентированный граф. Сетью называют произвольный неориентированный граф или мультиграф.

3. Основы теории алгоритмов.

Речь в данном разделе [теоретических основ МО] пойдет о практическом использовании алгоритмов для решения задач АСОИУ на компьютерных системах с широким выходом на программирование.

Ведь всякий алгоритм – это программа действий, а машинные программы, реализующие алгоритмы, есть точные инструкции на выполнение определенной последовательности процедур. Сам процесс программирования – есть перевод записей алгоритмов на язык, понятный компьютеру.

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

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

1. Первое направление основано на простой идее: каждый элементарный вычислительный шаг можно представить так, чтобы его могла выполнять простая вычислительная машина т.е. абстрактная машина. Эту машину можно представить как универсальную алгоритмическую модель. Впервые эта машина была предложена А. Тьюрингом (1936 ÷ 1937 гг.), за ней закрепилось название "Машина Тьюринга". Алан Тьюринг – английский ученый, его открытие известно в теории алгоритмов, как машинное понятие алгоритмической модели.

2. Второе направление связано с вычислительными функциями двух видов: а)???, т.е. подстановки функции, порождающей математические формулы, в которых порядок действий определяется расстановкой скобок; б) рекурсии, т.е. определения очередного значения функции через ранее вычисленные значения этой же функции. Например, функция факториала: n! = 1 · 2 · 3 ·…· n. Функции из целых чисел, построенные с помощью ??? рекурсии называют рекурсивными.

3. Третье направление: если рассматривать формальное преобразование данных (не употребляя машинной терминологии: память, состояние машины, запись, считывание и т.д.), то описание действий превращается в систему подстановок, которые указывают, какие замены символов и в каком порядке надо производить. Наиболее известная модель такого типа – нормальный алгоритм Маркова (НАМ). Марков А.А. (1903 ÷ 1979 гг.) – выдающийся русский математик, всемирно признанный разработчик конструированной математики.

6.2.6.1. Машина Тьюринга.

Одно из утонченных понятий алгоритма связано с формализованным описанием его в виде машины Тьюринга, работа которой напоминает действия вычислителя, производящего элементарные операции над некоторой воспринимаемой им частью данных или промежуточных результатов. Идея Тьюринга состоит в том, что работа вычислителя, следующего некоторой последовательности (системе) предписаний, может быть в принципе, осуществлена машиной, выполняющей эти же предписания. Машина Тьюринга (МТ) представляет собой бесконечную в обеих направлениях ленту с условно левой и правой частями, разделенную на клетки, каждая из которых либо пуста (S₀), либо содержит один из множества символов {S₁, S₂, S₃, …, S_n}. С помощью управляющей головки (УГ) машина Тьюринга каждый раз воспринимает только одну клетку и может находиться только в одном из состояний {q₁, q₂, q₃, …, q_m}, либо q₀, в которых q₀ является пассивным или заключительным, а {q₁, q₂, q₃, …, q_m} – активным, определяющим переход к очередному шагу вычислительного процесса.

Действия Машины Тьюринга (МТ) в активной ??? – это запись какого-либо символа в исходную клетку и перемещение относительно (УГ) вправо (R), или влево (L) на одну клетку определяется парой S_i, q_j, где S_i – воспроизводимый символ, а q_j – текущее состояние машины. Подобное множество активных машинных состояний находится как произведение множеств:

M = S · Q

S = {S₀, S₁, S₂, …, S_n} и Q = {q₀, q₁, q₂, …, q_m}, т.е.

Работа МТ протекает ???:

1. нахождение в начальной ситуации в активном состоянии q_j:

2. в результате элементарного действия переход в другое состояние, если последнее активно, то переход в следующее состояние, выполняя ??? действие и т.д. до перехода к заключительной пассивной ситуации (q₀).

Тезис Тьюринга.

Всякий алгоритм в интуитивном смысле может быть реализован как некая машина Тьюринга. Конкретная МТ может быть описана с помощью конечной функциональной таблицы с "m" столбцами для активных состояний {q₁, q₂, q₃, …, q_m}и "n+1" строками, соответствующими символам { S₀, S₁, S₂, S₃, …, S_n}.

В каждую клетку таблицы записывают действие, соответствующее ситуации S_i, q_i и , , выражениями вида S_kRq_e, S_kLq_e и S_kCq_e, означающими, что после записи в исходную клетку символа S_k и перехода в состояние q_e – положение вновь воспринимаемой клетки соответственно: правое, левое, не меняется.

Таблица Тьюринга.

Q S	q1	q2	q3	q4	……	qm-2	qm-1	qm
S0	S0Rq1	S0Rq2	S0Rq3	S0Rq4		S0Rq m-2	S0Rq m-1	S0Rq m
S1	S1Rq1	S1Rq2	S1Rq3	S1Rq4
S2	S2Rq1
S3	S3Rq1
……
Sn-1	Sn-1 Rq1
Sn	Sn Rq1
Sn+1	Sn+1 Rq1

В общем случае, если задана функция φ (x₁ ,x₂, …, x_n) из области определения функции φ, записанный на месте, может быть переработан машиной Тьюринга в соответствующие значения φ (x₁ ,x₂, …, x_n), при этом φ (x₁ ,x₂, …, x_n) называют функцией, вычисленной по Тьюрингу.

При этом система предписаний, задаваемая в виде таблице Тьюринга и преобразовывающая слова из алфавита {S₀, S₁, S₂, …,S_k} в слова того же алфавита, называют алгоритмом в смысле Тьюринга. Сама МТ занимает значительное место в теории алгоритмов. Физика тезиса Тьюринга такова: для любой вычислительной функции, (т.е. функции, для которой существует вычислительный алгоритм), можно построить машину Тьюринга, которая ее вычислит. Машина Тьюринга является хоть и не простой, но универсальной алгоритмической моделью. К сожалению, самые простые алгоритмы реализуются на МТ с большой грамоздскостью, выполняемых элементарных операций. Это послужило причиной разработки других математических моделей, уточняющих поиски построения алгоритма. Следует отметить, что МТ была построена не для выполнения вычислений, а для того, чтобы доказать, что любой сложный алгоритм можно построить на выполнении простых (автоматически выполняемых) операций.

Примечание (справка).

Алан Тьюринг (1912 - 1954), Англия, США. Закончил Кембриджский университет в Англии в 1935 г. А. Тьюрингу удалось дать (на интуитивном уровне) определение понятия алгоритма. Для этого он изобрел некоторую гипотетическую конструкцию – машину (получившую название машина Тьюринга (МТ)) в 1937 году. Это произошло в Пристанском университете США. Вторую жизнь МТ получила после изобретения ЭВМ, для которых понятие алгоритма – центральное.

6.2.6.2. Нормальный алгоритм Маркова.

Для абстрактного описания исходных данных, промежуточных и конечных результатов вычислений в теории алгоритмов введено их символьное изображение в виде слов некоторого алфавита. Как уже упоминалось выше, алфавит – это любая конечная система попарно различных знаков, называемых буквами (символами). Последовательность букв – слова: а, аа, aba, abb, aba – слова. Существуют правила описания конкретных объектов определенными словами и абстрактно.

Основная задача теории алгоритмов связана с проблемами преобразования одних слов в другие. Если слово L является частью слова M, то говорят, что L входит в M.

abc bc bab – M

abc – L

Преобразование одних слов в другие проиводится при помощи подстановок вида P→Q.

Совокупность всех слов в алфавите вместе с конечной системой допустимых

подстановок называется ассоциативным исчислением .

Два слова в АИ смежные, если одно из них преобразуется в другие путем однократной подстановки. Два слова в АИ (p, q) – эквивалентны, если существует дедуктивная цепочка слов, ведущая от "P" к "q", (дедукция – общие свойства группы предметов по умозаключению).

Нормальный алгоритм Маркова (НАМ) – это ассоциативное исчисление со следующими правилами:

1. Для заданного слова применяются все подстановки до исчерпания полного их множества.

2. Подстановки применяются в первоначально заданном порядке.

3. Всегда заменяется самое левое вхождение слова.

4. Слово, полученное после подстановки, рассматривается как исходное.

Например, задан алфавит {а, б, в, …, я} и система подставок:

№ п/п	Формулы
1.	Х → ОР
2.	М → СЛ
3.	Р → НХ
4.	УХ → О
5.	ИР → КР
6.	а → б
7.	бз → ю
8.	б → н
……
n	………

Рассмотрим процесс преобразования слова "Муха" в слово "Слон".

2 4 6 8

По НАМ можно представить как: "муха" → "слуха" → "слоа" → "слоб" → "слон".

В общем случае применение НАМ к слову "L" при "n" подстановках (i = 1, 2, 3, …, n) представляется следующим образом (рис. 6.3.):

1. Считать i = 1 (параметр цикла), перейти к п.2.

2. Проверить применимость i-ой формулы подстановки, если "да", то перейти к п.3, если "нет", то – к пункту 5.

3. Левую часть "i-й" формулы P_i → Q_i в преобразуемом слове заменить на Q_i, и результат считать преобразуемым словом; перейти к п. 4.

4. Если i-я формула является заключительной подстановкой, то процесс прекратить. В противном случае – переход к п.1.

5. Проверить равенство i = n. Если "да", то процесс прекратить, если "нет" – переход к п.6.

6. Увеличить i на "1" и перейти к п.2.

Таким образом, НАМ – это семейство алгоритмов поиска пути в бесконечном лабиринте АИ, в которых элементарными действиями являются подстановки, определяющие в заданном порядке преобразование одного слова в другое (АИ – ассоциативное исчисление).

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

6.2.6.3. Вычислимые функции.

Функция y = φ (x₁, x₂, x₃, …, x_n) вычислима, если существует алгоритм, определяющий значение этой функции для многих значений аргументов.

Арифметические функции.

1. φ (x) = x + 1; φ (x) =12y; y (a, b, c) = ab + c.

1, (x < 0);

2. Sign (x) =

0, (x > 0).

3. .

4. ; .

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

Общий вид рекурсивных функций:

Y (n) = φ [Y (n-1), x] = φ (Y ₀, n-1, x), где n = 0, 1, 2… члены натурального ряда, определяющие шаг изменения аргумента, Y₀ – исходные значения функции, Y (n-1) – предыдущее значение функции.

Рекурсивные методы исчисления основаны на образовании функций φ (x₁, x₂, x₃, …, x_n) из ранее известных двумя способами:

1) Способ подстановки известных функций в другие, ранее определенные функции. Т.е., если заданы "n" каких-либо функций от одних и тех же переменных:

f₁ (x₁; x₂; x₃; …; x_m);

f₂ (x₁; x₂; x₃; …; x_m);

……………………

……………………

……………………

f_n (x₁; x₂; x₃; …; x_m); , то можно задать по определению функцию φ (x₁, x₂, x₃, …, x_n) как:

φ (x₁, x₂, x₃, …, x_n) = f [f₁ (x₁, x₂, x₃, …, x_n), f₂ (x₁, x₂, x₃, …, x_n), f_n (x₁, x₂, x₃, …, x_n)]. Определение заданных аргументов через промежуточные функции от этих аргументов называют операцией суперпозиции или подстановки.

2) Способ (схема) примитивной рекурсии, согласно которой каждое последующее значение функции определяется предыдущим значением, т.е.:

y (n, x) = φ [y (n-1, x), x]

Y (0, x) = Y₀ , где Y₀ – исходная функция, "n" – шаг функции следования, х –

переменные. Пример, n! = 1·2·3·…· n.

Функции, определенные посредством этих двух выше приведенных способов (исходя из нуля и операции следования) называются примитивно-рекурсионными функциями (ПРФ). К их числу относятся все арифметические функции, например:

φ (0, х) = 0;

φ (n, х) = φ (n-1, х) +1

Частично-рекурсивные функции (ЧРФ).

Если функция не является всюду определенной, то вводится понятие частично-рекурсивной функции, позволяющее широкой класс вычислимых функций охваттить рекурсивной схемой. Числовая функция f (x₁, x₂, x₃, …, x_k) – частично рекурсивна, если имеется хотя бы один набор (x₁, x₂, x₃, …, x_k), для которого значение функции неопределенно.

Пусть - подмножество , на котором определена функция . И пусть - подмножество значений , на котором функция неопределенна. При этом , т.е. сумма подмножеств равна исходному множеству.

Введем характеристическую функцию χ для обозначения частично-рекурсивной функции:

где "m" номер набора x₀, x₁, x₂, …, x_k-1, который в области существование f (x₀, x₁, x₂, …, x_k-1) не искажает ее значений, а в области - обращает ее в нуль.

Пример: потребуем, чтобы χ была примитивно-рекурсивной функцией, т.е.:

χ (0, x) = α;

χ (n, x) = F [χ (n-1, x), x] , а именно:

χ (0, x) = 1

χ (n, x) = χ (n-1, x) + 1 так,

что χ₀ = 1, χ = 0, χ₂ = 1, χ₃ = 0 и т.д., т.е. чередование 0, 1.

Можно предположить, что для любой комбинации < x₀, x₁, x₂, …, x_k-1> функции f может быть вычислена по схеме примитивной рекурсии.

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

Введенные понятия позволяют доказать следующие теоремы:

Теорема 1: Любая машина Тьюринга эквивалентна некоторой частично-рекурсивной функции.

Теорема 2: Всякая частично-рекурсивная функция может быть вычислена некоторой машиной Тьюринга, т.е. является вычислимой по Тьюрингу.

Следствия:

1. Всякий алгоритм интуитивном смысле есть некоторая частично-рекурсивная функция и наоборот.

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

Физическая сущность.

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

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

Например, формула a · b + c/d получается подстановкой в функцию x + y функций a · b вместо (x) и c/d вместо (y).

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

n! = 1 · 2 · 3 · 4 ·…· n.

С помощью суперпозиции факториал определить нельзя.

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

6.2.6.4. Технология алгоритмизации.

Решение задач на ЭВМ производится в соответствии с рядом этапов, ориентированных на решение задач любой сложности. Этапы решения задач на ЭВМ :

• содержательная постановка задачи;

• формализация математической модели;

• выбор математического метода решения;

• конструирование алгоритма решения задачи;

• составление и отладка рабочей программы по разработанному алгоритму;

• получение решения, анализ результатов.

В данном разделе учебника остановимся на рассмотрении этапа конструирования алгоритма.

Алгоритм – конечная последовательность точно определенных действий, приводящих к однозначному решению поставленной задачи. Он обладает такими свойствами, как универсальность, понятность, дискретность, правильность, результативность, определенность.

Выполнение алгоритмов определяется следующими правилами: последовательность действий, альтернативность действий, повторные действия, использование вспомогательных алгоритмов.

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

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

Процесс составления алгоритмов – алгоритмизация. Алгоритм задается словесно, таблично, графически (при помощи блок-схемы).

Табличное задание представляет алгоритм в форме таблиц и расчетных формул. Блок-схема – это способ представлена с помощью геометрических блоков. Последовательность блоков и соединительных линий образуют блок-схему. Описание алгоритмов с помощью блок-схем – наиболее наглядный и распространенный способ задания алгоритмов. Линии соединения отдельных блоков показывают направление процесса обработки в схеме. Каждое такое направление называют ветвью. В соответствии с ГОСТом используются определенные геометрические формы блоков:

Все блоки нумеруются (кроме начала и останова); стрелки на соединительных линиях не ставят; алгоритмы бывают линейными, разветвленные, циклические.

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

Разветвленный алгоритм содержит одну или несколько ветвей обработки.

Циклический алгоритм содержит один или несколько циклов. Цикл – это многократно повторяемая часть алгоритма. Параметр цикла – переменная при каждом новом вхождении в цикл принимающая новое значение.

Алгоритм независимо от структуры (сложной или простой) всегда имеют один "останов". Все ветви должны сойтись в блоке "останов".

Конструирование алгоритма производится в соответствии с выбранным методом решения и с учетом установленного срока решения поставленной задачи. При конструировании алгоритмов важно обеспечить принцип нисходящего планирования. Нисходящее планирование – это пошаговая детализация алгоритма, позволяющая на каждом шаге осуществлять требуемые действия с учетом результатов предыдущих шагов. Проверки правильности алгоритмов производятся путем: 1) проверки результатов на конкретных исходных данных; 2) логического анализа конечных результатов относительно постановки задачи.

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

Анализ алгоритмов включает в себя:

• анализ логической структуры;

• анализ выполнения;

• анализ правильности.

6.2.7. Исследование операций.

Исследование операций можно определить как научный подход к решению задач организационно-экономического управления. При решении любой конкретной задачи применение методов исследования операций предполагает:

1. построение математических (экономико-математических, статистических) моделей для задач принятия решений и управления в сложных ситуациях или в условиях неопределенности;

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

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

Совершенно очевидно, что именно эти задачи разрабатываются и ??? в АСОИУ предприятий перерабатывающих пищевых (в том числе мясо-молочных) производств. Именно на объектах пищевой промышленности задача быстрого и эффективного принятия решений (или выбора способа действий) является главной для всех операционных исследований. В условиях рыночной экономики производственно-технические, конъюктурно-комерческие, организационно-экономические и прочие факторы находятся в сложной взаимной зависимости. Так, например, план выпуска молочной продукции крупным городским молочным комбинатом должен учитывать, прежде всего, меняющийся по периодам года, месяцам, дням, неделям спрос покупателей, потребности в сырье и материалах, мощности оборудования, оборотные фонды, ограничения производственно-технического характера, транспортные затраты, маркетинговые особенности рынка. Составление плана, который был бы одновременно и реальным, и экономически выгодным, является задачей далеко не легкой даже при наличии современных компьютерных ???, вычислительных сетей.

Операционный подход направлен на совершенствования процедур выработки управленческих решений в АСОИУ, при этом степень успешности данного подхода в условиях рынка измеряется частой прибылью, полученной за счет ??? реализации результатов исследования операций. Чтобы тот или иной подход к решению конкретных задач АСОИУ пищевых предприятий можно было квалифицировать как операционный, он должен содержать следующие элементы:

1. Ориентация на принятие решения. Основные результаты анализа должны иметь непосредственные отношения к выбору способа действий.

2. Оценка на основе критериев экономической эффективности, при этом сравнение различных вариантов действий должно основываться на количественных оценках (расходы, доходы, наличие денежных средств, норма прибыли, капитальных вложений, колебания рыночного спроса и др.)

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

4. Необходимость использования ЭВМ, что обусловлено решением задач управления в АСОИУ, которые характеризуются сложностью используемых математических моделей, большими объемами данных, подлежащих обработке, громоздкостью вычислительных процедур, обеспечивающих те или иные подсистемы управления и контроля работы пищевого предприятия.

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

6.2.7.1. Примеры задач исследования операций.

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

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

Задача №3. К заданному сроку необходимо провести массовое обследование потребительского рынка, спроса и поведения множества показателей продовольственных товаров крупного административного района большого города. На обследования выделены материальные средства, персонал, оборудование. Требуется разработать такой план обследования, установить нужное число регистраторов информации, их размещение, характер и количество вопросов, чтобы как можно точнее выявить и обосновать покупательский спрос.

Задача №4. Необходимо так распределить сумму выделенных капитальных вложений между предприятиями одного производственного объединения (например, мясоперерабатывающего), чтобы получить максимальную фондоотдачу от эксплуатации этих предприятий (в виде получаемой прибыли, сокращение производственных и транспортных затрат, снижение себестоимости и др.).

Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-то управляемом мероприятии (операции), преследующими определенную цель. В задаче №1 – это организация выборочного контроля с целью обеспечить высокое качество выпускаемой продукции; в задаче №2 – это организация временных торговых точек с целью организации эффективной распродажи колбасных изделий; в задаче №3 – массовое обследование потребительского рынка с целью точного выявления и обеспечения покупательского спроса; в задаче №4 – распределение капитальных фондов между предприятиями производственного объединения с целью получения максимальной фондоотдачи. В каждой задаче заданы некоторые условия проведения этого мероприятия, в рамках которых следует принять решение такое, чтобы мероприятие принесло определяющую выгоду. Условиями выполнения операции в каждой задачи оказываются средства, которыми мы располагаем, время, технология и др.

Следует усвоить основные понятия и определения исследования операций.

Операция – любое управляемое мероприятие, направленное на достижение поставленной цели.

Результат операции зависит от способа ее проведения, т.е. выбора некоторых параметров, называемых решением.

Оптимальными считают те решения, которые по тем или иным решения, которые по тем или иным соображениям предпочтительнее других.

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

6.2.7.2. Модель и эффективность операций.

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

Составление модели операций требует понимания сущности описываемого явления и значения математического аппарата.

Эффективность операций – степень их приспособленности к выполнению задачи – количественно выражается в виде критерия эффективности – целевой функции.

Например, в задаче об распределении капитальных средств критерий эффективности – прибыль от реализации производимой продукции за счет вложения этих средств, которую нужно максимизировать, в транспортной задаче минимизируются суммарные затраты на перевозку грузов от поставщиков (например, ГМЗ) до множества потребителей (например, торговых точек). Выбор критерия эффективности определяет практическую ценность решения задачи АСОИУ.

6.2.7.3. Общая постановка задачи исследования операций.

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

• постоянные факторы (условия выполнения операций), на которые мы влиять не можем. Обозначим их через а₁; а₂; а₃ …;

• зависимые факторы (элементы решения) х₁; х₂; х₃ …; которые в известных пределах мы можем выбирать по своему усмотрению.

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

Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп. Поэтому целевую функцию Z можно записать в виде:

Z = f (х₁, х₂,х₃,…, а₁, а₂, а₃,…).

Следует отметить большой класс оптимальных моделей. Такие задачи возникают при оптимизации процессов планирования и управления сложными системами (экономическими объектами: предприятиями, комбинатами, фирмами и др.).

Оптимизационную задачу можно сформировать в общем виде так:

найти значение переменных х₁, х₂,х₃,…, х_n, удовлетворяющие системе уравнений (неравенств):

φ_i (х₁, х₂,х₃,…, х_n) ≤ b_i, i = 1, 2, 3,…, m (1)

и обращающие в максимум (или минимум) целевую функцию, т.е.

Z = f (х₁, х₂,х₃,…, х_n)→ max (min) (2)

при х₁, х₂,х₃,…, х_n ≥ 0 (3)

Упорядоченная совокупность значений "n" переменных х₁, х₂,х₃,…, х_n представляется точкой n-мерного пространства. Эту точку обозначим через х = (х₁, х₂,х₃,…, х_n), а само оптимальное решение .

Качестве примера рассмотрим классическую задачу экономико-организационного анализа и управления – задачу потребления.

Задача 5. Имеется "n" видов ассортимента молочной продукции, количество которых (в натуральных единицах) х₁, х₂,х₃,…, х_n по ценам соответственно Р₁, Р₂, …, Р_n за единицу.

Суммарная стоимость этих продуктов составляет .

Уровень потребления "Z" на рынке продуктов питания может быть выражен некоторой функцией: Z = f (х₁, х₂,х₃,…, х_n), называемой функцией полезности.

Необходимо найти такой ассортимент молочных продуктов х₁, х₂,х₃,…, х_n при величине доходов покупателей I, чтобы обеспечить максимальный уровень потребления, т.е.

Z = f (х₁, х₂,х₃,…, х_n)→ max (3)

при условии

(4)

i = 1, 2, 3, …n (5)

Решение этой задачи функциональной подсистемы "Маркетинг" АСОИУ городского молочного комбината, зависящее от цепи Р₁, Р₂, Р₃ …, Р_n и величины дохода I, называют функциями спроса.

Очевидно, что рассмотрения задача потребления (3 ÷ 5), так же как и другие (задачи 1 - 4) является частным случаем сформулированной выше общей задачи (1 – 2) на определения экстремума ограничениях, т.к. задачей на условный экстремум.

В тех случаях, когда функции f и φ_i задачи (1 - 2) хотя бы дважды дифференцируемы, можно применять классические методы оптимизации. Однако их применение в исследовании операций ограничено, т.к. задача определения условного экстремума функции "n" переменных технически трудна. Классические методы ??? не работают, если множество допустимых значений аргумента дискретно и функция Z задана таблично. Поэтому для решения задачи (1 – 2) применяют методы математического программирования.

• Если критерий эффективности Z = f (х₁, х₂,х₃,…, х_n) представляют линейную функцию, а функции φ_i (х₁, х₂,х₃,…, х_n) в системе ограничений также линейны, то такая задача является задачей линейного программирования.

• Если, исходя из содержательного смысла, ее решение выражается целыми числами, то эта задача целочисленного линейного программирования.

• Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования.

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

• Если в задаче математического программирования имеется переменная времени и критерий эффективности выражается не в явном виде как функция переменных, а косвенно – через уравнения, описывающие принятие операций во времени, то такая задача является задачей динамического программирования.

• Если функция f и φ_i в выражениях (1 - 2) зависят от параметров, то получим задачу параметрического программирования, если эти функции носят случайный характер, - задачу стохастического программирования.

• Если точный ??? алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программирования, которое позволяет существенно сократить просматриваемое число вариантов и найти, (если не оптимальное) то достаточно приемлемое, удовлетворяющее с точки зрения практики решения.

• По своей содержательной постановке множество задач исследования операций может быть разбито на ряд классов.

1. Задачи сетевого планирования и управления рассматривают соотношения между строками окончания крупного комплекса операций (робот) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.

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

3. Задачи распределения ресурсов возникают при определенном наборе работ (операций), которые необходимо выполнять при ограниченных ресурсах, и требуется найти оптимальные распределения ресурсов между выполняемыми работами (операциями) или состав работ.

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

5. Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, разлива молока в пакеты) на различных видах технического оборудования.

6. Задачи оптимального закрепления потребителей, например, молочной продукции за заводами-изготовителями заключаются в определении оптимального числа и мест размещения (адресов) организаций торговли за конкретными городскими молочными заводами.

7. Задачи составления оптимальных маршрутов доставки готовой скоропортящейся продукции с пищевых предприятий до множества потребителей с учетом особенностей транспортной сети большого города и качества доставляемой многоассортиментной продукции состоит в выборе наиболее экономических маршрутов.

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

9. Многокритериальные задачи исследования операций, тогда успех решения задачи зависит не от одного, а сразу от нескольких критериев. Математический аппарат может принести пользу в данном случае, по крайней мере, ??? отбросить заведомо неудачные варианты решений.

В создании современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л. В. Котловаг, Н.П. Сусленко, Е.С. Вентцель, Н.Н. Моисеев, Д.Б. Юдин и многие другие; зарубежные ученые Р. Бельман, Г. Данциг, Дж. Нейман, Г. Кун, Т. Скати и др.

Методы исследования операций, как и любые другие математические методы в той или иной степени упрощенной (???) решение задачи. Отражают порой нелинейные процессы линейными моделями, стохастические системы – детерминированными, динамические процессы – статистическими моделями и т.д.

Однако не следует преуменьшать значение количественных методов исследования операций в теоретических основах математического обеспечения АСОИУ.

Уместно напомнить, в связи с этим, шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т.Саати:

"НО – это искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами".

6.2.7.4. Общая постановка задачи линейного программирования.

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

В АСОИУ (организационно-экономического характера) используют экономическо-математические модели. В таких моделях объектом является организационно-экономический процесс (использование ресурсов, закрепление потребителей за поставщиками, выдача оптимальных маршрутов доставки грузов от завода до потребителей и т.п.), а специальным языком – классические и специально разработанные математические методы.

Экономико-математическая модель – математические описания исследуемого экономического процесса или объекта. Математическое моделирование углубляет количественный экономический анализ, интенсифицирует экономические расчеты.

Можно выделить четыре этапа экономико-математического моделирования:

1. Ставятся цели и задачи исследования, формируются условия, ограничения решения задачи, строится математическая модель изучаемого объекта.

2. Осуществляется выбор метода решения задачи либо разработка такого метода, т.е. определяется путь исследования, конструируется алгоритм решения задачи, строится подробная блок-схема алгоритма с комментариями.

3. Проводится программирование, т.е. реализация алгоритма на конкретной ЭВМ, ??? исходные данные и нормативно-справочная информация. Проверяется правильность выбора модели, метода решения и алгоритма на опытном материале.

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

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