Предыдущий пост Поделиться Следующий пост
Про планирование и вычислительную мощность, часть вторая
lex_kravetski

В первой части я написал про распространённое заблуждение, будто планирование невозможно, поскольку «всех компов не хватит на учёт товаров». Оказалось, домашнего компа в общем-то хватит даже на то, чтобы учесть все физические экземпляры товаров конечного потребления. Как водится, это не все поняли, поэтому оценку количества этих товаров начали ловко обращать в «невозможность планирования производства». Сообщаю: для планирования производства не нужен учёт каждого физического экземпляра. Планирование производство, оно про другое — про сумму физических экземпляров, а не про каждый отдельный.

Однако вопрос планирования производства всё равно для общей массы людей — что-то вроде метафизики тонких миров. Сам никто не считал, однако из спец-передачи «Приведения существуют» точно знает, как оно там в тонком мире всё обстоит. Правда, в случае с экономикой передача называется «Планирование невозможно». И в ней говорится, что оно невозможно, потому что невозможно совсем.

Редкие люди что-то считали сами. Или хотя бы спрашивали специалистов, как посчитать. Один из таких товарищ awas1952. Он в 1996-м году посчитал.

Должен отметить, что Вассерман мне, конечно, друг, но истина дороже. Вся математика в статье по ссылке — правильная. То есть, при постановке именно такой задачи и решении её именно таким методом получится так, как написано в статье. Однако из этого никак не следует, что плановая экономика в принципе невозможна на данном этапе и даже не следует, что она на данном этапе хуже рыночной. А всё потому, что решена не та задача не теми методами.

Вкратце, вот о чём в статье говорится. Есть у нас сколько-то там видов продукции. Производство одних видов завязано на другие виды. Нам надо посчитать, сколько и чего нам следует произвести в условиях ограниченности ресурсов. Для этого мы строим систему линейных уравнений, где описывается «взаимоотношение» каждого вида продукции с каждым другим. И эту систему нам надо решить для нахождения наших плановых значений.

Видов продукции, положим, у нас миллиард (Вассерман говорит о 20 миллионах, но жизнь же не стоит на месте). Это — 109. Если мы построим для решения системы уравнений матрицу, то она будет иметь 109 столбцов и 109 колонок. Искать решения будем методом Гаусса, который имеет сложность О(n3). Это означает, что для поиска решения нам понадобится порядка n3 операций, где n — размерность матрицы. В нашем случае операций, соответственно, будет 1027. Полагая скорость топовых современных процессоров равной 10 гГц, мы выясним, что для поиска решения нам понадобится 1027/1010 = 1017 секунд (понятно, что это значение — приблизительное, но нам сейчас нужен порядок величины). Год состоит из, приблизительно, 3*107 секунд. Значит, на решение задачи нам потребуется 3*109 лет. Распараллелив вычисления и подключив к решению миллион компьютеров, мы всё равно будем решать её 3000 лет, что нам никак не подходит.

Казалось бы, наглядно доказано, что плановая экономика невозможна. Однако нет, доказано лишь, что слишком долго искать точное решения общего случая миллиарда линейных уравнений методом Гаусса.

Да-да. Здесь рассматривается самый общий случай — матрица, в которой каждую ячейку может занимать какое угодно число. Но даже сам автор совершенно правильно замечает, что матрица у нас — не самая общая. Для производства солнечных очков не требуется пулемёт (ну, если к процессу не привлекается кровавая гэбня, конечно), поэтому в соответствующих ячейках будет стоять ноль. Можно сказать даже больше: почти во всех ячейках этой матрицы стоят нули, поскольку производство каждого продукта завязано, ну, в худшем случае, на тысячу других. Но никак не на весь миллиард. Таким образом, мы имеем сильно вырожденную матрицу — разреженную.

Как снова совершенно верно замечает автор, для такой матрицы поиск решения даже методом Гаусса уже имеет сложность O(n2,5), однако оценку по времени почему-то уже не даёт, полагая, что «всё равно очень долго». Но, друзья мои, сложность — степенная функция. В такой функции понижение степени может радикально всё изменить. Давайте всё-таки посчитаем.

(109)2,5 = 3*1022 операций

3*1022 / 1010 = 3*1012 секунд = 105 лет

