Линейное программирование

6. Проблемы практической реализации. Сложность

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

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

В течение долгого времени не было известно, принадлежит ли линейное программирование к неполиномиальному классу задач, названному «трудные» или к полиномиальному классу «лёгкие». В 1970 Виктор Клее и Джордж Минти создали пример, показавший, что классический симплексный алгоритм потребует экспоненциального числа шагов при решении наихудшего случая задачи линейного программирования. В 1978 советский математик Леонид Генрихович Хачиян разработал алгоритм для решения задач линейного программирования, имеющий полиномиальное время выполнения. Это -- метод внутренней точки, использующий эллипсоиды, вписанные в область допустимых значений. Хачиян доказал, что время вычисления будет гарантированно меньше, чем полиномиальная функция размерности задачи и количества входных данных. Однако степень полинома, которую он установил, оказалась слишком высокой для того, чтобы этот алгоритм можно было использовать при решении практических задач.

Алгоритм индийского математика, Нарендра Кармаркара был важным развитием теоретического вывода Хачияна. Кармаркар показал, как задача линейного программирования может быть решена за полиномиальное время. Кроме того, алгоритм Кармаркара был применим для решения задач линейного программирования на практике.

Современные пакеты для решения задач линейного программирования совмещают симплекс-метод Данцига с более современными методами внутренней точки. Это позволяет самым последним вариантам решать задачи, включающие до одного миллиарда переменных. Для таких огромных задач используются большие параллельные суперкомпьютеры с более чем тысячей процессоров. Но даже на намного более скромных 4-процессорных компьютерах задачи линейного программирования с миллионом переменных решались за полчаса, при использовании методов внутренней точки.