Линейное программирование в примерах и задачах. Методические указания. Корытов И.В - 12 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

22 23
Решение двойственной задачи с использованием
теорем двойственности
Пример 4. Решить двойственную задачу, построенную
в примере 2, используя теоремы двойственности.
Использование первой теоремы двойственности
Информация для решения двойственной задачи с ис-
пользованием теорем двойственности содержится в сим-
плекс-таблице, полученной на последнем шаге решения ис-
ходной задачи:
БП
F
1
x
2
x
3
x
4
x
5
x
6
x
Реше-
ние
F
1 0 0
8
9
−
4
1
−
0 0 16
2
x 0 0 1
8
3
−
4
1
0 0 2
1
x
0 1 0
4
1
2
1
−
0 0 2
5
x
0 0 0
8
3
4
1
1 0 4
6
x
0 0 0
4
1
−
2
1
0 1 3
Таблица взята без столбцов, соответствующих искус-
ственным переменным.
Первая теорема двойственности. Если одна из двой-
ственных задач имеет решение, то другая также имеет
решение, причем оптимальные значения их целевых функций
равны.
Согласно первой теореме двойственности в данной за-
даче
16minmax
=
= FZ .
Использование теоремы о соответствии переменных
исходной и двойственной задач
Таблица соответствия переменных:
Переменные исходной задачи
Основные Балансовые
1
x
2
x
3
x
4
x
5
x
6
x
5
y
6
y
1
y
2
y
3
y
4
y
Балансовые Основные
Переменные двойственной задачи
Теорема. Строго положительным компонентам оп-
тимального решения одной из взаимно двойственных задач
соответствуют нулевые компоненты оптимального реше-
ния другой задачи.
Теорема дает возможность установить, какие перемен-
ные двойственной задачи принимают при оптимальном ре-
шении нулевые значения.
Таблица соответствия значений и знаков переменных:
Компоненты оптимального решения исходной задачи
1
x
=2
2
x
=2
3
x =0
4
x
=0
5
x =4
6
x =3
5
y =0
6
y =0
1
y >0
2
y >0
3
y =0
4
y =0
Знаки компонент оптимального решения двойственной за-
дачи
Использование второй теоремы двойственности
Вторая теорема двойственности позволяет найти ос-
тавшиеся ненулевые значения компонент оптимального ре-
шения двойственной задачи.
Вторая теорема двойственности. Компоненты оп-
тимального решения одной из двойственных задач равны 
                                                           Использование теоремы о соответствии переменных
                                                           исходной и двойственной задач
Решение двойственной задачи с использованием                   Таблица соответствия переменных:
          теорем двойственности
                                                                        Переменные исходной задачи
     Пример 4. Решить двойственную задачу, построенную         Основные                 Балансовые
в примере 2, используя теоремы двойственности.                x1      x2       x3       x4        x5         x6
Использование первой теоремы двойственности                   y5       y6      y1       y2        y3         y4
     Информация для решения двойственной задачи с ис-         Балансовые                 Основные
пользованием теорем двойственности содержится в сим-                  Переменные двойственной задачи
плекс-таблице, полученной на последнем шаге решения ис-
ходной задачи:                                                  Теорема. Строго положительным компонентам оп-
                                                           тимального решения одной из взаимно двойственных задач
           БП F   x1 x 2   x3    x 4 x5 x6 Реше-           соответствуют нулевые компоненты оптимального реше-
                                            ние            ния другой задачи.
                             9     1                            Теорема дает возможность установить, какие перемен-
           F 1    0   0    −     −     0   0   16
                             8     4                       ные двойственной задачи принимают при оптимальном ре-
                             3    1                        шении нулевые значения.
           x2 0   0   1    −           0   0   2
                             8    4                             Таблица соответствия значений и знаков переменных:
                            1      1
           x1 0   1   0          −     0   0   2
                            4      2                         Компоненты оптимального решения исходной задачи
                            3     1
           x5 0   0   0                1   0   4            x1 =2   x 2 =2   x3 =0     x 4 =0   x5 =4    x6 =3
                            8     4
                             1    1                         y 5 =0   y 6 =0    y1 >0      y 2 >0 y 3 =0   y 4 =0
           x6 0   0   0    −           0   1   3
                             4    2                        Знаки компонент оптимального решения двойственной за-
                                                                                     дачи
     Таблица взята без столбцов, соответствующих искус-
ственным переменным.
     Первая теорема двойственности. Если одна из двой-     Использование второй теоремы двойственности
ственных задач имеет решение, то другая также имеет            Вторая теорема двойственности позволяет найти ос-
решение, причем оптимальные значения их целевых функций    тавшиеся ненулевые значения компонент оптимального ре-
равны.                                                     шения двойственной задачи.
     Согласно первой теореме двойственности в данной за-       Вторая теорема двойственности. Компоненты оп-
даче max Z = min F = 16 .                                  тимального решения одной из двойственных задач равны
22                                                                                                                23

Страницы