С миллионом компьютеров это уже один месяц на решение. От трёх тысяч лет такой результат радикально отличается. Даже точное решение в лоб уже не выглядит нереальным. Ведь, повысив частоту процессора в десять раз, мы обойдёмся уже сотней тысяч компьютеров. Заделав девайс (который, к слову, уже есть и называется «видеокарта») для матричных операций, реализованных на уровне железа, мы и в тысячу раз скорость вычислений повысим. Тысяча компьютеров уже за месяц справится. Усовершенствуем алгоритм хотя бы до сложности O(n2,4)… В общем, вариантов масса. Но даже безо всяких усовершенствований ясно: задачу реально решить на современном уровне развития за вполне приемлемое время.

Но самый мега-бонус в том, что нам не обязательно решать эту задачу. Конечно, самое точное и общее решение — это приятно, тут без базара. Но наш мир не идеален: это решение — переуточнённое. Оно находится за пределами «шума» — неизбежных ошибок в процессе производства. Такая точность нам просто не нужна. Нам нужна ощутимо меньшая, на которую мы, тем не менее, будем ориентироваться с некоторым её превышением — для надёжности.

Что это значит? Положим, у нас есть метод прогноза энергопотребления района города. Этот прогноз, как проверила практика — весьма точный. При этом может возникнуть неожиданный выброс активности энергопотребителей, который поднимет энергопотребление на один процент по отношению к предсказанному. Если мы будем поставлять ровно столько, сколько прогнозировали, энергии на всех не хватит. Поэтому нам надо бы поставлять, скажем, на десять процентов больше — выброс на десять процентов ведь практически невероятен, чего нельзя сказать об однопроцентном. Итак, мы предсказали некую величину, но закладываемся в том числе и на то, что может быть в реальности незначительно превышена. Но и в этом случае мы потребности удовлетворим.

У того же Вассермана в статье написано вот что: «Рынок добивается избытка. По возможности во всём. Каждого товара должно быть больше, чем нужно». Всё правильно, но с чего бы ровно так же не делать и плану? При рынке ведь товары не возникают из ничего — их кто-то делает. А раз делает, то кто-то распорядился это делать. Плановая экономика тоже распорядится — нет проблем.

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

Нам не нужен учёт всего миллиарда товаров разом. Мы можем выделить из них однотипные и упростить исходную матрицу. Так, например, яблоки разных сортов для своего выращивания требуют примерно одного и того же оборудования, специалистов одного и того же профиля, примерно одинаковых трудозатрат. Этих сортов, положим для определённости, — сто штук. Мы можем в общем плане считать их просто яблоками, решить задачу оптимизации по яблокам, а потом, внутри решения для «обобщённых яблок» уже оптимизировать по сортам. Это не так точно, но точность — вполне достаточная. В среднем каждый продукт из миллиарда имеет, положим, сто сортов. То есть, наша матрица уменьшается с миллиарда строк до 10 миллионов. Ну и с колонками — аналогично.

(107)2,5 = 3*1017 операций. В тридцать тысяч раз меньше. Вместо миллиона компьютеров безо всяких усовершенствований нам достаточно сотни. И за месяц всё посчитаем.

Ещё, конечно, есть задача по оптимизации «детальных матриц» — их у нас 10 миллионов. Но их размерность существенно меньше.

Но и это ещё не всё. В «общей» матрицы даже после упрощения по сходным типам можно выделить независимые миноры (матрицы, более низких порядков) — ведь будут такие виды продуктов, которые в своём производстве вообще практически никак не пересекаются по своим связям с другими. Пусть таких миноров будет хотя бы десять. И мы сможем решать систему уже для десяти матриц с порядком примерно в миллион.

10*(106)2,5 = 3*1016 операций. Сложность упала ещё на порядок. Сто компьютеров будут решать эту задачу три дня. При незначительных (и уже существующих в реальности) усовершенствованиях — несколько часов.

При этом мы имеем почти точное решение задачи.

Самое интересное, нам и такого не надо, поскольку мы не можем мгновенно перестроить всё производство, а вынуждены делать ровно то же самое, что делается при капитализме — смещать производство в требуемую сторону, а не перестраивать его каждый раз с нуля.

План, таким образом, решает задачу не полного пересчёта производства, а поиска его оптимального смещения — ровно ту же задачу решает рынок. Однако при рынке, ввиду отсутствия полной информации каждый собственник вынужден решать данную задачу чисто эмпирически: пробовать и смотреть на результат. При плановой же экономике, располагая полной информацией, мы получаем возможность численного поиска правильного смещения — программной эмуляцией собственников, как это ни смешно звучит.

