Пионер и основатель теории линейного программирования – советский ученый Леонид Витальевич Канторович. Над подобными проблемами он работал в конце 1930-х годов. В 1940-м вышла его фундаментальная статья «Об одном эффективном методе решения некоторых классов экстремальных проблем». В ней Канторович заложил математические основы линейного программирования (правда, тогда оно еще так не называлось).

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

Одна из классических знаменитых задач линейного программирования – задача о диете Стиглера, датируемая 1945 годом. Звучит она примерно так: какие из 77 продуктов должны входить в потребительскую корзину одного человека (скажем, мужчины среднего веса), чтобы он получил необходимую норму девяти питательных веществ (включая калории) и при этом стоимость продуктов была минимальной? Это очень важная задача в экономике, потому что ее решение определяет минимальную потребительскую стоимость полноценного питания.

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

Уже к концу 1950-х линейное программирование достаточно широко использовалось в нефтяной индустрии. Сегодня оно лежит в основе огромного класса задач оптимизации, включая задачи менеджмента и микроэкономики: планирование, логистика, составление расписаний. Задачи, где нужно минимизировать стоимость или максимизировать доход при заданных ограничениях.