Задача линейного программирования может не иметь оптимального решения по нескольким причинам:

• Отсутствие области допустимых решений. 1 Это происходит, когда ограничения задачи противоречивы. 1
• Неограниченность области допустимых решений в направлении оптимизации целевой функции. 1
• Зацикливание. 1 Это возможно, когда в вырожденной задаче совпадают две соседние вершины области допустимых решений. 1 В таком случае после некоторого числа итераций алгоритм может вернуться к уже рассмотренному варианту, и процесс может повториться. 1
• Неограниченность целевой функции. 2 Это случается, если для какого-либо из векторов условия с оценкой, противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного. 2
• Несовместность системы ограничений. 4 В таком случае область допустимых решений является пустым множеством. 4