Недавно узнал одну красивую и, на мой взгляд, уникальную историю, спешу поделиться. Эта история о том, что модель, придуманная для нужд сугубо прикладных, оказалась глубже, чем кажется с первого взгляда, и в некоторый момент обогатила математику занятным результатом. Который можно взять и использовать где-нибудь еще. А уникальность истории в том, что это не про какую-нибудь физику с зеркальной симметрией, где все очень увлекательно, но малопонятно. Тут будет короткий рассказ, доступный людям с базовым знанием линала: про экономику и многогранники.
Рассмотрим систему линейных уравнений Ax=b с вещественными коэффициентами, где число уравнений g меньше чем число неизвестных f. Решение такой системы - аффинное подпространство V в R^g. Давайте посмотрим на множество P всех решений, у которых все координаты неотрицательны (пишут x≥0). То есть P - это пересечение V с неотрицательным конусом в R^g. Будем предполагать, что это множество непустое, чтобы не делать каждый раз об этом оговорку. Множество P - это какой-то выпуклый полиэдр, может быть, ограниченный, а может и нет.
Определение. Система Ax=b и соответствующий полиэдр решений называется моделью Леонтьева с замещением, если любой столбец матрицы A содержит не более одного положительного элемента, и, кроме того, b≥0.
Поймем, откуда такое берется. Допустим, что у нас есть g товаров - они же ресурсы, они же goods. И f фабрик - они же производства. Каждая фабрика умеет за единицу времени, рабочий цикл, преобразовать какой-то набор ресурсов, в определенных количествах, в новый ресурс, в каком-то количестве. Или просто потребить какой-то набор ресурсов и нихрена не произвести. Не очень понятно, зачем такое может быть нужно, - но нам не жалко, пусть будет. Таким образом, рабочий цикл каждой фабрики характеризуется вектор-столбцом (a[1,j],a[2,j],...,a[g,j])^t, где a[i,j] - количество i-го ресурса, произведенного фабрикой. Видно, что все эти числа, кроме, быть может, одного, неположительны: фабрика же их тратит, а не производит. Составим из этих столбцов матрицу A.
Теперь должно быть понятно, что решить систему Ax=b с неотрицательными x, - это означает найти, сколько должна работать каждая фабрика, чтобы по итогу вся наша экономика произвела заданный вектор-столбец b ресурсов. Мы хотим (ну наверное), чтобы был профицит, поэтому условие b≥0 тоже кажется довольно естественным.
Окей, вот вам модель, можете ее использовать например в разработке экономических игрушек, по типу Зельеварения. Хотя так с нуля придумать "правила размена ресурсов", чтобы хоть одно решение было, - это уже не вполне очевидно. Интуитивно понятно, что производиться должно примерно больше, чем потребляться, поэтому положительный элемент в столбце должен мажорировать сумму модулей отрицательных - ну в среднем по палате, по крайней мере. История, которая написана ниже, она в каком-то смысле про то, что это "усреднение по столбцам" не так много качественно различных комбинаций может давать.
Модель придумал Василий Леонтьев (нобелевский лауреат по экономике, между прочим) в книге
W.W.Leontief, Structure of the American Economy, 1919-1939. An Empirical Application of Equilibrium Analysis, 1951.
Книгу не читал, про что там - не знаю. Но как я понял по всяким статьям, изначально в модели предполагалось, что каждый товар можно производить только одним способом, - грубо говоря, только на одной фабрике, - поэтому в матрице A все положительные элементы в столбцах появлялись на попарно разных позициях. Вот модель Леонтьева с замещением (Leontief substitution model) - это как раз без этого условия. Слово "замещение" в названии - оно про то, что какой-нибудь сахар, например, можно производить разными способами из разного сырья на разных фабриках.
Что дальше с моделью Леонтьева делать - это уже вопрос практического интереса. Например, можно попытаться среди всех решений найти такое, которое минимизирует какие-нибудь косты, - то есть погонять на полиэдре решений P симплекс-метод. Или можно прокачать модель, чтобы она включала время: смотреть, чего происходит с производством раз в квартал, и где надо подкрутить, чтобы не было кризиса перепроизводства: получается какая-то динамика на полиэдре. И это только в экономике. А ведь можно примерно ту же модель допилить для оптимизации каких-нибудь информационных потоков, распараллеливания программ, бизнес-администрирования и бог знает чего еще.
Наверняка это всё уже делают, но сейчас не о том. Вернемся к математике.
Напомню для тех кто не знал, что полиэдр называется простым, если в любой его вершине сходится ровно столько гиперграней, какова его размерность. Будем говорить, что система Ax=b находится в общем положении, если ее полиэдр простой. Если брать коэффициенты уравнений наобум, всегда получается система в общем положении: потому что вероятность того, что более чем n случайных гиперплоскостей в R^n пересекаются в одной точке, равна нулю.
И-и-и, дамы и господа, барабанная дробь...
Теорема. Если система Леонтьева с замещением в общем положении, то
1) если полиэдр решений ограничен (= тотальная система Леонтьева), то он комбинаторно эквивалентен произведению симплексов
2) если полиэдр неограничен, то симплициальный комплекс, двойственный к полиэдру решений является полноразмерным подкомплексом в джойне границ симплексов, гомеоморфным диску.
Этот замечательный факт доказан в статье
L.J.Billera, J.S.Provan, Leontief Substitution Systems and Matroid Complexes, Mathematics of Operations Research 7:1 (1982),
хотя, чтобы извлечь именно такую формулировку из их статьи, требуется немного поскрипеть мозгами.
И когда это утверждение впервые видишь, то думаешь: да лааадно, быть такого не может. Щас производство в виде пятиугольника наладим. Не получается. Потом думаешь, ок, ну раз так, то должно как-то концептуально доказываться. Жахнуть двойственность Гейла: очень удачно, что столбцы матрицы A двойственны к нормалям многогранника, условие на столбцы что-то должно говорить о Гейл-двойственной конфигурации. Но вот нифига: двойственность Гейла позволяет доказать, что любой полиэдр можно реализовать матрицей А с не более одним положительным числом в каждом столбце. Цимес в правой части системы: неотрицательность b очень сильные дополнительные ограничения накладывает. Биллера-Прован по существу ссылаются на технический результат другой работы, и там какое-то злое вуду с двойственностью задач выпуклой оптимизации. Без хорошего знания линейного программирования и соответствующей интуиции не вкурить. Короче, мои отношения с этой теоремой сейчас на стадии депрессии: вроде вот же оно доказательство, и слова какие-то знакомые. Но целиком непонятно.
Такие дела. Чем теорема хороша для практики? Например, у произведения симплексов можно легко посчитать реберный диаметр, что дает оценку на сложность симплекс-метода. И эта оценка даже приятнее, чем в общей гипотезе Хирша: диаметр не просто ограничен чем-то линейным от числа вершин, но и даже чем-то линейным от размерности, фантастика. Произведение симплексов все же довольно тощий многогранник, не то что какие-нибудь пермутоэдры с фуллеренами.
Чем теорема хороша для теории? Я бы сказал, парой лемм, которые используются для доказательства. Рассмотрим симплициальный комплекс Леонтьева - симплициальный комплекс, двойственный к простому полиэдру решений для системы Леонтьева в общем положении.
Лемма 1. Тотальный комплекс Леонтьева (ограниченная ситуация) является матроидом (симплициальным комплексом независимых подмножеств матроида).
Тут можно вспомнить, что матроиды - это, вообще говоря, какие-то штуковины, гомотопные букетам сфер одной размерности. Но комплекс Леонтьева - это ведь симплициальная сфера если полиэдр ограниченный. То есть это псевдомногообразие. Ясно, что не абы какой матроид является псевдомногообразием.
Лемма 2. Если матроидный комплекс является псевдомногообразием, то он изоморфен джойну границ симплексов. Если матроидный комплекс является псевдомногообразием с границей, то он изоморфен джойну симплекса и границ симплексов.
Леммы довольно универсальные, одна из них внезапно в наших темных торических делах пригодилась. Другая, полагаю, тоже пригодится.
А еще можно задавать какие-то осмысленные вопросы. Например, насколько разнообразной может быть комбинаторика производства, если разрешить фабрикам производить одновременно не один товар, а, например, два? То есть ослабить условие на матрицу до двух положительных значений в столбце.
Надеюсь, заинтриговал.
Комментариев нет:
Отправить комментарий