Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

Тут можно читать онлайн Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов - бесплатно полную версию книги (целиком) без сокращений. Жанр: Математика, издательство «Де Агостини», год 2014. Здесь Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте лучшей интернет библиотеки ЛибКинг или прочесть краткое содержание (суть), предисловие и аннотацию. Так же сможете купить и скачать торрент в электронном формате fb2, найти и слушать аудиокнигу на русском языке или узнать сколько частей в серии и всего страниц в публикации. Читателям доступно смотреть обложку, картинки, описание и отзывы (комментарии) о произведении.
  • Название:
    Том 11. Карты метро и нейронные сети. Теория графов
  • Автор:
  • Жанр:
  • Издательство:
    «Де Агостини»
  • Год:
    2014
  • Город:
    Москва
  • ISBN:
    978-5-9774-0682-6
  • Рейтинг:
    3.8/5. Голосов: 101
  • Избранное:
    Добавить в избранное
  • Отзывы:
  • Ваша оценка:
    • 80
    • 1
    • 2
    • 3
    • 4
    • 5

Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов краткое содержание

Том 11. Карты метро и нейронные сети. Теория графов - описание и краткое содержание, автор Клауди Альсина, читайте бесплатно онлайн на сайте электронной библиотеки LibKing.Ru

Наш мир полон не только букв и цифр, но и самых разных изображений. Это картины, фотографии, произведения искусства, многочисленные схемы… Вспомните схему вашей линии метро или автобусного маршрута — это всего лишь линия с точками, рядом с которыми подписаны названия остановок. Подобные схемы из точек и линий называются графами. Именно о них вы узнаете, прочитав эту книгу.

Том 11. Карты метро и нейронные сети. Теория графов - читать онлайн бесплатно полную версию (весь текст целиком)

Том 11. Карты метро и нейронные сети. Теория графов - читать книгу онлайн бесплатно, автор Клауди Альсина
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать
Пионер линейного программирования математик Джон фон Нейманобщается со - фото 119

Пионер линейного программирования математик Джон фон Нейманобщается со студентами Принстонского университета. 1947 год.

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

Рассмотрим компанию, которая производит два типа напитков А и В , в которых сочетаются два ингредиента а и Ь . Прибыль от продажи единицы напитка А составляет 6 евро, от единицы напитка В — 5 евро. В рассматриваемый период на складе компании находится 1000 литров а и 3000 литров Ь . При производстве напитка А нужно смешать 0,3 литра а и 0,5 литра Ь , при производстве В — 0,3 литра a и 0,7 литра Ь . Как получить максимальную прибыль?

* * *

ДЖОРДЖ ДАНЦИГ (1914–2005)

Этот блестящий математик, который много лет преподавал в Стэнфордском университете, считается отцом линейного программирования наряду с Леонидом Канторовичем. Данциг разработал симплекс-метод, который лег в основу практического применения линейного программирования. О Данциге рассказывают, что как-то раз он опоздал на занятие по статистике, которое вел Ежи Нейман, и подумал, что две задачи, написанные на доске, — это домашнее задание. Оно оказалось трудным, но Данцигу удалось решить его. Нейман был потрясен: 25-летний студент справился с задачами, которые считались нерешаемыми. Если бы Данциг знал это, то никогда не попробовал бы решить их.

* * *

Условия задачи сведены в следующую таблицу.

Алгоритм решения подобных задач в общем виде выглядит так 1 Какими ресурсами - фото 120

Алгоритм решения подобных задач в общем виде выглядит так:

1. Какими ресурсами мы располагаем?

2. Каков объем каждого ресурса?

3. Какие продукты нужно изготовить?

4. Сколько ресурсов требуется для изготовления каждого продукта?

5. Каковы неизвестные величины?

6. По какой формуле рассчитывается прибыль?

Обозначим за х объем выпуска напитка А , за у — объем выпуска напитка В , для изготовления которых нам потребуются ресурсы а и Ь . Формула расчета прибыли, которую нужно максимизировать, такова:

6 х + 5 у .

Однако на переменные х и у накладываются дополнительные условия, вызванные ограниченностью ресурсов:

x >= 0,

у >= 0,

0,5 x + 0,3 у =< 1000,

0,5 x + 0,7 у =< 3000.

Мы составили математическую модель задачи, и теперь необходимо найти максимальное значение выражения 6 х + 5 у для пары значений ( х, у ), которые будут удовлетворять четырем вышеперечисленным ограничениям. Построим область допустимых решений, которую образуют все точки ( х, у ) в декартовой системе координат, удовлетворяющие условиям задачи.

Графическое представление области допустимых решений имеющей форму - фото 121

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

Область допустимых решений имеет форму многоугольника. Именно в вершинах этого многоугольника расположены значения ( х, у ), обеспечивающие максимальную прибыль, которая рассчитывается по формуле 6 х + 5 у . Чтобы найти максимально возможный объем прибыли, нужно выполнить следующие действия.

1. Определить координаты вершин области допустимых решений.

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

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

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

* * *

РЕШЕНИЯ ЗАДАЧ

Цепь в прямоугольнике (стр. 106):

Цепь на квадратной сетке стр 107 Задача о четырех окружностях стр 110 - фото 122

Цепь на квадратной сетке (стр. 107):

Задача о четырех окружностях стр 110 Магическая гексаграмма стр 111 - фото 123

Задача о четырех окружностях (стр. 110):

Магическая гексаграмма стр 111 чтобы получить одно из возможных решений - фото 124

Магическая гексаграмма (стр. 111): чтобы получить одно из возможных решений, нужно расположить числа в рядах, сверху вниз, следующим образом: 10; 4, 7, 9, 6; 8, 5; 1, 11, 12, 2; 3.

* * *

Здесь снова появляется теория графов: эта задача может быть решена с помощью симплекс-метода, разработанного Джорджем Данцигом.

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

Плоский граф соответствующий области допустимых решений которая представляет - фото 125

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

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

Поиск быстрых алгоритмов для решения подобных задач всегда имел особую важность. Работы Кармаркара позволяют, например, найти оптимальные решения на 50—100 % быстрее, чем традиционный симплекс-метод.

Эпилог

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

Хорхе Вагенсберг

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

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

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать


Клауди Альсина читать все книги автора по порядку

Клауди Альсина - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки LibKing.




Том 11. Карты метро и нейронные сети. Теория графов отзывы


Отзывы читателей о книге Том 11. Карты метро и нейронные сети. Теория графов, автор: Клауди Альсина. Читайте комментарии и мнения людей о произведении.


Понравилась книга? Поделитесь впечатлениями - оставьте Ваш отзыв или расскажите друзьям

Напишите свой комментарий
x