найти максимум линейной ф-ции 
переменных 
при ограничениях
где 
— заданные числа. Задача минимизации ф-ции (1) сводится к задаче максимизации путем замены знаков всех коэфф. с, - на противоположные. П. л. является наиболее развитой и законченной областью программирования математического. Общая постановка задачи П. л. и один из подходов к ее решению (идея разрешающих множителей или двойственных оценок) впервые приведены в работе советского ученого Л. В. Канторовича в 1939. В этой же работе намечен один из методов решения задачи — метод последовательного сокращения невязок.
В работе советских ученых Л. В. Канторовича и М. К. Гавурина, выполненной в 1940 применительно к транспортной задаче, разработан еще один метод решения задачи П. л., получивший название метода потенциалов. Бурное развитие П. л. тесно связано с появлением ЭЦВМ и их использованием для решения эконом. задач. Началом этого развития послужила разработка в 1949 амер. математиком Дж. Б. Данцигом эффективного метода решения задачи П. л., получившего название симплекс-метода. Этот метод является обобщением метода потенциалов на общую задачу П. л., но разработан независимо от него. Позднее был описан еще один — двойственный симплекс-метод, который по существу является симплекс-методом для решения двойственной задачи П. л., но формулируется в терминах исходной задачи. Все отмеченные методы являются конечными. Кроме них, для решения задачи П. л. используются итеративные методы, дающие за конечное число шагов лишь приближенное (с заданной степенью точности) решение. Тесная связь между П. л. и игр теорией позволяет использовать для решения задач П. л. численные методы теории игр.
Другая группа итеративных методов характеризуется заменой исходной задачи на эквивалентную ей выпуклую экстрем, задачу без ограничений, для решения которой используются различные градиентные методы.
Для решения задач П. л. с большим числом переменных и ограничений разработаны декомпозиции методы, позволяющие вместо исходной задачи решать последовательность задач меньшего объема. Эти методы дают возможность обойти трудности, возникающие в связи с ограниченной емкостью оперативной памяти ЭЦВМ. Методы П. л. недостаточны при решении задач с дополнительными ограничениями на целочисленность значений переменных; изучением таких задач занимается программирование целочисленное (дискретное). Экономные методы решения задач П. л., коэфф. которых зависят от параметров, разрабатываются в параметрическом программировании. Наряду с общей задачей изучаются различные частные задачи П. л., такие как транспортные, распределительные задачи, задачи теории расписаний, выбора и др. Некоторые идеи П. л. используются в теории наилучших приближений, теории моментов и других разделах математики.
В виде задачи П. л. формулируются с достаточной степенью точности многочисленные задачи перспективного и оперативного планирования в различных отраслях нар. х-ва, управления разнообразными производственными и технологическими процессами, орг-ции бесперебойной и целенаправленной работы комплексов оборудования.
Наиболее распространенным примером задачи П. л. является задача планирования работы предприятия, выпускающего некоторый однородный продукт. Эта задача ставится следующим образом: имеется 
различных технологий и 
ресурсов (рабочая сила, сырье, энергия, транспорт и т. д.) произ-ва. Известны: 
единиц продукта, которое можно получить при использовании 
технологии в единицу времени 
расход 
ресурса при использовании 
технологии 
общий запас 
ресурса 
время, в течение которого произ-во ведется по 
технологии. Требуется отыскать план 
при котором из имеющихся запасов выпускалось бы макс. к-во продукта. Математически эта задача формулируется в виде (1), (2), (4) при 
Каждой задаче П. л. соответствует двойственная задача, переменные и ограничения которой также имеют экономическую интерпретацию (см. Двойственности теория в программировании линейном).
Любую задачу П. л. можно представить в каноническом виде
Ограничения (6) часто записывают в векторной форме:
где 
. Функцию 
линейной формой (ф-цией цели) задачи, матрицу 
коэффициентов при переменных в (6) — матрицей условий, вектор 
— вектором условий, В — вектором ограничений.
Вектор 
удовлетворяющий уравнениям (6) и (7), наз. планом задачи. План, на котором линейная форма принимает макс. значение, наз. оптимальным планом (или решением) задачи. Если задача П. л. имеет хотя бы один план, мн-во всех ее планов определяет в ге-мерном пространстве переменных выпуклое многогранное мн-во. Опорным планом наз. план, соответствующий вершине этого мн-ва. Опорный план невырожден, если ему соответствует вершина, в которой ровно 
(для задачи (5-7)) переменных принимают положительные значения; мн-во векторов условий, соответствующих этим 
переменных, образуют базис.
Задача П. л. наз. разрешимой, если существует хотя бы один оптим. план X, для которого все 
иограниченной, если мн-во ее планов ограничено, т. е. является выпуклым многогранником. Если задача и разрешима и ограничена, среди ее оптим. планов имеется хотя бы один опорный. Число опорных планов конечно. Оптим. план можно искать только среди опорных планов. Это свойство так или иначе использовано во всех конечных методах П. л. В симплекс-методе и его модификациях оптим. план достигается при движении по опорным планам исходной задачи. Процесс начинается с анализа некоторого опорного плана. Если этот план не оптимален, осуществляется переход к новому опорному плану с большим значением линейной формы. В двойственном симплекс-методе процесс начинается с опорного плана двойственной задачи (псевдоплана исходной задачи). При переходе от одного псевдоплана к следующему значение линейной формы уменьшается. Процесс решения заканчивается, как только псевдоплан становится планом. В методе последовательного сокращения невязок процесс решения начинается с некоторого (не обязательно опорного) плана двойственной задачи, которому в соответствие ставится вектор 
исходной задачи (не являющийся, вообще говоря, планом). Правила перехода от одного вектора 
к другому неотрицательному вектору обеспечивают сокращение разностей (невязок) между правыми и левыми частями условий (6). Вектор, для которого все невязки обращаются в нуль, является оптим. планом задачи.
Лит.. Канторович Л. В. Математические ме-тоды организации и планирования производства. Л., 1939; Канторович Л. В. Экономический расчет наилучшего использования ресурсов. М., 1960; Юдин Д. В., Гольштейн Е. Г. Линейное программирование. М., 1969 [библиогр. с. 418—421]; Данциг Дж. Линейное программирование, его применения и обобщения. Пер. с англ. М., 1966 {библиогр. с. 564—589]. В. А. Трубин.
