Проблема с перчатками

В исследовании операций перчаток проблема ^[1] (также известная как проблема с презервативами ^[2]) — это задача оптимизации, используемая в качестве примера того, что самые дешевые капитальные затраты часто приводят к резкому увеличению времени эксплуатации, но самое короткое время работы не обязательно должно обеспечиваться самыми дорогими капитальными затратами. ^[3]

Постановка задачи

Каждый из M врачей должен осмотреть каждого из N пациентов, надев перчатки во избежание заражения. Каждую перчатку можно использовать любое количество раз, но одну и ту же сторону перчатки нельзя подвергать воздействию более чем одного человека. Перчатки можно использовать повторно любое количество раз, причем одновременно можно использовать более одной.

Учитывая M врачей и N пациентов, минимальное количество перчаток G ( M , N ), необходимое всем врачам для осмотра всех пациентов, определяется по формуле:

г ( М , 1) = М
г (1, Н ) = Н
Г ( М + 1, Н + 1) = М + Н

Подробности

Наивным подходом было бы оценить количество перчаток просто как G ( M , N ) = MN . Но это число можно значительно сократить, воспользовавшись тем, что каждая перчатка имеет две стороны, и нет необходимости использовать обе стороны одновременно.

Лучшее решение можно найти, выдав каждому человеку собственную перчатку, которую он будет использовать на протяжении всей операции. Каждая парная встреча тогда защищена двойным слоем. Обратите внимание, что внешняя поверхность перчаток врача соприкасается только с внутренней поверхностью перчаток пациента. Это дает ответ перчаток M + N , который значительно ниже, чем MN .

Продолжительность цикла по этой схеме равна K · max( M , N ), где K — продолжительность одной парной встречи. Обратите внимание, что это точно такой же срок службы, если бы использовались перчатки MN. Очевидно, что в этом случае увеличение капитальных затрат не привело к сокращению времени эксплуатации.

Число G ( M , N ) можно уточнить, допустив асимметрию в первоначальном распределении перчаток. Наилучшую схему дает:

Доктор №1 носит N перчаток, наложенных одна на другую. Он посещает N пациентов по очереди, оставляя после каждого крайнюю перчатку.
Врачи от № 2 до ( M − 1) носят по одной перчатке и следуют двухуровневому протоколу при каждом взаимодействии, как описано выше.
Доктор № M не носит ни одной своей, но посещает всех пациентов N , по очереди собирая их перчатки и постепенно превращая их в многослойную перчатку. Обратите внимание, что при первой встрече он использует только нетронутую внутреннюю часть перчатки Пациента № 1, так что она по-прежнему безопасна.

В этой схеме используются (1 · N ) + (( M - 1 - 1) · 1) + (1 · 0) = M + N - 2 перчатки. Дальнейшее сокращение этого числа невозможно.

Тогда продолжительность рабочего времени определяется следующим образом:

N последовательных взаимодействий для установки перчаток.
max( M − 2, N ) распараллеленные взаимодействия для промежуточного этапа.
N последовательных взаимодействий для сбора перчаток.

Продолжительность цикла: K · (2 N + max( M − 2, N )).

Видно, что минимум G ( M , N ) значительно увеличивает время изготовления, иногда в 3 раза. Заметим, что выигрыш в количестве перчаток составляет всего 2 единицы.

То или иное решение может быть предпочтительным в зависимости от относительной стоимости перчатки с учетом более длительного времени ее эксплуатации. Теоретически промежуточное решение с ( M + N − 1) также должно встречаться в качестве возможного решения, но для этого требуются такие узкие окна для M , N и параметров стоимости, чтобы быть оптимальными, что его часто игнорируют.

Другие факторы

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

Также медицинские перчатки являются двусторонними; поэтому существует лучшее решение, которое использует

\min \left(\lceil M/2\rceil +N,M+\lceil N/2\rceil \right)

перчатки, где менее многочисленная группа снабжена перчаткой каждая, более многочисленная - парами. Первые из каждой пары используют чистый интерфейс, вторые — наоборот. ^{[ оригинальное исследование? ]}

Ссылки

^ Вайсштейн, Эрик В. «Проблема с перчатками» . Математический мир .
^ Варди, И. Проблема презервативов. Ч. 10 баллов в разделе «Вычислительные развлечения в системе Mathematica» . Редвуд-Сити, Калифорния: Аддисон-Уэсли, стр. 203–222, 1991. ISBN 0-201-52989-0 .
^ Хайнал, А. ; Ловас, Л. (1978). «Алгоритм предотвращения распространения некоторых заболеваний с минимальными затратами». В Дж. К. Ленстре ; AHG Риннуй Кан ; П. ван Эмде Боас (ред.). Взаимодействие между информатикой и исследованием операций . Математический центр .

[1] Вайсштейн, Эрик В. «Проблема с перчатками» . Математический мир .

[2] Варди, И. Проблема презервативов. Ч. 10 баллов в разделе «Вычислительные развлечения в системе Mathematica» . Редвуд-Сити, Калифорния: Аддисон-Уэсли, стр. 203–222, 1991. ISBN 0-201-52989-0 .

[3] Хайнал, А. ; Ловас, Л. (1978). «Алгоритм предотвращения распространения некоторых заболеваний с минимальными затратами». В Дж. К. Ленстре ; AHG Риннуй Кан ; П. ван Эмде Боас (ред.). Взаимодействие между информатикой и исследованием операций . Математический центр .

[1]

[2]

[3]