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

Размещено на http://www.allbest.ru/

СВОЙСТВА (0, 1) - МАТРИЦ



Содержание

Введение

Глава 1. Предварительные сведения

1.1 Теория (0, 1) - матриц

1.2 Графы

1.3 Паросочетания в двудольных графах

1.4 Задачи линейного программирования

1.5 Симплекс-метод

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

1.7 Компьютерное решение задач линейного программирования

Глава 2. Теоремы Кёнига, Фробениуса-Кёнига

2.1 Теоремы Фробениуса - Кёнига

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

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

Заключение

Список литературы

программирование кёниг ранг дискретный



Введение

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

С конца XIX в. опережающими темпами стала развиваться дискретная математика, важной составной частью которой является комбинаторный анализ.

Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Р.В. Бруалди, Я. Бернулли, Л. Эйлер, Дж. Райзера, Д.Р. Фалкерсон, Д. Гейл, а также многие методы используемые в дискретной математике представлены в книгах В.Н. Сачкова, В. Е. Тараканова, К.А. Рыбникова, и др.

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

(0, 1) - матрицы находят свое применение в линейном программировании, при построении и анализе экономических моделей, решению различных проблем логистики и назначения, процессам обработки информации, в теории информации и т.д.

В данной диссертации будет подробно рассмотрена роль линейного программирования в решении задач, связанных с (0, 1) - матрицами, и проанализировано использование для решения соответствующих задач современных математических пакетов, таких как SimplexWin и Microsoft Excel. Всё вышесказанное обуславливает актуальность выбора темы для данной исследовательской работы.

Объектом исследования являются теория (0, 1) - матриц и теория графов.

Предмет исследования составляют задачи (0, 1) - матриц, связанные с теорией графов.

Методы исследования. В диссертации используются методы комбинаторного анализа.

Цель работы состоит в исследовании свойств (0, 1) - матриц, теории графов, и их применении в линейном и дискретном программировании.

Для достижения данной цели были сформулированы следующие задачи:

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

Теоретически обосновать связь между графами и (0, 1) - матрицами и наглядно показать эту связь на примерах.

Разработать теоретико-методическое описание методов линейного и дискретного программирования.

Рассмотреть применения теории (0, 1) - матриц для решения задач линейного программирования симплекс - методом в программе SimplexWin.

Содержание и структура работы.

Диссертация состоит из введения, двух глав, заключения, списка литературы.

Во введении даны основные характеристики работы.

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

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

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

В данной работе решение задач осуществляется численно, посредством составления вычислительных алгоритмов в среде SimplexWin и Microsoft Excel.

Основные результаты работы приведены в заключении.



Глава 1. Предварительные сведения

1.1 Теория (0, 1) - матриц

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

Матрицей называется прямоугольная таблица, составленная из чисел или других символов. Числа aij, называются элементами матрицы. Горизонтальный ряд элементов i матрицы, называется строкой. Вертикальный ряд элементов j матрицы, называется столбцом.

Если матрица имеет m строк и n столбцов, то ее размер m*n. Для краткости матрица обозначается заглавной буквой.

Пример 1. Матрица А

Линиями матрицы, называют строки и столбцы матрицы.

Диагональю матрицы A назовем такое множество мест, что никакие два не лежат в одной строке или одном столбце. Среди диагоналей квадратной матрицы выделяются главная, которая идет от верхнего левого угла к правому нижнему, и побочная, идущая от верхнего правого к нижнему левому углу. [34, стр.45-63]

Индексы элементов главной диагонали матрицы порядка n - это (i,i), побочной - это (i,n -i +1)(i =1,2,....n).

Следом матрицы является сумма элементов, расположенных на её главной диагонали.

Матрица A, называется рефлексивной, если все диагональные элементы матрицы равняются 1.

Подматрицей A' размером m*n, называется матрица, образованная всеми элементами A, лежащими на пересечении m строк и n столбцов.

Матрица, размера m*n, все элементы которой равны 0, называется нулевой подматрицей.

Блочная (клеточная) матрица - представление матрицы, при котором она рассекается вертикальными и горизонтальными линиями на прямоугольные части - блоки (клетки). [33, стр. 57-59]

Для каждой матрицы A а[ai j ] размера m*n можно определить операцию транспонирования, заключающуюся в том, что ее строки по порядку записываются в виде столбцов, двигаясь слева направо. Данная матрица размером m*n, называется транспонированной и обозначается A^T, определенная как

A^Ti j =Aji.

Пример 2. Транспонирование матрицы

Матрица A называется неотрицательной, если все элементы которой, являются действительными неотрицательными числами.

Если в матрице число строк равно числу столбцов m =n, то такую матрицу называют квадратной, причем число ее строк или столбцов называется порядком матрицы.

Квадратная матрица, называется диагональной, если все элементы, данной матрицы, вне главной диагонали равны нулю. [34, стр. 67-71]

Диагональная матрица, называется единичной, если все элементы на главной диагонали равны единице, а все остальные нулю.

Квадратная матрица, называется перестановочной, если она имеет в каждой строке и каждом столбце ровно одну единицу.

