Реферат по истории математики Научный проф. Верещагин Н. К
Скачать 272.28 Kb.
|
| Глава 3. Задача о назначениях: «взвешенный» вариант задачи о паросочетаниях §3.1. Монж: оптимальное назначение Задача о назначениях является одной из старейших задач комбинаторной оптимизации. Еще в 1784 году ее исследовал Монж (Monge) (в своих работах он использовал термин «задача о транспортировке». Монж был мотивирован задачей транспортировки земли, которую он рассматривал как дискретную, комбинаторную задачу транспортировки молекул: «Когда необходимо перевезти землю из одного места в другое, необходимо учитывать как количество перевозимой земли, так и наличие свободного места там, куда она перевозится. Цена транспортировки одной молекулы пропорциональна ее весу и расстоянию перевозки, а значит, полная цена перевозки должна быть пропорциональна сумме произведений весов молекул на пройденное расстояние». Формально, Мондж рассматривает следующую задачу: «Пусть на плоскости заданы две области, ABCD и abcd, ограниченные произвольным контуром, непрерывные или дискретные, найти пусть которому должна следовать каждая молекула М первой области, чтобы перейти в некоторую молекулу m второго области, таким образом, что в результате этого перемещения область ABCD была перемещена в область abcd, и сумма произведений веса каждой молекулы на пройденное ей расстояние было минимальным». Мондж предложил геометрический метод решения данной задачи. Несмотря на его геометрическую интуитивность, он был не совсем верен, как заметил в 1928 году Аппель. §3.2. Теорема Эгервари В 1931 году Эгервари опубликовал «взвешенный» вариант теоремы Кёнига: Пусть элементы a_ij матрицы A размера n неотрицательные целые числа, и пусть для некоторых наборов неотрицательных чисел L_i и M_j выполнены условия: а_ij <= L_i + M_j (для всех I и j), тогда получим что min sum (L_k + M_k) = max (a_1p(1) + .. + a_np(n)), где максимум берется по всем перестановкам p. Доказательство, предложенное Эгервари, сугубо алгоритмично и ведет к алгоритму, использующему «невзвешенную» задачу о паросочетании в качестве подзадачи. Пусть W – максимальное число в матрице А, тогда алгоритму потребуется применить задачу о Паросочетании O(nW) раз, а суммарное время работы алгоритма составит O(nWB(n)), где B(n) – наилучшая оценка времени работы алгоритма нахождения максимального Паросочетания. Этот метод послужил основой для сформулированного в 1955 году «Венгерского метода» Куна, которые мы подробнее рассмотрим далее. Другим результатом Эгервари было установление следующей двойственной природы задачи о взвешенном Паросочетании: пусть G = (V, E) – двудольный граф и пусть w: E -> R неотрицательная весовая функция. Тогда вес максимального Паросочетания в G равняется минимальному значению y(V), где y: V -> R, таково что: y >= 0 и y_u + y_v >= w(uv). §3.3. 1940е годы Первый алгоритм для задачи о назначениях был опубликован Истерфилдом (Easterfield) в 1946 году. Мотивация этого алгоритма была следующей: «Что касается исследования в области задач демобилизации вооруженных сил, представляется возможным организовать переход людей из расформированных отрядов в другие отряды таким образом, чтобы их не пришлось потом переводить снова то момента их демобилизации. Более того, исследования количеств людей в различных группах позволили бы организовать этот процесс с наименьшим возможным количеством задержек. К сожалению, непредвиденный конец Японской войны не дал возможности проверить эффективность этой теории в деле. Тем не менее, алгоритм, изложенный в данной статье, возник именно в процессе исследований в этой области». Похоже, что Истерфилд работал, не имея представления о других исследованиях в данной области. Он сформулировал и доказал теорему эквивалентную теореме Халла, а также представил метод решения данной задачи, из которого можно извлечь результаты, полученные Эгервари. Идея Истерфильда основана на переборе всех подмножеств вершин в лексикографическом порядке, что привело к алгоритму со сложностью O(n^2 * 2^n) (что является улучшением по сравнению с перебором всех перестановок, на который требуется n! действий). Этот алгоритм был в дальнейшем уточнен в 1960 году. Настоящий прорыв в решении задачи о назначениях был совершен в 1951 году, когда Диниц показал, что задача о назначениях может быть сформулирована как линейная программа, автоматически обладающая целочисленным решением. Таким образом, к задаче о назначениях стало возможно применить симплекс-метод. Диниц рассматривал задачу о назначениях применительно к распределению работы среди людей. Он писал: «Как было сказано, в задаче о назначениях возникает лишь конечное число перестановок. Поэтому с математической точки зрения достаточно рассмотреть все перестановки и выбрать из них оптимальную. Например, если мы рассмотрим задачу для хотя бы для 10 человек, возникнет более трех с половиной миллионов перестановок, поэтому данный математический подход окажется неприменимым на практике». В 1949 году Робинсон в отчете для RAND написал что его «неудачный попытки» решения задачи о коммивояжере привели к интересному алгоритму решения задачи о назначениях, основанном на «отмене циклов». Идея его была следующей: рассмотрим произвольную перестановку p. Для всех i,j определим «длину» L_ij = a_jp(j) – a_ip(i) если j != p(i), и бесконечности в противном случае. Если в графе с такими длинами возникнет цикл отрицательного веса, это позволит сразу улучшить перестановку p. Если же такого цикла не окажется, то перестановка p оптимальна. Как отметил Робинсон, данный метод можно применять к графам из 50 вершин, при условии наличия необходимых вычислительных средств. §3.3. Ранние 1950е На семинаре по теории игр в Принстонском Университете в 1951 году, Фон Нейман (Von Neumann) указал на то, что задача о назначениях может быть сформулирована в виде игры с нулевой суммой для двух игроков, и нахождение ее решения эквивалентно поиску оптимальной стратегии в этой игре. Игра устроена следующим образом: пусть задана матрица A. Первый игрок будет играть строками этой матрицы, второй игрок – столбцами. Первый игрок выбирает номер строки, второй – номер столбца, после чего первый «платит» второму A_ij «денег». Индексы строк и столбцов чередоваться не могут, таким образом игра продолжается n раундов (где n – размер матрицы). Сведение данной игры к задаче о назначениях не очевидно. В дальнейшем к этой идее обращались Браун (Brown) и Робинсок. Фон Нейман также заметил, что поиск оптимальной стратегии по видимому можно осуществить за время пропорциональное некоторой степени n, что заметно меньше чем «очевидное» решение за время n!. Тем не менее, никакой аргументации этого наблюдения не последовало. Похожие идеи также были в работах Дулмага (Dulmage) и Гальперина (Halperine) (1955) и Купманса (Koopmans) и Бекмана (Beckmann) (1955, 1957). В работах Лорда (Lord) (1952) и Двайера (Dwyer) (1954), был изложен некоторый геометрический подход («метод оптимальных регионов»). Обзор методов решения задачи о назначениях по состоянию на 1953 год был сделан Моцкиным (Motzkin) в 1956 году. §3.4. Вычислительные результаты начала 1950х годов В статье, представленной в 1951 году на Симпозиуме по Линейным Неравенствам и Линейному Программированию в Вашингтоне, Воташ (Votaw) и Орден (Orden) упомянули, что для решения задачи о назначениях размера 10 * 10 требуется около 3 минут вычислений на машине SEAC (National Bureau of Standards Eastern Automatic Computer). В то же время для решения задачи о назначениях того же размера при использовании симплекс-метода требовалось около 20 минут. Однако, в воспоминаниях Куна от 1991 года он пишет: «Эта история началась летом 1953 года, когда Национальное Бюро Стандартов США собрали группу выдающихся алгебраистов и специалистов по комбинаторике в Институте Численного анализа (INA) расположенного на территории Университета Калифорнии в Лос-Анджелесе. Из-за нехватки места, я делил офис с Тедом Моцкиным, чьи работы в области линейных неравенств продвинули эту теорию на десять лет вперед. Одной из новинок, презентованных в INA, был компьютер SWAC (Standards Western Automatic Computer). SWAC был меньше, но быстрее чем его предшественник – компьютер SEAC. В течение лета, Томпкинс (C.B. Tompkins) предпринимал попытки решить задачу о назначениях размера 10*10 на машине SWAC. Но так как эта задача является задачей линейного программирования со 100 неотрицательными переменными и 20 ограничивающими равенствами, ему это не удалось. В 1953 году в мире просто не существовало машины, способной справиться с такими объемами вычислений». §3.5. Венгерский метод Куна-Манкреша В 1955 году Кун разработал новый комбинаторный подход решения задачи о назначениях. Он базируется на работе Егервари от 1931 года, а потому Кун выбрал для него название «Венгерский метод». В 1957 году метод был улучшен Манкрешом (Munkres). Несмотря на то, что в оригинале метод был сформулирован в терминах матриц, он представляет собой комбинаторный подход к решению задачи о назначениях. Оригинальный алгоритм имеет сложность работы O(N^4). В одной из статей Форда и Фалкерсона от 1957 года, в примечании было приведено следующее интересное сравнение: «Для решения задачи об оптимальных назначениях размера 20*20, при использовании симплекс-метода, требовалось около часа вычислений на компьютере. Новый подход Куна позволяет решить эту задачу всего за 30 минут вручную». В 1970 году Эдмондс и Карп улучшили алгоритм, что позволило достичь времени работы O(N^3). С этих пор задачу о назначениях можно было фактически считать решенной. Глава 4. Дальнейшие исследования в теории потоков §4.1. Потоки минимальной стоимости Аналогично тому, как задача о паросочетании была обобщена на случай ребер с различными весами (задача о назначениях), задача о максимальном потоке может быть обобщена как задача о максимальном потоке минимальной стоимости. Для решения этой задачи также справедлив метод Форда и Фалкерсона, за исключением того, что дополняющий путь нужно выбрать кратчайшим относительно стоимостей ребер сети. Для этой цели можно использовать классический алгоритм Форда-Беллмана нахождения кратчайшего пути. Это позволит достичь оценки времени работы алгоритма для максимального потока минимальной стоимости O(E V^3). Джонсон (Johnson) разработал метод потенциалов, обобщающий классический алгоритм Дейкстры нахождения кратчайшего пути на случай графов с отрицательными ребрами, что позволило улучшить время работы до O(E V^2). Однако, существуют более эффективные с практической точки зрения алгоритмы решения задачи. Идея состоит в последовательном приближении («алгоритм масштабирования») исходной сети. Соответствующий алгоритм был изложен в 1987-1989 годах Гольдберг (Goldberg) и Тарьян (Tarjan) опубликовали целую серию статей по этой тематике. Другой алгоритм в 1988 году представил Орлин (Orlin) в статье «Быстрый сильно-полиномиальный алгоритм нахождения максимального потока минимальной стоимости». §4.2. Динамические потоки. Задача транспортировки Интерес к транспортировке возник в области потоков в сетях в течение 1940-х и 50-х годов. Было опубликовано множество работ в этой области, однако все они содержали одно интересное упущение. Несмотря на естественную связь между потоками в сетях и задачами транспортировки, большинство исследований в области теории потоков игнорировали самый главный вопрос, который задает любой ребенок, сидящий на заднем сиденье автомобиля: «Мы уже приехали?». Родители, вынужденные постоянно выслушивать этот вопрос, несомненно, подумают о времени, прежде чем думать о том, куда и как ехать далее. Форд и Фалкерсон были хорошо осведомлены о важности времени в транспортировке, и они учли его в их модели сети. Они обобщили стандартное определение сети путем добавления в него транзитных времен между вершинами, получив тем самым динамическую сеть. Каждое ребро yz в динамической сети моделирует трубопровод из вершины y в вершину z. Пропускная способность ребра yz соответствует площади сечения труб, тем самым ограничивая количество потока, которое может быть передано за единицу времени. Транзитные времена соответствуют длине трубопровода; они определяют, сколько времени требуется потоку на прохождения из вершины y в вершину z вдоль ребра yz. Динамический поток перемещается с течением времени в динамической сети. Он является расширением традиционных потоков; отображением пар (ребро, время) в величину потока, а не отображением ребер как это было ранее. Со времен Форда и Фалкерсона исследования в области динамических потоков направлены как на теоретические исследования математических моделей, так и на практические и алгоритмические аспекты их реализации. В то же время было уделено недостаточно внимания алгоритмической теории. В частности, очень немного было известно о вычислительной сложности задач о динамических потоках. В диссертации Хоупа (Hoppe, 1995) акцент был сделан именно на разработке теоретически эффективных алгоритмов. Эта работа устранила разрыв между изучением потоков в традиционных и динамических сетях. §4.3. Универсально-максимальные динамические потоки Форд и Фалкерсон рассматривали простейшую потоковую задачу в динамической сети: задачу о максимальном динамическом потоке. Входом для данной задачи является временной интервал T и динамическая сеть с одним источником и одним стоком; решением является допустимый динамический поток, который пересылает наибольшее возможное количество потока из истока в сток за время T. Форд и Фалкерсон обнаружили оригинальный полиномиальный алгоритм для данной задачи. Гэйл, Уилкинсон и Миниека рассматривали вариант задачи о максимальном динамическом потоке, в котором сток должен был получить как можно больше потока на каждом промежуточном шаге до T и включительно. Вдобавок к этому поток должен покидать источник как можно позднее. (Факт существования такого потока нетривиален и был установлен Гэйлом). Позже Уилкинсон и Миниека независимо получили псевдополиномиальный алгоритм нахождения такого потока. Первый полиномиальный алгоритм нахождения значения универсально-максимального динамического потока для любого ребра для каждого отдельного момента времени (т.е. временной разрез полного решения) был предложен Хоупом. Он также предложил первый полиномиальный алгоритм, который приближает универсально-максимальный динамический поток с коэффициентом 1 + eps для любого eps > 0. (Алгоритм работает полиномиальное относительно 1/eps время). §4.4. Наибыстрейшие потоки Другой вариант задачи о максимальном динамическом потоке это задача о наибыстрейшем потоке, в которой нам задана величина потока v и требуется найти допустимый динамический поток, который доставит v единиц потока из источника в сток за наименьшее возможное время. Задача о наибыстрейшем потоке может быть сведена к задаче о максимальном динамическом потоке с помощью двоичного поиска. Баркард (Burkard) и др. изучали эту задачу и описали более эффективную технику ее решения. Задача эвакуации является обобщением задачи о наибыстрейшем потоке на случай нескольких источников. Для каждого из них нам задан вектор снабжения и требуется найти допустимый динамический поток, который доставляет требуемое количество потока из каждого источника в сток за наименьшее возможное время. В традиционной сети без времен транзита, задача эвакуации тривиально сводится к задаче о максимальном потоке с одним источником (путем добавления "суперисточника"). Однако, в динамическом случае, задача является гораздо более сложной, чем задача о наибыстрейшем потоке. В то же время она полезнее: задача эвакуации была изначально сформулирована в практической модели эвакуации из зданий. Хоуп (Hoppe) в своей диссертации (1995) представил первый (сильно) полиномиальный алгоритм для задачи о наибыстрейших перевозках - обобщении задачи эвакуации, где в дополнение к нескольким источникам разрешены несколько стоков. Алгоритм Хоупа также для целочисленных входных данных гарантирует целочисленное решение. В 2005 году в работе «Наибыстрейшие потоки с несколькими источниками» Рауфа (Rauf) алгоритм Хоупа был обобщен на случай сетей с несколькими источниками. §4.5. Планирование сетей Несмотря на то, что задача эвакуации и задача о наибыстрейшей перевозке мотивированы необходимостью планирования действий в случае бедствий и непредвиденных ситуаций, они имеют приложения и в других областях. Рассмотрим компьютерную сеть; каждая машина имеет свою очередь на вычисление задач единичного размера. Задача может быть либо вычислена на машине локально, либо послана по сети для удаленного вычисления. Каждое соединение в сети можно охарактеризовать пропускной способностью и временем транзита. Требуется распланировать выполнение задач таким образом, чтобы последняя из них была вычислена как можно раньше. Эта задача легко сводится к задаче о наибыстрейших перевозках, применяя наш алгоритм решения которой мы получим первый полиномиальный алгоритм решения задаче о планировании вычислительных сетей для задач единичного размера, но только в некоторых очень специальных случаях. Физзано (Fizzano) и Штейн (Stein) рассматривали кольцевые сети с единичными пропускными способностями и транзитными временами. Хоуп предложил алгоритм, работающий в сети общего вида, с произвольными пропускными способностями и временами транзита. Заключение Исследования потоков в сетях развивались одновременно с теорией линейного программирования (и теорией оптимизации в более общем случае). Так как потоки в сетях представляют собой специальный вид линейных программ, они могут быть решены как линейные программы. Более того, для сетей с целочисленными пропускными способностями гарантировано наличие целочисленного решения. Доказательство этого факта в 1955 году позволило получить первый алгоритм точного решения потоковых задач в сетях небольшого размера. Однако, структура потоковых задач ведет к гораздо более эффективным решениям (как с теоретической, так и с практической точек зрения), чем решение линейных программ. И тот подход получил наибольшее внимание со стороны исследователей с тех пор как Форд и Фалкерсон выбрали его в своем фундаментальном труде по потокам в сетях. В течении последующих четырех десятилетий одной из основных задач для сообщества исследователей в области компьютерных наук и исследования операций стало повышение эффективности алгоритмов для потоков в сетях. Решенной эту задачу можно считать в 1997 году, с появлением алгоритма Рао - Гольдберга. С тех пор основные усилия исследователей направлены на изучение динамических потоков – обобщения обычных («статических») потоков, учитывающего время. Исследования в теории потоков были прежде всего мотивированы военными нуждами - благодаря связи между максимальными потоками и минимальными разрезами. Решение задачи о минимальном разрезе позволяло построить эффективный план бомбардировок системы транспортного сообщения противника. Помимо этого с практической точки зрения была крайне важна задача об эвакуации, на случай бомбардировок или чрезвычайных происшествий. «Мирным» применением теории потоков являются всевозможные задачи связанные с транспортировкой грузов. В более простой модели ответ на этот вопрос дает задача о назначениях – обобщение задачи о максимальном паросочетании. Более сложные модели опираются на теорию динамических потоков, и здесь есть еще много задач для дальнейших исследований. Библиография
|
Похожие:
 | Программа по формированию навыков безопасного поведения на дорогах... Авторский коллектив: В. Г. Антонов, д э н., проф., О. Н. Громова д э н., проф., Г. Р. Латфуллин, д э н., проф., А. В. Райченко, д... | | Реферат по методике преподавания математики Научный Решение уравнений содержащих переменную под знаком модуля |
| Реферат по истории науки на тему: «Периодизация истории математики... Методические указания для подготовки к экзамену кандидатского минимума по истории и философии науки | | Программа по формированию навыков безопасного поведения на дорогах... Проф. В. М. Гаврилов, проф. В. А. Голиченков, проф. Л. П. Корзун, проф. А. М. Рубцов, проф. Е. С. Лобакова, доц., к б н |
| Реферат сдается в приемную комиссию вместе с необходимыми для поступления... К вступительному испытанию по специальности поступающий готовит научный реферат. Научный реферат по специальности должен носить исследовательский... |  | Тематика научных рефератов для поступающих в аспирантуру по направлению... К вступительному испытанию по специальности поступающий готовит научный реферат. Научный реферат по специальности должен носить исследовательский... |
| Рабочая программа по истории 8 класс Программа предназначена для изучения курса истории России XIX века на базовом уровне в его традиционном варианте в объеме 40 ч (2... | | Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы... ... |
| Рабочая программа учебной дисциплины Российского государственного медицинского университета (академик ран и рамн, проф. В. С. Савельев, проф. Ю. А. Нестеренко, проф.... | | Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П |
| Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П | | Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П |
| Имитационно-подражательные танцы эвенков Работа учащейся моши «Токкинская... Реферат должен быть написан по истории науки, в соответствии со специальностью, по которой обучается аспирант или соискатель (история... | | А. А. Арефьева Научный Среди основных видов можно выделить: научный туризм; туры истории природы; приключенческий туризм; путешествия в природные заповедники... |
| Программа дисциплины История экономических учений для специальности... «Экономическая теория» экономическая методологии и истории Председатель проф. О. И. Ананьин Зав кафедрой проф. О. И. Ананьин | | Программа дисциплины История экономических учений для специальности... «Экономическая теория» экономическая методологии и истории Председатель проф. О. И. Ананьин Зав кафедрой проф. О. И. Ананьин |
