|
Реферат: Лекции по вычислительной математике (Компьютеры)
Вычислительная математика
Специальность ПО
5-й семестр
Конспект лекций
Лекция 1
Общее описание метода ветвей и границ организации пол-ного перебора
возможностей. Решение задачи о коммивояжере методом ветвей и границ:
основная схема.
Пусть [pic]- конечное множество и [pic] - ве-щественно-значная
функция на нем; требуется найти минимум
этой функции и элемент множества, на котором этот минимум
достигается.
Когда имеется та или иная дополнительная информация о множестве,
решение этой задачи иногда удается осуществить без полного перебора
элементов всего множества M. Но чаще
всего полный перебор производить приходится. В этом случае
обязательно возникает задача, как лучше перебор организовать.
Метод ветвей и границ - это один из методов организации полного
перебора. Он применим не всегда, а только тогда, когда
выполняются специфические дополнительные условия на множе-
ство M и минимизируемую на нем функцию. А именно, -
предположим, что имеется вещественно-значная функция ( на множестве
подмножеств множества M со следующими двумя свойствами:
1) для [pic] (здесь [pic] - множество, состоящее
из единственного элемента [pic]);
2) если [pic] и [pic], то [pic].
В этих условиях можно организовать перебор элементов множества M с
целью минимизации функции на этом множестве так:
разобьем множество M на части (любым способом) и выбе-
рем ту из его частей (1, на которой функция ( минимальна; за-тем разобьем
на несколько частей множество (1 и выберем ту из его частей (2, на которой
минимальна функция (; затем разо-бьем (2 на несколько частей и выберем ту
из них, где минималь-на (, и так далее, пока не придем к какому-либо
одноэлементно-му множеству [pic].
Это одноэлементное множество [pic]называется рекордом.
Функция (, которой мы при этом выборе пользуемся, называется
оценочной. Очевидно, что рекорд не обязан доставлять минимум
функции f; однако, вот какая возможность возникает сократить
перебор при благоприятных обстоятельствах.
Описанный выше процесс построения рекорда состоял из последовательных
этапов, на каждом из которых фиксировалось
несколько множеств и выбиралось затем одно из них. Пусть [pic]
[pic] - подмножества множества M, возникшие на предпослед-нем этапе
построения рекорда, и пусть множество [pic] оказалось
выбранным с помощью оценочной функции. Именно при разбие-нии [pic] и возник
рекорд, который сейчас для определенности обозначим через [pic].
Согласно сказанному выше, [pic],
[pic]; кроме того, по определению оценочной функции, [pic].
Предположим, что [pic]; тогда для любого элемента m множества M,
принадлежащего множеству [pic], будут верны не-
равенства[pic][pic]; это значит, что при полном пере-
боре элементов из M элементы из [pic] уже вообще не надо рас-
сматривать. Если же неравенство [pic] не будет выполне-
но, то все элементы из [pic] надо последовательно сравнить с най-
денным рекордом и как только отыщется элемент, дающий мень-
шее значение оптимизируемой функции, надо им заменить ре-корд и продолжить
перебор. Последнее действие называется
улучшением рекорда.
Слова метод ветвей и границ связаны с естественной гра-
фической интерпретацией всего изложенного: строится много-
уровневое дерево, на нижнем этаже которого располагаются
элементы множества M, на котором ветви ведут к рекорду и его
улучшениям и на котором часть ветвей остаются «оборванными»,
потому что их развитие оказалось нецелесообразным.
Мы рассмотрим сейчас первый из двух запланированных в
этом курсе примеров применения метода ветвей и границ - ре-шение задачи о
коммивояжере. Вот ее формулировка.
Имеется несколько городов, соединеных некоторым обра-зом дорогами с
известной длиной; требуется установить, имеет-
ся ли путь, двигаясь по которому можно побывать в каждом горо-
де только один раз и при этом вернуться в город, откуда путь был начат
(«обход коммивояжера»), и, если таковой путь имеет-
ся, установить кратчайший из таких путей.
Формализуем условие в терминах теории графов. Города
будут вершинами графа, а дороги между городами - ориентиро-ванными
(направленными) ребрами графа, на каждом из кото-рых задана весовая
функция: вес ребра - это длина соответству-
ющей дороги. Путь, который требуется найти, это - ориентиро-ванный
остовный простой цикл минимального веса в орграфе (напомним: цикл
называется остовным, если он проходит по всем вершинам графа; цикл
называется простым, если он прохо-
дит по каждой своей вершине только один раз; цикл называется
ориентированным, если начало каждого последующего ребра совпадает с концом
предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф
называется полным, если в нем име-ются все возможные ребра); такие циклы
называются также га-
мильтоновыми.
Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим,
что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть
как частный случай задачи о ком-мивояжере для полных орграфов.
Действительно, если данный орграф не является полным, то его можно
дополнить до полного недостающими ребрами и каждому из добавленных ребер
при-писать вес (, считая, что ( - это «компьютерная бесконечность», т.е.
максимальное из всех возможных в рассмотрениях чисел. Если во вновь
построенном полном орграфе найти теперь лег-чайший гамильтонов цикл, то при
наличии у него ребер с весом ( можно будет говорить, что в данном, исходном
графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший га-
мильтонов цикл окажется конечным по весу, то он и будет иско-мым циклом в
исходном графе.
Отсюла следует, что задачу о коммивояжере достаточно ре-шить для
полных орграфов с весовой функцией. Сформулируем
теперь это в окончательном виде:
пусть [pic] - полный ориентированный граф и [pic] -
весовая функция; найти простой остовный ориентированный цикл («цикл
коммивояжера») минимального веса.
Пусть [pic] конкретный состав множества вершин и
[pic] - весовая матрица данного орграфа, т.е.
[pic],
причем для любого [pic].
Рассмотрение метода ветвей и границ для решения задачи о коммивояжере
удобнее всего проводить на фоне конкретного
примера. Пользуясь введенными здесь обозначениями, мы проводим это описание
в следующей лекции.
Введем некоторые термины. Пусть имеется некоторая чис-
ловая матрица. Привести строку этой матрицы означает выде-лить в строке
минимальный элемент (его называют константой приведения) и вычесть его из
всех элементов этой строки. Оче-видно, в результате в этой строке на месте
минимального эле-мента окажется ноль, а все остальные элементы будут
неотрица-тельными. Аналогичный смысл имеют слова привести столбец матрицы.
Слова привести матрицу по строкам означают, что все строки матрицы
приводятся. Аналогичный смысл имеют слова
привести матрицу по столбцам.
Наконец, слова привести матрицу означают, что матрица
сначала приводится по строкам, а потом приводится по столб-цам.
Весом элемента матрицы называют сумму констант приве-
дения матрицы, которая получается из данной матрицы заменой обсуждаемого
элемента на (. Следовательно, слова самый тяжелый нуль в матрице означают,
что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с
максимальным весом.
Приступим теперь к описанию метода ветвей и границ для
решения задачи о коммивояжере.
Первый шаг. Фиксируем множество всех обходов коммиво-
яжера (т.е. всех простых ориентированных остовных циклов). По-
скольку граф - полный, это множество заведомо непусто. Сопо-ставим ему
число, которое будет играть роль значения на этом
множестве оценочной функции: это число равно сумме констант
приведения данной матрицы весов ребер графа. Если множест-во всех обходов
коммивояжера обозначить через (, то сумму
констант приведения матрицы весов обозначим через (((). При-веденную
матрицу весов данного графа следует запомнить; обо-значим ее через M1;
таким образом, итог первого шага:
множеству ( всех обходов коммивояжера сопоставлено чис-ло ((() и
матрица M1.
Второй шаг. Выберем в матрице M1 самый тяжелый нуль; пусть он стоит в
клетке [pic]; фиксируем ребро графа [pic] и раз-
делим множество ( на две части: на часть [pic], состоящую из
обходов, которые проходят через ребро [pic], и на часть [pic],
состоящую из обходов, которые не проходят через ребро [pic].
Сопоставим множеству [pic] следующую матрицу M1,1: в
матрице M1 заменим на ( число в клетке [pic]. Затем в получен-ной матрице
вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и
столбцов сохраним их исходные номера. Наконец, приведем эту последнюю
матрицу и запомним сумму констант приведения. Полученная приведенная
матрица и будет матрицей M1,1; только что запомненную сумму констант
приведения прибавим к ((() и результат, обозначаемый в даль-нейшем через
(([pic]), сопоставим множеству [pic].
Теперь множеству [pic] тоже сопоставим некую матрицу
M1,2. Для этого в матрице M1 заменим на ( число в клетке [pic]
и полученную в результате матрицу приведем. Сумму констант
приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим
запомненную сумму констант приведения к
числу ((() и полученное число, обозначаемое в дальнейшем че-
рез (([pic]), сопоставим множеству [pic].
Теперь выберем между множествами [pic] и [pic] то, на
котором минимальна функция ( (т.е. то из множеств, которому
соответствует меньшее из чисел (([pic]) и (([pic]).
Заметим теперь, что в проведенных рассуждениях исполь-зовался в
качестве исходного только один фактический объект - приведенная матрица
весов данного орграфа. По ней было вы-делено определенное ребро графа и
были построены новые
матрицы, к которым, конечно, можно все то же самое применить.
При каждом таком повторном применении будет фиксироваться очередное ребро
графа. Условимся о следующем действии: пе-ред тем, как в очередной матрице
вычеркнуть строку и столбец,
в ней надо заменить на ( числа во всех тех клетках, которые со-ответвуют
ребрам, заведомо не принадлежащим тем гамильто-новым циклам, которые
проходят через уже отобранные ранее ребра; эту довольно трудную фразу мы
еще не раз рассмотрим в
следующей лекции на конкретном примере.
К выбранному множеству с сопоставленными ему матрицей и числом (
повторим все то же самое и так далее, пока это воз-можно.
Доказывается, что в результате получится множество, со-стоящее из
единственного обхода коммивояжера, вес которого равен очередному значению
функции (; таким образом, оказы-ваются выполненными все условия,
обсуждавшиеся при описа-нии метода ветвей и границ.
После этого осуществляется улучшение рекорда вплоть до получения
окончательного ответа.
Реферат на тему: Лекции по информационным технологиям
Информационные технологии лекция 2ая.
В зависимости от сферы использования информация делится на:
1) экономическую
2) техническую
3) генетическую
Виды информации:
текстовая, числовая, графическая.
Различают виды информации по способу передачи и восприятия. Информацию,
передаваемую видимыми образами и символами, называют визуальной, звуками –
аудиальной, ощущениями – тактильной, запахом и вкусом – оргоно –
лептической, а выдаваемую или воспринимаемую ЭВМ – машинной.
Классификация по признаку область возникновения: Элементарная (
отражающая процессы и явления неодушевленной природы), биологическая (
процессы живой природы) и социальная ( человеческого общества).
Формы представления информации: непрерывная и дискретная. Непрерывная
информация – величина характеризующая процесс не имеющий перерывов или
промежутков ( т. тела). Дискретная – последовательность символов,
характеризующая прерывистую изменяющуюся величину (речь).
Свойства информации.
Достоверность и полнота, ценность и актуальность, ясность и понятность,
языки.
Информация достоверна, если она отображает истинное положение дел. Полна,
если ее достаточно для принятия решения. Ценность информации зависит от
того, какие задачи можно решать с ее помощью. Актуальность важно иметь при
работе в постоянно меняющихся условиях.
Поскольку из-за многозначности понятия информация, очень трудно дать
четкое определение , рассматривают по крайней мере четыре различных подхода
к данному понятию. В первом «обыденном» подходе, слово информация
применяется как синоним интуитивно понимаемых слов: сведение, значение,
сообщение, осведомление. Во втором «кибернетическом» подходе понятие
информация широко используется в системе управляющего сигнала,
передаваемого по линиям связи (1,0). В «философском» понятии информация
тесно связана с такими понятиями как взаимодействие, отражение. В
«вероятностном» подходе под информацией не любое сообщение, а лишь то,
которое уменьшает неопределенность знаний о каком либо событии у получателя
информации.
Понятия экономической информации.
Под экономической информацией понимается информация, характеризующая
производственные отношения в обществе. К экономической информации относятся
сведения, которые циркулируют в экономической системе, о процессах
производства, материальных ресурсах, процессах управления производством,
финансовых процессах, а так же сведения экономического характера, которыми
обмениваются различные системы управления.
В соответствии с общей теорией управления, процесс управления можно
представить как взаимодействие двух систем: управляющей и управляемой.
Система управления предприятием функционирует на базе информации на
состоянии объектов его входов и выходов в соответствии с поставленной
целью. Управление осуществляется подачей управленческих воздействий с
учетом обратной связи и внешней среды, рынка и вышестоящих органов
управления. Назначение управляющей системы – формировать такие воздействия
на управляемую систему, которые побуждали бы её принять состояние,
определенное управляющей системой.
Цель – выполнение производственной программы в рамках технико-
экономических ограничений.
Обратная связь – данные о ходе производства.
Планы и содержание обратной связи не что иное, как информация. Поэтому
процессы формирования управляющих воздействий является процессами
преобразования экономической информации.
Экономической информации характерны следующие свойства: точность,
достоверность, оперативность.
Точность – обеспечивает ее однозначное восприятие всеми потребителями.
Достоверность определяет допустимый уровень искажения как поступающей так и
результатной информации, при которой сохраняется эффективность
функционирования системы. Оперативность – отражает актуальность информации
для необходимых расчетов и принятия решений в изменившихся условиях.
Виды экономической информации.
Экономическую информацию принято подразделять по следующим
признакам: функциям управления и месту возникновения. По функциям
управления разделяется на планово-учетную, нормативно-справочную и отчетно-
статистическую экономическую информацию.
Плановая (директивная) – включает в себя директивные значения планируемых и
контролируемых показателей бизнес планирования на некоторые периоды в
будущем.
Учетная информация отражает фактические значения, запланированных
показателей за определенный период времени.
Нормативно – справочная – содержит справочные и нормативные материалы,
связанные с производственными отношениями и процессами. (50-60%).
Отчетно-статистическая – отражает результаты статистической деятельности
фирмы для вышестоящих органов управления, органов Гос. статистики и т.д.
Классификация экономической информации по уровням управления включает в
себя входную и выходную. Входная информация – поступающая в фирму из вне и
используемая как первичная информация для реализации экономических и
управленческих функций, а так же задач управления. Выходная информация, –
поступающая из одной системы в другую. Одна и те же информация может
являться входной для одного структурного подразделения, так и выходной для
другого. Информационные ресурсы – информация используемая на производстве,
в технике, в управлении обществом, специально организуемая и обрабатываемая
с помощью ЭВМ.
Информационные ресурсы рассматриваемые в масштабе страны называются
«национальными информационными ресурсами».
| |
