Беседы об АСУ

В настоящее время круг проблем, которые исследует эта наука, существенно расширился (хотя те военные операции тоже остались), но название по привычке сохранилось. Многие ведущие ученые в этой области считают, что, несмотря на то, что данный термин недостаточно точно отражает суть дела, а порой даже вводит в заблуждение, к нему следует относиться с должным уважением. В США, впрочем, достаточно популярно и другое название — «наука управления».

История исследования операций началась в 1941 году, когда английский исследователь Ф. Хичкок формализовал одну из центральных задач, названную «транспортной задачей». Вообще надо заметить, что характерной особенностью данной науки является обилие специфических задач с не очень строгими названиями. Более того, формулируются эти задачи порой как полушутливая головоломка и не имеют прямого отношения ни к военным, ни к прочим операциям. Может даже создаться впечатление, что та или иная задача вообще не имеет прикладного значения. Вот, например, задача о ранце.

Солдат размышляет перед походом: «Обжился на постое, кое-каких вещичек накопил, а с собой все не возьмешь, ранец мал… Вот и решай, что оставить, что выкинуть…» Формально задача ставится так. Ранец имеет некоторую предельную «грузоподъемность». Каждая вещь характеризуется, во-первых, ценностью ее в глазах владельца, во-вторых, весом. Требуется определить набор вещей, общий вес которых не превышает «грузоподъемность» ранца, а суммарная ценность максимальна.

Задача эта, в общем, непростая. Житейское правило «берем самое дорогое» к оптимальному решению не приводит. Скажем, в ранце можно унести не более 100 единиц груза, а предметов всего пять, вес и ценность которых перечислены в таблице 6.

Табл. 6.

Тогда по житейскому правилу надо брать предметы № 1 и 2 с суммарной ценностью 130, а оптимальное решение, которое находится перебором, утверждает — надо брать вещи № 3, 4 и 5 с суммарной ценностью 140 и не превышающие предельную «грузоподъемность» ранца. Кстати, уже для такой простой задачи перебрать надо 32 варианта решения!

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

На рисунке изображена условная карта, содержащая четыре города. Расстояния между городами указаны в таблице 7. Попробуем составить маршрут коммивояжеру, учитывая, что его родной город носит № 1.

Табл. 7.

Простое житейское правило предлагает всегда направляться в город, который расположен ближе всего. По этому правилу надо сначала переместиться в город № 4, из № 4 в № 3, из № 3 в № 2, а потом вернуться в № 1. Суммарное расстояние 24 километра. Однако полный перебор всех возможных маршрутов показывает, что если сначала посетить город № 3, за ним № 2, потом № 4 и вернуться в № 1, то суммарное расстояние будет только 22 километра.

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

Задача о солдатском ранце возникла в связи с весьма серьезной прикладной проблемой. Известно, что транспортный корабль характеризуется некоторой грузоподъемностью, которую нельзя превысить. А каждый предмет (здесь имелись в виду танки, пушки и прочие «предметы» того же сорта) имеет ценность в свете предстоящих операций. Вот в связи с задачей о загрузке транспортных средств при планировании операций и появился ранец. Почему бы прямо не назвать вещи своими именами?

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

С проблемой, о чем же задача: о корабле, о самолете или стульях, — первым сталкивается ученый, который ее и формулирует. Естественно, что название и содержание задачи в большой степени зависит от его чувства юмора. А поскольку с юмором в среде ученых не бедно, то и появилось в науке об исследовании операций множество задач с «именами».