В исследовании операций проблема перчаток [ 1] (также известная как проблема презерватива [2] ) представляет собой задачу оптимизации, используемую в качестве примера того, что самые дешевые капитальные затраты часто приводят к резкому увеличению времени эксплуатации, но самое короткое время эксплуатации не обязательно должно обеспечиваться самыми дорогими капитальными затратами. [3]
M врачей должны осмотреть каждого из N пациентов, надев перчатки , чтобы избежать заражения. Каждую перчатку можно использовать любое количество раз, но одна и та же сторона перчатки не может быть использована более чем одним человеком. Перчатки можно использовать повторно любое количество раз, и одновременно можно использовать более одной перчатки.
При наличии M врачей и N пациентов минимальное количество перчаток G ( M , N ), необходимое всем врачам для осмотра всех пациентов, определяется по формуле:
Наивным подходом было бы оценить количество перчаток просто как G ( M , N ) = MN . Но это число можно значительно сократить, используя тот факт, что каждая перчатка имеет две стороны, и нет необходимости использовать обе стороны одновременно.
Лучшее решение можно найти, назначив каждому человеку свою собственную перчатку, которая будет использоваться в течение всей операции. Каждое парное соприкосновение затем защищается двойным слоем. Обратите внимание, что внешняя поверхность перчаток врача соприкасается только с внутренней поверхностью перчаток пациента. Это дает ответ M + N перчаток, что значительно ниже MN .
Продолжительность выполнения при этой схеме равна K · max( M , N ), где K — продолжительность одного парного столкновения. Обратите внимание, что это точно такой же продолжительность выполнения, если бы использовались перчатки MN. Очевидно, что в этом случае увеличение капитальных затрат не привело к сокращению времени операции.
Число G ( M , N ) может быть уточнено далее, допуская асимметрию в начальном распределении перчаток. Лучшая схема дается следующим образом:
В этой схеме используется (1 · N ) + (( M − 1 − 1) · 1) + (1 · 0) = M + N − 2 перчаток. Это число не может быть уменьшено дальше.
Тогда время выполнения определяется по формуле:
Продолжительность: K · (2 N + max( M − 2, N )).
Очевидно, что минимальный G ( M , N ) значительно увеличивает продолжительность изготовления, иногда в 3 раза. Обратите внимание, что выигрыш в количестве перчаток составляет всего 2 единицы.
Одно или другое решение может быть предпочтительным в зависимости от относительной стоимости перчатки, оцененной по сравнению с более длительным временем работы. Теоретически промежуточное решение с ( M + N − 1) также должно встречаться как возможное решение, но для этого требуются такие узкие окна по M , N и параметрам стоимости, чтобы быть оптимальными, что его часто игнорируют.
Из формулировки задачи не следует, что применяется принцип заражения, то есть если внутренняя часть одной перчатки была затронута внешней частью другой, которая ранее касалась какого-то человека, то эта внутренняя часть также считается затронутой этим человеком.
Кроме того, медицинские перчатки являются двусторонними, поэтому существует лучшее решение, которое заключается в использовании
перчатки, где менее многочисленная группа оснащена перчаткой каждая, более многочисленная в парах. Первые из каждой пары используют чистый интерфейс, вторые переворачивают перчатку. [ оригинальное исследование? ]
