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

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

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

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

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

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

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

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

ìа₁₁x₁+а₁₂x₂+ ... +а_1nx_{n =} b₁

ïа₂₁x₁+а₂₂x₂+ ... +а_2nx_{n =} b₂

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

îа_m1x₁+а_m2x₂+ ... +а_mnx_{n =} b_m

и линейная функция ¦=c₁x₁+c₂x₂+ ... +c_nx_n (II).

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

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

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