Действительно, представив поведение виртуального собственника в виде некоторого набора параметров, мы можем, например, сгенерировать популяцию «собственников» случайным образом, а потом искать при помощи генетического алгоритма того «собственника» (тот набор параметров), который в результате даст наиболее хорошо соответствующее плану смещение. Совокупность «собственников», обратно же, может выступать как единица популяции. И сгенерировав множество их совокупностей мы генетическим алгоритмом найдём ту совокупность, которая лучше всех справилась с планом. Радость от такого подхода в том, что мы не завязаны на некоторую детерминируемую сложность алгоритма, а можем сами подбирать количество итераций, соответствующую доступному нам времени.

Реальная задача, которую решает планирование, может быть сформулирована так: имеется текущее состояние производства, включающее в себя производственные мощности, человеческие и природные ресурсы, план работ. Надо найти новое состояние, относительно близкое к текущему, но лучше соответствующее спросу. Эта задача — задача принципиально иной сложности, нежели «планирование с нуля», рассмотренное в середине статьи.

С потерей точности, конечно — она от количества итераций зависит. Но нам же не надо получить самое правильное решение, нам достаточно более хорошего, чем при рынке — с чисто экспериментальным поиском (который, кстати, тоже можно организовать). И такое решение таки будет.

Комбинация этих методов не только делает планирование производства доступным уже прямо сегодня, но и делает его почти полностью автоматическим — всё, что не касается инноваций и человеческого фактора (взаимоотношений трудящихся, то бишь), можно рассчитать без участия человека. С гораздо более качественными, чем при рынке, результатами.


Кстати, интересный технологический вопрос

А нельзя ли подобные задачи решать методом Монте-Карло?

Re: Кстати, интересный технологический вопрос

Генетические алгоритмы быстрее нужную точность дают. А для реальной задачи — градиентный спуск.

Монте-Карло хорош в основном для процессов слабопонятной природы — на уровне «почти ничего непонятно».

вычисления - фигня и самое простое, нужны только программисты и компьютеры.

самое сложное - ввод *актуальных* данных и поддержание их актуальности на нужном уровне.

(Удалённый комментарий)
(Удалённый комментарий)
Одно слово - np-полнота. Если бы это были линейные уравнения то все могло бы получится в реальности придется решать задачи логистики - это сложные задачи на графах, с вероятностью 99% np-полнота. Я не говорю, что плановая экономика невозможна или плоха(с данными вычислениями это не имеет ничего общего) но решить задачу управления обществом информатике не под силу и еще очень долго так будет.

Лекс, а ты думаешь люди, которые простых слов не понимают, уразумеют всё через высшую математику?

Re: Ответ на вашу запись...

Эти — нет. А нормальные — да.

"Оказалось, домашнего компа в общем-то хватит даже на то, чтобы учесть все физические экземпляры товаров конечного потребления."... это даже не смешно...
Ну нельзя же так... вроде ИТ-спеца из себя пытаешься позиционировать... Зачем тогда вообще сервера? :)
вроде для энергетиков чего-то говоришь ваял? чего же они на домашних писюках не сидят? они-то вообще один товар всего учитывают...

а 1С для нормального предприятия зачем сервачка требует? а в банках наверное все идиоты сидят? у них тоже всего один товар учитывается, а они зачем-то миллионы баксов тратят... наверное ИТ-шники хотят много откатов и поэтому требуют железо, хотя оно и не требуется..

полная бредятина...

все в мире идиоты, один Лекс на коне... хрена там - писюк справится.. народ миллиарды тратит на учетные системы, а тут все просто...

> Зачем тогда вообще сервера? :)

Здесь речь идёт лишь об оценке сложность задачи, а не о практической реализации.

