Задача линейного программирования

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

(2.1)

при ограничениях

(2.2)
(2.3)
(2.4)
(2.5)
- произвольные (2.6)

где , - заданные действительные числа;

(1) – целевая функция;

(1) – (6) –ограничения;

- план задачи.

Пусть ЗЛП представлена в следующей записи:

(2.7)
(2.8)
(2.9)
Чтобы задача (2.7) – (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r > n вообще невозможен. При r = n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r < n. В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будут свободными, их обозначают СП.

Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .
Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

Теорема. Если система векторов содержит m линейно независимых векторов , то допустимый план

(2.10)

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

Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.

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