2. Основная теорема теории линейного программирования

Связь между двойственными задачами линейного программирования устанавливает следующая теорема.

Теорема двойственности. Каковы бы ни были исходные данные, для задач I и I* имеет место один из следующих взаимоисключающих случаев.

1⁰ . В основной и двойственной задачах имеются оптимальные векторы х⁰ и у⁰, причем значение линейных функций μ(x⁰) и ν(y⁰) на этих векторах совпадают.

2⁰ . В основной задаче имеются допустимые векторы, но линейная функция μ(x) на множестве этих векторов не ограничена сверху. При этом в двойственной задаче допустимых векторов не существует.

3⁰. В двойственной задаче имеются допустимые векторы, но линейная функция ν(y) на множестве этих векторов не ограничена снизу. При этом в прямой задаче допустимых векторов не существует.

4⁰. Ни в одной из рассмотренных задач нет допустимых векторов.

Рассмотрим примеры, иллюстрирующие случаи теоремы двойственности.

Пример 3. Максимизировать функцию μ(x)= х₁ – 2х₂ на множестве векторов х=(х₁, х₂), удовлетворяющих условиям

х₁, х₂ ≥ 0,

–x₁ – х₂ + 1 ≥ 0,

х₂ + 3 ≥ 0.

В этом случае

I={1,2}, I₁= Ø, I₂ =I; J={1,2}, J₁= J, J₂= Ø. Тогда двойственной к ней является следующая задача:

Минимизировать функцию ν(у)= у₁ + 3у₂ на множестве векторов у=(у_1, у₂), удовлетворяющих условиям

у₁ ≥ 0, у₂ ≥ 0,

– y₁ + 1=0,

– y₁ + y₂ – 2=0.

Применим для решения этих задач графический метод.

На рис. 2, а допустимая область заштрихована, на рис. 2, б допустимой областью является четырехугольник OABC, он обведена жирной линией; жирным показаны линии уровня для функции цели. Обе задачи имеют оптимальные векторы x⁰=(4; –3) и y⁰=(1; 3). Значения функции цели на этих векторах совпадают: μ(x⁰)=ν(у⁰)=10.

Таким образом, имеет место случай 1⁰ теоремы двойственности.

а б

Рис. 2. Графическое решение примера 3:

а – основная задача, допустимая область – заштрихованный луч;

б – двойственная задача, допустимая область – граница

многоугольника OAВС.

Пример 4. Максимизировать функцию μ(x)=x₁ на множестве векторов x=(x₁, x₂), удовлетворяющих условиям

– x₁ + x₂ + 3 ≥ 0,

2x₁ – 2x₂ – 4 ≥ 0.

Запишем двойственную задачу.

Минимизировать функцию ν(у)=3y₁ – 4y₂ на множестве векторов y=(y₁, y₂) , удовлетворяющих условиям

у₁ ≥ 0, у₂ ≥ 0,

– y₁ + 2y₂ + 1 = 0,

– y₁ – 2y₂ = 0.

Геометрическая иллюстрация решения примера приведена на рис. 3. На рис. 3, а допустимая область существует, но функция цели не ограничена сверху. На рис 3, б допустимых векторов нет, параллельные прямые не пересекаются. Таким образом, мы имеем случай 2⁰ теоремы двойственности.

а б

Рис. 3. Графическое решение примера 4: а – в основной задаче допустимые векторы существуют, но функция цели не ограничена;

б – в двойственной задаче нет допустимого решения.

Пример 5. Максимизировать функцию μ(x)= x₁ – x₂ на множестве векторов x=(x₁, x₂), удовлетворяющих условиям

x₁ ≥ 0, x₂ ≥ 0,

– x₁ – 1 ≥ 0,

– x₁ + x₂ + 1 ≥ 0.

Запишем двойственную задачу.

Минимизировать функцию ν(у)= – y₁ + y₂ на множестве векторов y=(y₁, y₂), удовлетворяющих условиям

у₁ ≥ 0, у₂ ≥ 0,

– y₁ – y₂ + 1 = 0,

y₂ – 1 = 0.

Геометрическая иллюстрация решения этих задач приведена на рис. 4.

а б

Рис. 4. Графическое решение примера 5.: а – в задаче I нет допустимого решения; б – в задаче I* имеются допустимые решения, но функция цели ν(у) не ограничена снизу.

Пример 6. Максимизировать функцию μ(x)= – x₁ + 2x₂ на множестве векторов x=(x₁, x₂), удовлетворяющих условиям

x₁ ≥ 0, x₂ ≥ 0,

x₁ – x₂ – 2 ≥ 0,

– x₁ + x₂ + 1 ≥ 0.

Запишем двойственную задачу.

Минимизировать функцию ν(у)= – 2y₁ + y₂ на множестве векторов y=(y₁, y₂), удовлетворяющих условиям

у₁ ≥ 0, у₂ ≥ 0,

y₁ – y₂ – 1 = 0,

– y₁ + y₂ + 1 = 0.

Геометрическая иллюстрация решения этих задач приведена на рис. 5.

а б

Рис. 5. Графическое решение примера 6.: а – в задаче I нет допустимых векторов; б – в задаче I* нет допустимых векторов.