Лине́йное программи́рование, раздел математики, посвящённый теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных равенств и неравенств. Задачи линейного программирования являются математическими моделями различных задач технико-экономического содержания.

Типичной задачей линейного программирования является задача нахождения максимума по $x_1,\ldots,x_n$ линейной функции $$\sum_{j=1}^{n}c_jx_j\tag1$$при условиях$$\sum_{j=1}^n a_{ij}x_j ⩽ b_i,\quad i=1,\ldots,m, \tag2$$$$x_j⩾0,\quad j=1,\ldots,n,\tag3$$где $n, m, c_j, a_{ij}$ и $b_i$ – заданные числа.

Такая задача возникает, например, при планировании работы предприятия. Пусть предприятие может выпускать $n$ видов продукции, единица продукции вида $j$ даёт прибыль $c_j$, $j=1,\ldots,n$. В производстве используются ресурсы $n$ видов (сырьё, время работы станков, рабочая сила, энергия и т. п.). Расход ресурса $i$ на производство единицы продукции вида $j$ составляет $a_{ij}$. Общий ресурс вида $i$ ограничен величиной $b_i$, $i= 1, \ldots, m$. Требуется определить производственный план (программу; отсюда название), т. е. найти объёмы выпуска $x_j⩾0$ по каждому из видов продукции с тем, чтобы были выполнены ограничения $(2)$, а суммарная прибыль $(1)$ была максимальной.

Функцию $(1)$ в линейном программировании принято называть целевой функцией (критерием оптимальности, критерием эффективности), вектор $x= (x_1,\ldots,x_n)$, удовлетворяющий условиям $(2)$, $(3)$, называется допустимым решением, или планом, а множество векторов $x$, определяемое условиями $(2)$, $(3)$, называется допустимым множеством, или множеством планов. Допустимое решение $x^*$, доставляющее максимум целевой функции $(1)$, называется оптимальным. Ещё одним примером прикладных задач линейного программирования является транспортная задача.

В задачах линейного программирования более общего вида по сравнению с $(1)$–$(3)$ некоторые (или все) из условий $(2)$ могут быть равенствами, а на некоторые (либо на все) переменные $x_j$ не налагаются условия неотрицательности. Любая задача линейного программирования может быть приведена к эквивалентной задаче вида $(1)$–$(3)$. В некоторых задачах линейного программирования возникает ограничение, связанное с целочисленностью величин $x_1,\ldots,x_n$. В этом случае говорят о задачах целочисленного линейного программирования.

Задачей линейного программирования, двойственной задаче $(1)$–$(3)$, называется задача минимизации функции $$\sum_{i=1}^{m}b_iy_i\tag4$$при условиях$$\sum_{i=1}^ma_{ij}y_i⩾c_j,\quad j=1,\ldots,n,\tag5$$$$y_i⩾0,\quad i=1,\ldots,m.\tag6$$Задачи $(1)$–$(3)$ и $(4)$–$(6)$ либо обе имеют решения, либо обе неразрешимы. Значения целевых функций $(1)$ и $(4)$ на решениях совпадают.

Одним из основных методов решения задач линейного программирования является симплексный метод. Его идея состоит в следующем: допустимое множество планов, задаваемое ограничениями $(2)$ и $(3)$, представляет собой выпуклое многогранное множество; если оно ограничено, то оно является выпуклым многогранником. Если задача линейного программирования имеет решение, то существует вершина $x^*$ этого многогранника, являющаяся оптимальным планом. Симплексный метод состоит в направленном переборе, при котором значения целевой функции возрастают от вершины к вершине. Каждой вершине соответствует система уравнений, получаемая из системы неравенств $(2)$, $(3)$, и вычислительная процедура симплексного метода состоит в последовательном решении систем линейных алгебраических уравнений. Простота алгоритма делает этот метод удобным для реализации. Для решения задач линейного программирования применяются также итерационные методы построения последовательности приближений, пределом которой является оптимальный план.

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

Развитие линейного программирования началось в 1939 г. с исследований Л. В. Канторовича, в которых он предложил универсальный математический метод для решения задач экономического характера, таких как задача о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта. Во 2-й половине 1940-х гг. Т. Купманс обращал внимание математиков на задачи, сводящиеся к нахождению экстремумов линейных функций на многогранниках. В это же время американский математик Дж. Данциг (ввёл термин «линейное программирование») и Канторович независимо друг от друга предложили эффективный метод решения таких задач, получивший название симплексного метода. Этот и другие методы решения задач линейного программирования требуют большого объёма вычислений; они стали эффективно реализовываться только с появлением быстродействующих ЭВМ в начале 1950-х гг.