Практическое применение ГИС: решение задачи коммивояжера. 14 страница

Для разработки рекомендаций необходимо каждый блок развернуть до соответствующей когнитивной карты, отражающей состояние изу­чаемой социальна-экономической системы. Характер взаимного влия­ния вершин отражен в когнитивной карте знаками «+» и «-». На основе когнитивной карты проводится сценарное моделирование, результаты которого отражаются на графиках, с помощью которых можно судить о ходе процессов в системе (монотонных, резонансных, неустойчивых). При выборе варианта процесса можно руководствоваться критериями монотонности процесса, минимизации числа управляющих воздействий и числа шагов, за которые будут достигнуты желаемые значения пара­метров.

Может проводиться анализ укрупненных когнитивных карт либо формируются двухуровневые карты (как, например, при анализе региональной системы образования в [1]).

• 1. Горелова Г.В. Региональная система образования: методология комплексных исследований / Г.В. Горелова, Н.Х. Джаримов. - Майкоп, 2002. 2. Горелова Г.В. Моделирование и выбор сценариев социально-эконо-

мических систем / Г.В. Горелова // В сб.: Менеджмент, экономика и финан­
сы: региональное управление. - Таганрог, Изд-во ТИУиЭ, 2003. - С. 152-
155. 3. Гранберг А.Г. Основы региональной экономики / А.Г. Гран-
берг. - М.: ГУ ВШЭ, 2000. 4. Найссер У. Познание и реальность /
У. Найссер.- М., 1981. 5. Современная западная философия: словарь. -
М.: Изд-во полит, лит., 1991.-С. 127-128. 6. Сол то Р. Когнитивная пси­
хология / Р. Солто. - М.: Мир, 1996. 7. Станкевич Л.А. Интеллекту­
альные технологии и представление знаний. Интеллектуальные системы /
Л.А. Станкевич. - СПб: Изд-во СПбГТУ, 2000. В.Н. Волкова

КОМБИНАТОРИКА - одно из направлений математики, пред­шествовавшее и ставшее в дальнейшем основой дискретной ма­тематики (см.).

Элементы комбинаторики возникли в древней математике*.

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

Первые теоретические построения комбинаторики начались в XVII в. и связаны с именами Блеза Паскаля («Трактат об ариф­метическом треугольнике», 1665 г.), Пьера Ферма, Кристиана Гюйгенса, Якоба Бернулли («Искусство предположений», рабо­та опубликована после смерти автора в 1713 г.), с ранними рабо­тами Георга Лейбница (он в 1666 г. в возрасте 20 лет подготовил сочинение на тему «Рассуждение об искусстве комбинаторики», ставшее основой его диссертации). Немалое место комбинатори­ка занимала и в работах Леонарда Эйлера, который в 18-19 лет проявлял интерес к магическим квадратам, а в дальнейшем по­святил комбинаторным задачам свыше 10 специально написан­ных им сочинений и ряд неопубликованных рукописей.

В конце XVIII в. попытку построения общей теории комби­наторики предпринял немецкий математик Карл Фридрих Гин-денбург, написавший трактат «Новая система перестановок, ком­бинаций и вариации...» (Лейпциг, 1781 г.).

* Обзор истории развития комбинаторных знаний подготовлен студен­том А.С. Леоновым [10].

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

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

На основе графических средств комбинаторики возникли теория графов (графические построения в комбинаторике при­менялись и ранее, но возникновение первых теоретико-графовых работ связывают с именем Л. Эйлера), топология (термин введен Иоганном Бенедиктом Листингом, учеником Гаусса).

Таблично-матричный аппарат развивали многие математики. Теорию определителей развивали А. Коши, К.Г. Якоби. Приме­няемая в настоящее время для обозначения определителя квад­ратная таблица, окаймленная вертикальными отрезками прямых, впервые была введена А. Кэли, работы которого сыграли осно­вополагающую роль в формировании матричного исчисления.

