Журнал «Компьютерра» №31 от 30 августа 2005 года

Линейное программирование (ЛП) - это задача оптимизации линейной функции при линейных же на нее ограничениях. В наиболее простой переформулировке она сводится к тому, разрешима ли данная система линейных неравенств. Эта кажущаяся абстрактной задача имеет огромное количество применений и возникает в самых разных оптимизационных приложениях. В клиентах у крупнейшего производителя софта для решения задач ЛП - французской компании - ходят такие индустриальные гиганты, как Siemens, IBM, Visa International, France Telecom, United Airlines и многие другие. Говорят, что когда-то советская государственная программа развития Госплана фактически сводилась к тому, чтобы закодировать всю экономику СССР в виде огромной задачи линейного программирования, а потом ее решить и получить оптимальный план[Об этом Л. В. Канторович говорил в своей Нобелевской лекции. Кстати, векторы, лежащие в ограниченном задачей многограннике, в русской терминологии до сих пор называют планами].

Хотя о пользе решения систем линейных неравенств размышлял еще Фурье, впервые о применениях ЛП заговорили во второй четверти XX века. Начавшиеся исследования сразу же привели к успеху: по всей видимости, независимо друг от друга американец Джордж Данциг (George Dantzig) и советский математик Леонид Витальевич Канторович пришли (для разных, но эквивалентных формулировок исходной задачи) фактически к одному и тому же результату. Этот результат называется сейчас симплекс-методом; суть его - в обходе вершин соответствующего задаче многогранника в поиске оптимума. Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач. Важность его столь велика и бесспорна, что после того, как работы Канторовича были опубликованы, его приоритет доказан, а сам математик начал активно пропагандировать применение оптимизационных задач на практике, Л. В. Канторович получил Нобелевскую премию - по экономике, разумеется.

Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян[Как я узнал во время подготовки статьи, 29 апреля 2005 года Леонид Генрихович, в последние годы работавший в США, скоропостижно скончался] (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.

Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, если не десятками, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний хоть и экспоненциален в худшем случае, однако на практике справляется с задачами ЛП многократно лучше. Все промышленные (да и кустарные) реализации решения ЛП основаны на симплекс-методе и его вариантах (которых - столь же экспоненциальных, сколь и их прародитель - уже накопилось довольно много).

Кстати, симплекс-метод для решения ЛП тоже отнюдь не стоит на месте, и производительность софта прирастает не только благодаря закону Мура. Один из основателей компании ILOG Роберт Биксби (Robert E. Bixby) рассказывал, что как-то раз, забавы ради, он взял ILOG 1.0 (выпущенный в середине восьмидесятых) и установил (видимо, перекомпилировал) его на современном компьютере. Разница между ILOG 1.0 и последней версией нынешнего ILOG оказалась видна невооруженным взглядом - свежий софт работал в несколько тысяч раз быстрее.

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

Pro et contra: выполнимость