Матрица A и B называется перестановочно подобными, если A =PBPT для некоторой перестановочной матрицы P. Содержательный смысл этого определения заключается в том, что A получается из B одинаковыми перестановками строк и столбцов.

Рангом матрицы A =(ai j ), называется максимальное количество линейно независимых строк или столбцов. Ранг матрицы обозначается rank( A).

Граничным рангом матрицы A =(ai j ) называется, наибольшее число таких её положительных элементов, никакие два из которых не лежат в одной строке или одном столбце. Граничный ранг матрицы обозначается rankt ( A).

Рангом покрытия матрицы A, называется наименьшее число линий, на которых расположены все её положительные элементы. Ранг покрытия матрицы обозначается с( A). [34, стр. 69-85]

1.2 Графы

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

Пара V (G), E(G) называется простым графом, если V (G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечного множества неупорядоченных пар различных из V (G), называемых ребрами (или линиями). Иногда V (G) называют множеством вершин, а E(G) - множеством ребер графа G. Каждое ребро определяется парой вершин.

Графы удобно изображать диаграммами следующим образом. Элементы множества V изображаются точками плоскости. Элементы множества E изображаются на плоскости линиями, соединяющими вершины графа. [4, стр. 132-144]

Пример 3.

Рисунок 1. Граф, где ребро e1 инцидентно вершинам v1 и v2 ; v1 и v4

являются смежными вершинами, а e1 и e2 - смежными ребрами

Две вершины графа G называются смежными вершинами, если они являющиеся концевыми для некоторого ребра.

Каждый элемент eA если упорядоченная пара (v1, v2 ) элементы множества R, вершины v1 и v2 называются концевыми точками или концами ребра e. Точка v2, называется начальной вершиной, а v4 - конечной вершиной ребра e.

Вершина и ребро графа G называются инцидентными друг другу, если вершина является для этого ребра концевой.

Два ребра, инцидентные одной и той же вершине, называются смежными ребрами графа (см. Рисунок 1.).

Число инцидентных вершине vi - ребер называется степенью вершины графа и обозначается d (vi ). Вершина степени 1, называется висячей вершиной, а степени 0 изолированной.

Граф, не имеющий ребер, называется пустым. Граф, степени всех вершин которого равны n -1, называется полным. [1, стр. 245-258]

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

Маршрутом в графе G, называется всякая чередующаяся последовательность вершин и ребер.

Длинной маршрута называют количество содержащихся в них ребер.

Путем называется маршрут не нулевой длины, в котором все вершины различны.

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

Контур - это замкнутый маршрут не нулевой длины, у которого все вершины различны (за исключением первой и последней).

Контур длины 1 называется петлей.

Граф G =(V, E) и G =(V ', E') называется изоморфными, если существует такая биекция у: V >V', что (u,v)E -(у(u),у(v)) E'. С точки зрения теории изоморфные графы представляют, по существу один граф, но с различными обозначениями вершин.

Полустепенью исхода od( v ), называется число выходящих из нее вершин.

Полустепенью захода вершин [37, стр. 139].

id (u), называется число входящих в нее

Граф G =(V, E) и G =(V ', E') называется подграфом графа G, если V' и E', что ребро (vi,v j ) содержится в E' только в том случае, если vi в v j содержатся в V' и G', называется собственным подграфом G, если E' собственное подмножество E или V' - собственное подмножество V. Если все вершины графа G присутствуют в подграфе G' называется основным подграфом G. (см. Рисунок 2.) графа G, тогда G'

Рисунок 2. Граф и некоторые его подграфы :

а) - граф G ; б) - подграф G' ; в) - подграф G'' ; г) - подграф G'''

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

Вершинным покрытием графа G называется множество вершин, покрывающих все ребра графа G =(V, E).

Числом вершинного покрытия графа G, называется наименьшее число вершин во всех вершинных покрытиях графа. [3, стр. 23-27]

Граф, содержащий единственную вершину, и не содержащий петли, называют тривиальным.

Ориентированный граф или орграф называется граф G =(V, E), у которого множество ребер является множеством упорядоченных пар.

Если ребра графа G ориентированы, графически они изображается стрелками, называемыми дугами.

Если ребра не имеют ориентации, граф называется неориентированным. [37, стр. 278-286]

Орграф называется сильно связным, если для любых двух его вершин u, v существует (u,v) - путь.

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

Компонента сильной связности может содержать несколько вершин или состоять из одной вершины. Компонента сильной связности, состоящая из одной вершины и не содержащая петли, называется тривиальной.

Лемма 1. Для всех вершин равносильны.

Существует открытый u, v орграфа G следующие утверждения (u,v)- маршрут. Существует (u,v)- путь.



Рисунок 3. Орграфы без петель с двумя и тремя вершинами

Лемма 2. Не тривиальный орграф G является сильно связным тогда и только тогда, когда существует замкнутый маршрут, содержащий все его вершины.

Лемма 3. Для всех вершин u орграфа G следующие утверждения равносильны.

Существует (u,v)- маршрут не нулевой длины.

Существует - контур.

Лемма 4. Справедливы утверждения.

Множество ребер каждого замкнутого маршрута не нулевой длины можно разбить на контуры.

