![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
(no subject)
Dec. 25th, 2004 11:57 amEсть такой малоизвестный класс оптимизационных задач, задачи о холодильнике.
Впервые вопрос был поставлен еще Гилбертом в 1907 году, но только с появлением бытовых холодильников к его решению были привлечены широкие круги математиков. Литтлвуд в 1935 году сформулировал первую проблему из этого класса: имеется холодильник с набором из N продуктов, количеством Pn. Имеется список из К блюд, на каждое из них уходит некоторое количество исходных продуктов, описываемое N-мерным вектором (конечно, часть элементов - нулевые, т.е. не во всяком блюде присутствуют все ингредиенты). Задача состоит в том, чтобы максимально долго протянуть на имеющемся запасе.
После того, как была разработана теория линейного программирования, интерес к задаче возобновился. Джон фон Нейман и Данциг показали, что не всегда имеется хоть какое-нибудь решение. Канторович в 1949 году, после отмены карточек, сформулировал новую задачу: если продукты можно докупать, то какова оптимальная стратегия (два варианта - с ограничениями на покупки и без).
В годы, когда в США было экономическое процветание, появилась задача об опустошении холодильника. В ней оптимизировался уже другой функционал - нужно было либо за заданное время сожрать максимум из содержимого холодильника, либо за кратчайшее время опустошить его полностью. Важнейший результат, за который была присуждена премия Совета по мясо-молочной промышленности в 1960 году, состоял в том, что надо максимизировать покупку говядины.
Окончательно задача была решена с появлением быстродействующих ЭВМ третьего поколения. Численное решение прямым перебором оказалось настолько быстро сходящимся, что дальнейшие теоретические исследования утратили смысл. Однако и сейчас в Гарварде и Беркли решают так называемую "задачу о ворчестерширском соусе" - как максимально быстро истребить то, что практически невозможно есть.
Впервые вопрос был поставлен еще Гилбертом в 1907 году, но только с появлением бытовых холодильников к его решению были привлечены широкие круги математиков. Литтлвуд в 1935 году сформулировал первую проблему из этого класса: имеется холодильник с набором из N продуктов, количеством Pn. Имеется список из К блюд, на каждое из них уходит некоторое количество исходных продуктов, описываемое N-мерным вектором (конечно, часть элементов - нулевые, т.е. не во всяком блюде присутствуют все ингредиенты). Задача состоит в том, чтобы максимально долго протянуть на имеющемся запасе.
После того, как была разработана теория линейного программирования, интерес к задаче возобновился. Джон фон Нейман и Данциг показали, что не всегда имеется хоть какое-нибудь решение. Канторович в 1949 году, после отмены карточек, сформулировал новую задачу: если продукты можно докупать, то какова оптимальная стратегия (два варианта - с ограничениями на покупки и без).
В годы, когда в США было экономическое процветание, появилась задача об опустошении холодильника. В ней оптимизировался уже другой функционал - нужно было либо за заданное время сожрать максимум из содержимого холодильника, либо за кратчайшее время опустошить его полностью. Важнейший результат, за который была присуждена премия Совета по мясо-молочной промышленности в 1960 году, состоял в том, что надо максимизировать покупку говядины.
Окончательно задача была решена с появлением быстродействующих ЭВМ третьего поколения. Численное решение прямым перебором оказалось настолько быстро сходящимся, что дальнейшие теоретические исследования утратили смысл. Однако и сейчас в Гарварде и Беркли решают так называемую "задачу о ворчестерширском соусе" - как максимально быстро истребить то, что практически невозможно есть.
