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

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

задача в которой фигурируют ограничения в форме неравенств, называется — основной задачей линейного программирования (ОЗЛП).

.

.

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

.

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