Задачей линейного программирования называется задача, в которой минимизируемым или максимизируемым критерием является линейная функция, причем на переменные налагаются ограничения, которые также представляются линейными функциями. Комбинация скаляров или векторов, обычно обозначаемых Xi,называется линейной, если она может быть записана в виде
с 1 Х 1 + с 2 Х 2 +... +с n Х n, (1)
где все коэффициенты с — константы. Например, функция
4 х 1+ 3 х 2+ 5 x 3 + 2
линейна относительно переменных x1 , x2 , x3 , тогда как функция
не линейна относительно тех же переменных. Величины Х 1..., Х nназываются линейно зависимыми, если для некоторого набора ci в предположении, что не все ci равны нулю, имеет место следующее равенство:
(2)
С другой стороны, если 
только тогда, когда все коэффициенты сi равны нулю, то величины Хi... Хп называются линейно независимыми.
Линейное программирование стало быстро развиваться после второй мировой войны, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности. Применение линейного программирования оказалось плодотворным в таких областях, как:
1. Оптимальное регулирование полетов на воздушных линиях.
2. Распределение во времени транспортировки грузов с заводов и складов к базам.
4. Планирование промышленного производства.
5. Система оплаты контрактов.
6. Проектирование систем связи и распределение в них потоков сообщений.
7. Распределение кадров.
8. Организация максимальных потоков в транспортных сетях.
Широкое привлечение внимания к линейному программированию привело к тому, что до некоторой степени была преувеличена его значимость; часто упускали из виду, что оно применимо лишь тогда, когда выполняются лежащие в его основе допущения, которые в свою очередь базируются на линейном математическом представлении реального мира. В нелинейном программировании не используются столь сильные упрощения.
Хотя задача линейного программирования может быть сформулирована по-разному, запишем ее в следующей форме:
минимизировать 
(3)
при ограничениях
(4)
(5)
где a, b и с — константы, а хi — искомые переменные.
Уравнения (3)-(5) можно компактно записать в матричной форме. Пусть X и с – вектор-столбцы размерности (n ´ 1); а –матрица констант размерности (n ´ m) и b – вектор-столбец размерности (m ´ 1):
Тогда в матричных обозначениях уравнения (3)-(5) запишутся следующим образом:
минимизировать 
(6)
при ограничениях
(7)
(8)
где верхний индекс Т означает транспонирование.
Для решения задачи, выраженной уравнениями (6)-(8), были предложены различные методы, один из которых (симплекс-метод) стал общеупотребительным и который, в частности, кратко рассмотрен в учебном пособии по методам оптимизации [3].
Пример. Этот пример иллюстрирует связь между уравнениями (3)-(5) и реальной задачей. Крупная авиакомпания ассигновала 600 млн. долл. на лизинг самолётов трех типов. Годовой лизинг самолёта А стоит 10 млн. долл., самолёта В — 20 млн. долл. и самолёта С — 23 млн. долл. Сколько самолётов каждого типа нужно заказать, чтобы получить наибольшую производительность в тонно-километрах на один день с учетом приведенных ниже условий?
Самолёт А требует для эксплуатации одного экипажа на каждую смену, максимальное число смен в сутки 3, производительность 21000 тонно-километров за каждую смену.
Самолёт В требует двух экипажей на каждую смену, максимальное число смен в сутки 3, производительность 36000 тонно-километров за каждую смену.
Самолёт С требует двух экипажей на каждую смену, максимальное число смен в сутки 3, производительность 37800 тонно-километров за каждую смену.
Кроме того, число экипажей должно быть не больше 145, число самолётов — не больше 30.
Эта задача может быть сформулирована в терминах линейного программирования следующим образом. Обозначим число смен индексами 1, 2 и 3, а число самолётов каждого типа — прописными буквами А, В и С. Таким образом А 1 означает количество самолётов типа А, работающих одну смену в сутки.
Сначала необходимо выбрать функцию цели. В данном примере критерием оптимальности является производительность, соответствующая функции (3):
у = 21000 А1 + 42000 А2 + 63000 А3 + 36000 В1 + 72000 В2 + 108000 В3 + 37800 С1 + 75600 С2 + 113400 С3,
где у - количество тонно-километров. Запишем далее выражения для ограничений. Здесь мы имеем дело с ограничениями трех типов: 1) общая стоимость лизинга всех самолётов не должна превышать 600 млн. долл.; 2) количество самолётов должно быть не более 30; 3) количество экипажей должно быть не более 145:
1) 10 млн. (А1 + А2 + А3) + 20 млн.(В1 + В2 + В3) + 23 млн. (С1 + С2 + С3)≤ 600 млн.;
2) А1 + A2 + A2 + B1 + B2 + B3 + Cl + C2 + С3 ≤ 30;
3) А1 + 2А2 + 3А3 + 2В1 + 4B2 + 6В3 + 2С1 + 4С2 + 6С3 ≤ 145.
Кроме того, поскольку самолёты являются физическими объектами, то их количество не может быть отрицательной величиной, и тогда имеют место следующие неравенства, соответствующие условиям (5):
Ai ³ 0, Bi ³ 0, Ci ³ 0, i = 1, 2, 3.
Поставленная таким образом задача может быть решена соответствующим методом линейного программирования; в результате определяется количество самолётов типов А, В и С, максимизирующее величину целевой функции (производительность) у.
Решение: 12 самолётов типа А, 0 самолётов типа В и 18 самолётов типа С.