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

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

Задача линейного программирования - student2.ru (2.1)


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


Задача линейного программирования - student2.ru (2.2)
Задача линейного программирования - student2.ru (2.3)
Задача линейного программирования - student2.ru (2.4)
Задача линейного программирования - student2.ru (2.5)
Задача линейного программирования - student2.ru - произвольные Задача линейного программирования - student2.ru (2.6)


где Задача линейного программирования - student2.ru , Задача линейного программирования - student2.ru - заданные действительные числа;

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

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

Задача линейного программирования - student2.ru - план задачи.


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


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

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


Теорема.Если система векторов Задача линейного программирования - student2.ru содержит m линейно независимых векторов Задача линейного программирования - student2.ru , то допустимый план


Задача линейного программирования - student2.ru (2.10)


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


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

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

Наши рекомендации