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

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

 эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;

 при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);

 эти значения были неотрицательными.

Задачами такого рода и занимается линейное программирование.

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

Дана система линейных уравнений:

 а11x1+а12x2+... +а1nxn= b1

 а21x1+а22x2+... +а2nxn= b2

(I) í........................

 аm1x1+аm2x2+... +аmnxn= bm

и линейная функция ¦=c1x1+c2x2+... +cnxn (II).

Требуется найти такие неотрицательные решения х1³ 0, х2³ 0... хn³ 0 (III) системы (I) при которых функция ¦ принимает наименьшее (наибольшее) значение.

Уравнения (I) называются ограничениями данной задачи, уравнение (II) называется линейной формой, а уравнение (III), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.

Казалось бы, т.к. задача линейного программирования ставится как задача минимизации некоторой функции ¦, то можно применить классический прием дифференциального исчисления. Однако частные производные ¦ равны коэффициентам при неизвестных, которые в «нуль» одновременно не обращаются.