Отсутствие решения задачи линейного программирования

Симплекс-метод: случай, когда система не имеет ни одного решения

В примере, рассмотренном в статье «Симплекс-метод решения задач линейного программирования: типичный пример и алгоритм», система ограничений была совместной и имелся конечный оптимум, причём единственный. В этой статье проиллюстрирован случай, когда одно из условий нарушается: система несовместна, то есть, не имеет ни одного решения, в том числе и оптимального.

Пример. Найти максимум функции при ограничениях

Сведём систему ограничений-неравенств к системе уравнений путём введения неорицательных добавочных переменных:

Переменные , , примем за основные. Соответствующее базовое решение (0; 0; -9; -2; 8) — недопустимое. Поэтому прежде всего воспользуемся симплексным методом для нахождения допустимого базисного решения.

Шаг I. Основные переменные: , , ; неосновные переменные , . Выразим основные переменные через неосновные (линейную форму пока не рассматриваем):

Переводим в основные переменные. Полагаем . При имеем и переходит в неосновные переменные.

Шаг II. Основные переменные , , ; неосновные переменные , . Снова выразив основные переменные через неосновные, приходим к системе

Во втором уравнении полученной системы и свободный член, и все коэффициенты при неосновных переменных отрицательны. Это является признаком того, что данная система несовместна. Она не имеет ни одного решения, в том числе и оптимального.

Источник

Неограниченные решения

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

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

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

Пример 8. (Неограниченная целевая функция)

Рассмотрим следующую задачу ЛП.

Максимизировать при ограничениях

Симплекс-таблица начальной итерации этой задачи имеет следующий вид.

Из этой таблицы видно, что в качестве вводимой переменной можно взять как  ₁, так и  ₂. Поскольку переменная  ₁ имеет максимальный (по абсолютной величине) отрицательный коэффициент в W()-строке, именно ее следует ввести в базисное решение. Однако заметим, что во всех ограничениях коэффициенты, стоящие перед переменной  ₂ отрицательны или равны нулю. Это означает, что значение переменной  ₂ может возрастать до бесконечности, и при этом не нарушается ни одно ограничение. Поскольку увеличение на 1 значения пе­ременной  ₂ приводит к увеличению на 1 значения целевой функции, значит, неограниченное увеличение значения переменной  ₂ ведет к неограниченному увеличению значения целевой функции. Эта ситуация проиллюстрирована на рис. 4.2.4. На этом рисунке видно, что пространство допустимых решений не ограничено в направлении оси  ₂ и значение целевой функции может быть ка­ким угодно большим.

Правило выявления неограниченности решения следующее.

Если на какой-либо симплекс — итерации коэффициенты в ограничениях для какой-нибудь небазисной переменной будут неположительными, значит, пространство решений не ограничено в направлении возрастания этой переменной. Кроме того, если коэффициент этой переменной в W()-строке отрицателен, когда рассматривается задача максимизации, или положителен в задаче минимизации, целевая функция также не ограничена.

Отсутствие допустимых решений

Если ограничения задачи ЛП несовместны (т.е. они не могут выполняться одно­временно), то задача не имеет допустимых решений. Такая ситуация не может воз­никнуть, если все неравенства, составляющие систему ограничений, имеют тип «» с неотрицательными правыми частями, так как в этом случае дополнительные пере­менные могут составить допустимое решение. Для других типов ограничений мы используем искусственные переменные. И хотя в оптимальном решении все искус­ственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В против­ном случае в оптимальном решении будет присутствовать хотя бы одна положи­тельная искусственная переменная.

С практической точки зрения отсутствие допустимых решений свидетельствует о том, что задача плохо сформулирована.

Пример 9. (Отсутствие допустимых решений)

Рассмотрим следующую задачу ЛП.

Максимизировать при ограничениях

Результат применения симплекс-метода представлен в следующей таблице.

Данные из этой таблицы показывают, что в точке оптимума искусственная пе­ременная R имеет положительное значение (= 4), что свидетельствует об отсутст­вии допустимого решения. На рис. 4.2.5 графически представлена ситуация данной задачи. Алгоритм симплекс-метода, допуская положительные значения искусст­венной переменной, по существу, превращает неравенство 3 ₁+4 ₃  12 в 3 ₁+4 ₃  12. (Объясните, почему так происходит.) В результате получаем то, что можно назвать псевдо оптимальным решением.

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

Правила формирования переменных и ограничений двойственной задачи ЛП [19].

1. Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи.
2. Каждой из переменных прямой задачи соответствует ограничение двойственной задачи.
3. Коэффициенты при какой-либо переменной в ограничениях прямой задачи становятся коэффициентами ограничения двойственной задачи, соответствующей этой переменной, а правая часть формируемого ограничения равна коэффициенту при этой переменной в выражении целевой функции.
4. Коэффициенты целевой функции двойственной задачи равны правым частям ограничений прямой задачи.
5. Поиск экстремума целевой функции двойственной задачи меняется на поиск противоположного экстремума по сравнению с прямой задачей.

Пример 9. (Прямая и двойственная задача линейного программирования)

Прямая задача	Прямая задачав стандартной форме	Двойственныепеременные
Максимизировать при ограничениях	Максимизировать при ограничениях

Двойственная задача Минимизировать при ограничениях

Источник