Пусть c1,c2,...,ck - все контуры сильно связного орграфа G, длины которых, соответственно, равны l1,l2,,lk. Тогда длина любого замкнутого маршрута в орграфе G имеет вид x1l1 +x2l2 +… +xklk, где x1,x2,...xk N 0. Длина любого замкнутого маршрута орграфа G делится на число d, - период орграфа G.

Доказательство. 2) Пусть R - некоторый замкнутый маршрут не нулевой длины в орграфе. Определим рекуррентно конечную последовательность замкнутых маршрутов R1* =R, R2*, R3*, …. Если замкнутый маршрут Ri* строго «включает» контур Ci, то вычеркивая Ci из маршрута Ri, за исключением последней вершины, получаем замкнутый маршрут Ri*1. Повторяя эту операцию несколько раз получим контур, содержащий начало маршрута R. Если x j - число появлений контура C j в маршруте R, то длина R имеет вид (1). [14, стр. 82-86]

Далее рассмотрим определение двудольного графа, и приведем примеры ассоциированных матриц с орграфами и двудольными графами.

Граф G называется двудольным графом (или биграф), множество вершин V которого можно разбить на два подмножества V1 и V2, таким образом, что каждое ребро графа G соединяет вершины из разных множеств (будем говорить, что ребра G соединяют множества V1 и V2 (см. Рисунок 4).

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

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

Двудолный граф называется элементарным, если он не содержит параллельных ребер (см. Рисунок 5.).

V1 V2

Рисунок 5. Элементарный двудольный граф

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

Многие свойства (0, 1) - матриц основаны на том, что свойства (0, 1) - матриц можно интерпретировать как свойства ассоциированных орграфов и двудольных графов.

Пример 4. С матрицами



ассоциированы, соответствующие орграфы, изображенные (см. Рисунок 6.).

Рисунок 6. (0, 1) - матрицы и ассоциированные с ними орграфы

Пример 5. С матрицей

ассоциирован двудольный граф G(A), изображение (см. Рисунок 7.).

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

1.3 Паросочетания в двудольных графах

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

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

Вес паросочетания, есть сумма весов всех его ребер.

Пример 6. Паросочетанием является {e1, e4} в графе на (см. Рисунок 8.).

Рисунок 8. Паросочетание в двудольном графе

Рисунок 9. Максимальное паросочетание

Максимальное паросочетание - это такое паросочетание, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания. Другими словами, паросочетание графа G является наибольшим, если любое ребро в G имеет непустое пересечение по крайней мере с одним ребром из G. Множество {e1, e5, e6} - это максимальное паросочетание в графе на (см Рисунок 9.). Число ребер в максимальном паросочетании графа G будет называться G и обозначаться через б1(G).

Паросочетание максимального веса в двудольном графе определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. [37, стр. 217-236]

Наибольшее паросочетание (или максимальное по размеру паросочетание) - это такое паросочетание, которое содержит максимальное количество рёбер.

Число паросочетания графа - это число рёбер в наибольшем паросочетании. У графа может быть множество наибольших паросочетаний. При этом любое наибольшее паросочетание является максимальным, но не любое максимальное будет наибольшим.

Насыщенной (покрытой) вершиной в паросочетании M, называется концевая вершина ребра M.

Например, вершина v паросочетания {e1, e5, e6} в графе на рис. 9 насыщенна. Вершины, не «охваченные» паросочетанием, называются ненасыщенными (непокрытыми).

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

Любое совершенное паросочетание является максимальным.

Совершенное паросочетание является также рёберным покрытием минимального размера. Таким образом, - размер максимального паросочетания не превосходит минимального рёберного покрытия.

Пусть двудольный граф G =(V, E) с разбиением ( X,Y ) обозначается тройкой ( X,Y, E). Множество X паросочетается с Y в двудольном графе ( X,Y, E), если существует такое паросочетание M, что каждая вершина Х насыщена в M. Паросочетание M в этом случае называется полным паросочетанием Х с Y. [30, стр. 97-112]

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

Сначала установим несколько утверждений, справедливых для двудольных графов. Они являются основополагающими при исследовании паросочетания.

Пусть G - произвольный граф, н(G)- число паросочетания графа G, ф(G) - число вершинного покрытия, б(G) - вершинное число независимости и с(G)- число реберного покрытия.

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



Лемма 5. Для любого графа G справедливо равенство

б(G) +ф(G) =V (G).

Лемма 6. Для любого графа G, не имеющего изолированных вершин, выполняется соотношение н(G) +с(G) =V (G)

Доказательство. Пусть С - реберное покрытие графа G, содержащее с(G). Пусть через С обозначается подграф графа G с множеством ребер С и множеством вершин V (G). Поскольку С минимально, подграф С состоит из объединения вершин, то n =с-с (G). С другой стороны С содержит по крайней мере одно ребро, поэтому мы получим паросочетание М, и следовательно

н(G) ?n =с-с(G) или н(G) +с(G) ?с (1.3.1)

Пусть теперь М 0 какое-либо паросочетание в G и U - множество вершин, не покрытых М 0. Тогда U - независимое множество. Далее, граф G не имеет изолированных вершин и поэтому для каждой из с-2н(G) вершин множества U можно выбрать ребро, покрывающее ее. Обозначим эту совокупность ребер через S. Тогда М ?S если реберное покрытие для G и мы имеем:

с(G) ?M ?S =н(G) +с-2н(G) =с-н(G).

Значит,

н(G) +с(G) ?-с (1.3.2)



Объединим неравенства (1.3.1) и (1.3.2), получаем доказываемый результат.

При доказательстве леммы 5 видна связь между наименьшими вершинными покрытиями и независимыми множествами вершин, а именно, если S - наименьшее вершинное покрытие, то V (G) S - наибольшее независимое множество вершин. Этой взаимной дополнительности как раз не достает реберным покрытием и паросочетаниям. Видно, что связанные с б(G) и ф(G), будет исследовать проще, чем задачи, в которых рассматриваются н(G) и с(G).

В случае двудольного графа в добавление к основным тождествам, выполняется еще одно легко устанавливаемое соотношение, которое, является единственным наиболее важным результатом во всей теории паросочетаний на сегодняшний день. Приводимое нами доказательство, впервые было предложено Л. Ловасом (1975). [22, стр. 112-127]

Теорема 1. Минимаксная теорема Кёнига.

Для двудольного графа G справедливо соотношение ф(G) =н(G).

Доказательство. Для всякого графа G справедливо неравенство

н(G) ?ф(G) (1.3.1).

Теперь получим обратное неравенство. Для этого будем удалять ребра из графа G, пока это возможно, так, чтобы ф не изменялось. Полученный в результате минимальный граф обозначим через G'. Следовательно, ф(G') =ф(G), но ф(G' -e) <ф(G) состоит из независимых ребер для любого ребра e в G'. Убедимся, что G'

Допустим противное. Тогда найдутся ребра x и у, смежные в вершине a графа G'. Рассмотрим граф G' -x. Из минимальности G' следует, что существует вершинное покрытие Sx графа G' -x с Sx =ф(G') -1. Ни одна вершина ребра x очевидно не лежит в Sx. Аналогично, имеется множество S y, покрывающие G' -y и не содержащее ни одной вершины ребра y, причем Sy =Sx. Сформируем подграф G" графа G';

G" =G'[{a} ?(Sx ?Sy )]

где ?- симметрическая разность.

Пусть t =Sx ?Sy. Тогда V (G") =2(ф(G") -1 -t) +1 и, поскольку граф (G") 21 двудольный, имеется множество T, которое покрывает G", и T ?ф(G') -1-t ).

Ясно, что T ' =T ?(Sx ?Sy ) покрывает граф G'. Предположим, что z - какое-либо ребро в G'. Если z ?x или z ?y, то оно покрывается обоими множествами Sx и S у, т.е. либо z покрывается пересечением Sx ?Sy, либо соединяется Sx -Sy с Sy -Sx. Во втором случае z является ребром графа G"и, следовательно, покрывается множеством T.

Наконец, x и у - ребра графа G" и, значит, покрывается множеством T.

Таким образом,

ф(G') ?T '

=T ?(Sx ?Sу ) =T

Sx ?Sу

?ф(G') -1 -t +t =ф(G') -1,

т.е. пришли к противоречию. Итак, граф как и утверждалось. Следовательно, G' состоит из независимых ребер,

ф(G) =ф(G') =н(G') ?н(G) (1.3.3)

Отсюда и из неравенства (1.3.1) получаем требуемое. [22, стр. 167]

1.4 Задачи линейного программирования

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

Линейное программирование возникло из практических потребностей, поэтому оно находит применение при решении широкого класса различных экономических задач, задач управления и планирования, оптимального размещения оборудования, товаров и т.д.

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

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

Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

Опорным планом, называется, такой допустимый план, совокупность векторных коэффициентов при ненулевых компонентов которого представляет собой систему линейно независимых векторов. [5, стр. 80]

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

Переменные столбцы коэффициентов при которых образуют полную систему единичных независимых столбцов, будем называть базисными (ХБ ), а остальные переменные - небазисными.

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

Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны.

Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).

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

Задачи линейного программирования можно группировать по-разному.

Например, по содержанию задачи, по сфере использования, по видам математических моделей.

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

Стандартная задача линейного программирования



или в матричной записи, где x =(x1, x2,..., xn), c =(c1,c2,...,cn), b =(b1,b2,...,bm), A=(ai j )- матрица коэффициентов. Вектор c называется вектором коэффициентов линейной формы, b - вектором ограничений.

Каноническая задача линейного программирования

или в матричной записи,

Общая задача линейного программирования

В этой задаче часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности.

Далее более подробно будет рассмотрена общая задача линейного программирования во второй главе.

Все эти три перечисленные формы задач эквивалентны в том смысле, что каждую из них можно решать простыми преобразованиями привести к любой из двух остальных. Поэтому, если имеется способ решения одной из этих задач, то тем самым мы умеем решать любую из трех задач линейного программирования. [37, стр. 212-234]



1.5 Симплекс-метод

Симплекс-метод, является универсальным методом, применимым к любой задаче линейного программирования в канонической форме (ЗЛП).

Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен.

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

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

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

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

Симплексный метод гарантирует, что при этом новом решении линейная форма, если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным. [5, стр. 53-57]

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

Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

нахождение оптимального решения.

При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.

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

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

Перед составлением симплекс-таблицы задача должна быть преобразована, система ограничений приведена к допустимому базисному виду, c помощью которого из целевой функции должны быть исключены базисные переменные.

Таблицы симплекс - метода необходимо строить до тех пор, пока не будет получен оптимальный план. План будет считаться оптимальным, если в последней индексной строке симплекс-таблицы будут только нули и положительные числа.

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

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

Под задачей дискретного программирования понимается задача математического программирования [22, стр. 212]

f (x 0 ) =min f (x), x G, (1.6.1)

множество допустимых решений, т.е. 0 ?G=N <, где G - число элементов множества G все допустимые можно пронумеровать x1, x 2,.....x N: вычислить x1, x 2,.....x N и найти наименьшее значение.

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



Поэтому

отсюда видно, что с ростом числа переменных объем вычисленной работы резко возрастает.

В качестве примера задачи дискретного программирования рассмотрим задачу частично целочисленного линейного программирования - одну из наиболее часто встречающихся и наиболее изученных задач.

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

Таким образом, здесь используется модель общей задачи математического программирования с дополнительным ограничением:

x1, x2,.........xn - целочисленны.

Задача формулируется следующим образом:

Если n1 <n, то задача называется частично целочисленной, если n1 =n - полностью целочисленной.

Пример 7.

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

Рассмотрим задачу x1 +x2 >max, x =(x1, x2)G. Построим область G.

Пусть -б>0 иррациональное число, например, б=2. Тогда на прямой x 2 =бx1 нет ни одной точки с обеими целочисленными координатами, кроме точки (0,0). Рассмотрим прямую x 2 =бx1 при x1 ?0, x2 ?0.

Возьмем x1 =б, тогда x2 =бб. В полученном прямоугольнике с вершинами (0,0), ( б,0), ( б, б, б), (0, б, б) выделим все точки целочисленными координатами и проведем из точки (б, б, два отрезка так, чтобы в полученном четырехугольнике ОАВС не было ни одной целочисленной точки, кроме точки (0,0) (см.Рисунок.10.).

Рисунок.10, 11.

Область G построена. Параметр а может быть выбран так, чтобы решение линейной задачи была точка (б,б,б), тогда, выбирая а, можно сделать

(x1 +x2) =б(1 +б)

сколь угодно большим числом,

Решение целочисленной задачи - точка (0,0), x1 +x2=0. Поэтому разность между значениями линейных функций целочисленной и линейной задачи для оптимальных решений этих задач может быть сколь угодно большой. Пусть теперь область G имеет вид треугольника АВС (см. Рисунок 11.). В этом случае линейная задача имеет то же решение, что и ранее, а целочисленная задача неразрешима. [37, стр.86-90]

Рассмотрение этого простого примера позволяет сделать два важных вывода:

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

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

В данном параграфе, изложение материала задач линейного программирования ограниченно рассмотрением классической транспортной задачи.

Постановка задачи.

Пусть имеется m пунктов производства грузов с запасами ai, n пунктов потребления однородной продукции b j. Объем производства в пункте производства с номером "i" равен ai ; объем потребления в пункте потребления с номером " j " равен b j (i = 1,2,…,m; j=1,2,…,n).

Предполагается, что производство и потребление сбалансированы, т.е. m n

Матрицу C =|| cij || будем называть матрицей тарифов (или матрицей транспортных расходов), затраты на перевозку единицы продукции из пункта производства "i" в пункт потребления " j ". [16, стр. 189-196]

Требуется составить план перевозок, которые не выходят за пределы мощностей производителей, удовлетворяет полностью всех потребителей и минимизирует суммарные затраты на перевозку.



Через пункт " j ". Тогда xi j m n обозначим объем перевозки из пункта производства "i" в

Задача (1.4.1) - (1.4.4) - это задача линейного программирования, число переменных xi j равно m *n, число ограничений (1.4.2) и (1.4.3) равно m +n.

Число ненулевых значений xi j не превосходит m +n -1, так как в силу условий сбалансированности строки матрицы задачи, формируются из условий (1.4.2) и (1.4.3), линейно зависимы. Известно, что условие сбалансированности производства и потребления является необходимым и достаточным условием разрешимости транспортной задачи. Известно также, что значение целевой функции (1.4.1) ограничено снизу и сверху, если все ci j, ai и bi ограничены, при этом хi j ?min(aib j ).

Транспортную задачу можно рассматривать как каноническую задачу и решать её симплекс-методом.

Теорема 1. Система линейных ограничений транспортной задачи совместна тогда и только тогда, когда

a1 + +am =b1 + +bn. (1)

Доказательство. Пусть система линейных ограничений транспортной задачи совместна и xi j - ее некоторое решение, i =(1, 2,...., m), j =(1, 2,...., n). Имеем



Пусть справедливо равенство (1.4.3). Обозначим

M =a1 + +am =b1 + +bn.

Тогда xij =aib j / M, i =(1, 2,...., m), j =(1, 2,...., n), является решением транспортной задачи.

Транспортная задача имеет решение тогда и только тогда, когда

Равенство (1.4.3) - это равенство запасов и потребностей.

Если выполняется равенство (1.4.3), то транспортная задача называется сбалансированной.

Однако, может случиться, что запасы не равны потребностям,

a1 + +am >b1 + +bn a1 + +am <b1 + +bn (1.4.5), (1.4.6).

Запасы превосходят потребности или потребности превосходят запасы. Если выполняется неравенства (1.4.5) или (1.4.6), то транспортная задача называется несбалансированной.

Для несбалансированной задачи можно отыскать план перевозок, который будет минимизировать транспортные издержки, но при этом не будут удовлетворены все потребности или не будет вывезен весь запас.

Решение несбалансированной транспортной задачи сводится к решению сбалансированной транспортной задачи. Пусть выполняется условие (1.4.4). Тогда в математическую модель транспортной задачи вводится фиктивный пункт потребления номер (n +1) с потребностью

bn+1 =a1 + +am -(b1 + +bn).

Все тарифы на доставку грузов в этот пункт считают равными 0.

Матрица тарифов в этом случае имеет вид:

Матрица перевозок имеет вид

Транспортные расходы в этом случае будут снова равны сумме (1.4.2) и

a1 + +am =b1 +… +bn +bn+1.

Таким образом, решение несбалансированной транспортной задачи свелось к решению сбалансированной транспортной задачи.

Пусть выполняется условие (1.4.5). Тогда в математическую модель транспортной задачи вводится фиктивный пункт отправления номер (m +1) с запасом, равным am+1 =(b1 +...+bn) -(a1 +...+am).

Все тарифы на доставку груза из этого пункта считают равными 0.

Матрица тарифов в этом случае имеет вид

Матрица перевозок имеет вид



Получаем

a1 + +am +am+1 =b1 + +bn.

Транспортные расходы равны (1.4.2). Решение несбалансированной транспортной задачи свелось к решению сбалансированной транспортной задачи.

1.7 Компьютерное решение задач линейного программирования

Расчет симплекс-таблиц является сложной рутинной процедурой в ходе выполнения, которой высока вероятность счетной ошибки со стороны человека. Умножать и вычитать дроби, совсем непросто. В настоящее время разработано достаточно много программ, позволяющих найти оптимальное решение для задач линейного программирования (например, надстройка «Поиск решения» для MS Excel, SimplexWin и др.). Отчеты с анализом полученного решения, формируемые программами, настолько же подробны, что и симплекс-таблицы.

Среди преимуществ применения программ можно выделить следующие:

1. Существенное сокращение времени, требуемое для выполнения расчетов (т.е. резкое увеличение скорость при выполнении расчетов на компьютере, снижение числа ошибок).

Увеличение скорости модификации дает возможность достаточно просто изменить цифры, формулы или ограничения.

Простота распространения. Минусы: при машинном расчете могут накапливаться ошибки округления, что может отрицательно сказаться на качестве решения.

Рассмотрим на примере технологию решения ЗЛП с использованием функции «Поиск решения» табличного процессора Excel. [19, стр.237-246]

Надстройка «Поиск решения» - это надстройка, входящая в поставку Excel, предназначенная для оптимизации моделей при наличии ограничений.

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

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

Чтобы вызвать «Поиск решения», нужно выбрать меню «Данные/Поиск Решения». Надстройка «Поиск решения», хотя и входит в поставку Excel, не подключается автоматически к этой программе.

Поэтому если в меню «Данные» отсутствует команда «Поиск решения», значит, настройка не подключена.

Для её подключения нужно:

Выбирать команду «Файл-Параметры» (см. Рисунок 12, 13).

Рисунок 12.

«Настройки» перейти и в открывшемся диалоговом окне Надстройки выделяется «Поиск решения».

Управление: « Настройки Excel» - « Перейти»

Рисунок 13.

Выбираем «Пакет анализа» и «Поиск решений» подтверждаем «ОК» (см. Рисунок 14).

Рисунок 14.

В правом верхнем углу программы появилась новая группа «Анализ» с командами «Анализ данных» и «Поиск решений» (см. Рисунок 15).

Рисунок 15.

Параметры поиска решения, выбирается метод решения: «Поиск решения нелинейных задач методом ОПГ», «Найти решение» (см. Рисунок 16).



Рисунок 16.

Для решения задач линейного программирования с помощью MS Excel требуется соблюдать следующие рекомендации:

Перед решением задачи линейного программирования желательно привести её к стандартному специальному виду.

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

Переменные решения группируются в отдельный блок столбцов/строк; аналогично ограничения группируются в свой блок строк/столбцов.

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

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

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

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

Далее рассмотрим пакет SimplexWin

Программа SimplexWin предназначена для решения задач линейного программирования симплекс методом. Решение задач линейного программирования, в данной программе, происходит полностью в автоматизированном режиме, т.е. дополнительные переменные и искусственные базисы вводятся автоматически. Алгоритм решение задачи линейного программирования, представляет собой последовательность таблиц с конечным ответом или сообщением об отсутствии решения. Очень удобно, программа поддерживает загрузку и сохранение данных в файле или выводит полученные результаты в таблице Excel (см. Рисунок 17).

Рисунок 17.



Глава 2. Теоремы Кёнига, Фробениуса-Кёнига

2.1 Теоремы Фробениуса-Кенига

Теорема Фробениуса-Кёнига и Кёнига.

Пусть P =(0,1) множество, где P - это матрица A размера m*n.

Теоремы Фробениуса - Кёнига и Кёнига характеризуют расположение нулей в (0,1) - матрице.

Лемма 1. Пусть матрица APn*n. Матрица A имеет нулевую подматрицу 0s*t, s +t =n +1, тогда и только тогда, когда каждая диагональ матрицы A содержит нуль 0.

Доказательство. Пусть матрица A имеет нулевую подматрицу 0s*t, s +t =n +1. Переставив строки и столбцы матрицы A, получим блочную матрицу

где B P(n-s)*t, C P(n-s)*(n-t), D Ps*(n-t). Любая диагональ, состоящая из единиц 1, должна содержать единицы 1 из первых t столбцов матрицы B. Эти единицы 1 должны располагаться в строках. Значит, n -s ?t. Получили t -1 =n -s ?t - противоречие. Доказано, что каждая диагональ матрицы A содержит нуль 0.

Пусть каждая диагональ матрицы A содержит нуль 0. Докажем индукцией по числу n, что матрица A имеет нулевую подматрицу 0s*t, где s +t =n +1. Если n =1, то утверждение очевидно выполнено.

Предположим, что утверждение доказано для всех матриц порядки которых меньше числа n, n ?2.

Докажем утверждение для матрицы A порядка n. Если A - нулевая матрица, то утверждение выполнено. Пусть A - не нулевая матрица и aij =1 для некоторых индексов i, j. Рассмотрим матрицу A(i |j), полученную из матрицы A вычеркиванием строки с номером i и столбца с номером j.

Матрица A(i | j) имеет порядок n -1. Каждая диагональ матрицы A(i | j) содержит нуль 0. По индукционному предположению, матрица A(i | j) имеет нулевую подматрицу 0s'*t', s'+t'=(n -1) +1 =n. Переставив строки и столбцы матрицы A, получим блочную матрицу

где B Pt*t, C Pt*s, B Cs*t D Ps*s. Каждая диагональ матрицы B содержит нуль 0, или каждая диагональ матрицы D содержит нуль 0.

Пусть каждая диагональ матрицы B содержит нуль 0. По индукционному предположению, матрица B имеет нулевую подматрица 0s `*t ` такую, что s `+t `=t'+1. Поэтому матрица A имеет нулевую подматрица 0s*t такую, что s =s'+s `, t =t''. Имеем s +t =s'+s `+t `=s'+t'+1 =n +1.

Рассмотрим две классические комбинаторные теоремы, характеризующие размещение нулей и единиц в (0, 1) - матрицах.

Теорема 1. Фробениуса-Кёнига.

Пусть матрица APm*n, m ?n. Матрица A имеет нулевую подматрицу 0s*t, s +t =n +1, тогда и только тогда, когда каждая диагональ матрицы A содержит нуль 0.

Доказательство. Дополним матрицу A до квадратной матрицы B порядка n, приписав к ней n -m утверждения равносильны: строк, состоящих из единиц 1. Следующие матрица A имеет нулевую подматрицу 0s*t, s +t =n +1; матрица B имеет нулевую подматрицу 0s*t, s +t =n +1; когда каждая диагональ матрицы B содержит нуль 0 ; каждая диагональ матрицы A содержит нуль 0.

Основной теоремой о ранге покрытия является теорема Кёнига.

Теорема 2. Кёнига

Ранг покрытия любой матрицы APn*n равен граничному рангу rankt ( A).

Доказательство. Обозначим Rc - ранг покрытия матрицы A. По определению граничного ранга, существует rankt ( A) единиц 1, никакие две из которых не принадлежат одной линии матрицы A. Поэтому Rc ?rankt ( A).

Докажем теперь неравенство Rc ?rankt ( A). Пусть k строк и q столбцов содержат все единицы 1 матрицы A, k +q =Rc. Если k =Rc или q =Rc, то неравенство Rc ?rankt ( A) справедливо. Поэтому далее будем считать, что k <Rc и q <Rc.

Переставив строки и столбцы матрицы, получим блочную матрицу

где B Pk*q, C Pk*(n-q), D P(n-k)*q, 0 =0(n-k)*(n-q).

Имеем q ?n -k. k +q =Rc. Поэтому справедливы неравенства k =Rc -q ?n -q,

Допустим, что каждая диагональ матрицы C содержит нуль 0. По теореме Фробениуса - Кёнига, матрица C имеет нулевую подматрицу 0s*t, s +t =n -q +1. Тогда матрица A имеет нулевую подматрицу 0s*t, s'=n -k +s, t'=t. Поэтому все единицы матрицы A можно покрыть n -s'=k -s строками и n -t'=n -t столбцами. Все единицы матрицы A можно покрыть противоречие.

k -s +n -t =(n +k) -(s +t) =k +q -1=Rc -1 линиями -

Доказано, что матрица C содержит диагональ, на которой расположены единицы 1.

Аналогично доказывается, что матрица t D содержит диагональ, на которой расположены единицы 1.

Значит, в матрице A существует k +q единиц 1, никакие две из которых не лежат на одной линии. Поэтому rankt (A) ?k +q =Rc.

Теорема Кёнига играет важную роль в комбинаторных рассмотрениях, особенно в теории графов. [13, стр. 24-26]

Граничный ранг, и соответствующая ему не нулевая диагональ вычисляется алгоритмами нахождения наибольшего паросочетания в двудольном графе. Более глубоко с комбинаторной теорией матриц можно познакомиться по книгам [Рыбников, 1985], [Сачков, Тараканов, 2000].

Для двудольного графа имеется более определенное утверждение:

Число ребер графа G( A) вершинного покрытия.

в наибольшем паросочетании равно числу

Доказательство теоремы Кёнига в матричной формулировке, в том виде в каком она рассматривается в комбинаторике.

Теорема 3.

Пусть матрица APm*n. Граничный ранг rankt ( A) равен числу паросочетаний (число вершинного покрытия) графа G( A).

Доказательство. Заметим, что каждое множество единиц 1 матрицы A, никакие две из которых не лежат на одной линии, определяет паросочетание в графе G( A), и наоборот.

Пусть дан двудольный граф G(V1,V2, R), у которого множество вершин V разбивается на два независимых подмножества V1 и V2, т.е. вершины в каждом из этих подмножеств несмежные между собой. Предположим, что вершины графа пронумерованы, причем сначала пронумерованы вершины из множества V1, затем из множества V2. При такой нумерации вершин матрица смежности A графа G(V1,V2, R) будет иметь вид:

где порядок квадратной нулевой матрицы в верхнем левом углу равен V1, а порядок квадратной нулевой матрицы в правом нижнем углу равен V2. Информация о связях в двудольном графе хранится в матрице А12 размерности V1 *V2. Заметим, что любую (0,1) - матрицу мы можем рассматривать как матрицу смежности некоторого двудольного графа.

Поскольку любой матрице А с элементами aij мы можем сопоставить

матрицу A с элементами aij, причем ai j =1, если ai j ?0, и ai j =0, если ai j =0, то любой прямоугольной матрице мы можем сопоставить двудольный граф с матрицей смежности.

Рассмотрим двудольный граф, (см. Рисунок 18) и его матрицу :

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

Вершинам множества V1 ={A1, A2, A3, A4}соответствуют строки матрицы, а вершинам A12 множества V2 ={A5, A6, A7, A8} соответствуют столбцы этой матрицы. Ребрам графа соответствуют единицы этой матрицы. Так ребру соединяющему вершину A2 с вершиной A7 соответствует 1, стоящая на месте (i, j), где i =2, j =7 -4 =3. Далее, очевидно, что вершина с номером i V1 «покрывает» ребра, которым соответствуют единицы, расположенные в i -oй строке. Вершина с номером k V2 «покрывает» ребра, которым соответствуют единицы, расположенные в j -ом столбце, где j=k- V1 =k -4. Очевидно, что число вершинного покрытия б0 равно минимальному числу линий (как строк, так и столбцов) содержащих все единицы. В данном примере таких линий 3 (первый столбец, вторая и четвертые строки; или первый и третий столбцы и четвертая строка). То есть, в нашем примере б0 =3.

Ребра, образующие наибольшее паросочетание, соответствуют наибольшему числу единиц, попарно не лежащих на одной линии. Так в данном примере наибольшее паросочетание образуют ребра, соответствующие единицы которых, расположены на местах: ( A1,A1), ( A2,A3) и ( A4,A2) или ( A3,A1), ( A2,A3) и ( A4,A4). Теорема доказана.

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

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

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

Задаётся матрица размера (m *n).

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

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

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

Для нахождения наибольшего паросочетания рассмотрим общую задачу линейного программирования. Общая задача заключается в отыскивании вектора (x1, x2,..., x j,..., xn ), минимизирующего линейную форму (функцию цели задачи)

c1x1 +c2x2 +...c jx j +...cnxn (2.2.1)

Переменные которой подчинены следующим линейным ограничениям:

где аij, bi, и c j - заданные постоянные величины, а m<n,

Без ограничения общности можно считать все bi неотрицательными, ибо в противном случае соответствующее уравнение можно умножить на -1. В различных ситуациях удобно использовать разные виды записи общей задачи линейного программирования. Наиболее употребляемыми из них являются следующие:

Минимизировать n c j x j 1 при условиях x j ?0, j =1, 2,...,n и

Минимизировать сX при условии X ?0 и AX =b, где с =(с1, c2,...cn ) - вектор строка, Х =(х1, х2,...хn ) - вектор-столбец, A=(ai j ), столбец. b =(b1,b2,...bn ) - вектор столбец и 0 - n-мерный нулевой вектор

...