Кому нужна математика? Понятная книга о том, как устроен цифровой мир - [5]
Исследование операций начало развиваться относительно недавно, после Второй мировой войны. И далеко не сразу научные результаты нашли практическое применение. В 2002 году в специальном юбилейном выпуске в честь 50-летия журнала «Исследование операций» Чарльз Холт делится своими воспоминаниями о том, как он и его коллеги Франко Модильяни, Джон Муф и Герберт Симон разрабатывали и внедряли научные методы планирования производства:
Мы взяли интервью у менеджеров пятнадцати компаний. Поначалу менеджеры отрицали наличие каких-либо проблем. По крайней мере таких, с которыми коллеги-профессора могли хоть как-то помочь. Но когда мы расспрашивали более подробно, возникали картины наподобие телеги на разваливающихся колесах – системы, катящиеся без всякого контроля от одного кризиса к другому{1}.
В процессе работы все менеджеры постепенно переключились на систему «коллег-профессоров». Команда написала книгу «Планирование производства, инвентаря и трудовых ресурсов». Модильяни и Симон получили Нобелевские премии по экономике, а работы Муфа легли в основу исследований Роберта Лукаса, тоже впоследствии лауреата Нобелевской премии.
Методы исследования операций глубоко внедрились в современный бизнес. Никому не придет в голову планировать большое производство или составлять расписание самолетов вручную. Для этого есть подготовленные специалисты и стандартное коммерческое программное обеспечение. Даже самый элементарный подход в рамках исследования операций всегда превзойдет любое решение «на глазок». Исследование операций преподают не только на факультетах прикладной математики, но и в бизнес-школах.
В этой главе мы расскажем о задачах оптимизации, которые, в частности, возникают при планировании и составлении расписаний.
Проклятие размерности
Сложность задач оптимизации заключается в невообразимом множестве возможных решений. Чтобы продемонстрировать масштаб проблемы, давайте посмотрим на самый простой вариант расписания.
У нас есть один прибор, на котором нужно выполнить 25 заданий. Спрашивается: в каком порядке выгоднее всего это делать? «Выгода» может зависеть от срока выполнения, времени, проведенного в очереди, и других факторов.
Задача непростая, о ней написана не одна диссертация. Но, допустим, мы решили поступить наипростейшим образом. Берем самый мощный компьютер и пишем программу, которая считает прибыль и убытки для каждой возможной последовательности заданий. После этого выбираем наиболее выгодную последовательность.
Теоретически все правильно. Но прежде чем запустить программу, давайте посчитаем, сколько разных последовательностей ей придется перебрать.
На первое место можно поставить любое из 25 заданий. Для каждого из 25 вариантов для первого места у нас есть 24 варианта для второго места. Получается, что первые два места можно заполнить
25 × 24 = 600
способами. Продолжаем: 23 варианта для третьего места, 22 – для четвертого и так далее. Всего у нас получается
25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 15511210043330985984000000
способов.
Это число называется двадцать пять факториал и обозначается «25!». Насколько оно велико? Если взять современный процессор с тактовой частотой 2 ГГц (2 млрд операций в секунду), то для выполнения такого количества операций ему понадобится 245 млн лет! А на то, чтобы просчитать все варианты, с прибылью и убытками, да еще и перемещать информацию в памяти компьютера, – и того больше. А ведь задачка казалась совсем простой, всего один прибор, всего 25 заданий. Не сравнить с серьезным современным производством.
Такое явление называется проклятием размерности. Даже при скромном количестве вводных данных степень свободы в выборе решения колоссальна. Перебрать все варианты просто невозможно. Значит, понадобятся другие подходы, более умные и нетривиальные, и именно для этого нужна математика.
Для некоторых задач удается найти гарантированно лучший ответ относительно быстро. Но для целого разряда так называемых NP-трудных задач, как, например, упомянутая выше задача об упаковке, сложно придумать метод, который работал бы намного быстрее, чем тривиальный полный перебор всех вариантов. Удастся ли когда-нибудь? Это открытый вопрос, но большинство ученых считают, что нет, потому что таких методов просто не существует. Многие практические задачи NP-трудные. В этом случае математики стремятся к быстрым и «почти» оптимальным решениям. А на практике приходится мириться с тем, что ответ достаточно хороший, но не всегда самый выгодный из возможных.
Разных методик для разных задач придумано множество. Мы расскажем о линейном программировании. Это мощная и уже ставшая классической теория, которая невероятно успешно применяется на практике.
Линейное программирование
Как возникают задачи линейного программирования, мы объясним на еще одном простом примере.
Допустим, у нас есть два склада: на северном и на южном конце города. В офис поступили заказы от двух клиентов. Клиент А заказал 60 листов железа, а клиент Б – 40 листов. На южном складе у нас в наличии 70 листов железа, а на северном – 35, то есть общего запаса хватает. Но мы хотим свести расходы на доставку к минимуму. Цены доставки приведены в табл. 2.1.
Эта книга — уникальный путеводитель в мире высшего образования для абитуриентов и их родителей. Автор — математик и увлеченный, талантливый педагог — знает изнутри систему высшего образования в России и Голландии, имеет богатый опыт работы со студентами разных специальностей из разных стран. Нелли Литвак нашла понятную формулу «попадания в призвание» и предлагает семь правил, которые помогут любому старшекласснику сделать обоснованный индивидуальный выбор. Как понять, какая профессия подходит именно вам? Что необходимо знать о вузе и учебной программе и как извлечь максимальную пользу за предстоящие годы инвестиций в самого себя? Абитуриентам книга даст отправные точки для поиска и выбора специальности, а родителям подскажет, как избежать конфликтов с детьми и поддержать их в принятии одного из главных решений в жизни.
По статистике, голландские дети – самые счастливые в мире. Именно в этой стране живет и растит двух девочек автор книги Нелли Литвак. Будучи успешным профессионалом, она тем не менее одним из главных своих достижений считает хорошие отношения со старшей дочерью. А доверительные отношения в семье психологи рассматривают как отправную точку благоприятного становления личности. Наблюдая педагогические успехи и провалы родителей и учителей, семейный и школьный уклад нескольких поколений в России и в Голландии, сравнивая традиции образования и воспитания, Нелли Литвак решила систематизировать собственные методы и накопленный опыт и поделиться ими с другими.
В этой книге говорится об Исконной Вере и Стари у Южных Славян. Исследование, которое мы провели, не основывается на песнях, преданиях и обрядах, сохранившихся до сих пор, ни даже на письменных летописях. Главная особенность научного подхода, примененного в этой книге, это его опора на образные представления, которые у Южных Славян, совместно со многими другими народами, возникли со временем.
Это первая и, к сожалению, пока единственная книга в нашей философской литературе, специально посвященная обману – столь повсеместному явлению, пронизывающему все поры нашей личной и общественной жизни. Фундаментальная ценность правды понятна каждому. Но представьте себе, что произошло бы в жизни людей, в политике, экономике и т.п., если бы вдруг все люди перестали обманывать, говорили только правду? Автор ставил своей целью: рассмотреть и по возможности упорядочить чрезвычайно многообразные проявления обмана, осмыслить такие феномены как добродетельный обман, полу-правда, самообман, опираясь на философские, психологические, исторические материалы и произведения художественной литературы.
Книга представляет собой один из первых в отечественной научной литературе опытов междисциплинарного подхода к проблематике искусственного интеллекта. В ней рассматриваются философские, методологические, общетеоретические и социокультурные аспекты данной проблематики, обсуждаются актуальные задачи моделирования искусственного интеллекта в связи с рядом логических и математических вопросов и под углом соотношения искусственного интеллекта с естественным и современных разработок проблемы "сознание и мозг".
Никогда не уйдет в прошлое интерес к познанию происхождения и последующей эволюции уникального человеческого вида. От древесной обезьяны до человека разумного — дистанция огромного размера. В настоящем издании она заполняется известными и новейшими материалами по истории антропологических знаний о движущих силах и закономерностях развития семейства гоминид, адаптивном полиморфизме вида гомо сапиенса, его расовой структуре, перспективах развития.
Технологии захватывают мир, и грани между естественным и рукотворным становятся все тоньше. Возможно, через пару десятилетий мы сможем искать информацию в интернете, лишь подумав об этом, – и жить многие сотни лет, искусственно обновляя своё тело. А если так случится – то что будет с человечеством? Что, если технологии избавят нас от необходимости работать, от старения и болезней? Всемирно признанный футуролог Герд Леонгард размышляет, как изменится мир вокруг нас и мы сами. В основу этой книги легло множество фактов и исследований, с помощью которых автор предсказывает будущее человечества.
В монографии исследуются эволюция капиталистического отчуждения труда в течение последних ста лет, возникновение новых форм отчуждения, влияние растущего отчуждения на развитие образования, науки, культуры, личности. Исследование основывается на материалах философских, социологических и исторических работ.