Варшавский В. И., Поспелов Д. А

Вид материалаДокументы

Содержание


N нуждающихся в квартирах, и имеется т
Подобный материал:
1   ...   5   6   7   8   9   10   11   12   13
§ 4.4. Проблема нескольких арен

Цирк, наверное, самое древнее в мире искусство. Во всяком случае, одно из древнейших. И за тыся­челетия своего существования цирк, конечно, изме­нился. Но со времен появления в нем круглой арены диаметр ее во всех цирках мира стандартен. Все цирковые номера рассчитаны на его величину, изме-

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 тому назад, на ученом совете Ленинград­ского Отделения Центрального Экономико-Математи­ческого института АН СССР, при подведении итогов конкурса научных работ молодых ученых нами была испробована такая многошаговая процедура оценки. Уже третий тур привел к перемене только восьмого и девятого места, и по общему мнению членов совета оценка результатов конкурса была справедливой.

Справедливость при этом понимается как разум­ный компромисс между собственным представлением о системе предпочтений и противоречащей ему си­стемой предпочтений у остальных членов комиссии. Существенна устойчивость этого компромисса. Аналогичные процедуры можно предложить и для жилищной комиссии.