ВУЗ:
Составители:
24 25
абсолютным значениям коэффициентов при соответст-
вующих переменных, находящихся в сроке целевой функции
симплекс-таблицы, содержащей оптимальное решение дру-
гой задачи.
Согласно второй теореме двойственности таблицу со-
ответствия значений и знаков переменных можно допол-
нить значениями переменных
1
y и
2
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 =
8
9
2
y =
4
1
3
y =0
4
y =0
Компоненты оптимального решения двойственной задачи
Эта таблица и содержит окончательное решение двой-
ственной задачи
Y
=(
8
9
,
4
1
,0,0).
Таким образом, первая теорема двойственности дает
оптимальное значение целевой функции, а вторая теорема
двойственности – значения всех компонент оптимального
плана двойственной задачи. Эти значения, как видно, сов-
падают со значениями, полученными с помощью симплекс-
метода (см. пример 3).
Восстановление последней симплекс-таблицы двойст-
венной задачи
Решение двойственной задачи уже получено, однако,
его можно представить более наглядно, а именно в виде
симплекс-таблицы, соответствующей оптимальному реше-
нию двойственной задачи.
Согласно теореме и таблице соответствия переменных,
а также условию, в симплекс-таблице, содержащей опти-
мальное решение двойственной задачи, базисными будут
принимающие ненулевое значение переменные
1
y и
2
y .
Строки в последней симплекс-таблице исходной зада-
чи удобнее переставить таким образом, чтобы они следова-
ли в порядке возрастания номеров соответствующих пере-
менных двойственной задачи, а строка целевой функции
находилась внизу таблицы:
БП
F
1
x
2
x
3
x
4
x
5
x
6
x
Реше-
ние
3
y
5
x
0 0 0
8
3
4
1
1 0 4
4
y
6
x
0 0 0
4
1
−
2
1
0 1 3
5
y
1
x
0 1 0
4
1
2
1
−
0 0 2
6
y
2
x
0 0 1
8
3
−
4
1
0 0 2
F
1 0 0
8
9
−
4
1
−
0 0 16
Затем нужно подготовить бланк таблицы двойствен-
ной задачи с таким же порядком расположения строк и с
учетом количества ограничений и, следовательно, базисных
переменных:
БП
Z
1
y
2
y
3
y
4
y
5
y
6
y
Реше-
ние
3
x
1
y
0 1 0
4
x
2
y
0 0 1
Z
1 0 0
Далее транспонируются «неединичные» столбцы из-
мененной последней симплекс-таблицы исходной задачи:
абсолютным значениям коэффициентов при соответст- мальное решение двойственной задачи, базисными будут
вующих переменных, находящихся в сроке целевой функции принимающие ненулевое значение переменные y1 и y 2 .
симплекс-таблицы, содержащей оптимальное решение дру- Строки в последней симплекс-таблице исходной зада-
гой задачи. чи удобнее переставить таким образом, чтобы они следова-
Согласно второй теореме двойственности таблицу со- ли в порядке возрастания номеров соответствующих пере-
ответствия значений и знаков переменных можно допол- менных двойственной задачи, а строка целевой функции
нить значениями переменных y1 и y 2 : находилась внизу таблицы:
Компоненты оптимального решения исходной задачи БП F x1 x 2 x3 x 4 x5 x6 Реше-
ние
x1 =2 x 2 =2 x3 =0 x 4 =0 x5 =4 x6 =3
3 1
y 5 =0 y 6 =0 9 1 y 3 =0 y 3 x5 0 0 0 1 0 4
y1 = y2 = y 4 =0 8 4
8 4 y 4 x6 0 0 0 −
1 1
0 1 3
Компоненты оптимального решения двойственной задачи 4 2
1 1
y 5 x1 0 1 0 − 0 0 2
Эта таблица и содержит окончательное решение двой- 4 2
3 1
9 1 y6 x2 0 0 1 − 0 0 2
ственной задачи Y =( , ,0,0). 8 4
8 4 9 1
Таким образом, первая теорема двойственности дает F 1 0 0 − − 0 0 16
8 4
оптимальное значение целевой функции, а вторая теорема
двойственности – значения всех компонент оптимального
Затем нужно подготовить бланк таблицы двойствен-
плана двойственной задачи. Эти значения, как видно, сов-
ной задачи с таким же порядком расположения строк и с
падают со значениями, полученными с помощью симплекс-
учетом количества ограничений и, следовательно, базисных
метода (см. пример 3).
переменных:
Восстановление последней симплекс-таблицы двойст-
венной задачи БП Z y1 y2 y3 y4 y5 y 6 Реше-
ние
Решение двойственной задачи уже получено, однако,
x3 y1 0 1 0
его можно представить более наглядно, а именно в виде
симплекс-таблицы, соответствующей оптимальному реше- x4 y2 0 0 1
нию двойственной задачи. Z 1 0 0
Согласно теореме и таблице соответствия переменных,
а также условию, в симплекс-таблице, содержащей опти- Далее транспонируются «неединичные» столбцы из-
мененной последней симплекс-таблицы исходной задачи:
24 25
