Рассмотрение особенностей паросочетания в двудольных графах. Обзор примеров решения задач дискретного программирования методами линейного программирования. Исследование теоремы Кёнига и Фробениуса-Кёнига. Вычисление граничного ранга и ранга покрытия.
Аннотация к работе
СВОЙСТВА (0, 1) - МАТРИЦВ настоящее время, в связи с усилением значимости информационных технологий, задачи теоретической кибернетики и информатики переживают бурный рост и развитие. При изучении сложных систем и построения их моделей, таких как матрицы, графы, блок - схемы, потоки информации и многое другое, приходится иметь дело с большим количеством параметров, учитывать всевозможные свойства и их различные состояния. Настоящая диссертационная работа принадлежит области комбинаторного анализа и посвящена изучению свойств (0, 1) - матриц, в том числе вопросам связи таких матриц с теорией графов. (0, 1) - матрицы находят свое применение в линейном программировании, при построении и анализе экономических моделей, решению различных проблем логистики и назначения, процессам обработки информации, в теории информации и т.д. Для достижения данной цели были сформулированы следующие задачи: На основе теоретического анализа научной литературы изучить основные свойства (0, 1) - матриц, доказательства теоремы Фробениуса-Кенига и Кенига, теорию графов и их связь с (0, 1) - матрицами.С этой целью вводятся в рассмотрение прямоугольные таблицы, составленные из чисел, называемые матрицами. Матрицей называется прямоугольная таблица, составленная из чисел или других символов. Горизонтальный ряд элементов i матрицы, называется строкой. Вертикальный ряд элементов j матрицы, называется столбцом. Матрица А Линиями матрицы, называют строки и столбцы матрицы.Пара V (G), E(G) называется простым графом, если V (G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечного множества неупорядоченных пар различных из V (G), называемых ребрами (или линиями). Число инцидентных вершине vi - ребер называется степенью вершины графа и обозначается d (vi ). Граф, степени всех вершин которого равны n-1, называется полным. Маршрутом в графе G, называется всякая чередующаяся последовательность вершин и ребер. Граф G =(V, E) и G =(V ", E") называется подграфом графа G, если V" и E", что ребро (vi,v j ) содержится в E" только в том случае, если vi в v j содержатся в V" и G", называется собственным подграфом G, если E" собственное подмножество E или V" - собственное подмножество V.Многие задачи комбинаторной математики связаны с построением тех или иных паросочетаний в двудольных графах. Паросочетанием в двудольном графе, называется множество ребер, попарно не имеющих общих вершин. Максимальное паросочетание - это такое паросочетание, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания. Паросочетание максимального веса в двудольном графе определяется как паросочетание, для которого сумма весов ребер паросочетания имеет максимальное значение. Наибольшее паросочетание (или максимальное по размеру паросочетание) - это такое паросочетание, которое содержит максимальное количество ребер.Линейное программирование возникло из практических потребностей, поэтому оно находит применение при решении широкого класса различных экономических задач, задач управления и планирования, оптимального размещения оборудования, товаров и т.д. Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования.Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m <n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, которые приближают нас к области допустимых решений, пока на каком-то шаге решения либо базисное решение окажется допустимым и к нему применяют алгоритм симплексного метода, либо мы убеждаемся в противоречивости системы ограниче
План
Содержание
Введение
Глава 1. Предварительные сведения
1.1 Теория (0, 1) - матриц
1.2 Графы
1.3 Паросочетания в двудольных графах
1.4 Задачи линейного программирования
1.5 Симплекс-метод
1.6 Решение задач дискретного программирования методами линейного программирования
1.7 Компьютерное решение задач линейного программирования
Глава 2. Теоремы Кенига, Фробениуса-Кенига
2.1 Теоремы Фробениуса - Кенига
2.2 Вычисление граничного ранга и ранга покрытия, нахождением числа паросочетаний двудольного графа
2.3 Примеры вычисления граничного ранга и ранга покрытия
Заключение
Список литературы программирование кениг ранг дискретный