Лінійне програмування або лінійна оптимізація — це метод досягнення найкращого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі, які вимоги представлені через лінійні відношення. Лінійне програмування є технікою для оптимізації лінійної цільової функції, яка є обмеженою лінійними рівняннями і лінійними нерівностями. Допустима множина є опуклим політопом, який є множиною визначеною як перетин скінченної кількості півпростірів, кожен з яких визначає лінійна нерівність. Основною цільовою функцією є дійсно-значима афінна функція визначена на цьому багатограннику. Алгоритм лінійного програмування знаходить цю точку на багатограннику, де ця функція набуває найменшого чи найбільшого значення, якщо така точка існує.