3. Неединственность решения.

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

Рассматривается задача P в канонической форме с m уравнениями (ограничениями), n переменными, m ≤ n:

f₀(x) = c⁰ · x → max при A⁰x = b⁰, x ≥ 0.

Пусть X – множество допустимых решений задачи P, X^* – множество оптимальных решений задачи. Предполагаем, что задача разрешима (X^* ≠ Ø).

x^* – некоторое базисное оптимальное решение с базисом β и базисной матрицей B.

Если x₁ – альтернативное решение, то все точки отрезка {(1–λ) x^* + λ x₁ | λ [0; 1]} также являются решениями, т.е. лежат в X^*.

Утверждение: Условия x₁ X^* и необходимы и достаточны, чтобы вектор x₁ был альтернативным решением задачи P.

Доказательство: Пусть x₁ – альтернативное решение задачи. Тогда x₁ X^* и x₁ ≠ x^*. Если их небазисные части совпадают и равны нулю x_1н(β) = x^*_н(β) = 0, то их базисные части x_1б(β) и x^*_б(β) удовлетворяют системе уравнений Bx = b⁰. Так как B – невырожденная матрица (как базисная), то у этой системы единственное решение. Поэтому x₁ = x^*. Получаем противоречие с положением об альтернативности этого решения. Отсюда некоторые небазисные компоненты вектора x₁ положительны и соответственно g(x₁) > 0.

Обратно: пусть есть некоторое оптимальное решение x₁ X^*, для которого g(x₁) > 0. Но так как для решения x^*_н(β) = 0, то g(x^*) = 0 и x₁ ≠ x^*. Получаем, что x₁ – альтернативное решение задачи P.

Правило для построения альтернативных решений:

Формулируется задача P₁ линейного программирования: максимизация произвольной линейной функции на X^* с ограничениями

A⁰x = b⁰, x ≥ 0, f₀(x) = f₀(x^*).

Задача P₁ совместна, а, значит, либо неограниченна, либо разрешима.

В первом случае – решая задачу симплекс-методом, найдем луч L = {x⁰ + λv | λ ≥ 0}, целиком лежащий в X^*. Любая точка на этом луче – будет альтернативным решением.

Во втором случае – найдем базисное оптимальное решение, которое может совпадать с x^*.

Из рассмотренного утверждения – задача P₁ с целевой функцией имеет альтернативное решение, если оно существует.

Рассмотрим задачу P^{^} (максимизация на множестве оптимальных решений суммы небазисных переменных):

при A⁰x = b⁰, x ≥ 0, f₀(x) = f₀(x^*).

Следствие: Задача P^{^} либо неограниченна, либо разрешима. В первом случае существует луч альтернативных решений. Во втором случае: если x₁ –решение задачи P^{^}, то либо g(x₁) = 0 и x^* – единственное решение исходной задачи P, либо g(x₁) ≠ 0 и x₁ – альтернативное решение.

Приведем задачу P к базису (оптимальному) β. Задача примет вид P`:

при Ax = b, x ≥ 0.

где вектор b и все γ_i неотрицательны (так как базис допустим и оптимален), в матрице A базисным переменным соответствуют столбцы из единичной матрицы.

Эти задачи эквивалентны, значения их ЦФ совпадают для всех допустимых решений. Последняя симплекс-таблица для задачи P описывает задачу P`.

Пусть I₀ = {i | b_i = 0}, v = (v_j | j N(β)). Очевидно, что элементов множества I₀ и вектора v меньше, чем m+1 и n соответственно. Покажем, что задача P^{^} заменяется задачей Q с меньшим числом переменных и ограничений:

v ≥ 0.

Теорема (критерий альтернативного решения): Задача P имеет альтернативное решение тогда и только тогда, когда максимум ЦФ в задаче Q не равен нулю.

Доказательство:

1. Пусть задача P имеет альтернативное решение. Тогда существует x₁ X^*, для которого g(x₁) > 0.

Определим вектор v задачи Q следующим образом: v_j = x_1j для j N(β). Тогда условие неотрицательности в задаче Q выполнено, так как x₁ допустимое решение задачи P.

В задаче P` уравнение с номером i имеет вид . Пусть i I₀, тогда b_i = 0. Тогда для вектора x₁ получаем

, так как .

Таким образом, выполнено неравенство в задаче Q.

Условие f(x₁)=f(x^*) влечет , так как x^*_н = 0. Получили, что вектор v допустим в Q и h(v) = g(x₁) > 0.

Значит, максимум функции h в задаче Q не может быть нулем.

2. Пусть максимум ЦФ в задаче Q не равен нулю. Задача является совместной, так как нулевое решение допустимо. Следовательно, задача либо неограниченна, либо разрешима.

Тогда существует некоторое допустимое решение v = (v_j | j ∉ N(β)) задачи Q, для которого h(v) > 0. Тогда при любом λ > 0 вектор λv также является допустимым решением (проверяется подстановкой) и для него h(λv) = λh(v) > 0.

Определим вектор x₁ следующим образом:

для всех j ∉ N(β) положим x_1j = λv_j.

если j N(β), то j = j(i) для некоторого i {1,…,m}; пусть .

если , то , так как b_i ≥ 0.

если , то i ∉ I₀.

Тогда b_i > 0, и мы можем подобрать такое λ, чтобы обеспечить Достаточно выбрать λ ≤ λ₀, где λ₀ – минимум отношений b_i к по всем i, для которых .

Если таких нет, то λ₀ = + ∞. В любом случае λ₀ > 0.

Таким образом, получим полностью определенный вектор x₁ ≥ 0, удовлетворяющего всем ограничениям по построению.

Из следует, что .

Поэтому x₁ X^*.

При этом .

Тогда x₁ – альтернативное решение задачи P.

Следствие 1: Для существования альтернативного решения в задаче P необходимо, чтобы γ_k было равно нулю при некотором k N(β).

Следствие 2: Для существования альтернативного решения в задаче P достаточно, чтобы при некотором k N(β) выполнялись условия γ_k = 0 и a_ik ≤ 0 для всех i из I₀.

Следствие 3: Если решение x^* задачи P невырожденно, то для существования альтернативного решения достаточно чтобы γ_k было равно нулю при некотором k N(β).