Мат_модели
.pdf
|
|
B1 |
|
|
|
|
|
|
B2 |
|
|
B3 |
|
|
B4 |
|
|
|
ai |
|
|
ui |
|
|
||||||
A1 |
|
|
|
|
11 |
|
|
5 |
|
|
M |
|
|
|
2 |
80 |
|
0 |
|
|
||||||||||
|
− M |
|
|
|
|
|
|
−8 |
|
|
|
|
|
60 |
|
20 |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
A2 |
|
|
|
|
M |
|
|
|
|
4 |
|
|
5 |
|
|
|
9 |
170 |
|
7 |
|
|
||||||||
|
18 − 2M |
|
|
|
10 |
|
|
|
|
|
120 |
|
40 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
A3 |
70 |
|
|
9 |
|
|
|
8 |
|
|
7 |
30 |
M |
100 |
|
|
M −2 |
|
|
|||||||||||
|
|
|
|
|
|
|
|
M −13 |
|
|
|
M −11 |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
bj |
70 |
|
|
|
|
|
10 |
|
|
|
180 |
|
90 |
|
400 |
|
|
|
|
|
||||||||||
v j |
|
11 − M |
|
|
|
−3 |
|
|
−2 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|||||||||
Максимальную положительную оценку |
33 |
= M −11 имеем в |
клетке A3 B3 |
|||||||||||||||||||||||||||
и строим цикл, соединяющий клетки |
A3 B3 , |
A2 B3 , A2 B4 |
и A3 B4 : |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
120 |
|
|
|
|
|
|
|
|
|
40 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
+ |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Так как |
|
= min(30,120) = 30 , делаем перестановку по циклу |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
90 |
|
|
|
|
|
|
|
|
|
70 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
|
|
– |
|
|
|
|
+ |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
и получаем транспортную таблицу с новым планом |
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
B1 |
|
|
|
|
|
|
|
B2 |
|
B3 |
|
|
B4 |
|
|
ai |
|
ui |
|
|||||||||
A1 |
|
|
|
|
11 |
|
|
5 |
|
|
M |
|
|
|
2 |
|
80 |
|
|
0 |
|
|
||||||||
|
−11 |
|
|
|
|
|
|
|
|
−8 |
|
|
|
|
60 |
|
|
20 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
A2 |
|
|
|
|
M |
|
|
|
4 |
|
|
5 |
|
|
|
9 |
|
170 |
|
|
7 |
|
|
|||||||
|
7 − M |
|
|
|
|
|
10 |
|
|
|
|
|
90 |
|
|
70 |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
A3 |
|
|
|
|
|
9 |
|
|
8 |
|
|
7 |
|
|
|
M |
|
100 |
|
|
9 |
|
|
|||||||
70 |
|
|
|
|
|
|
|
|
− 2 |
|
|
|
|
30 |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
bj |
70 |
|
|
|
|
|
10 |
|
|
|
180 |
|
|
|
90 |
|
400 |
|
|
|
|
|
||||||||
v j |
0 |
|
|
|
|
|
|
−3 |
|
−2 |
|
|
2 |
|
|
|
|
|
|
|
|
|
||||||||
Находим потенциалы: u1 = 0 |
|
v4 |
= 2 |
|
u2 = 7 |
|
v3 = −2 |
, v2 = −3 ; |
||||||||||||||||||||||
v3 = −2 |
u3 |
= 9 |
|
|
v1 = 0 , |
а оценки для свободных клеток 11 = −11 < 0 , |
||||||||||||||||||||||||
12 = −8 < 0 , |
21 = 7 − M < 0, |
32 = −2 < 0, |
34 |
=11− M < 0. Так как все оценки |
отрицательны, то данная таблица – заключительная, и увеличивая пере-
80
возку в клетке A3 B2 на 50, получим оптимальный план перевозок, удов-
0 |
0 |
60 |
20 |
|
|
летворяющий всем ограничениям задачи: X = |
0 |
10 |
90 |
70 |
и |
|
70 |
50 |
30 |
0 |
|
|
|
F ( X * ) = 4 60 + 2 20 + 4 10 +5 90 +9 70 +9 70 + 7 30 = 2240.
Пример 9. |
Найти решение транспортной задачи |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
B2 |
|
B3 |
|
B4 |
|
|
ai |
|
|
|
|
A1 |
|
11 |
5 |
|
|
4 |
|
2 |
|
80 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A2 |
|
1 |
4 |
|
|
5 |
|
9 |
|
170 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A3 |
|
9 |
8 |
|
|
7 |
|
10 |
|
150 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
70 |
60 |
|
180 |
|
90 |
|
|
400 |
|
|
|
|
если из A1 в B4 перевозки запрещены, а из A2 |
в B4 |
должно быть завезено |
||||||||||||
не менее 40 ед. груза, а из A3 в B3 |
– не более 50 ед. груза. |
|
|
|||||||||||
Решение. Поскольку из A1 |
в B4 перевозки не могут быть осущест- |
|||||||||||||
влены, |
то тариф в A1B4 считаем равным M . Запасы A2 и потребности B4 |
|||||||||||||
уменьшаем на 40, а также вводим дополнительного потребителя B33 по- |
||||||||||||||
требностями 180 −50 =130 . Соответственно, в клетке A3B33 стоимость пе- |
||||||||||||||
ревозок считаем равной M , а потребности B3 |
приравниваем к 50. Полу- |
|||||||||||||
чаем таблицу |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
B2 |
|
B3 |
|
B4 |
|
|
B33 |
|
|
ai |
|
A1 |
|
11 |
5 |
|
|
4 |
|
M |
|
|
4 |
|
80 |
|
|
|
0 |
|
50 |
|
|
|
30 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
A2 |
|
1 |
4 |
|
|
5 |
|
9 |
|
|
5 |
|
130 |
|
|
70 |
60 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
A3 |
|
9 |
8 |
|
|
7 |
50 |
10 |
100 |
M |
|
150 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
bj |
|
70 |
60 |
|
50 |
|
50 |
|
|
130 |
|
|
|
|
Найдем начальное опорное решение методом минимального тари- |
||||||||||||||
фа. В клетку A2 B1 |
вводим максимально возможную перевозку 70, в клет- |
|||||||||||||
ку A2 B2 |
–60, A1B3 |
– 50, A1B33 |
– 30, A3B4 – 50 и A3B33 |
– 100. Поскольку план |
81
вырожденный, клетку A1B2 |
|
считаем занятой с нулевой перевозкой. Нахо- |
|||||||||||||||||||||
дим потенциалы и оценки |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
|
B2 |
|
|
B3 |
|
|
B4 |
|
B33 |
|
ai |
ui |
|
|||||||
A1 |
|
11 |
5 |
|
|
4 |
|
|
M |
|
|
|
4 |
80 |
0 |
|
|||||||
|
−9 |
0 |
|
50 |
|
|
|
|
30 |
|
|
|
|||||||||||
|
|
|
|
|
|
14-2M |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
A2 |
|
1 |
4 |
|
|
5 |
|
|
|
9 |
|
|
|
|
5 |
130 |
−1 |
|
|||||
|
70 |
|
60 |
|
|
− 2 |
|
|
|
|
4 − M |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
A3 |
|
9 |
8 |
|
|
|
7 |
|
|
|
10 |
|
|
|
M |
150 |
M − 4 |
|
|||||
|
M −11 |
|
|
M −7 |
|
|
M −7 |
|
|
50 |
|
|
100 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
bj |
|
70 |
|
60 |
|
|
|
50 |
|
|
50 |
|
|
130 |
|
|
|
|
|||||
v j |
|
2 |
|
5 |
|
|
|
4 |
|
|
|
14 − M |
4 |
|
|
|
|
||||||
Из |
|
двух |
клеток |
с |
максимальной |
|
положительной |
оценкой |
|
||||||||||||||
33 = 32 = M −7 выбираем клетку |
A3B3 (так как там меньший тариф) и |
||||||||||||||||||||||
строим цикл, соединяющий клетки |
|
A3 B3 , A1B3 , A1B33 |
и A3B33 : |
|
|
||||||||||||||||||
|
|
|
|
50 |
|
|
|
|
30 |
|
|
|
|
|
|||||||||
|
|
|
|
|
– |
+ |
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
– |
100 |
|
|
|
|
|
||
Так как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
= min(50,100) = 50 , делаем перестановку по циклу |
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
80 |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
– |
+ |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
50 |
+ |
|
|
|
|
|
– |
50 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
и получаем транспортную таблицу с новым планом |
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
B1 |
|
B2 |
|
|
B3 |
|
|
B4 |
|
B33 |
|
ai |
ui |
|
|||||||
A1 |
|
11 |
5 |
|
|
4 |
|
|
M |
|
|
|
4 |
|
|
|
|||||||
|
−9 |
0 |
|
|
7 − M |
|
|
14 − 2M |
|
80 |
|
|
80 |
0 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
A2 |
|
1 |
4 |
|
|
5 |
|
9 |
|
|
|
|
5 |
130 |
−1 |
|
|||||||
|
70 |
|
60 |
|
|
5 − M |
|
|
|
4 − M |
|
|
|
− 2 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
A3 |
|
9 |
8 |
|
|
|
7 |
|
10 |
|
|
|
M |
150 |
M − 4 |
|
|||||||
|
M −11 |
|
|
M −7 |
|
50 |
|
|
|
50 |
|
|
50 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
bj |
|
70 |
|
60 |
|
|
|
50 |
|
|
50 |
|
|
130 |
|
|
|
|
|||||
v j |
|
2 |
|
5 |
|
|
|
11 − M |
14 − M |
4 |
|
|
|
|
Цикл, построенный в клетке с максимальной положительной оценкой 32 = M −7 (соединяющий клетки A3B2 , A1B2 , A1B33 и A3B33 ) имеет вид
82
0 |
|
|
80 |
– |
+ |
||
|
+ |
– |
50 |
|
|
|
|
|
|
|
со знаком минус в клетке с нулевой перевозкой. Это означает, что клетка
A3B2 объявляется занятой (с нулевой перевозкой), |
а A1B2 – свободной. |
|||||||||||||||||||||||||
Для нового базиса считаем потенциалы и оценки и получаем |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
|
|
|
|
B2 |
|
B3 |
|
|
B4 |
|
|
|
B33 |
|
ai |
ui |
|
||||||
A1 |
|
|
|
11 |
|
|
5 |
|
|
|
|
4 |
|
|
|
M |
80 |
|
4 |
80 |
0 |
|
||||
|
− 2 − M |
|
|
7 − M |
|
|
7 − M |
|
|
14 − 2M |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
A2 |
|
70 |
|
1 |
60 |
4 |
|
|
|
|
5 |
|
|
|
9 |
|
|
|
|
5 |
130 |
M −8 |
|
|||
|
|
|
|
|
|
|
− 2 |
|
|
|
− 4 |
|
|
|
|
M −9 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
A3 |
|
|
|
9 |
0 |
8 |
50 |
|
7 |
50 |
|
10 |
|
|
M |
150 |
M − 4 |
|
||||||||
|
− 4 |
|
|
|
|
|
|
|
|
|
|
50 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
bj |
|
70 |
|
|
|
|
60 |
|
|
|
50 |
|
50 |
|
|
130 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
v j |
|
9 − M |
12 − M |
11 − M |
14 − M |
4 |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Имеем единственную положительную оценку 2,33 |
= M −9 в A2 B33 с цик- |
|||||||||||||||||||||||||
лом из клеток |
A2 B33 , |
A3B33 , A3B2 и A2 B2 : |
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
60 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
+ |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
0 |
|
+ |
|
|
|
|
|
– |
50 |
|
|
|
|
|
||||
Так как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
= min(50,60) = 50 , приходим к циклу |
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
50 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
– |
|
|
|
|
+ |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
50 |
+ |
|
|
|
|
|
– |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и получаем транспортную таблицу с новым планом. Вычисляем новые потенциалы и убеждаемся, что все оценки отрицательны. Данная таблица – заключительная, и увеличивая перевозку в клетке A2 B4 на 40, а так-
же складывая перевозки, записанные в соответствующих клетках столбцов B3 и B33 , получим
83
|
|
B1 |
|
|
B2 |
|
|
B3 |
|
|
|
B4 |
|
|
|
|
B33 |
|
ai |
ui |
|
|||||
A1 |
|
|
|
|
11 |
|
|
|
5 |
|
|
|
4 |
|
|
|
|
M |
|
80 |
|
4 |
80 |
0 |
|
|
|
−11 |
|
|
|
− 2 |
|
|
|
− 2 |
|
|
|
5 − M |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A2 |
|
70 |
|
|
1 |
10 |
|
4 |
|
|
|
5 |
|
|
|
|
|
9 |
|
|
|
5 |
130 |
1 |
|
|
|
|
|
|
|
|
|
− 2 |
|
|
|
−3 |
|
|
|
|
50 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
A3 |
|
|
|
|
9 |
50 |
|
8 |
50 |
|
7 |
50 |
|
10 |
|
|
M |
150 |
5 |
|
||||||
|
− 4 |
|
|
|
|
|
|
|
|
|
|
|
9 − M |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
bj |
|
70 |
|
60 |
|
50 |
|
|
|
50 |
|
|
|
|
130 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
v j |
|
0 |
|
3 |
|
2 |
|
|
|
5 |
|
|
|
|
4 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
80 |
0 |
|
|
|
||||
оптимальный |
план перевозок |
X = |
70 |
10 |
|
50 |
40 , удовлетворяющий |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
50 |
|
50 |
50 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
всем ограничениям задачи, и
z( X * ) = 4 80 +1 70 + 4 10 +5 50 +9 40 +8 50 + 7 50 +10 50 = 2290 .
Задачи для самостоятельного решения
|
|
B1 |
B2 |
B3 |
B4 |
ai |
|
|
A1 |
3 |
4 |
7 |
9 |
100 |
|
88. Найти решение транспортной задачи с таблицей |
A2 |
16 |
5 |
12 |
4 |
100 |
, |
|
A3 |
8 |
11 |
12 |
5 |
200 |
|
|
bj |
80 |
110 |
90 |
120 |
|
|
если из A |
в B |
и из A |
в B перевозки не могут быть осуществлены. |
|
|
|
||||
1 |
2 |
2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
B2 |
B3 |
B4 |
ai |
|
|
|
|
|
A1 |
5 |
14 |
6 |
21 |
120 |
|
89. Найти решение транспортной задачи с таблицей |
A2 |
20 |
13 |
17 |
14 |
90 |
, |
|||
|
|
|
|
A3 |
8 |
21 |
6 |
7 |
180 |
|
|
|
|
|
bj |
95 |
110 |
80 |
70 |
|
|
если из A3 |
в B2 |
перевозки не могут быть осуществлены, а из A1 в B4 должно быть |
||||||||
перевезено 70 ед. груза. |
|
|
|
|
|
|
|
|
84
|
|
|
|
B1 |
|
B2 |
B3 |
B4 |
|
ai |
|
||
|
|
A1 |
7 |
12 |
16 |
|
|
11 |
|
150 |
|
||
90. Найти решение транспортной задачи с таблицей |
|
A2 |
8 |
2 |
4 |
|
|
2 |
|
140 |
, |
||
|
|
A3 |
9 |
15 |
16 |
|
|
7 |
|
110 |
|
||
|
|
bj |
75 |
145 |
120 |
|
|
60 |
|
|
|
||
если из A2 в B4 перевозки запрещены, из A1 в B3 должно быть доставлено не менее |
|||||||||||||
40 ед. груза, а из A3 в B1 – не более 50 ед. груза. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
|
B2 |
B3 |
|
B4 |
|
ai |
|
|
|
|
A1 |
3 |
10 |
7 |
|
|
10 |
|
140 |
|
||
91. Найти решение транспортной задачи с таблицей |
|
A2 |
4 |
9 |
19 |
|
|
25 |
|
105 |
, |
||
|
|
A3 |
6 |
4 |
5 |
|
|
2 |
|
115 |
|
||
|
|
bj |
60 |
130 |
55 |
|
|
115 |
|
|
|||
если из A2 в B1 перевозки запрещены, из A1 в B2 должно быть перевезено 50 ед. |
|||||||||||||
груза, а из A3 в B4 – не более 20 ед. груза. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
|
B2 |
B3 |
B4 |
|
ai |
|
||
|
|
A1 |
|
9 |
|
6 |
7 |
|
|
11 |
|
70 |
|
92. Найти решение транспортной задачи с таблицей |
|
A2 |
|
3 |
|
14 |
25 |
|
|
19 |
|
170 |
, |
|
|
A3 |
|
2 |
|
8 |
17 |
|
|
10 |
|
140 |
|
|
|
bj |
|
90 |
|
60 |
160 |
|
|
70 |
|
|
|
если из A1 в B4 должно быть перевезено не менее 50 ед. груза, из |
A3 в B3 |
должно |
|||||||||||
быть перевезено не менее 30 ед. груза, а из A2 в B2 – 40 ед. груза. |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
|
B2 |
B3 |
|
B4 |
|
ai |
|
|
|
|
A1 |
12 |
|
14 |
11 |
|
|
20 |
|
90 |
|
|
93. Найти решение транспортной задачи с таблицей |
|
A2 |
3 |
|
4 |
5 |
|
|
9 |
|
155 |
, |
|
|
|
A3 |
2 |
|
18 |
14 |
|
|
12 |
|
125 |
|
|
|
|
bj |
100 |
75 |
75 |
120 |
|
|
|
||||
если из A1 в B4 должно быть перевезено не менее 40 ед. груза, из A2 |
в B3 |
– не более |
|||||||||||
50 ед. груза, а из A3 в B1 – не менее 60 ед. груза. |
|
|
|
|
|
|
|
|
|
|
|
|
|
85
ЭЛЕМЕНТЫ ВЫПУКЛОГО И
ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
§1. Задача квадратичного программирования
Рассмотрим задачу оптимизации вида
z(x )→ min (max), x X ,
где множество X Rn , как и в задаче линейного программирования, определяется системой линейных неравенств, а функция z является квадратичной (т.е. многочленом второй степени по переменным x1 , x2 ,K, xn ).
Задача математического программирования с квадратичной целевой функцией называется задачей квадратичного программирования.
Сформулируем сначала общую теорему об условиях оптимальности задачи квадратичного программирования.
Теорема (необходимое и достаточное условие экстремума). Пусть
X Rn – выпуклое множество, заданное системой линейных неравенств
g1 (x1 ,K, xn ) ≤ 0,
KKK
gm (x1 ,K, xn ) ≤ 0.
а z – выпуклая функция на X . Для того, чтобы точка x X являлась точкой глобального минимума функции z на X , необходимо и достаточно, чтобы существовал вектор λ = (λ1 , λ2 ,Kλm ) Rm , удовлетворяю-
щий условиям
Lx′i (x ,λ)= 0 , i =1,K,n ,
λj g j (x* )= 0 , λj ≥ 0 , j =1,K, m ,
86
m
где L(x,λ)= f (x) + ∑λj g j (x) – функция Лагранжа.
j =1
Замечание. Необходимое и достаточное условие экстремума является частным случаем теоремы Куна-Таккера о связи экстремумов выпуклой функции на выпуклом множестве со стационарными точками функции Лагранжа. Поэтому далее при его использовании мы будем ссылаться на теорему Куна-Таккера.
Пример 1. Графически найти решение задачи квадратичного программирования
z = (x −16)2 + ( y −12)2 → min
2x + y ≤19,−5y +3x ≥ −30,
5x − 4 y ≤15,
x ≥ 0, y ≥ 0,
и проверить выполнение условий теоремы Куна-Таккера.
Решение. Построим сначала на плоскости (x, y) выпуклое множе-
ство, заданное системой |
ограничений задачи. |
Изобразим прямые |
l1 : 2x + y =19 , l2 : 3x −5y = −30, |
l3 : 5x − 4 y =15 . Легко видеть, что нетривиаль- |
|
y |
|
|
l1 |
|
|
|
M |
|
|
B |
|
A |
K |
|
l2 |
|
|
|
C |
|
O |
D |
|
|
x |
|
|
l3 |
|
87
ные ограничения вместе с условиями x ≥ 0, y ≥ 0 задают пятиугольник
OABCD с угловыми точками O(0,0) , A(0,6), B(5,9), C(7,5) и D(3,0). Далее,
линиями уровня целевой функции z являются концентрические окружности (x −16)2 + ( y −12)2 = C с центром в точке M (16,12), лежащей, очевид-
но, вне многоугольника OABCD . Поэтому минимальное значение функции z достигается в точке касания с отрезком BC окружности соответствующего радиуса. Найдем точку касания K как точку пересечения прямой l1 и прямой m1 , перпендикулярной l1 и проходящей через точку
M (16,12). Так как прямая l1 определяется уравнением 2x + y =19 , а вектор нормали к ней, равный nr = (2,1), является направляющим вектором для
прямой m , то каноническим уравнением m является |
x−16 |
= |
y −12 |
, а общим |
||||
|
1 |
|||||||
1 |
|
|
1 |
2 |
|
|
||
x − 2 y = −8 . Точка пересечения K = l1 ∩m1 |
находится как решение системы |
|||||||
2x + y =19, |
K (6,7). |
|
|
|
|
|
||
|
− 2 y = −8. |
|
|
|
|
|
||
x |
|
|
|
|
|
|
|
|
Таким образом, решением задачи |
является |
точка |
x = (6,7) и |
|||||
z(x )= z(6,7)= (6 −16)2 + (7 −12)2 |
=125 . |
|
|
|
|
|
|
|
Проверим теперь, что точка x = (6,7) является решением системы,
определяемой необходимыми и достаточными условиями экстремума. Перепишем систему ограничений в виде
2x + y ≤19,5y −3x ≤ 30,5x − 4 y ≤15,
− x ≤ 0,
− y ≤ 0,
и составим функцию Лагранжа
L(x,λ) = (x −16)2 + ( y −12)2 + λ1(2x + y −19)+
+ λ2 (5y −3x −30)+ λ3 (5x − 4 y −15) −λ4 x −λ5 y.
Теперь мы можем записать условия теоремы в виде системы:
88
L′x = 2(x −16) + 2λ1 −3λ2 +5λ3 −λ4 = 0,
L′y = 2( y −12) + λ1 +5λ2 − 4λ3 −λ5 = 0,
λ (2x + y −19) = 0,λ12 (5y −3x −30)= 0,
λ3 (5x − 4 y −15)= 0,
λ4 x = 0,λ5 y = 0.
Подставляя x = 6, y = 7 , немедленно убеждаемся, что λ2 = λ3 = λ4 = λ5 = 0 , и
система в действительности является переопределенной и сводится к условиям
− 20 + 2λ1 = 0,
−10 + λ1 = 0,
откуда имеем, что λ1 =10 ≥ 0, т.е. для точки x = (6,7) условия теоремы вы-
полнены.
Пример 2. Рассмотрим теперь другой метод решения задачи
z = (x −16)2 + ( y −12)2 → min
2x + y ≤19,−5y +3x ≥ −30,
5x − 4 y ≤15,
x ≥ 0, y ≥ 0,
основанный на применении симплекс-метода. Сначала приведем систему нетривиальных ограничений к каноническому виду, т.е. введем балансовые неотрицательные переменные u1,u2 ,u3 , такие что
2x + y +u1 =19,5y −3x +u2 = 30,5x − 4 y +u3 =15.
При этом получим, что 2x + y −19 = −u1 и условие λ1(2x + y −19) = 0 перепи-
сывается в виде λ1u1 = 0 и, аналогично, λ2u2 = λ3u3 = 0 . Таким образом, не-
обходимые и достаточные условия экстремума для исходной задачи
89