Свойства (0,1)-матриц

Минимизировать сX при условии х1Р1 +х2Р2 +...хnРn =Р0, X ?0 и где Рj ( j =1, 2....,n) -j -й столбец А и Р0 =b. [9, стр. 23-25]

Если матрица состоит из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, чтобы никакие две из них не лежали на одной и той же линии. Термином "линия" обозначается либо строка, либо столбец в матрице).

В двудольном графе:

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

Линии - это вершинное покрытие.

Единицы матрицы представляют собой рёбра.

Требование, чтобы никакие две единицы не лежали на одной линии, соответствует паросочетанию.

Пример 8. Рассмотрим двудольный граф, (см. Рисунок 19), с долями

V1 ={v1,v2,,v6}, V2 ={v1,v2,,v6}. Веса ребер, соединяющих вершины vi и u j, обозначены cij и заданы равенствами c11 =1, c53 =3, c12 =2, c55 =1 c13 =3, c64 =3, c22 =4, c66 =3. c32 =6, c34 =3, c43 =4, c46 =2,

Рисунок 19. Двудольный граф.

Перенумеруем ребра по порядку слева направо e1, e2,, e12 и определим переменные x1, x2,, x12.

Для каждого паросочетания определены значения переменных xi :

xi =1, если ребро ei принадлежит паросочетанию ;

xi =0, если ребро ei не принадлежит паросочетанию ;

Задача нахождения паросочетания наибольшего веса равносильно следующей задаче линейного программирования.

Найти наибольшее значение функции

x1 +2x2 +3x3 +4x4 +6x5 +3x6 +4x7 +2x8 +3x9 +x10 +3x11 +3x12

на множестве решений системы линейных неравенств.

Далее рассмотрим пример нахождения ранга покрытия и граничного ранга матрицы А.

Пример 9. Рассмотрим (0, 1) - матрицу A =(ai j ) размера 5*7

Подчеркнутые единицы 1 расположены на диагонали. В строках с номерами 1 и 4 и столбцах с номерами 1 и 3 расположены все единицы 1 матрицы A. Ранг покрытия и граничный ранг матрицы A равны 4, т.е. rankt ( A) =4, max{s +t | 0s*t - подматрица матрицы A} =5 +7 -4 =8.

Матрица APm*n определяет G(A) =G(V1 ?V2, E) - двудольный граф такой, что:

