Во время Второй мировой войны британская армия столкнулась с необходимостью оптимизировать принятие стратегических решений, чтобы повысить действенность операций. Было разработано большое количество аналитических инструментов для выявления наилучшего способа координации военных действий.
Эта практическая дисциплина получила название исследование операций. Она позволила усовершенствовать британскую систему радаров дальнего обнаружения и помогла Соединенному Королевству лучше управлять людскими и материальными ресурсами. Во время войны сотни британцев участвовали в исследовании операций. В дальнейшем для оптимизации процессов в торгово-промышленной деятельности были применены новые идеи. Исследование операций включает в себя определение целевого показателя, который подлежит оптимизации, то есть максимизации или минимизации. Эта дисциплина позволяет максимизировать такие целевые показатели, как урожай, прибыль или производительность, и минимизировать убытки, риск или стоимость.
Например, исследование операций используется авиакомпаниями для оптимизации графиков полетов. Точные корректировки в планировании распределения трудовых ресурсов и оборудования могут сэкономить миллионы долларов. Еще один пример касается нефтеперерабатывающих заводов, где определение оптимальных пропорций сырья в смеси может рассматриваться как задача исследования операций.
Задачи линейной оптимизации
Задачи, где целевой показатель и ограничения можно смоделировать с использованием линейных уравнений[55], называются задачами линейной оптимизации. Давайте посмотрим, как решаются эти задачи.
Умная меблировка В вашем офисе не хватает каталожных шкафов. Шкаф X стоит 10 долларов, занимает 6 квадратных футов и содержит 8 кубических футов папок. Шкаф Y стоит 20 долларов, занимает 8 квадратных футов и содержит 12 кубических футов папок. У вас есть 140 долларов, и вы можете использовать под шкафы до 72 квадратных футов площади офиса. Какие шкафы следует приобрести, чтобы максимизировать емкость хранения?
Прежде всего определим переменные нашей задачи. Мы хотим найти количество шкафов каждого типа, которые следует приобрести, поэтому:
• x — количество шкафов модели X;
• y — количество шкафов модели Y.
Мы хотим максимизировать емкость хранения. Дадим емкости хранения имя z и смоделируем это значение как функцию от x и y:
• z = 8x + 12y.
Теперь выберем значения x и y, которые дадут максимальное значение z. При этом мы должны соблюсти ограничение по бюджету (то есть уложиться в 140 долларов) и по площади (она должна быть меньше 72 квадратных футов). Смоделируем эти ограничения:
• 10x + 20y ≤ 140 (ограничение по бюджету);
• 6x + 8y ≤ 72 (ограничение по площади);
• x ≥ 0, y ≥ 0 (нельзя купить отрицательное количество шкафов).
Как бы вы решили эту задачу? Покупка максимального количества шкафов с наилучшим соотношением хранение/площадь не является правильным решением, потому что пространство под установку шкафов ограниченно. Можно пойти по пути полного перебора: написать программу, вычисляющую z для всех возможных x и y, и получить пару, дающую оптимальное z. Это решение годится для простых задач, но оно невыполнимо при большом количестве переменных.
Оказывается, что решать задачи линейной оптимизации вроде этой можно и без программирования. Нужно просто использовать правильный инструмент для работы: симплекс-метод. Он очень эффективно справляется с задачами линейной оптимизации. Симплекс-метод помогает целым отраслям решать сложные проблемы, начиная с 1960-х годов. Когда перед вами встанет такая задача, не изобретайте колесо, просто возьмите готовый симплексный решатель.
Симплексные решатели требуют указать функцию для максимизации (или минимизации) и уравнения, моделирующие ограничения. Решатель сделает все остальное. В данной задаче максимальное значение z достигается при x = 8 и y = 3.
Рис. 5.6. Значения x и y, удовлетворяющие ограничениям задачи
Симплекс-метод отыскивает оптимальное значение в пространстве приемлемых решений. Чтобы понять механику его работы, представим все возможные значения x и y на двумерной плоскости (рис. 5.6). Ограничения по бюджету и площади представлены на графике линиями.
Обратите внимание, что пространство всех возможных решений является замкнутой областью на графике. Доказано, что оптимальным решением линейной задачи должна быть угловая точка замкнутой области — та, где пересекаются линии, представляющие ограничения. Симплекс проверяет угловые точки и вычисляет, которая из них оптимизирует z. Отнюдь не просто визуализировать этот процесс в задачах линейной оптимизации, имеющих более двух переменных, но математический принцип везде работает одинаково.
Задачи о максимальном потоке в Сети
Многие задачи, касающиеся сетей и потоков, можно сформулировать с точки зрения линейных уравнений и, следовательно, решить при помощи симплекс-метода. Например, во время холодной войны армия США вычисляла маршруты пополнения материально-технических запасов, которые Советский Союз мог использовать в Восточной Европе (рис. 5.7).
Рис. 5.7. Рассекреченный военный отчет 1955 г., показывающий пропускную способность советской сети железных дорог
Сеть снабжения Сеть железных дорог представлена линиями, которые соединяют города. Каждая имеет максимальную пропускную способность — самый большой ежедневный поток грузов. Какой объем можно перевезти из заданного производящего города в заданный потребляющий город?
Чтобы смоделировать задачу с линейными уравнениями, каждой железной дороге нужно назначить переменную, представляющую объем грузов, который она сможет перевезти. Ограничения следующие: ни одна железная дорога не может перевезти больше своей пропускной способности; входящий поток грузов должен быть эквивалентен исходящему во всех населенных пунктах, кроме производящего и потребляющего городов. Затем нужно подобрать такие значения для переменных, которые позволят доставить в получающий город максимум грузов.
Мы не будем подробно расписывать, как отобразить эту задачу в линейной форме. Наша цель здесь состоит только в том, чтобы донести мысль, что многие задачи оптимизации с привлечением графов, стоимости и потоков можно легко решить существующими реализациями симплекс-метода. В Сети есть вся необходимая документация. Смотрите в оба и не изобретайте колеса.
Подведем итоги
Мы показали несколько хорошо известных алгоритмов и методов решения самых разнообразных задач. Первым делом, приступая к решению новой задачи, всегда старайтесь найти готовый алгоритм или метод.
Существует большое количество важных алгоритмов, которые мы не смогли включить в эту главу. Например, имеются поисковые алгоритмы, более продвинутые, чем алгоритм Дейкстры (такие как, A*[56]), алгоритмы, оценивающие подобие двух слов (расстояние редактирования Левенштейна), алгоритмы машинного обучения и многие другие…
Полезные материалы
• Комен Т., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы. Построение и анализ. — М.: «Вильямс», 2016.
• Алгоритмы (Algorithms, Sedgewick, см. https://code.energy/sedgewick).
• Простая модель линейного программирования (Simple Linear Programming Model, Katie Pease, см. https://code.energy/katie).
Глава 6. Базы данных
Хотя я известен прежде всего своими работами в области баз данных, мои фундаментальные умения лежат в области архитектуры: это анализ технических требований и построение простых, но изящных решений.
Управлять колоссальными объемами данных в компьютерных системах очень сложно, но часто жизненно необходимо. Биологи хранят и получают последовательности ДНК и связанные с ними структуры белка. Facebook управляет контентом, созданным миллиардами людей. Amazon отслеживает свои продажи, запасы товаров и логистику.
Как хранить все эти большие, постоянно изменяющиеся массивы данных на дисках? Как дать разным агентам возможность одновременно получать, редактировать и добавлять данные? Вместо того чтобы самостоятельно решать эти задачи, мы используем систему управления базами данных (СУБД) — специальный компонент программного обеспечения для управления базами данных. СУБД организует и хранит информацию, она обеспечивает возможность доступа и изменения этой информации. Прочитав главу 6, вы научитесь:
понимать реляционную модель большинства баз данных;
использовать гибкость нереляционных баз данных;
координировать работу компьютеров и распределять между ними ваши данные;
лучше соотносить информацию с картами при помощи географических баз данных;
обмениваться данными с различными системами, используя прием сериализации данных.
Реляционные базы данных распространены шире, но нереляционные нередко оказываются проще и эффективнее. Базы данных очень разнообразны, и сделать выбор между ними бывает непросто. В этой главе сделан общий обзор различных типов современных СУБД.