(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
1. Я не уверен, что решение системы линейных уравнений имеет коэффициент параллелизации 1
2. И, вообще, в решении системы линейных уравнений заложена масса интересных грабель. Могу дать ссылку...

(Удалённый комментарий)
а вообще вопрос - то не в этом...

вы уточните.. чего вы собираетесь считать? потребности? план производства? план добычи ресурсов? оптимизировать добычу ресурсов и производство, исходя из планов потребления? как решать задачу приоритетности производства того или иного товара в условиях недостатка ресурсов? и главным образом человеческих? как бороться с тем, что все хотят сидеть в чистом кабинете и в интернете, а не пахать на поле?

/*как бороться с тем, что все хотят сидеть в чистом кабинете и в интернете, а не пахать на поле?*/

Естественным отбором. Кто умный - в кабинет, кто глупый - в поле.

(Удалённый комментарий)
Два дня назад обсуждали подобную тему.. для начала можно не ставить такой глобальной задачи вообще.. сначала просто оптимизировать управление и привести данные к единому формату.. тогда вместо 50 чиновников будет один, который больше не "решатель", а скорее оператор.. и даже если что-то решает, то должен это обосновать..

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

Как это реестров избирателей нет? Когда приходишь голосовать - где галочку то ставишь, что в той толстой тетрадке по-твоему?

Но есть нюансы

Помимо планирования собственно производства необходимо ведь планировать распределение добычу исходных материалов, планировать их доставку от мест добычи до мест производства, а потом планировать доставку от мест производства к конечному потребителю.

Например добывают стекло для солнечных очков во Владивостоке, везут в Калининград для сборки, а потом обратно. Как-бы тут не появилось ещё одной np-задачи.

(Удалённый комментарий)
У математиков всегда так: из реальной задачи делаем модель, для модели доказываем теорему - а вот насколько ее результат применим к исходной задаче, это уже вопрос сложный.

Внедрить АСУ по всей стране - мегапроект.
Самое интересное, это переходной этап и внедрение.
Можно ли плановую систему вводить поэтапно, конвертируя капитализм в коммунизм?

Есть ещё один интересный момент - насколько система планирования будет устойчива к коррупции. Есть забавный рассказ - Драйер С. - Конец шпината.
Или взять те же самые спекуляции - за деньги или без них.

Вопросы интересные и правильные.

Насчёт поэтапности, то её, по-видимому, следует обеспечивать за счёт иерархического планирования. В принципе, госплан так и поступал, давая некоторые пункты годового плана в агрегированных показателях. Далее постепенно детализировать систему.

Насчёт коррупции это вопрос отдельный. Как эта проблема решается в рамках крупных корпораций? Определённым образом решается. Вообще большинство проблем, которые обычно называют в числе "могильщиков" плановой экономики, уже успешно разрешены в крупных современных корпорациях.

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

Строго говоря, сам по себе план не ограничивает конкуренцию. Например, перед составлением годового плана все заводы представляют свои новые наработки и они между собой начинают жёстко конкурировать за место в плане. Кто лучшее сделал — тот больший заказ и получит. Остальным придётся как-то выкручиваться. Но это теоретически.

Есть любопытная книга "Математическое моделирование в экологии: Историко-методологический анализ"(доступная online http://elementy.ru/lib/430230/430231) - полистайте хотя бы 5,6 главы. Смысл в том, что проблема не вычислительной мощности, а в отсутствии мат. моделей для предсказания. На небольших лабораторных популяциях жучков, уже оказывается невозможно предсказать колебания численности между поколениями. Более сложные модели среда-жертва-хищник (опять же в лабораториях под колпаком) дают погрешность до 0.5 - что делает их бесполезными.

Re: Ответ на вашу запись...

Само собой. Планирование экономики и матмодель жизни жучков — это же одно и то же.

Отлично.
Только Вы математизируете все сильно, на мой взгляд. Статью Вассермана не читал но осуждаю. Судя по тому, что Вы написали, бред полнейший.

Занудный вопрос по постановке

Хм... А не подменяет ли уважаемый Лекс нахождение
оптимального решения нахождением решения, удовлетворяющего
граничным условиям? Вроде, слово "оптимизация" в тексте
есть, а явной целевой функции нет.

Решение системы линейных уравнений да, находится методом Гаусса, но.
Решение может быть единственным (это бывает редко), может не существовать,
решений может быть много. Вопрос еще в том, как получить их все и выбрать лучшее.

Re: Занудный вопрос по постановке

Решение может быть единственным (это бывает редко)

Почему редко? Оно единственно почти всегда, кроме сугубо особых случаев.

может не существовать

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

(Удалённый комментарий)
А что самое интересное, нам необязательно искать точное решение системы уравнений. Можно обойтись приближённым решением (например, методом итераций) - требующим количество операций порядка n^2.


+1

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

Вообще на практике время решения такой задачи асимптотически зависит не от размера матрицы, а от числа ненулевых элементов в ней. А сколько будет ненулевых элементов можно прикинуть. Сколько различных продуктов используется в среднем при изготовлении нового продукта? Думаю, в среднем в районе 10-20. В середине 80-х для задачи с 120 000 ненулевых элементов в матрице поиск точного решения занимал несколько секунд ("Timber harvest problems", IBM 3090) (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.9137)

А с тех пор, как говорится, много воды утекло: http://www.springer.com/cda/content/document/cda_downloaddocument/9780387955728-c10.pdf?SGWID=0-0-45-101639-p2292776

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=176692&isnumber=4470

и т.д.

Вообще люто-бешено хочу вот эту статью: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=712960&isnumber=15442


?

Log in

No account? Create an account