Формулировка общей задачи линейного программирования.

Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.

Каждая совокупность значений переменных (аргументов функции f), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция f, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции f, называется оптимальным планом задачи.

Задачей линейного программирования является выбор из множества допустимых планов наиболее выгодного (оптимального).

В общей постановке задача линейного программирования выглядит следующим образом:

Нужно определить максимум или минимум линейной целевой функции (линейной формы)

при ограничениях в виде равенств или неравенств

, i = 1, . . . , r;

, i = r+1, . . . , g;

, i = g+1, . . . , m;

x_ij ≥ 0 - требование неотрицательности управляющей переменной

где x_j, j=1, . . ., n – управляющие переменные, или решения задачи,

b_i, a_ij, i=1, . . ., m, j=1, . . ., n – параметры,

f – целевая функция.

Задача содержит n переменных и m ограничений.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂, ..., х_n являются неотрицательными:

Естественным решением сформулированной задачи линейного программирования является метод простого перебора: найти произвольное решение х₁ в допустимой области, вычислить (с, х₁), затем найти другое решение х₂, вычислить (с, х₂) и т.д. и среди полученных значений целевой функции (с, х) выбрать наименьшее. Этот путь перебора оказывается нереализуемым в связи со сложностью поиска допустимых решений, (допустимая область решений имеет бесконечное множество точек) и невозможностью поиска всех допустимых решений. Для решения задач линейного программирования строятся такие схемы поиска, которые позволяют выбирать оптимальный план, не перебирая всех возможных вариантов.