Варшавский В. И., Поспелов Д. А
Вид материала | Документы |
СодержаниеN нуждающихся в квартирах, и имеется т |
- Герберт Александер Саймон Исследователи ии: Лотфи Заде Исследователи ии: А. А ляпунов,, 9.34kb.
- «Как привлечь средства государственных институтов развития» Варшавский Владислав Римович, 48.54kb.
- Аннотация к научно-образовательному материалу, 114.81kb.
- 141. Поспелов В. И., Стальнов В. С. Содружественная аккомодация глаз при дисбинокулярной, 167.36kb.
- Тезисы докладов участников III международного конгресса «Россия и Польша: память империй, 1372.37kb.
- Д. А. Поспелов, Г. С. Осипов, 487.33kb.
- Варшавский А. С. Следы на дне, 1828.32kb.
- Рабочая программа учебной дисциплины Для направления 080100. 62 «Экономика» (программа, 562.39kb.
- Диспут с Пирром: прп. Максим Исповедник и христологические споры VII столетия / Отв, 73.89kb.
- Программа дисциплины: Имитационные модели для направления Прикладная математика и информатика, 120.53kb.
Цирк, наверное, самое древнее в мире искусство. Во всяком случае, одно из древнейших. И за тысячелетия своего существования цирк, конечно, изменился. Но со времен появления в нем круглой арены диаметр ее во всех цирках мира стандартен. Все цирковые номера рассчитаны на его величину, изме-
132
нение ее может привести к трагическому исходу опасного номера (а какие номера в цирке не опасны?). Поэтому возникло острое противоречие между размером арены и стремлением сделать помещение цирка более вместительным. Но если арена не может быть увеличена, то как увеличить размер зрительного зала? Сидящим вдали от арены мало удастся увидеть, и уж тем более они не смогут испытать того «эффекта присутствия», которым так славится цирк.
Выход из этого положения был найден в том, что вместо одной арены в современных цирках их стало несколько. Теперь цирковые номера могли идти в параллель, а при необходимости последовательно дублироваться на различных аренах. Увеличилась «пропускная способность» цирка. Зритель получил возможность за один вечер увидеть куда больше, чем в старом цирке. Исчезла необходимость длительных перерывов между номерами, связанных с подготовкой арены и артистов.
Но возникла новая задача. Как планировать номера на имеющихся аренах? В хорошо отработанной программе, когда время на подготовку каждого номера и исполнение его известно с большой точностью, эта проблема стоит не столь остро. Но в сборных программах-ревю, особенно с участием иностранных артистов, трудно заранее точно предсказать ту последовательность номеров на каждой из арен, которая позволит провести всю программу в минимальное время.
Эта задача — пример известного класса задач о составлении оптимальных расписаний обслуживания при наличии времени, требуемого для переналадки оборудования. Классической моделью этой задачи является задача о расписании обработки сложных деталей на станках, требующих при переходе от выполнения одной операции к другой некоторого времени для переналадки. Мы просто, как часто делается в нашей книге, привели пример такого содержания, чтобы возбудить у читателя рой нужных нам ассоциаций.
А на деле мы в дальнейшем рассмотрим куда более сложную и серьезную модель обслуживания, чем та, которой пользуется режиссер цирковой программы. Но метод, который мы обсудим, вполне пригоден и для решения задачи об использовании нескольких
133
арен цирка. И если среди читателей нашей книги неожиданно найдется деятель циркового искусства, любящий читать научно-популярную литературу, то он может смело применять тот метод, который мы укажем.
Среди систем вычислительных машин, решающих различные хозяйственные, информационные или научные задачи, можно выделить группу систем с постоянным набором программ, хранящихся в их памяти. Такие системы предназначены для решения конечного набора задач N1, N2, ... , Nk. Число машин, входящих в систему, равно l, и имеет место неравенство l>k. Обозначим программы для решения тех или иных задач через M1, M2, .... Mk; с их помощью решаются нужные потребителям задачи. Заявки на выполнение программ поступают на вход системы в случайном порядке, и система не знает априори никаких характеристик этого потока.
Каждая машина системы может быть настроена на выполнение некоторой определенной программы Mi (i = 1, 2, ..., k). Это означает, что в оперативной памяти машины хранится сама программа для решения задачи Ni и необходимые для этого исходные данные. Подобно арене, приготовленной для выступления определенной группы артистов, такая вычислительная машина подготовлена для выполнения вполне определенной программы. Настройку системы машин будем производить децентрализованно. Для этого придадим каждой ЭВМ автомат, имеющий k состоянии. Пусть pij есть вероятность смены состояния с номером i на состояние с номером j (перенастройка ЭВМ с программы Мi на программу Мj). Как всегда Сумма (pij)=l. Если автомат Am (т — номер ЭВМ в системе и т=1,2,..,l) настроен на выполнение программы Mi и свободен, а на вход системы поступает заявка на ее выполнение, то Am берет эту заявку на обслуживание и получает сигнал поощрения. Автомат Am есть автомат с переменной структурой, о котором мы рассказывали в гл. 2. Поэтому, получив сигнал поощрения, он увеличивает вероятность рii и пропорционально уменьшает остальные вероятности pij для i не равное j. Если автомат при поступлении требования на решение задачи Ni был настроен на нее, но уже выполняет другое, ранее
134
поступившее требование на решение тон же задачи, то он также получает сигнал поощрения и меняет вероятности переходов, как и автомат, принимающий к исполнению вновь поступившую заявку.
Пусть автомат Am настроен на выполнение программы Mi и свободен, а вновь пришедшая заявка требует выполнения программы mj при j i; тогда поощрение и наказание Am зависят от той ситуации, которая сложилась в данный момент в вычислительной системе. Если среди свободных автоматов имеются такие, которые настроены на М,, то они берут заявку на обслуживание, а на вход Am никакого сигнала не поступает. Он продолжает ждать «свою законную» заявку. Если же таких автоматов в системе нет, то они отказываются от обслуживания, а все свободные автоматы (в том числе и Am), получают сигнал наказания. Этот сигнал заставляет Am уменьшить значение рii и увеличить пропорционально все остальные значения рij при i не равном j.
Что может дать такая модель настройки? Нетрудно видеть, что вычислительные машины системы с помощью настраиваемых автоматов будут выбирать из входного потока требований на обслуживание прежде всего те, которые чаще всего в этом потоке встречаются. Вспомнив о парикмахерской, мы можем сказать, что мастера всегда готовы обслужить клиентов, регулярно появляющихся в парикмахерской, а случайный приезжий, как правило, получит у них отказ со ссылкой на то, что часть мастеров заняты, а остальные ждут своих клиентов, которые «вот-вот должны подойти».
Для управления бытового обслуживания населения, которому подчиняется эта парикмахерская, дело обстоит не слишком хорошо. Мастера простаивают, а клиенты получают отказ. Для тех, кто проектировал вычислительную систему, ситуация аналогична. Простои ЭВМ не приносят ничего, кроме убытка. Штраф же, которым облагаются простаивающие ЭВМ, берется, в конце концов, из того же кармана.
Из этого положения можно найти, например, следующий выход. Пусть сначала к потоку требований на обслуживание адаптируется только одна ЭВМ. Когда она начнет работать с полной загрузкой, оставшийся поток требований можно использовать для обучения следующей ЭВМ и т. д. На долю
135
какой-то ЭВМ останется «тощий поток», содержащий лишь редко встречающиеся заявки. И специально для этой ЭВМ можно сделать буферную память, в которой редкие заявки будут ждать своей очереди на обслуживание (небольшой очереди, так как эти заявки поступают нечасто), а не будут получать обидный отказ. В парикмахерской роль такой особой ЭВМ может выполнять молодой мастер-практикант, к которому образуется очередь из случайных для данной парикмахерской клиентов. Читатели, посещающие модные парикмахерские салоны в крупных городах, конечно, видели реализацию этой процедуры на практике.
Разницу в предложенных двух способах адаптации автоматов можно проиллюстрировать на конкретном примере, полученном путем моделирования на вычислительной машине. Будем оценивать качество функционирования системы отношением Н=L*/Lt, где L*—число выполненных заявок за некоторый фиксированный интервал времени, a Lt — число всех поступивших за это время заявок. Пусть вычислительная система состоит из двух ЭВМ, настроенных на выполнение одной из четырех программ M1, М2, М3 и M4 соответственно автоматами А1 и А2. На вход системы обслуживания поступает поток требований на выполнение указанных программ. Характеристики этого потока, неизвестные для A1 и A2 в описываемом эксперименте, были заданы следующими вероятностями появления заявки определенного типа: P1=0,15, P2=0,30, Рз=0,45, Р4=0,10. До обучения системы Н=0,5. После обучения по первому способу Н=0,54. Таким образом, первый способ обучения оказывается не слишком эффективным. Если же второй автомат обучается на потоке, остающемся после отбора из него заявок первым автоматом, который так адаптировался, что он настраивается на выполнение только одной программы, то при втором способе обучения Н=0,57 после обучения первого автомата, а после обучения автомата А2. значение Н стало равно 0,63. Если же второй автомат заявок не теряет, то при определенном периоде наблюдения Н= 0,85.
Рассмотренная нами задача о распределении ЭВМ вычислительной системы по заявкам на обслуживание, поступающим случайным и заранее неиз-
136
вестным образом, является прообразом многих технических задач, возникающих при управлении сложными системами. Управление коммутацией каналов на узле связи, включение насосов в большой водопроводной сети, работ сортировочной горки на железной дороге и многое другое может быть организовано по принципу, который был изложен в трех последних параграфах.
§ 4.5. Задача о жилищной комиссии и родственные ей задачи
До сих пор, говоря о децентрализованном управлении и коллективном поведении, мы имели ввиду поведение, целью которого является удовлетворение тем или иными критериям пользы. Однако очень часто при организации совокупного поведения целью системы является достижение согласованного поведения объектов, образующих систему. Организуя поведение системы, мы должны уметь обеспечить возможность для ее составных частей договориться между собой.
В предыдущей главе мы уже рассматривали возможные варианты договоров. Такими договорами, или соглашениями, были процедура общей кассы и правила случайного парного взаимодействия. С другой стороны, указанные соглашения сами по себе могут являться целью поведения, направленного на ее достижение. Поведение, направленное па достижение подобных целей, образует в некотором смысле более высокий, чем рассмотренные ранее, уровень управления. Децентрализация здесь означает, что соглашения не навязываются свыше, а порождаются взаимодействием объектов. Формулировка правил такого взаимодействия есть задача следующего уровня иерархии управления.
Если считать, что бога нет, то на самом верхнем уровне иерархии, порождающем правила поведения для более низкого уровня, эти правила должны быть весьма просты и не могут порождаться никаким другим механизмом, кроме случайного перебора. Пусть ограниченного, направленного, но перебора.
Задача о достижении договоренности обычно усложняется противоречивостью интересов договаривающихся сторон. Если два человека любят друг друга, то достижение договоренности о вступлении
137
в брак обычно не связано с существенными трудностями. Но попытка достичь соглашения о раздела имущества при разводе подчас оказывается нереальной без вмешательства суда. Централизованное решение задачи через суд снижает размер получаемого каждым имущества на величину судебных издержек.
Рассмотрим несколько ситуаций, в которых достижение соглашения связано с преодолением противоречивых интересов, и обсудим возможные процедуры взаимодействия, обеспечивающие достижение такого соглашения.
Очень часто принятие тех или иных решений достигается путем голосования. Сначала отбирается некоторое количество, обычно существенно ограниченное, альтернативных соглашений или решений. Затем проводится голосование и в соответствии с соглашением, достигнутым на более высоком уровне иерархии, отбирается решение, получившее большинство голосов. Таким образом функционируют многочисленные советы, комиссии, парламенты и международные организации. Функции голосования формируются и в некоторых технических системах, например в системах повышенной надежности. Однако использование механизма голосования не всегда приводит к желаемым результатам, а при некоторых соглашениях о процедуре голосования, принятие решения оказывается невозможным. Вспомните, например, о праве вето в Совете Безопасности.
Представьте себе Технический совет крупной самолетостроительной фирмы. В этот совет входят специалисты самого различного профиля — специалисты по прочности и электронике, специалисты по двигателям и аэродинамике, специалисты по системам пожаротушения и дизайнеры. Если в таком совете решения принимаются голосованием, то для подавляющего большинства членов совета многие из рассматриваемых вопросов весьма далеки от области их профессиональных интересов. В таком случае любое решение принимается непрофессиональным большинством.
Можно ли в этой ситуации улучшить качество принимаемых решений? Можно. За счет введения очень простого правила участия в голосовании. Каждый член совета в течение, например, года может голосовать ограниченное число раз. Тогда в каждом
138
голосовании будут принимать участие только заинтересованные в результате голосования члены совета.
Компетентность принимаемых решений в этом случае возрастает. Для каждого члена совета возникнет необходимость решать две задачи: принимать или не принимать участие в голосовании и, если принимать, то как голосовать. Приведенный пример интересен еще и тем, что он иллюстрирует ситуацию, в которой ограничение па ресурс, используемый в системе (число участии в голосовании), улучшает качество ее функционирования.
Выше мы же заметили, что процедура голосования не всегда обеспечивает принятие решения. Решение может оказаться невозможным, если для его принятия требуется 2/3 голосов или если решение должно быть принято абсолютным большинством, а число возможных решений превышает два. Известно несколько процедур, устраняющих такие тупиковые ситуации. Голосование проводится в несколько туров. Если в очередном туре не удалось выработать решение, то может быть снижено число решений, участвующих в следующем туре, или отброшены решения, получившие наименьшее число голосов, или, как это имеет место на президентских выборах во Франции, изменено соглашение о принятии решения, и в последнем туре оно принимается относительным большинством. Однако при таком механизме все вынуждены согласиться с принятым решением, но большинство голосовавших с ним не согласно. С другой стороны, наличие права вето, казалось бы, полностью зачеркивает возможность эффективного применения процедуры голосования для принятия решений.
Попытаемся все-таки подумать, каким же образом можно добиваться принятия решений при наличии права вето и явно противоречивых интересах участвующих в голосовании. Для этого обратимся к сформулированной М. Л. Цетлиным «Задаче о жилищной комиссии». В лекции, прочитанной им на заседании секции Физиологического общества в Москве 23 февраля 1965 г., он говорил: «...в нескольких словах я хочу пояснить, в чем состоит трудность распределения жилплощади и какое отношение имеет она к автоматам. Имеется сколько-то квартир, вообще говоря, не очень много, гораздо меньше, чем число нуждающихся. Если бы их было много, то
139
никакой проблемы, никакой жилищной комиссии не было бы, ей просто нечего было бы делать. Все квартиры мы будем считать одинаковыми, скажем, двухкомнатными. Если будут разные квартиры, то будет просто несколько разных задач: как распределить двухкомнатные квартиры, как распределить однокомнатные квартиры и т. д.
Имеется N нуждающихся в квартирах, и имеется т членов комиссии, т не очень большое. Давайте теперь представим себе, как фактически работает комиссия. Каждый человек берет в руки список нуждающихся и смотрит, кто из них нуждается больше всех, кто следующий и т. д., т. е. каждый составляет некоторую очередь из нуждающихся. Вот, например, первый из них пишет так (я буду людей обозначать буквами, если можно):
a1,a2,a3,a4, ... , an
а где-то он еще проведет черту, скажем, после a3 (квартиры кончились). Заметьте, что, составляя список, он будет очень тщательно выбирать тех, кто попадет левее черты. Так же поступит второй член комиссии, третий и т. д. Эти свои мнения они друг другу сообщат. Например, можно считать, что они выпишут их на доске. Ну и дальше, говоря формально, останется только разводить руками. Ничего здесь решить голосованием нельзя и вот почему. Потому, что у нас квартир меньше, чем нуждающихся, и, как правило, эти списки не будут ни у кого совпадать. Но если я составил список и один из моих людей не попал, то я за такое решение голосовать отказываюсь. Поэтому я буду голосовать только за свой список. До тех пор, пока я не буду уверен, что мне удастся провести своих людей, я голосовать «за» не буду. А если буду, то зря меня выбирали в жилищную комиссию. Смотрите, что будет получаться. На доске написаны мнения всех членов комиссии. Если ока-жется, что у большинства эти мнения совпадают, тогда можно решить вопрос голосованием. Давайте разберемся, вероятно ли это? Нет, совершенно невероятно потому, что на самом деле имеется N! разных мнений, где N — число нуждающихся, и вероятность того, что мнения совпадут очень невелика. Поэтому первое, что увидят члены жилищной комиссии: прийти к общему мнению невозможно. Кстати,
140
во всякой разумно устроенной жилищной комиссии решение не принимается голосованием: начинают голосовать лишь тогда, когда есть уверенность, что это решение единогласно. Ясно, почему это делается. Если я остаюсь при своем особом мнении и меня не сумели бы убедить, что решение правильно, то жилищная комиссия заседала бы все это время напрасно. Я пойду в местком, и разбирательство начнется сначала. Как правило, решение жилищной комиссии должен утверждать местком, и если кто-нибудь из членов комиссии обоснованно возражает, то местком ничего не утвердит, а пошлет жилищную комиссию утрясать между собой мнения. Значит, решать при помощи голосования все-таки нельзя. Может быть, здесь стоит сказать, когда можно решать голосованием. Если мы, здесь собравшиеся, будем выбирать председателя из трех возможных кандидатов, то мы вполне можем решить такую задачу голосованием, потому что возможных мнений здесь гораздо меньше, чем число собравшихся, и только в таких случаях и можно решать голосованием. В нашем случае решать голосованием нельзя. Значит, члены комиссии должны прийти к какому-то разумному компромиссу, договариваясь между собой без голосования. Как они могут между собой договариваться? Прежде всего, никому не возбраняется изменять свои мнения. Во-вторых, и мы всегда об этом всерьез думаем (хотя, я думаю, это не очень верно), мы можем пытаться друг друга уговаривать. На самом деле, по любому вопросу, вероятно, здравого человека можно в чем-то как-то убедить... Оказывается, что эта задача может быть сформулирована в терминах игр автоматов...»
М. Л. Цейтлин хорошо представлял себе описанную ситуацию, так как, кроме того, что он был замечательным ученым, в течение многих лет он был членом жилищной комиссии Института прикладной математики АН СССР.
Рассмотрим ситуацию с несколько менее жесткими, чем в жилищной комиссии, противоречиями в интересах. Рассмотрим конкурсную комиссию, отбирающую научные работы для премирования на конкурсе. Если конкурс проводится в научном учреждении достаточно широкого научного профиля, то представители отделов, как правило, убеждены, что
141
работа, выполненная в их отделе, которую они хорошо понимают, лучше, чем работы, выполненные в других отделах, которые они понимают хуже или вообще не понимают и поэтому считают чушью. Заключительная стадия работы такой комиссии несколько напоминает соревнования по фигурному катанию — каждый член комиссии упорядочивает все выступления (работы) и сумма занятых мест является окончательной оценкой каждого выступления. При этом членов комиссии могут ожидать неожиданные сюрпризы, когда с результатами голосования не согласен никто. Рассмотрим конкретный пример.
Пусть в некотором учреждении на конкурс подали работы семь человек: Иванов, Петров, Сидоров, Кошкин, Мышкин, Собакин и Лошадкин, представляющие четыре отдела. В комиссию входят представители этих отделов и председатель комиссии от дирекции. Лошадкин—сотрудник в институте сравнительно новый и еще не увяз в сложной структуре взаимоотношений.
В результате обсуждения члены комиссии следующим образом упорядочили кандидатов на три объявленные премии:
-
1. Иванов
1.
Собакин
1.
Иванов
,
Собакнн
I.
Иванов
2. Петров
2.
Иванов
2.
Мышкин
2.
Сидоров
2.
Кошкин
3. Сидоров
3.
Мышкин
3.
Кошкин
3.
Иванов
3.
Петров
4. Лошадкин
4.
Лошадкин
4.
Лошадкин
4.
Лошадкин
4.
Лошадкин
5. Кошкин
6. Мышкин
5. 6.
Кошкин Сидоров
5. 6.
Сидоров Петров
5. 6.
Петров Мышкин
5. 6.
Сидоров Собакин
7. Собакин
7.
Петров
7.
Собакин
7.
Кошкин
7.
Мышкин
На доске были выписаны следующие голосования:
-
Фамилия
Сумма мест
Результат
Число голосов за призовое место
Иванов
8
1-я премия
5
Петров
23
6-е место
2
Сидоров
Кошкин
21
22
3-я премия 4—5-е место
2 2
Мышкин
24
7-е место
2
Собакин
22
4—5-е место
2
Лошадкин
20
2-я премия
0
Лошадкин, которого ни один из членов комиссии не считал достойным премии, получил вторую премию. В то же время Собакин, которого два члена комиссии считали достойным первой премии, поделил с Кошкиным четвертое и пятое места. Результаты отклоняются комиссией по крайней мере тремя голосами
142
против двух, и председатель предлагает повторить работу, произнося при этом слова об объективности и ответственности. Подумаем, какие мотивы могут возникнуть у членов комиссии при новом упорядочивании.
Первый член комиссии доволен результатами, однако, полагая, что Иванову ничего не грозит, он может подкрепить позиции Сидорова и Петрова, немного повысив их оценку и понизив оценку у их -конкурентов.
Тем же путем второй член комиссии может попытаться подкрепить позиции Собакина и Мышкина. Аналогично действуют и остальные члены комиссии, борясь за своих кандидатов на премии. Списки второго тура выглядят следующим образом:
-
1. Петров
1.
Собакин
I
мышкин
1.
Собакнн
1.
Кошкин
2. Сидоров
2.
Мышкин
2.
Иванов
2.
Сидоров
2.
Петров
3. Иванов
3.
Иванов
3.
Кошкин
3.
Иванов
3.
Иванов
4. Мышкин
4.
Петров
4.
Петров
4.
Мышкин
4.
Мышкин
5. Кошкин
5.
Кошкин
5.
Лошадкин
5.
Петров
5.
Лошадкин
6. Лошадкин
6.
Лошадкин
6.
Сидоров
6.
Лошадкин
6.
Собакин
7. Собакин
7.
Сидоров
7.
Собакнн
7.
Кошкин
7.
Сидоров
Результаты снова были выписаны на доске:
-
Фамилия
Сумма
мест
Результат
Число голосов за призовое место
Иванов
14
1-я премия
5
Петров
16
3-я премия
2
Сидоров
24
6-е место
2
Кошкин
21
4-е место
2
Мышкин
15
2-я премия
2
Собакин
22
5-е место
2
Лошадкин
28
7-е место
0
Первый член комиссии удовлетворен результатами голосования, тем более, что он при следующем голосовании может только испортить жизнь Мышкину, но никак не может помочь Сидорову занять призовое место. Второй член комиссии может, конечно, повысить сумму мест Петрова до 19, но это никак не поможет Собакину. Аналогично третий член комиссии не может помочь Кошкину за счет Петрова, а пятый член комиссии не может помочь тому же Кошкину за счет Мышкина. Менее всех удовлетворен результатами четвертый член комиссии — только один из его фаворитов получил премию, но и он не в состоянии изменить результаты. Более
143
того, «темная лошадка» Лошадкин лишился своего случайного преимущества.
Полученное в результате второго тура решение устойчиво в том смысле, что никому в одиночку не удается изменить общее упорядочение, не ухудшив при этом собственный результат. Здесь просматривается очевидная аналогия с ситуацией равновесия по Нэшу.
С другой стороны, могут быть образованы коалиции среди членов комиссии, которые окажутся в состоянии изменить распределение. Существуют способы ограничения возможности образования коалиций, например признание сговора между членами комиссии аморальным.
Лет 10 тому назад, на ученом совете Ленинградского Отделения Центрального Экономико-Математического института АН СССР, при подведении итогов конкурса научных работ молодых ученых нами была испробована такая многошаговая процедура оценки. Уже третий тур привел к перемене только восьмого и девятого места, и по общему мнению членов совета оценка результатов конкурса была справедливой.
Справедливость при этом понимается как разумный компромисс между собственным представлением о системе предпочтений и противоречащей ему системой предпочтений у остальных членов комиссии. Существенна устойчивость этого компромисса. Аналогичные процедуры можно предложить и для жилищной комиссии.