Ознакомительная версия.
? Если Вы пренебрегаете четкостью формулирования идеи,
или считаете, что методология и теория – дела бесполезные и надо быть ближе к практике, или Вами владеет убеждение, что Вы можете все реализовать и без проекта,
или Вы считаете, что осуществить свое намерение Вы сможете без четкой идеи, теории и проекта,
– лучше не браться за дело. Вас ждет временный успех, основанный на Ваших прошлых методологических и теоретических знаниях. Почему временный?
Потому что Ваши имеющиеся знания не приведены в целостную и целую систему, предназначенную для реализации именно этого Вашего намерения. Потому что никто не приводит все необходимые Вам методологии и теории в систему, тем более – в целостную систему, для реализации этой Вашей идеи. Ваша идея имеет особенности, в связи с которыми надо из разных методологий и теорий взять все необходимое и это необходимое дополнить до достаточного объема и привести в целостную систему. А это можно осуществить только с помощью системной философии.
? Положения системной философии могут быть применены для решения математических задач.
Рассмотрим пример системной технологии решения для широко известной «задачи о коммивояжере» (ЗОК)[41] . Этот пример выбран по той простой причине, что в нем сочетается простота и понятность постановки задачи со сложностью нахождения точного или приемлемого для практики решения.
Постановка ЗОК выглядит следующим образом. Имеется n пунктов, в одном из которых находится коммивояжер. Все эти пункты коммивояжер должен посетить и вернуться для отчета в исходный пункт. Расстояния между ними известны. Требуется найти маршрут коммивояжера, при котором суммарное расстояние, которое он пройдет, будет наименьшим из всех возможных. Эту задачу постоянно решает любой путешественник, собирающийся посетить несколько городов. Вместо расстояний между городами можно взять стоимости проезда теми видами транспорта, которыми можно воспользоваться при переезде из одного города в другой. Вместо городов могут присутствовать операции технологического цикла, а вместо расстояний – время, необходимое для перехода от одной операции к другой. К задаче коммивояжера в формальном виде сводятся многие задачи управления, экономики, планирования и организации. Решить ЗОК простым перебором для больших n практически невозможно, так как число возможных решений равно (n-1)! или «(n-1) факториал».
Применение принципа обогащения к решению ЗОК позволяет построить эффективную технологию. В этом случае технология решения состоит из двух основных алгоритмов. Первый алгоритм позволяет обогатить исходный массив данных, исключая из него те «расстояния», которые не могут участвовать в оптимальном маршруте. Второй алгоритм позволяет найти оптимальный (или близкий к оптимальному) маршрут коммивояжера.
Задача поставлена и решена, как известная задача теории графов о нахождении оптимального гамильтонова цикла в графе[42] .
Для оптимального гамильтонова цикла справедливо следующее условие оптимальности: для любого простого маршрута, являющегося участком оптимального гамильтонова цикла и проходящего вершины графа в последовательности i1, i2, i3, ...,ia, (a=4,5, ...,n; il=1,2, ..., n) сумма весов входящих в него ребер ? (i1i2i3 ..., ia ) является минимальной в сравнении с любой другой суммой вида ? (i1i?2i?3...i?a-1ia):
? ( i1i2i3...ia) = min ? (i1i?2i?3...i?a-1ia ) (1)
при a =4, 5, ..., n; i=1,2, ..., n; i?2, i?3,..., i?a-1, ?P.
Здесь i?2, i?3,..., i?a-1 — одна из перестановок чисел i2, i3, ..., ia-1, P — множество всех перестановок этих чисел.
Очевидно, что если это условие не выполняется для каких-либо значений a и i, то существует гамильтонов цикл с меньшей длиной пути обхода вершин i1, i2, i3, ..., ia-1,ia . Но, если полученный гамильтонов цикл оптимален, то его нельзя улучшить изменением пути обхода вершин i1, i2, i3, ..., ia для любого a, имеющего значения в пределах от 4-х до n.
Значения a не могут быть меньше четырех, так как очевидно, что никакие два гамильтонова цикла не могут отличаться менее, чем тремя ребрами, проходящими четыре вершины поcледовательно в одном из двух возможных вариантов обхода: i1,i2,i3,i4 или i1,i3,i2,i4 .
Пусть оптимальный гамильтонов цикл обходит вершины графа в последовательности
i1, i2, i3, ..., in, i1. (1.а)
Гамильтонов цикл, оптимальный для определенного значения a, назовем a-оптимальным. Для a = 4 справедливо неравенство:
? (ikik+1) + ? (ik+1ik+2) + ? (ik+2ik+3) ?
? ? (ikik+2) + ? (ik+2ik+1) + ? (ik+1ik+3).
Условие (2) необходимо проверить для всех ik = i1, i2, ..., in и, если оно для всех ik справедливо, то это необходимое и достаточное условие того, что гамильтонов цикл 4-оптимален. Просуммировав левые и правые части неравенств, получающихся при значениях ik = i1, i2, ..., in, получаем необходимое условие 4-оптимальности в виде:
Справедливо следующее условие:
Если гамильтонов цикл a1-оптимален, то он a2-оптимален для любого a2<a1.
Если это условие не выполняется, т.е. a1-оптимальный гамильтонов цикл не является a2-оптимальным, то какой-то из простых путей длины a1 можно улучшить изменением обхода каких-то a2 вершин, что противоречит условия a1-оптимальности.
Перейдем к определению условия a-оптимальности, получаемого аналогично тому, как условие (З) получено из (2), из системы неравенств вида (2), для любого a=const суммированием для всех ik=1, 2, ..., n
Для каждого значения k будет иметь место система из ((а-2)!-1) неравенств по числу элементов множества Р, состоящего из (а-2)! перестановок чисел i?k+1, i?k+2, ..., i?k+a-2
При этом мы полагаем, что
? (ik,ik+1, ..., ik+a-1) = ? (ik, ik+1) + ? (ik+1ik+2 ) + ... + ? (ik+a-2 ik+a-1).
? (ik, i?k+1, ..., i?k+a-2, ik+a-1) = ? (ik, i?k+1) + ? (i?k+1, i?k+2) + ... + ? (i?k+a-2, ik+a-1).
Обозначим левую и правую части условия (4) буквами А и В, соответственно: А ? В.
В левой части неравенства вес каждого ребра, принадлежащего проверяемому участку гамильтонова цикла, участвует точно по одному разу в каждом неравенстве системы из ((a-2)!-1) неравенств, задаваемых перестановками, принадлежащими множеству Р, при фиксированной начальной вершине.
Кроме этого, при заданном a=const, если производить проверку выполнения условия (9.2.4), изменяя последовательно номер начальной вершины от i1 до in, то любое ребро гамильтонова цикла появится точно в (a-1) системах из этих ((a-2)!-1) неравенств как первое по счету, второе, третье и т.д. (a-1)-e ребро в проверяемых участках гамильтонова цикла.
Следовательно, левая часть неравенства (4) имеет вид:
Выражение для правой части условия (4) можно записать в виде:
Для того, чтобы получить выражение для правой части условия (4), необходимо найти число появлений ребер графа вида (ic, ic+N ) в каждой системе из ((a-1)!-1) неравенств, задаваемых определенным значением k, а также во всех системах этих неравенств, получаемых при изменении ik от i1 до in.
Очевидно, что число появлений пар (iс, ic+N) в правых частях неравенств вида (4) равно числу появлений пар (ic, ic+N) в последовательностях:
ik, i?k+1, i?k+2, ..., i?k+a-2, ik+a-1 (5)
задаваемых (a-2)! перестановками чисел i?k+1, i?k+2, ..., i?k+a-2.
Ознакомительная версия.
