Кирсанова О.В., Семёнова Г.А. Математическое программирование (типовой расчёт)
Подождите немного. Документ загружается.
40
столбец оценочных отношений d
i
, и в качестве разрешающей строки
выбираем ту, которой соответствует базисная переменная x
3
(с наи-
меньшим элементом в столбце оценочных отношений), то есть базис-
ными в плане II будут x
2
, x
4
.
Вычисляем элементы новой симплекс-таблицы 34.
Таблица 34
План
Базис
С
б
b
i
2
3
0
0
d
i
x
1
x
2
x
3
x
4
II
x
2
3
2
–2
1
1
0
x
4
0
18
–2
0
3
1
F
=
6
–8
0
3
0
Базисным решением на втором шаге будет X
2
= (0; 2; 0; 18) (точка
X
2
(0; 2) рис. 4), при котором целевая функция будет F равна 6, то есть
F
2
= 6.
Для базисного решения X
2
критерий оптимальности не выполнен,
так как в столбце, соответствующем свободной переменной x
1
, в це-
левой функции есть отрицательный элемент (–8).
Чтобы перейти к построению плана III, нужно перевести пере-
менную x
1
в базис. Тогда столбец x
1
– разрешающий столбец. Запол-
няем столбец оценочных отношений d
i
.
Так как все d
i
= ∞, то переменная x
1
может расти неограниченно.
А вместе с ней неограниченно возрастет и функция, то есть F* = .
Проиллюстрируем процесс решения графически (рис. 4). Подроб-
но этот метод был описан в упражнении 1.
Составим двойственную задачу. Преобразовывать систему нера-
венств не нужно, так как цель задачи – максимизация, а знаки в сис-
теме – «
».
Составим расширенную матрицу и транспонируем ее:
)(122
331
242
~
)(32
1234
212
YZXF
T
.
41
Таким образом, получили двойственную задачу:
.0,0
,33
,242
min,122
21
21
21
21
yy
yy
yy
xyZ
Так как функция исходной задачи неограниченна, то условия
двойственной задачи противоречивы, то есть она не имеет допусти-
мых решений.
Рис. 4
Ответ:
F
.
Условия двойственной задачи противоречивы.
Задача 4. Найдите решение задачи симплексным методом, про-
иллюстрировав его графически. Составьте двойственную задачу и, на
основании теорем двойственности, сделайте вывод о ее решении.
4.1.
12
12
12
12
3 2 max;
3 1,
2 3;
0, 0.
F x x
xx
xx
xx
4.2.
12
12
12
12
2 max;
1,
3 4;
0, 0.
F x x
xx
xx
xx
0
1
1
2
2
3
3
x
1
x
2
6
6
5
5
4
4
X
1
X
2
(1)
(2)
n
42
4.3.
12
12
12
12
2 max;
4,
2 4;
0, 0.
F x x
xx
xx
xx
4.4.
12
12
12
12
2 max;
3 4,
2;
0, 0.
F x x
xx
xx
xx
4.5.
12
12
12
12
3 max;
4 3,
2 6;
0, 0.
F x x
xx
xx
xx
4.6.
12
12
12
12
2 3 max;
2 3,
2 3 6;
0, 0.
F x x
xx
xx
xx
4.7.
12
12
12
12
5 2 max;
3,
2 5;
0, 0.
F x x
xx
xx
xx
4.8.
12
12
12
12
3 4 max;
2 4,
2 3 8;
0, 0.
F x x
xx
xx
xx
4.9.
12
12
12
12
2 max;
2,
2 3 8;
0, 0.
F x x
xx
xx
xx
4.10.
12
12
12
12
2 3 max;
3 3,
3 1;
0, 0.
F x x
xx
xx
xx
4.11.
12
12
12
12
3 4 max;
3 1,
3 4 6;
0, 0.
F x x
xx
xx
xx
4.12.
12
12
12
12
5 3 max;
4 1,
2 5;
0, 0.
F x x
xx
xx
xx
4.13.
12
12
12
12
3 4 max;
3 2 ,4
2 4;
0, 0.
F x x
xx
xx
xx
4.14.
12
12
12
12
5 3 max;
3 2 4,
5 3;
0, 0.
F x x
xx
xx
xx
4.15.
12
12
12
12
3 2 max;
4 3 6,
2 3;
0, 0.
F x x
xx
xx
xx
4.16.
12
12
12
12
3 max;
3 2 2,
3 4;
0, 0.
F x x
xx
xx
xx
43
4.17.
12
12
12
12
3 max;
2 1,
4 4;
0, 0.
F x x
xx
xx
xx
4.18.
12
12
12
12
3 2 max;
4 2,
4;
0, 0.
F x x
xx
xx
xx
4.19.
12
12
12
12
2 3 max;
5 4,
2 1;
0, 0.
F x x
xx
xx
xx
4.20.
12
12
12
12
3 max;
5 1,
3 2;
0, 0.
F x x
xx
xx
xx
4.21.
12
12
12
12
3 2 max;
5 2 4,
3 3;
0, 0.
F x x
xx
xx
xx
4.22.
12
12
12
12
2 3 max;
3 1,
4 2;
0, 0.
F x x
xx
xx
xx
4.23.
12
12
12
12
4 3 max;
3 2,
5;
0, 0.
F x x
xx
xx
xx
4.24.
12
12
12
12
2 5 max;
5 2 6,
2 2;
0, 0.
F x x
xx
xx
xx
4.25.
12
12
12
12
3 max;
3 2 6,
2 3 4;
0, 0.
F x x
xx
xx
xx
4.26.
12
12
12
12
4 max;
5 2 2,
3 5;
0, 0.
F x x
xx
xx
xx
4.27.
12
12
12
12
4 max;
3 2 8,
4 1;
0, 0.
F x x
xx
xx
xx
4.28.
12
12
12
12
2 max;
5 2,
3;
0, 0.
F x x
xx
xx
xx
4.29.
12
12
12
12
3 max;
5 3,
2;
0, 0.
F x x
xx
xx
xx
4.30.
12
12
12
12
3 4 max;
4 4,
1;
0, 0.
F x x
xx
xx
xx
4.31.
12
12
12
12
2 3 max;
2 2,
4 3 12;
0, 0.
F x x
xx
xx
xx
44
Упражнение 5. Найдите решение задачи симплексным методом,
проиллюстрировав его графически. Составьте двойственную задачу
и, на основании теорем двойственности, сделайте вывод
о ее решении.
.0,0
,12
,2
,2
max,2
21
21
2
21
21
xx
xx
x
xx
xxF
Решение.
Решим задачу симплекс-методом. Для этого приведем задачу к
каноническому виду:
.0,0,0,0,0
,12
,2
,2
max,2
54321
521
42
321
21
xxxxx
xxx
xx
xxx
xxF
В 1-ом и 3-ем равенствах нет базисных переменных (входящих
только в одно уравнение системы ограничений и только с коэффици-
ентом «1»).
Поэтому введѐм в эти уравнения искусственные (не имеющие
«экономического» смысла в данной задаче) неотрицательные пере-
менные r
1
, r
2
, которые в оптимальном решении обязательно станут
равными нулю. В целевую функцию добавляем «штраф» (–Mr
1
– Mr
2
)
за использование искусственных переменных (в случае минимизации
целевой функции добавляется штраф Mr
1
+ Mr
2
), где M 0.
В результате получим задачу линейного программирования:
.0,0,0,0,0,0,0
,12
,2
,2
max,2
2154321
2521
42
1321
2121
rrxxxxx
rxxx
xx
rxxx
MrMrxxF
Очевидно, что в такой задаче переменные r
1
, x
4
, r
2
можно исполь-
зовать в качестве базисных.
45
Решим модифицированную задачу симплекс-методом (подробно
этот метод был описан в упражнении 2). Единственным отличием яв-
ляется наличие M-строки, которая вычисляется по формуле:
Новая (F+M)-строка = Исходная F-строка – M·r
1
-строка – M r
2
-строка.
Выполним операцию в данном примере:
Исходная F -строка:
MM000210
M·r
1
-строка:
0002 MMMMM
M·r
2
-строка:
MMMMM 0002
Новая (F+M)-строка:
00000320130 MMMMM
Внесѐм данные задачи в симплекс-таблицу 35.
Таблица 35
План
Базис
С
б
b
i
1
2
0
0
0
–M
–M
d
i
x
1
x
2
x
3
x
4
x
5
r
1
r
2
I
r
1
–M
2
1
1
–1
0
0
1
0
2
x
4
0
2
0
1
0
1
0
0
0
2
r
2
–M
1
–1
2
0
0
–1
0
1
1/2
F
=
0
–1
–2
0
0
0
0
0
M
=
–3
0
–3
1
0
1
0
0
Базисным решением на первом шаге будет X
1
= (0; 0; 0; 2; 0) (точ-
ка X
1
(0; 0) рис. 5), при котором целевая функция будет F равна 0, то
есть F
1
= 0.
Базисное решение X
1
не является допустимым, так как в базисе
присутствуют искусственные переменные, поэтому критерий опти-
мальности для F-функции не выполнен. Сначала нужно оптимизиро-
вать M-функцию. В этой функции есть отрицательный элемент (–3), а
значит, M-функция не оптимальна.
Чтобы перейти к построению плана II, нужно перевести перемен-
ную x
2
в базис. Тогда столбец x
2
– разрешающий столбец. Заполняем
столбец оценочных отношений d
i
, и в качестве разрешающей строки
выбираем ту, которой соответствует базисная переменная r
2
(с наи-
меньшим элементом в столбце оценочных отношений), то есть базис-
ными в плане II будут r
1
, x
4
, x
2
.
46
Отметим, что уже первая итерация исключила из базисного реше-
ния искусственную переменную r
2
, что является результатом частич-
ного включения «штрафа» в целевую функцию. Это позволяет в
дальнейшем не учитывать переменную r
2
в симплекс-таблице.
Вычисляем элементы новой симплекс-таблицы 36.
Таблица 36
План
Базис
С
б
b
i
1
2
0
0
0
–M
–M
d
i
x
1
x
2
x
3
x
4
x
5
r
1
r
2
II
r
1
–M
3/2
3/2
0
–1
0
1/2
1
–1/2
1
x
4
0
3/2
1/2
0
0
1
1/2
0
–1/2
3
x
2
2
1/2
–1/2
1
0
0
–1/2
0
1/2
F
=
1
–2
0
0
0
–1
0
1
M
=
–3/2
–3/2
0
1
0
–1/2
0
3/2
Базисным решением на втором шаге будет X
2
= (0; 1/2; 0; 3/2; 0)
(точка X
2
(0; 1/2) рис. 5), при котором целевая функция будет F равна
1, то есть F
2
= 1.
Базисное решение X
2
всѐ ещѐ не является допустимым. Поэтому
продолжаем оптимизировать M-функцию. В столбцах, соответст-
вующих свободным переменным x
1
и x
5
, в M-функции есть отрица-
тельные элементы (–3/2 и –1/2); выбираем из них наименьший.
Чтобы перейти к построению плана III, нужно перевести пере-
менную x
1
в базис. Тогда столбец x
1
– разрешающий столбец. Запол-
няем столбец оценочных отношений d
i
, и в качестве разрешающей
строки выбираем ту, которой соответствует базисная переменная r
1
(с наименьшим элементом в столбце оценочных отношений), то есть
базисными в плане III будут x
1
, x
4
, x
2
.
Отметим, что вторая итерация исключила из базисного решения и
вторую искусственную переменную r
1
, что привело к полному вклю-
чению штрафа в целевую функцию и получению допустимого реше-
ния X
3
. Это позволяет в дальнейшем не учитывать переменную r
1
и
M-функцию в симплекс-таблице.
Вычисляем элементы новой симплекс-таблицы 37.
47
Таблица 37
План
Базис
С
б
b
i
1
2
0
0
0
–M
–M
d
i
x
1
x
2
x
3
x
4
x
5
r
1
r
2
III
x
1
1
1
1
0
–2/3
0
1/3
2/3
–1/3
x
4
0
1
0
0
1/3
1
1/3
–1/3
–1/3
3
x
2
2
1
0
1
–1/3
0
–1/3
1/3
1/3
F
=
3
0
0
–4/3
0
–1/3
4/3
1/3
M
=
0
0
0
0
0
0
1
1
Базисным решением на третьем шаге будет X
3
= (1; 1; 0; 1; 0)
(точка X
3
(1; 1) рис. 5), при котором целевая функция будет F равна 3,
то есть F
3
= 3.
Для базисного решения X
3
критерий оптимальности не выполнен,
так как в столбцах, соответствующих свободным переменным x
3
и x
5
,
в целевой функции есть отрицательные элементы (– 4/3 и – 1/3); вы-
бираем из них наименьший.
Чтобы перейти к построению плана IV, нужно перевести пере-
менную x
3
в базис. Тогда столбец x
3
– разрешающий столбец. Запол-
няем столбец оценочных отношений d
i
, и в качестве разрешающей
строки выбираем ту, которой соответствует базисная переменная x
4
(с
наименьшим элементом в столбце оценочных отношений), то есть ба-
зисными в плане IV будут x
1
, x
3
, x
2
.
Вычисляем элементы новой симплекс-таблицы 38.
Таблица 38
План
Базис
С
б
b
i
1
2
0
0
0
d
i
x
1
x
2
x
3
x
4
x
5
IV
x
1
1
3
1
0
0
2
1
x
3
0
3
0
0
1
3
1
x
2
2
2
0
1
0
1
0
F
=
7
0
0
0
4
1
Базисным решением на четвѐртом шаге будет X
4
= (3; 2; 3; 0; 0)
(точка X
3
(3; 2) рис. 5), при котором целевая функция будет F равна 7,
то есть F
4
= 7.
48
Для базисного решения X
4
выполнен критерий оптимальности,
так как в целевой функции нет отрицательных элементов. Кроме того,
все коэффициенты при свободных переменных (x
4
, x
5
) отличны
от нуля, следовательно, полученное решение X
4
оптимально
и единственно.
Таким образом, X* = (3; 2; 3; 0; 0), F
max
= 7.
Проиллюстрируем графически процесс решения (рис. 5). Подроб-
но этот метод был описан в упражнении 1.
Рис. 5
Составим двойственную задачу, для чего преобразуем систему
неравенств. Так как цель задачи – максимизация, то знаки в системе
должны быть «
». Поэтому 1-ое и 3-е неравенства умножим на (–1).
.0,0
,12
,2
,2
max,2
21
21
2
21
21
xx
xx
x
xx
xxF
Составим расширенную матрицу и транспонируем ее:
)(122
2211
1101
~
)(21
121
210
211
YZ
T
XF
.
x
2
3
2
1
X
2
X
1
n
X
3
X
4
0 1 2 3 x
1
49
Таким образом, получили двойственную задачу:
.0,0,0
,22
,1
min,22
321
321
21
321
yyy
yyy
yy
yyyZ
Установим соответствие между переменными и найдем решение
двойственной задачи (табл. 39).
Таблица 39
Абсолютные значения коэффициентов
при переменных целевой функции исходной задачи,
выраженной через свободные переменные еѐ оптимального решения
основные переменные
дополнительные переменные
x
1
x
2
x
3
x
4
x
5
0
0
0
4
1
y
4
y
5
y
1
y
2
y
3
дополнительные переменные
основные переменные
компоненты оптимального решения двойственной задачи
Y* = (0; 4; 1; 0; 0); Z* = F* = 7.
Контроль: Z* = –2 · 0 + 2·4 – 1·1 = 7.
Ответ: X* = (3; 2; 3; 0; 0); F
max
= 7.
Y* = (0; 4; 1; 0; 0); Z
min
= 7.
Задача 5. Найдите решение задачи симплексным методом, про-
иллюстрировав его графически. Составьте двойственную задачу и, на
основании теорем двойственности, сделайте вывод о ее решении.
5.1.
12
12
12
12
12
3 max;
3 8,
2 3 17,
5 12;
0, 0.
F x x
xx
xx
xx
xx
5.2.
12
12
12
2
12
4 max;
2 3 9,
2 11 33,
1;
0, 0.
F x x
xx
xx
x
xx