Задача П. к.-л. является частным случаем задачи программирования выпуклого. С другой стороны, П. к.-л. является обобщением программирования линейного.
Выпуклой кусочно-линейной ф-цией 
переменных 
которую можно представить в виде
где 
линейные ф-ции. Общую задачу П. к.-л. можно сформулировать в виде: найти минимум ф-ции F (X) при ограничениях
где 
заданные выпукл, кусочно-линейные ф-ции, 
вектор переменных задачи. Матрица А 
и вектор 
заданные величины. Система (1) определяет выпуклое многогранное мн-во возможных решений (планов) задачи.
К задачам П. к.-л. сводится ряд тех. и эконом, задач, напр., некоторые задачи календарного планирования произ-ва, некоторые транспортные задачи, задачи автомат, регулирования и т. д. Часто задачи линейного программирования с большим к-вом переменных и ограничений имеют специфические особенности, позволяющие переформулировать эти задачи в терминах П. к.-л. с уменьшением к-ва переменных и ограничений. Эта переформулировка обычно позволяет сократить время решения задачи и используемый объем запоминающего устройства ЭЦВМ, т. к. трудоемкость отдельной итерации для решения кусочно-линейной задачи, как правило, меньше, чем для решения соответствующей линейной задачи. Наконец, любую задачу выпуклого программирования можно точно или прибл. привести к задаче П. к.-л. Иногда такое приведение может быть достаточно эффективным.
Методы решения задач П. к.-л. являются, как правило, естественными обобщениями соответствующих методов линейного программирования: все осн. определения и свойства задач линейного программирования обобщаются на случай 
Наиболее важными из них являются перечисленные ниже. 1) Пусть 
Вектор 
опорным планом задачи (1), если он является планом и удовлетворяет линейнонезависимой системе 
ур-ний из следующего мн-ва:
т. e. точка X° принадлежит не менее, чем 
гиперплоскостям из указанного мн-ва. 2) Опорный план наз. невырожденным, если точка 
принадлежит точно 
гиперплоскостям. 3) План, на котором достигается минимум 
при условиях 
оптимальным планом, или решением задачи. 4) Решение задачи П. к.-л. достигается (если оно существует) на опорном плане. 5) План X задачи (1) является ее решением в том и только в том случае, если существует 
-мерный вектор 
такой, что а) функция 
Достигает в точке X минимума по X среди 
свойство наз. критерием оптимальности).
Общая схема конечных методов для задач П. к.-л. состоит, как правило, из той же последовательности действий, что и соответствующие схемы для задач линейного программирования. Так, напр., схема обобщения симплекс-метода включает в себя следующую последовательность операций: проверка текущего опорного плана на оптимальность с помощью критерия оптимальности и, если план не оптим., переход к новому опорному плану с меньшим значением целевой функции или выяснение неограниченности снизу значений целевой ф-ции. С вычисл. точки зрения опорный план, правила перехода к новому опорному плану и значение целевой ф-ции определяются заданием матрицы системы линейных ур-ний и вектора правых частей и их преобразований от шага к шагу в процессе действия алгоритма.
Кроме конечных методов, для решения задач П. к.-л. используются итерационные методы, в частности, для многих практических задач эффективны обобщенных градиентов методы. При этом предварительно задачу П. к.-л. с помощью ф-ций штрафа обычно сводят к задаче минимизации выпуклой кусочнолинейной ф-ции без ограничений.
Лит.: Гольштейн Б. Г., Юдин Д. В. Новые направления в линейном программировании. М.. 1966 [библиогр. с. 516—520].
В. А. Трубин.