V1 ={1,..., m},V2 ={1',2',..., n'};

{i, j `}E

тогда и только тогда, когда aij =1. Будем говорить, что двудольный граф G( A) ассоциирован с матрицей A.

2.3 Примеры вычисления граничного ранга и ранга покрытия

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

Рассмотрим пример решения задач линейного программирования в программе SimplexWin.

Задача 1. Вычислить граничные ранги (равные рангу покрытия).

Пусть дана матрица А с матрицей А связан двудольный граф (см. Рисунок 20).

Рисунок 20. Двудольный граф и (0, 1) матрица

Строки с номерами U1 и U 2 и столбцы V1 и V2 являются паросочетанием. Наибольшее паросочетание находится, из решения задачи линейного программирования.

Находим решение системы, которое максимизирует функцию F.

Шаг: После открытия программы « SimplexWin » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод.

Вводятся данные: тип критерия задачи min или max, ввод коэффициентов целевой функции и коэффициентов системы ограничений со знаками « ? », «? » или « = », ограничения вида хi ? 0 вводить не надо, симплекс-метод их учитывает в своем алгоритме (см. Рисунок 21).

Рисунок 21.

Шаг: Результат вычисления (нажать кнопку Вычислить). Полученную симплекс -таблицу преобразовываем в Excel (см. Таблицу 1).

Таблица 1 - Симплекс- таблица

Добавилось 12 дополнительных переменных

Результат вычисления (нажать кнопку Результат) (см. Рисунок 22). 3 Шаг:

Рисунок 22.

Решение:

Максимум равен 3. Ранг покрытия равен граничному рангу и равен 3. Найдем максимальную диагональ, заполненную единицами 1.

Среди оптимальных планов выбираем те, у которых все элементы равны 0 или

1. Такой план единственен (1,0,0,0,1,1).

Имеем x1 =1, x2 =x3 =x4 =0, x5 =x6 =1.

Эти значения переменных определяют ребра паросочетания наибольшего веса (см. Рисунок 23).

Рисунок 23. Выделенные ребра паросочетания наибольшего веса

Выбранные ребра определяют наибольшую диагональ, заполненную единицами

Задача 2. Вычислить граничные ранги (равные рангу покрытия).

Пусть дана матрица А с матрицей А связан двудольный граф (см.

Рисунок 24. (0, 1) - матрица и связанный с ней двудольный граф

Наибольшее паросочетание находится, из решения задачи линейного программирования.

Находим решение системы, которое максимизирует функцию F.

Шаг: После открытия программы « SimplexWin » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод. (см. Таблицу 2), (см. Рисунок 25).

Таблица 2 - Данные чисел переменных и чисел ограничений

Рисунок 25.

Шаг: Результат вычисления (нажать кнопку Вычислить) (см. Рисунок 26).

Рисунок 26.

Добавилось 12 дополнительных переменных, данные преобразованы в таблице Excel (см. Таблица 3).

Таблица 3 - Результаты вычисления

Шаг: Результат вычисления (см. Рисунок 27).

Рисунок 27.

Результат. Максимум равен 4. Ранг покрытия равен граничному рангу и равен 4.

Найдем максимальную диагональ, заполненную единицами 1.

Среди оптимальных планов выбираем те, у которых все элементы равны 0 или 1. Таких планов два (0,1,0,0,1,1,0,0,0,1,0,0,0,0) и (0,0,1,0,1,1,0,0,0,1,0,0,0,0).

Эти значения переменных определяют ребра паросочетания наибольшего веса.

Первый оптимальный план и соответствующий ему двудольный граф (См. Рисунок 28):

x1 =0, x2 =1, x3 =x4 =0, x5 =x6 =1, x7 =x8 =x9 =0, x10 =1, x11 =x12 =x13 =x14 =0.

Рисунок 28. Двудольный граф

Второй оптимальный план и соответствующий ему двудольный граф (см. Рисунок 29):

x1 =x2 =0, x3 =1, x4 =0, x5 =x6 =1, x7 =x8 =x9 =0, x10 =1, x11 =x12 =x13 =x14 =0.

Рисунок 29. Двудольный граф

Выбранные ребра определяют наибольшую диагональ, заполненную единицами.

Заключение

Настоящая диссертационная работа принадлежит области комбинаторного анализа и посвящена изучению свойств (0, 1) - матриц.

Несмотря на большое количество комбинаторных свойств (0, 1) - матриц, за основу бралось выявление связи (0, 1) - матриц с графами, которая требуется для определения граничного ранга, ранга покрытия и нахождения числа паросочетания двудольного графа, на основании определений и доказательств теорем Фробениуса-Кёнига и Кёнига.

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

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

На основе доказательств теорем Фробениуса-Кёнига и Кёнига, показана связь графов с (0, 1) - матрицами на примерах.

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

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

На примерах показаны решения задач линейного программирования симплекс - методом в программе (SimplexWin).

Список использованной литературы

1. Ope О. Графы и их применение. Пер. с анг. JI. И. Головиной/ Под ред. И. М. Яглома. - М.: Мир, 1965. - 176 с.

2. Айгмер Л. Комбинаторная теория. - М.: Мир, 1982. - 458 c.

3. Акулич, И.Л. Математическое программирование в примерах и задачах: учеб. пособие / И.Л. Акулич. - М.: Высшая школа, 1993. - 360 с.

4. Асанов М.О., Баранский В.А., Расин В. Дискретная математика: Графы матроиды, алгоритмы. - Ижевск.: НИЦ РХД, 2001, - 288 с.

5. Ашманов С.А. - М.: Наука. Главная редакция физико- математической литературы, 1981. - 340 с.

6. Басакер Р., Саати Т. Конечные графы.- М.: Наука,1973, - 368 с.

7. Березина Л.Ю. Графы и их применение: Пособие для учителей. - М.: Просвещение, 1979. - 143 с.

8. Гантмахер Ф. Р. Теория матриц. - М.: Наука, 1967. - 576 с.

9. Гасс С. Линейное программирование. Методы и приложения. Пер. с анг. Е.Г. Гольштейна, М.И. Сушкевича. - М.: Гос. изд-во физико- математической литературы, 1961, - 344 с.

10. .Жолобов Д.А. Введение в математическое программирование: учеб. пособие. - М.: МИФИ, 2008. - 376 с.

11. .Зарипова Э.Р., Кокотчикова М.Г. Дискретная математике. Часть III. Теория графов: учеб.пособие. - М.: Изд-во РУДН, 2013. - 245 с.

12. .Зыков A.A. Основы теории графов. - М.: Вузовская книга, 2004. - 664 с. 13.Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. - М.:1969, - 368 с.

13. .Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск.: Высшая школа, 1994, - 568 с.

14. .Кузнецов, А.В. Высшая математика. Математическое программирование: учеб. / А.В. Кузнецов, В.А. Сакович, Н.И. Холод. - Минск: Высш. школа, 2001. - 349 с.

15. .Кузнецов, А.В. Руководство к решению задач по математическому программированию: учеб. пособие / А.В. Кузнецов, Н.И. Холод, Л.С. Костевич. - Минск: Высш. школа, 2001. - 173 с.

16. .Кузнецов, Ю.Н. Математическое программирование: учеб. пособие / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. - М.: Высш. школа, 1980.- 345 с.

17. .Куликов Л.Я Алгебра и теория чисел. - М.: Высш. школа, 1979. - 376 с. 19.Лавренов, С.М. Excel: Сборник примеров и задач : / Под. редакцией С.М..Латипова А.Т. Применение линейного программирования в исследовании социально- экономических процессов: учеб. Пособие / А.Т. Латипова; под редакцией А.В. Панюкова. - Челябинск : Издат. Центр ЮУрГУ, 2010. - 123 с.

18. .Липский В. Комбинаторика для программистов: пер. с польск. - М.: Мир, 1988. - 225 с.

19. 22. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физики, химии. - М.: Мир, 1998. - 379 с.

20. .Малых А.Е. Комбинаторные аспекты теории графов в XIX столетии. - М., 1992. - Деп. в ВИНИТИ 24.03.92, № 1004 - В 92.

21. .Малых А.Е. Формирование комбинаторного анализа. - М., 1989. - 245 с.- Деп. в ВИНИТИ 01.12.89, № 7166 - В 89.

22. .Медведев, С.В. Элементы линейного программирования / С.В. Медведев, Е.Б. Полуэктова. - Челябинск : Издательство ЮУрГУ, 2003.- 295 с.

23. .Мур, Д. Экономическое моделирование в Microsoft Excel / Д. Мур, Л.

24. Уэдерфорд и др. - М.: Издательский дом «Вильямс», 2004. - 278 с.

25. .Нечепуренко М.И., Попков М.И., Майнагашев В.К. Алгоритмы и программы решения задач на графах и сетях.- Новосибирск.: Наука, Сиб.от-ние, 1990. - 515 с.

26. .Панюков, А.В. Задача об оптимальном потоке. Техника программной реализации / А.В. Панюков. - Челябинск: Издательство ЮУрГУ, 2001. - 43 с.

27. .Проблемы комбинаторного анализа / под ред. К.А. Рыбникова. - Серия: Математика. Новое в зарубежной науке. - М.: Мир. 1980. - 254 с.

28. .Райзер Г.Дж. Комбинаторная математика. - М.: Мир, 1966. - 367 с. 31.Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования теория, методы, приложения. - М.:Радио и связь, 1982. - 240 с.

29. 32.Риордан Дж. Введение в комбинаторный анализ. - М.: ИЛ, 1963. - 279 с. 33.Рыбников К.А. Введение в комбинаторный анализ. - М.: МГУ, 1969. -521 с.

30. .Сачков В.Н. Введение в комбинаторные методы дискретной математики. - М.: Наука, 1982.- 421 с.

31. .Сачков В.Н. Вероятностные методы в комбинаторном анализе. - М.: Наука, 1978. - 254 с.

32. .Сачков В.Н. Комбинаторные методы дискретной математики. - М.: Наука, 1978.- 258 с.

33. .Свами М., Тхуласираман К. Графы и, сети и алгоритмы. - М.: Мир, 1984.- 454 с.

34. .Сигал, И.Х, Иванова. А.П. Введение в прикладное дискретное программирование. - Москва.: Физматлит, 2002. - 346 с.

35. .Схрейвер А. Теория линейного и целочисленного программирования: в 2х-х т. Т.2.: Пер с анг. - М.: Мир, 1984, - 454 с.

36. .Уилсон Р. Введение в теорию графов. Пер. с анг. И.Г. Никитиной. - М.: Мир, 1977, - 456 с.

37. 39.Харари Ф. Теория графов. - М.: Мир, 1973. - 300 с.

38. .Харари Ф. Теория графов. Пер. с анг. В. П. Козырева; Под ред. Г. П. Гаврилова. Изд. 3-е, стереотипное. - М.: КомКнига, 2006. - 296 с.

39. .Холл М. Комбинаторика / Пер. С.А. Широковой. - М.: Мир, 1963. - 273 с.

Размещено на Allbest.ru