Дипломная работа на тему: Постановка задачи. Теория графов как математический аппарат для решения задач подобного типа

Введение

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Но такой избыток ресурсов бывает не всегда. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся "на глазок" (теперь, впрочем, зачастую тоже).

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

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

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

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: "оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения". И уже летом 1939 года была сдана в набор книга Л.В. Канторовича "Математические методы организации и планирования производства", в которой закладывались основания того, что ныне называется математической экономикой.

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

Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем - словом, стоит ли принимать такую книжку во внимание. Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого!

А самому Леониду Витальевичу - как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от "грехов" молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В. Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С. Немчиновым и В.В. Новожиловым) и Нобелевской премией в 1975 году.

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

В развитие динамического программирования большой вклад внес голландский ученый Эдсгер Вайб Дейкстра (1930-2002). Рассказывать об этом человеке можно очень долго и много. Только список его работ занимает "увесистый" десятимегабайтовый pdf-файл. Можно перечислять научные регалии, звания и степени, бесконечно повторять слова "неоценимый вклад" и "основоположник". Он являлся создателем принципа семафоров, одной из концептуальных основ синхронизации вычислительных процессов, а также одним из главных разработчиков языка ALGOL. Среди специалистов в области вычислительной математики широко известен алгоритм поиска кратчайшего пути, известный также как алгоритм Дейкстры. В 1972 году за свой вклад в развитие информационных технологий Дейкстра был удостоен премии Тьюринга, которую называют аналогом Нобелевской премии в области компьютеров.

Здесь сразу уместно будет привести несколько фрагментов из воспоминаний Дейкстры. Во-первых, алгоритм этот создавался не из простого любопытства, а для решения вполне конкретной задачи, а именно, - минимизации длины проводников на аналоге "материнской платы" нового разрабатываемого командой компьютера X1, так что лавровый венок создателя первой "утилиты всех времен и народов" класса CAD-CAE Дейкстре можно присваивать смело. А вот "во-вторых" лучше сказать словами самого Дейкстры: "На много лет и в широких кругах алгоритм поиска кратчайшего пути был основным источником моей славы, что мне всегда казалось странным - ведь он был создан даже без карандаша и бумаги, за чашкой кофе на солнечной террасе кафе в Амстердаме ...".

Оглавление

- Введение

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

- Теория графов как математический аппарат для решения задач подобного типа

- Основы теории графов

- Основные определения и теоремы

- Свойства связных графов

- Способы задания графов

- Нахождение кратчайшего пути в графе

- Волновой алгоритм

- Алгоритм Дейкстры ЗАКЛЮЧЕНИЕ

- Приложения

- Приложение 1. Программная реализация алгоритма Дейкстры

- Литература