Кирсанова О.В., Семёнова Г.А. Математическое программирование (типовой расчёт)
Подождите немного. Документ загружается.
50
5.3.
12
12
12
12
12
3 2 max;
2 6,
5,
2 6;
0, 0.
F x x
xx
xx
xx
xx
5.4.
12
12
12
12
12
3 4 max;
2 7,
4 19,
1;
0, 0.
F x x
xx
xx
xx
xx
5.5.
12
12
12
12
12
3 max;
6,
2 10,
4 12;
0, 0.
F x x
xx
xx
xx
xx
5.6.
12
12
12
12
12
2 max;
2 7,
6,
3 6;
0, 0.
F x x
xx
xx
xx
xx
5.7.
12
12
12
12
12
2 5 max;
3 2 19,
2 3 21,
4 13;
0, 0.
F x x
xx
xx
xx
xx
5.8.
12
12
12
12
12
4 max;
3 13,
6 7 61,
2 11;
0, 0.
F x x
xx
xx
xx
xx
5.9.
12
12
12
12
12
5 max;
5 18,
7 5 54,
2 9;
0, 0.
F x x
xx
xx
xx
xx
5.10.
12
12
12
12
12
2 max;
3 2 16,
4 5 33,
3 10;
0, 0.
F x x
xx
xx
xx
xx
5.11.
12
12
12
12
12
5 max;
6,
2 3 17,
3 10;
0, 0.
F x x
xx
xx
xx
xx
5.12.
12
12
12
12
12
3 2 max;
3 10,
5 6 47,
2 5 24;
0, 0.
F x x
xx
xx
xx
xx
5.13.
12
12
12
12
12
2 7 max;
5 2 24,
6 7 61,
5 14;
0, 0.
F x x
xx
xx
xx
xx
5.14.
12
12
12
12
12
2 max;
6 15,
7 5 52,
4 14;
0, 0.
F x x
xx
xx
xx
xx
51
5.15.
12
12
12
12
12
2 max;
6,
2 3 16,
3 8;
0, 0.
F x x
xx
xx
xx
xx
5.16.
12
12
12
12
12
3 max;
7,
4 5 33,
2 9;
0, 0.
F x x
xx
xx
xx
xx
5.17.
12
12
12
12
12
5 2 max;
3 9,
5 6 41,
2 5 19;
0, 0.
F x x
xx
xx
xx
xx
5.18.
12
12
12
12
12
5 max;
3 2 12,
5 8 48,
3 11;
0, 0.
F x x
xx
xx
xx
xx
5.19.
12
12
12
12
12
3 max;
3 14,
7 6 62,
4 12;
0, 0.
F x x
xx
xx
xx
xx
5.20.
12
12
12
12
12
3 4 max;
3 11,
7 6 55,
4 11;
0, 0.
F x x
xx
xx
xx
xx
5.21.
12
12
12
12
12
6 max;
3 12,
8,
2 9;
0, 0.
F x x
xx
xx
xx
xx
5.22.
12
12
12
12
12
2 5 max;
3 10,
5 6 47,
2 5 24;
0, 0.
F x x
xx
xx
xx
xx
5.23.
12
12
12
12
12
2 max;
3 5,
7 3 65,
5 23;
0, 0.
F x x
xx
xx
xx
xx
5.24.
12
12
12
12
12
4 max;
4 10,
2 5 32,
2 2;
0, 0.
F x x
xx
xx
xx
xx
5.25.
12
12
12
12
12
3 5 max;
2 2,
6 38,
2 3 18;
0, 0.
F x x
xx
xx
xx
xx
5.26.
12
12
12
12
12
2 3 max;
5 22,
7 6 63,
2 5 18;
0, 0.
F x x
xx
xx
xx
xx
52
5.27.
12
12
12
12
12
4 3 max;
5 2,
2 12,
4 13;
0, 0.
F x x
xx
xx
xx
xx
5.28
12
12
12
12
12
3 2 max;
5 2 24,
6 5 47,
3 10;
0, 0.
F x x
xx
xx
xx
xx
5.29.
12
12
12
12
12
3 4 max;
2 10,
2 11,
5 14;
0, 0.
F x x
xx
xx
xx
xx
5.30.
12
12
12
12
12
4 max;
3 9,
7,
2 8;
0, 0.
F x x
xx
xx
xx
xx
5.31.
12
12
2
12
12
2 max;
2,
2,
2 1;
0, 0.
F x x
xx
x
xx
xx
Упражнение 6. Найдите решение задачи симплексным методом,
проиллюстрировав его графически. Составьте двойственную задачу
и, на основании теорем двойственности, сделайте вывод о ее реше-
нии, подтвердив его графически.
.0,0
,33
,242
min,122
21
21
21
21
xx
xx
xx
xxF
Решение.
Решим задачу симплекс-методом. Для этого приведем задачу к
каноническому виду:
.0,0,0,0
,33
,242
min,122
4321
421
321
21
xxxx
xxx
xxx
xxF
Так как в уравнениях отсутствуют базисные переменные, то вво-
дим в них и в целевую функцию искусственные переменные r
1
и r
2
и
приходим к следующей задаче:
.0,0,0,0,0,0
,33
,242
min,122
214321
2421
1321
2121
rrxxxx
rxxx
rxxx
MrMrxxF
53
Внесѐм данные модифицированной задачи в симплекс-таблицу 40
(подробно этот метод описан в упражнении 5).
Базисным решением в таком случае будет X
1
= (0; 0; 0; 0) (точка
X
1
(0; 0) рис. 6), при котором целевая функция будет F равна 0, то есть
F
1
= 0.
Для базисного решения X
1
критерий оптимальности не выполнен,
так как в столбце, соответствующем свободной переменной x
2
, в M-
функции есть положительный элемент (+1).
Таблица 40
План
Базис
С
б
b
i
2
12
0
0
M
M
d
i
x
1
x
2
x
3
x
4
r
1
r
2
I
r
1
M
2
–2
4
–1
0
1
0
1/2
r
2
M
3
1
–3
0
–1
0
1
F
=
0
–2
–12
0
0
0
0
M
=
5
–1
1
–1
–1
0
0
Чтобы перейти к построению плана II, нужно перевести перемен-
ную x
2
в базис. Тогда столбец x
2
– разрешающий столбец. Заполняем
столбец оценочных отношений d
i
, и в качестве разрешающей строки
выбираем ту, которой соответствует базисная переменная r
1
(с наи-
меньшим элементом в столбце оценочных отношений), то есть базис-
ными в плане II будут x
2
, r
1
.
Вычисляем элементы новой симплекс-таблицы 41.
Таблица 41
План
Базис
С
б
b
i
2
12
0
0
M
M
d
i
x
1
x
2
x
3
x
4
r
1
r
2
II
x
2
12
1/2
–1/2
1
–1/4
0
1/4
0
r
2
M
9/2
–1/2
0
–3/4
–1
3/4
1
F
=
6
–8
0
–3
0
1/4
0
M
=
9/2
–1/2
0
–3/4
–1
–1/4
0
54
Базисным решением в таком случае будет X
2
= (0; 1/2; 0; 0) (точка
X
2
(0; 1/2) рис. 6), при котором целевая функция будет F равна 6,
то есть F
2
= 6.
Для базисного решения X
2
критерий оптимальности M-функции
выполнен, однако искусственная переменная r
2
осталась в базисе. Это
означает, что задача не имеет допустимых решений, то есть условия
исходной задачи противоречивы.
Проиллюстрируем графически процесс решения (рис. 6). Подроб-
но этот метод был описан в упражнении 1.
Рис. 6
Составим двойственную задачу. Преобразовывать систему нера-
венств не нужно, так как цель задачи – минимизация, а знаки в систе-
ме «».
Составим расширенную матрицу системы и транспонируем ее:
)(32
1234
212
~
)(122
331
242
YZXF
T
.
Таким образом, получили двойственную задачу:
.0,0
,1234
,22
max,32
21
21
21
21
yy
yy
yy
yyZ
0
1
1
2
2
3
3
x
1
x
2
9
8
7
6
6
5
5
4
4
(2)
(1)
55
Так как условия исходной задачи противоречивы, то в двойствен-
ной задаче либо функция неограниченна, либо условия протии-
воречивы.
Подтвердим это утверждение графически (рис. 7).
Рис. 7
Ответ: Условия исходной задачи противоречивы.
Z
.
Задача 6. Найдите решение задачи симплексным методом, про-
иллюстрировав его графически. Составьте двойственную задачу и, на
основании теорем двойственности, сделайте вывод о ее решении,
подтвердив его графически.
6.1.
12
12
12
12
3 min;
5 4 1,
3 2;
0, 0.
F x x
xx
xx
xx
6.2.
12
12
1
12
2 min;
2 3 6,
1;
0, 0.
F x x
xx
x
xx
0
1
1
2
2
3
3
y
1
y
2
6
6
5
5
4
4
Y
1
Y
2
(1)
(2)
n
56
6.3.
12
12
12
12
3 2 min;
4 3 6,
2 3;
0, 0.
F x x
xx
xx
xx
6.4.
12
12
2
12
2 6 min;
3 3,
2;
0, 0.
F x x
xx
x
xx
6.5.
12
12
12
12
2 min;
2,
2 3 8;
0, 0.
F x x
xx
xx
xx
6.6.
12
1
12
12
3 min;
3,
2 4;
0, 0.
F x x
x
xx
xx
6.7.
12
12
12
12
2 3 min;
2 2,
4 3 12;
0, 0.
F x x
xx
xx
xx
6.8.
12
12
1
12
6 3 min;
2 2,
3 1;
0, 0.
F x x
xx
x
xx
6.9.
12
12
12
12
2 5 min;
2 3 18,
3 3;
0, 0.
F x x
xx
xx
xx
6.10.
12
1
12
12
3 2 min;
2,
3 5;
0, 0.
F x x
x
xx
xx
6.11.
12
12
12
12
2 3 min;
2 2,
3 4;
0, 0.
F x x
xx
xx
xx
6.12.
12
12
1
12
4 3 min;
3,
2 4;
0, 0.
F x x
xx
x
xx
6.13.
12
12
12
12
4 3 min;
3 2,
5;
0, 0.
F x x
xx
xx
xx
6.14.
12
12
1
12
3 4 min;
2 4,
3;
0, 0.
F x x
xx
x
xx
6.15.
12
12
12
12
2 5 min;
5 2 6,
2 2;
0, 0.
F x x
xx
xx
xx
6.16.
12
12
2
12
3 4 min;
3,
2 4;
0, 0.
F x x
xx
x
xx
57
6.17.
12
12
2
12
2 min;
2 2,
3;
0, 0.
F x x
xx
x
xx
6.18.
12
12
2
12
4 3 min;
2 4,
3;
0, 0.
F x x
xx
x
xx
6.19.
12
12
12
12
3 min;
2 4,
3 9;
0, 0.
F x x
xx
xx
xx
6.20.
12
12
2
12
10 12 min;
3 3 2,
4 5;
0, 0.
F x x
xx
x
xx
6.21.
12
12
12
12
3 min;
5 3,
2;
0, 0.
F x x
xx
xx
xx
6.22.
12
12
2
12
5 2 min;
4 3 12,
3 10;
0, 0.
F x x
xx
x
xx
6.23.
12
12
12
12
2 min;
5 2,
3;
0, 0.
F x x
xx
xx
xx
6.24.
12
12
1
12
7 3 min;
2 4,
5 7;
0, 0.
F x x
xx
x
xx
6.25.
12
12
12
12
2 min;
3 3,
2 4;
0, 0.
F x x
xx
xx
xx
6.26.
12
12
1
12
2 5 min;
3 4 12,
3 10;
0, 0.
F x x
xx
x
xx
6.27.
12
12
12
12
4 min;
3 2 8,
4 1;
0, 0.
F x x
xx
xx
xx
6.28.
12
12
1
12
12 10 min;
3 3 2,
4 5;
0, 0.
F x x
xx
x
xx
6.29.
12
12
12
12
5 min;
2,
2 4;
0, 0.
F x x
xx
xx
xx
6.30.
12
12
2
12
3 7 min;
2 4,
5 7;
0, 0.
F x x
xx
x
xx
6.31
12
12
12
12
2 12 min;
2 4 2,
3 3;
0, 0.
F x x
xx
xx
xx
58
Упражнение 7. Найдите решение задачи графически и двойст-
венным симплекс-методом.
.0,0
,103
,113
,1623
min,2
21
21
21
21
21
xx
xx
xx
xx
xxF
Решение.
Решим задачу графически (рис. 8). Подробно этот метод был опи-
сан в упражнении 1.
Рис. 8
X* = (4; 2); F
min
= 8.
Для аналитического решения поставленной задачи ответим на во-
прос «Что выгоднее решать, прямую или двойственную задачу ли-
нейного программирования?».
n
x
2
12
11
10
9
8
7
6
5
4
3
2
1
0 1 2 3 4 5 6 7 8 9 10 11 x
1
X*
59
При решении прямой задачи симплекс-методом необходимо вве-
сти три дополнительные x
3
, x
4
, x
5
и три искусственные переменные r
1
,
r
2
, r
3
, а именно:
.0,0,0,0,0,0,0,0
,103
,113
,1623
min,2
32154321
3521
2421
1321
32121
rrrxxxxx
rxxx
rxxx
rxxx
MrMrMrxxF
Таким образом, не раньше, чем на четвѐртом шаге, базисное ре-
шение прямой задачи окажется допустимым решением.
Теперь составим двойственную задачу. Преобразовывать систему
неравенств не надо, так как цель задачи – минимизация, а знаки в
системе – «
».
Составим расширенную матрицу и транспонируем ее:
)(101116
2312
1133
~
)(21
1031
1113
1623
YZ
T
XF
.
Таким образом, получили двойственную задачу:
.0,0,0
,232
,133
max,101116
321
321
321
321
yyy
yyy
yyy
yyyZ
Приведем задачу к каноническому виду:
.0,0,0,0,0
,232
,133
max,101116
54321
5321
4321
321
yyyyy
yyyy
yyyy
yyyZ
.
Отметим, что для этого необходимо ввести две дополнительные
переменные и ни одной искусственной. Это приводит нас к тому, что
в данном случае уже на первом шаге получается допустимое ре-
шение.
Метод, при котором вначале симплекс-методом решается двойст-
венная задача, а затем оптимальное решение прямой задачи находит-
ся с помощью теорем двойственности, называется двойственным
симплекс-методом.