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

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

Рассматривается задача 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 _{1 j} для 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 _{1 j} = λ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 (β).

Поиск по сайту: