Постановка задачи линейного программирования
Рассмотренные нами методы решения задач оптимизации применимы к широкому классу задач, однако являются весьма сложными и требуют проведения значительных объемов вычислений. Между тем, существует ряд задач, являющихся частными случаями общей задачи оптимизации (4.2), для решения которых применимы методы, требующие для реализации более простых алгоритмов и значительно меньших вычислительных мощностей. К числу таких задач относится задача линейного программирования.
Задача линейного программирования сводится к поиску экстремума (максимума или минимума) линейной функции вида

Очевидно, искать экстремум этой функции, не налагая никаких ограничений на область изменения вектора





где





Те из соответствующих задач, в которых область изменения вектора



Определение 7.1
Линейным программированием называется комплекс методов оптимизации линейных функций в допустимой области, определяемой системой линейных уравнений и неравенств.
В общем случае задача линейного программирования при оптимизации функции




Представление задачи в форме (7.4) называется стандартной постановкой задачи линейного программирования

Переход от формы (7.3) к форме (7.4) осуществляется с помощью приема элиминации нетривиальных неравенств.