На основе конечно-геометрических идей во второй половине XIX в. появились дискретные геометрии, в том числе конечные, возникновению которых способствовали работы Н. Лобачевско­го, Б. Римана, Д. Гильберта.

В XX в. был предпринят ряд попыток построения общей тео­рии комбинаторики: систематическое изложение истории возник­новения и понятий комбинаторики дал Е. Нетто; теорию комби­наторного анализа, базирующуюся на новой трактовке теории производящих функций Лапласа в терминах симметрических фун­кций, разработал английский математик Мак-Магон.

Мощный стимул для своего развития получила комбинато­рика в 40-е гг. XX в. благодаря развитию вычислительной техни­ки, которая обеспечила ряд полезных для теории систем и сис­темного анализа возможностей: облегчение перебора вариантов решения; появление реальных возможностей решать комбинатор­ные задачи экстремального характера (см. Комбинаторные экст­ремальные задачи); возможность моделирования сложных систем с большим числом элементов.

В результате в научной математической литературе 50-х гг. XX в. произошел «комбинаторный взрыв». Резко возросло чис­ло работ, в которых ставились и решались теоретические и при­кладные задачи комбинаторного характера, а в 70-е гг. появи­лась серия монографий [2-9], где с различных позиций рассматривалась проблема построения общей комбинаторной теории.

Разновидностью комбинаторики являются морфологические методы (см.).

• 1.Рыбников К.А. История математики/К. А. Рыбников.-М.: Изд-во
МГУ, 1994. 2. Рыбников К. А. Введение в комбинаторный анализ /
К.А. Рыбников. - М.: Изд-во МГУ, 1972, 2-е изд., 1985. 3. Райзер Дж.
Комбинаторная математика / Дж. Райзер.-М.: Мир, 1966.4. Риодан Дж.
Введение в комбинаторный анализ / Дж. Риодан. - М.: ИЛ, 1963. 5. Сач­
ков В.Н. Комбинаторные методы дискретной математики/В.Н. Сачков.
- М., 1977. 6. Сачков В.Н. Вероятностные методы в комбинаторном
анализе / В.Н. Сачков. -М., 1978. 7. С а ч к о в В.Н. Введение в комбинатор­
ные методы дискретной математики / В.Н. Сачков. - М., 1982. 8. X о л л М.
Комбинаторный анализ / М. Холл. - М.: Иностр. лит., 1963. 9. Холл М.
Комбинаторика/ М. Холл. -М.: Мир, 1970. 10. Андреева О. Из истории
школьной математики / О. Андреева, Г. Бендиков, С. Васильев и др. (школь­
ники-члены юношеской секции «Кибернетика - Информатика - Системный
анализ»)/Под ред. В.Н. Волковой и В.Д. Ногина. - СПб.: Изд-во СПбГТУ,
2001. В.Н.Волкова

КОМБИНАТОРНЫЕ ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ - класс за­дач дискретного программирования, в которых требуется найти экстремум целочисленной линейной функции, заданной на конеч­ном множестве элементов, а также сами элементы этого конечно­го множества.

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

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

Задача о коммивояжере описывает класс моделей нахожде­ния замкнутых маршрутов, минимизирующих суммарное рассто-

яние (время, стоимость переезда) по маршруту из пункта А в,этот же пункте.

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

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

• 1. Корбут А.А. Дискретное программирование / А.А. Корбут,
Ю.Ю. Финкельштейн. - М.: Наука, 1969.2. Шкурба В.В. Задачи кален­
дарного планирования и методы их решения / В.В. Шкурба, Т.П. Подчасо-
ва, А.Н. Пшичук, Л.П. Тур. - Киев: Наукова думка, 1966. 3. Юди н Д. Б.
Линейное программирование (теория, методы и приложения) / Д.Б. Юдин,
Е.Г. Гольштейн.-М.: Наука, 1968.4. Balinski M.L. Integer programming:
methods, uses, computation / M. L. Balinski // Manag. Sci. - 1965. - 12. - № 3. -
P. 253-313. В.Н.Юрьев

Дата добавления: 2015-11-04