Решение_задач_исследования_операций
.pdf51
Задание 5
Для задачи с нелинейной целевой функцией и линейной системой ограничений графическим методом найти максимум и минимум; математическая модель задачи задана в вариантах табл. 2.5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 2.5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№ |
|
|
|
|
Задача |
№ |
|
|
|
|
|
|
Задача |
||||||
вариант |
|
|
|
|
|
|
|
|
|
вариант |
|
|
|
|
|
|
|
|
|
а |
|
|
|
|
|
|
|
|
|
а |
|
|
|
|
|
|
|
|
|
|
z = |
x1 − 2x2 |
|
(max, min ) |
|
z = |
|
|
x1 + x2 |
|
(max, min) |
||||||||
|
|
|
|
x1 + x2 |
|
|
|
|
2x1 − x2 |
||||||||||
1 |
x2 + x1 ≥ 6 |
2 |
x2 + x1 ≥ 4 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2x2 − x1 ≤ 6 |
|
3x2 − 2x1 ≤ 7 |
||||||||||||||||
|
|
|
− 2x1 + 6 ≥ 0 |
|
|
|
|
− 4x1 +11 ≥ 0 |
|||||||||||
|
x2 |
|
x2 |
|
|||||||||||||||
|
x1 ≥ 0; x2 ≥ 0 |
|
x1 ≥ 0; x2 ≥ 0 |
||||||||||||||||
|
z = |
2x1 − x2 |
|
(max, min ) |
|
z = |
|
|
2x1 |
|
|
(max, min) |
|||||||
|
|
|
|
x1 − x2 |
|
|
|
|
x1 − 3x2 |
||||||||||
3 |
2x2 + 3x1 ≥ 11 |
4 |
x |
|
|
+ x ≥ 5 |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
1 |
|
|
|
|
||
|
x2 ≤ 4 |
|
|
|
|
|
|
3x |
+ 2x ≤ 13 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
1 |
|
|
|
|
x2 − 3x1 + 8 ≥ 0 |
|
x2 |
|
≥ 1 |
|
|
|
|
||||||||||
|
x1 ≥ 0; x2 ≥ 0 |
|
x ≥ 0; x |
2 |
≥ 0 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
z = |
|
x1 + x2 |
(max, min ) |
|
z = |
2x1 − x2 |
(max,min) |
|||||||||||
|
|
|
|
||||||||||||||||
|
|
|
2x2 − x1 |
|
|
|
|
|
x1 − x2 |
||||||||||
7 |
x |
2 |
+ x ≥ 6 |
8 |
2x |
2 |
+ 3x − 16 ≥ 0 |
||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
||||||
|
3x |
2 |
− 2x ≤ 8 |
|
x2 |
|
≤ 5 |
|
|
|
|
||||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
− 4x + 14 ≥ 0 |
|
|
|
− 3x1 + 10 ≥ 0 |
||||||||||||
|
2 |
|
x2 |
|
|||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x ≥ 0; x |
2 |
≥ 0 |
|
x1 ≥ 0; x2 ≥ 0 |
||||||||||||||
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
52
|
|
z = |
|
|
2x2 |
|
(max, min) |
|
z = |
x2 |
+ 3x1 |
( |
) |
||||||
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
x2 − 3x1 |
|
|
x |
+ x |
|
max, min |
|
||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
9 |
|
x |
|
|
+ x |
− 7 ≥ 0 |
10 |
x2 − x1 − 2 ≤ 0 |
|
||||||||||
|
|
|
2 |
|
|
1 |
|
|
|
|
|||||||||
|
|
3x |
|
|
+ 2x |
≤ 18 |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
2 |
|
1 |
|
|
|
3x2 + 2x1 − 16 ≥ 0 |
|
|||||||
|
|
x2 |
|
≥ 2 |
|
|
|
|
2x |
2 |
+ 3x ≤ 19 |
|
|||||||
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
1 |
|
|
|
|||||||||
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
z = (x1 −1)2 + (x2 −1)2(max,min) |
|
z = (x1 +1)2 + (x2 −1)2 (max,min) |
||||||||||||||||
|
x + x ≥ 6 |
|
|
|
|
x |
|
+ x ≥ 4 |
|
||||||||||
|
|
2 |
1 |
|
|
|
|
|
|
|
|
2 |
|
1 |
|
|
|
||
11 |
2x2 − x1 ≤ 6 |
|
|
|
12 |
3x2 − 2x1 ≤ 7 |
|
||||||||||||
|
x − 2x + 6 ≥ 0 |
|
x |
2 |
− 4x +11≥ 0 |
|
|||||||||||||
|
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
|
||
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Продолжение табл. 2.5 |
||
|
|
|
|
|
|
|
|
|
|
№ |
|
|
|
|
Задача |
№ |
|
|
Задача |
варианта |
|
|
|
|
|
варианта |
|
|
|
|
|
z = x12 + (x2 −1)2 (max,min) |
|
z = (x1 − 4)2 + (x2 − 5)2 (max,min) |
|||||
|
|
2x |
|
+ 3x ≥ 1 |
|
x2 + x1 ≥ 5 |
|||
|
|
|
2 |
|
1 |
|
|
|
|
13 |
|
x2 |
≤ 4 |
|
14 |
3x2 + 2x1 ≤ 13 |
|||
|
|
|
− 3x1 + 8 ≥ 0 |
|
|
≥ 1 |
|
||
|
|
x2 |
|
x2 |
|
||||
|
|
x1 ≥ 0; x2 ≥ 0 |
|
x1 ≥ 0; x2 ≥ 0 |
|||||
|
|
|
|
|
|
||||
|
z = (x1 − 2)2 + (x2 − 3)2 (max,min) |
|
z = (x1 − 5)2 + (x2 − 5)2 (max,min) |
||||||
|
x ≤ x + 2 |
|
|
x + x ≥ 8 |
|||||
|
|
2 |
1 |
|
|
|
2 |
1 |
|
15 |
3x2 ≥ −2x1 +11 |
16 |
2x2 − x1 ≤ 7 |
||||||
|
|
|
|
|
|
|
|
− 2x1 + 7 ≥ 0 |
|
|
2x2 + 3x1 ≤ 14 |
|
x2 |
||||||
|
x1 ≥ 0; x2 ≥ 0 |
|
x ≥ 0; x ≥ 0 |
||||||
|
|
|
|
|
|
|
1 |
2 |
|
|
z = (x1 − 3)2 + (x2 − 4)2 (max,min) |
|
z = (x1 +1)2 + (x2 + 7)2 (max,min) |
||||||
|
x + x ≥ 6 |
|
|
2x + 3x −16 ≥ 0 |
|||||
|
|
2 |
1 |
|
|
|
|
2 |
1 |
17 |
3x2 − 2x1 ≤ 8 |
18 |
x2 |
≤ 5 |
|
||||
|
x − 4x +14 ≥ 0 |
|
x − 3x +10 ≥ 0 |
||||||
|
|
2 |
1 |
|
|
2 |
1 |
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
53 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
z = (x1 − 6)2 + (x2 − 6)2 (max,min) |
|
|
|
|
|
z = (x1 − 6)2 + (x2 − 5)2 (max,min) |
||||||||||||||||||||
|
|
|
x + x − 7 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
x − x − 2 ≤ 0 |
|
|
|
||||||||||||
|
|
|
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|||
19 |
|
3x2 + 2x1 ≤ 18 |
|
|
|
|
|
|
20 |
|
|
3x2 + 2x1 −16 ≥ 0 |
|
|
|||||||||||||||
|
|
|
|
≥ 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
−19 ≤ 0 |
|
|
||||
|
|
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2x2 + 3x1 |
|
|
||||||||
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
z = |
x1 − 2x2 |
|
(max, min ) |
|
|
|
|
|
|
|
x1 + x2 |
( |
|
) |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
x1 + x2 |
|
|
|
|
|
|
|
|
|
|
z = |
2x − x |
|
max, min |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
21 |
|
|
x |
|
|
+ x |
− 4 ≥ 0 |
|
|
|
22 |
|
|
x2 + x1 − 5 ≥ 0 |
|
|
|
||||||||||||
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
2x |
|
− x |
− 5 ≤ 0 |
|
|
|
|
|
|
|
|
|
|
≤ 15 |
|
|
|
||||||||
|
|
|
|
|
|
|
2 |
1 |
|
|
|
|
|
|
|
|
|
|
4x2 − x1 |
|
|
|
|||||||
|
|
|
|
x2 − 2 x1 + 5 ≥ 0 |
|
|
|
|
|
|
|
|
− 4 x1 |
+ 15 ≥ 0 |
|
|
|||||||||||||
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
|
x2 |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
z = |
2x1 − x2 |
(max, min ) |
|
|
|
|
|
z = |
|
2 x1 |
|
|
(max, min ) |
||||||||||||
|
|
|
|
|
|
|
x1 − x2 |
|
|
|
|
|
|
|
|
|
|
|
|
x1 − 3x2 |
|
|
|
||||||
23 |
|
|
2x |
2 |
|
+ 3x − 14 ≥ 0 |
|
|
|
24 |
|
|
4x |
2 |
+ 3x − 19 ≥ 0 |
|
|
||||||||||||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|||||||
|
|
|
|
3x |
|
+ x ≤ 14 |
|
|
|
|
|
|
|
x2 |
− 4 ≤ 0 |
|
|
|
|||||||||||
|
|
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
− 3x1 |
+ 14 ≥ 0 |
|
|
||||||
|
|
|
|
x2 − 2x1 + 7 ≥ 0 |
|
|
|
|
|
|
|
x2 |
|
|
|||||||||||||||
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Окончание табл. 2.5 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
№ |
|
|
|
|
|
|
Задача |
|
|
№ |
|
|
|
|
|
|
|
Задача |
|
|
|
|||||||
|
вар. |
|
|
|
|
|
|
|
|
|
|
|
|
|
вар. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
z = |
|
x1 |
+ 3x2 |
( |
) |
|
|
|
z = |
(x |
− 2)2 + (x |
|
− 3)2 |
(max,min) |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
|
|
|||||||
|
|
|
|
|
x1 + x2 |
|
|
max, min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
x + x − 4 ≥ 0 |
|
|
|
|
|
|
||||||||||
|
|
|
|
2 x |
|
|
≤ 3x |
|
|
|
|
|
|
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
||
|
25 |
|
|
|
2 |
|
|
1 |
|
|
|
|
|
26 |
|
2x2 − x1 − 5 ≤ 0 |
|
|
|
|
|
|
|||||||
|
|
|
|
x2 |
|
+ 4x1 ≥ 11 |
|
|
|
|
x − 2x + 5 ≥ 0 |
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
+ x1 ≤ 22 |
|
|
|
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
3x2 |
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
||||||||||||||
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
z = (x1 − 4)2 + (x2 − 2)2 (max,min) |
|
|
|
z = (x1 − 3)2 + (x2 − 2)2 (max,min) |
|
|||||||||||||||||||||
|
|
|
x + x − 5 ≥ 0 |
|
|
|
|
|
|
|
2x + 3x −14 ≥ 0 |
|
|
|
|||||||||||||||
|
|
|
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 |
|
|
|
|
|
|
|
|||
|
27 |
|
4x2 − x1 ≤ 15 |
|
|
|
|
|
|
28 |
|
3x2 + x1 ≤ 14 |
|
|
|
|
|
|
|||||||||||
|
|
|
x − 4x +15 ≥ 0 |
|
|
|
|
|
|
|
x − 2x + 7 ≥ 0 |
|
|
|
|
|
|||||||||||||
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 ≥ 0; x2 ≥ 0 |
|
|
|
|
|
|
|
|
x ≥ 0; x ≥ 0 |
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
|
|
|
|
|
|
|
54
|
z = (x1 +1)2 + (x2 − 4)2 (max,min) |
|
z = (x1 +1)2 + x22 (max,min) |
||||
|
4x + 3x −19 ≥ 0 |
|
2x ≤ 3x |
||||
|
|
2 |
1 |
|
|
2 |
1 |
29 |
x2 |
− 4 ≤ 0 |
30 |
x2 |
+ 4x1 ≥ 11 |
||
|
|
− 3x1 +14 ≥ 0 |
|
|
|
+ x1 ≤ 22 |
|
|
x2 |
|
3x2 |
||||
|
x1 ≥ 0; x2 ≥ 0 |
|
x1 ≥ 0; x2 ≥ 0 |
Задание 6
Найти точки условного экстремума функции U при заданных ограничениях методом Лагранжа. Варианты заданий даны в табл. 2.6
Таблица 2.6
№ варианта |
|
|
Задача |
1 |
U = x2 + y2 − xy + x + y − 4, при x + y + 3 = 0. |
||
2 |
U = 2xz − yz, |
при y + 2z = 3, |
|
|
|||
|
|
|
x + y = 2. |
3 |
U = 2x + y, при |
x2 + y2 =1. |
|
|
|
|
|
4 |
U = xy + yz, |
при |
|
|
x + y = 2, |
||
|
|
|
y + z = 2. |
5 |
U = 2xy, при |
2x − 3y − 4 = 0. |
|
|
|
|
|
6 |
U = xy + yz, |
при |
|
|
x − y = 2, |
||
|
|
|
y + z = 4. |
7 |
U = 2x + y − 2z, |
при x2 − y2 + z2 = 36. |
|
|
Продолжение табл. 2.6
№ варианта |
|
|
|
|
|
Задача |
8 |
U = |
1 |
+ |
1 |
, при x + y = 2. |
|
|
|
|
||||
|
|
x y |
|
|||
|
|
|
|
|
|
|
9 |
|
|
|
|
|
y + z = 6, |
|
U = 4x3 + y2 − z2 + 9xy, при |
|||||
|
|
|
|
|
|
x + y = 2. |
10 |
U = 6 − 4x − 3y, при |
x2 + y2 =1. |
||||
|
|
|
|
|
|
|
11 |
U = 4 y3 + x2 − z2 + 9xy, |
при x + y = 2, |
||||
|
||||||
|
|
|
|
|
|
x + z = 6. |
12 |
U = 2x + y, при x2 + y2 =1. |
|||||
|
|
|
|
|
|
|
13 |
U = 4 y3 + z2 − x2 + 9 yz, |
при x + z = 6, |
||||
|
||||||
|
|
|
|
|
|
x + z = 2. |
14 |
U = 4x + 9 y − 25, при |
4x2 + 36 y2 = 9. |
||||
|
|
|
|
|
|
|
55
15 |
U = 4 y3 + x2 − z2 |
+ 9xy, |
при |
2x + y + z = 8, |
|||||
|
|||||||||
|
|
|
|
|
|
|
|
3x + y + 2z = 14. |
|
16 |
U = |
x |
+ |
y |
, при |
x2 + y2 =1. |
|
|
|
|
|
|
|
|
|||||
|
2 |
3 |
|
|
|
|
|
||
17 |
U = 4z3 + y2 − x2 |
+ 9 yz, |
при |
2x + 3y + z = 14, |
|||||
|
|||||||||
|
|
|
|
|
|
|
|
x + y = 6. |
|
18 |
U = 3x2 − 8xy + 7 y2 , при x2 + y2 −1 = 0. |
||||||||
|
|
|
|
|
|
|
|
|
|
19 |
U = 4x3 + y2 − z2 |
+ 9xy, |
при |
2x + y − z = −2, |
|||||
|
|
||||||||
|
|
|
|
|
|
|
|
x + 2 y + z = 8. |
|
20 |
U = x2 +12xy + 2 y2 , при 4x2 + y2 − 25 = 0. |
||||||||
|
|
|
|
|
|
|
|
|
|
21 |
U = 4 y3 + x2 − z2 |
+ 9xy, при |
2x + y + z = 8, |
||||||
|
|||||||||
|
|
|
|
|
|
|
|
z − y = 4. |
|
22 |
U = 2x − y + z, при x2 + y2 + z2 =1. |
||||||||
|
|
|
|
|
|
|
|
|
|
23 |
U = 4z3 + y2 − x2 + 9 yz, |
при |
2x + 3y + z =14, |
||||||
|
|||||||||
|
|
|
|
|
|
|
|
|
x − y − 2z = 2. |
24 |
U = x2 + y2 , при |
3x + 2 y −11 = 0. |
|||||||
|
|
|
|
|
|
|
|
|
|
25 |
U = 4 y3 + z2 − x2 + 9 yz, |
при |
x + y + 2z = 8, |
||||||
|
|||||||||
|
|
|
|
|
|
|
|
|
x − y = 4. |
26 |
U = −xy2 , при |
x + 2 y −1 = 0. |
|
||||||
|
|
|
|
|
|
|
|
|
|
27 |
U = 4x3 + y2 − z2 + 9 yz, |
при |
x + 2 y + z = 8, |
||||||
|
|||||||||
|
|
|
|
|
|
|
|
|
x + 3y + 2z =14. |
28 |
U = xy2 z2 , при |
x + 2 y + 3z = 12 (x > 0, y > 0, z > 0). |
|
|
|
|
|
|
|
|
|
|
Окончание табл. 2.6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
№ варианта |
|
|
|
|
|
|
|
|
|
Задача |
|
29 |
U = 4 y3 |
+ z2 − z2 + 9 yz, при 2x + y + 3z =14, |
|
||||||||
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
x + z = 6. |
|
30 |
U = |
x |
|
+ |
y |
− 2 |
|
, при x2 + y2 =1. |
|
||
|
2 |
|
|||||||||
|
|
|
|
|
|
|
|||||
|
2 |
|
2 |
|
|
|
|
Рекомендации по решению индивидуальных заданий №2
Пример 2.1 Методом потенциалов решить транспортную задачу, исходные данные которой представлены в табл. 2.7. Первичное распределение поставок найти методом северо-западного угла.
56
Таблица 2.7
Поставщики |
|
Потребители |
|
Запасы |
||
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
1 |
2 |
5 |
3 |
a1 |
= 60 |
|
|
|
|
|
|
|
А2 |
1 |
6 |
5 |
2 |
а2 |
= 100 |
|
|
|
|
|
|
|
А3 |
6 |
3 |
7 |
4 |
а3 |
= 90 |
|
|
|
|
|
|
|
Потребности |
b1 = 20 |
b2 = 80 |
b3 = 40 |
b4 = 110 |
|
|
Вначале проверим, что имеем сбалансированную (закрытую)
транспортную задачу. Для этого вычислим сумму всех потребностей и сумму всех запасов. Имеем:
3
∑ai = 60 +100 + 90 = 250;
i=1
4
∑bj = 20 + 80 + 40 +110 = 250.
i=1
Сумма всех потребностей и сумма всех запасов совпадают, поэтому задача сбалансирована.
Найдем теперь начальное опорное решение методом северо- западного угла. Матрицу перевозок будем заполнять в направлении с северо-запада на юго-восток, удовлетворяя последовательно запросы потребителей В1, В2, В3, В4. При этом число заполненных клеток всегда должно быть на единицу меньше суммы числа строк и столбцов, т.е. равно m + n − 1 , а в некоторых клетках могут быть записаны нулевые перевозки.
1) Так как запасов А1 хватает на удовлетворение потребностей В1, то записываем в таблицу x11=20 и первый столбец исключаем из рассмотрения, а запасы А1 уменьшаем на 20. Значения перевозок будем записывать в верхних частях клеток, над диагоналями, а в нижних частях клеток записаны стоимости перевозок единицы груза от поставщика к потребителю.
2)Будем удовлетворять теперь заказ В2; запишем в таблицу значение x12=40 при этом запасы А1 будут исчерпаны и первую строку исключаем из рассмотрения, а потребности В2 уменьшаем на 40. Положим теперь x22=40 и уменьшим запасы А2. Второй столбец исключаем из рассмотрения.
3)За счет оставшихся запасов А2 можно удовлетворить потребности заказчика В3. Положим теперь x23=40 и уменьшим запасы А2 на 40. Третий столбец исключаем из рассмотрения.
57
4) За счет оставшихся запасов А2 можно частично удовлетворить потребности заказчика В4. Положим теперь x24=20 и исключим из рассмотрения вторую строку. Запишем теперь в таблицу значение x34=90. При этом все запасы будут исчерпаны, а заявки удовлетворены. Результаты вычислений приведены в табл. 2.8.
Вычислим стоимость перевозок:
F0=20+80+240+200+40+360=940 (ден. ед.)
Клетки, в которых записаны значения xij, называются базисными (они соответствуют базисным переменным). В рассмотренном примере m = 3, n = 4, число базисных переменных m + n − 1 = 6 ; имеем 6 занятых клеток.
|
|
|
|
|
|
Таблица 2.8 |
|
|
|
|
|
|
|
|
|
Поставщики |
|
Потребители |
|
|
|
Запасы |
|
|
В1 |
В2 |
В3 |
|
|
В4 |
|
А1 |
1 |
2 |
5 |
|
3 |
|
60,40,0 |
|
20 |
40 |
|
|
|
|
|
А2 |
1 |
6 |
5 |
|
2 |
|
110,60,20,0 |
|
|
40 |
|
40 |
|
20 |
|
А3 |
6 |
3 |
7 |
|
4 |
|
90,0 |
|
|
|
|
|
|
90 |
|
Потребности |
20,0 |
80,40,0 |
40,0 |
|
|
110,90,0 |
|
Для проверки полученного базисного решения на оптимальность, а также для перехода к новому «лучшему» решению применяют метод потенциалов.
Циклы в матрице. Для перехода от одного опорного решения к другому вводится понятие цикла. Циклом называется замкнутая ломаная линия с горизонтальными и вертикальными звеньями и вершинами в клетках, расположенными в одной строке или столбце. В любой вершине цикла происходит поворот звена ломаной линии на 90о Примеры простейших циклов изображены на рис. 2.1:
58
Рис. 2.1
Замечание. Ломаная может быть самопересекающаяся, но точки пересечения не могут служить вершинами цикла.
Циклы удовлетворяют следующим свойствам:
1) если |
в матрице размером (m × n) отмечено (m + n) клеток |
(m n ≥ m + n) , |
то всегда существует цикл, вершины которого лежат в |
отмеченных клетках (может быть не во всех).
2)Число вершин в каждом цикле четно.
3)В каждой строке (или столбце) число вершин четно.
Припишем всем вершинам цикла знаки «+» или «-», причем у двух соседних вершин знаки противоположны. Такой цикл называется означенным. Если в матрице перевозок выделить цикл, то клетки называют положительными (отрицательными) в зависимости от знака вершины цикла, расположенной в этой клетке.
Сдвигом по циклу на величину λ будем называть увеличение на λ объемов перевозок во всех положительных клетках и уменьшение объемов перевозок во всех отрицательных клетках на λ . В результате этой операции получим новую матрицу перевозок.
Известно, что, если в матрице перевозок содержится опорное решение, то:
1)Не существует цикла с вершинами и только в базисных клетках;
2)Для любой свободной клетки существует единственный цикл, одна вершина которого лежит в выбранной клетке, а все остальные в базисных клетках. Этот цикл называется циклом пересчета для данной клетки. Означим этот цикл прописав знак «+» свободной клетке.
Метод потенциалов для транспортной задачи
59
Известно, что если решение x* = {xij*}m×n транспортной задачи является оптимальным, то ему соответствует система m чисел u1 (i = 1, 2,..., m) ,
называемых потенциалами поставщиков, и n чисел v j ( j = 1, 2,..., n) ,
называемых потенциалами потребителей, удовлетворяющих условиям ui + v j = cij для базисных клеток и ui + v j < cij для свободных клеток. Здесь
сij -стоимость перевозки единицы груза от поставщика Аi к
потребителю Вj.
Составим и решим систему уравнений для потенциалов (базисных клеток m + n −1 , а неизвестных m + n ; чтобы найти частное решение, выберем один из потенциалов равный нулю).
Чтобы проверить решение транспортной задачи на оптимальность,
для каждой свободной клетки вычислим величину Sij = cij − ui |
− v j . Если |
хотя бы для одной свободной клетки выполняется условие |
Sij < 0 , то |
решение не является оптимальным. Если таких клеток несколько, то выбираем ту клетку, в которой величина Sij наименьшая. Эту клетку в
дальнейшем загружают (вводят в базис), а одну из базисных клеток вводят число свободных. Построим замкнутый цикл с вершиной в выбранной свободной клетке наименьшее значение).
Припишем этой клетке знак «+», а в остальных вершинах знаки будем чередовать при их обходе по часовой стрелке. В клетках цикла с отрицательными вершинами выберем наименьшее количество груза xij
и выполним потом сдвиг по циклу (число λ = xij прибавим к грузам в
положительных вершинах и вычтем число λ от грузов, записанных в отрицательных вершинах). Получим новое опорное решение.
В нашем примере введем потенциалы поставщиков u1 , u2 , u3 и
потенциалы потребителей v1, v2 , v3 , v4 .
Шаг 1: найдем потенциалы из равенств ui + v j = cij для каждой базисной (занятой) клетки. Имеем систему уравнений:
u + v |
= 1, |
|||
|
1 |
1 |
|
|
u1 + v2 |
= 2, |
|||
|
|
2 |
2 |
= 6, |
u |
|
+ v |
||
|
|
|
+ v3 = 5, |
|
u2 |
||||
u |
|
+ v |
= 2, |
|
|
|
2 |
4 |
= 4. |
u |
3 |
+ v |
||
|
|
4 |
|
Положим, u1 = 0 . Все остальные потенциалы определим из системы: v1 = 1, v2 = 2, v3 = 1, v4 = 2, u2 = 4, u3 = 6.
60
Вычислим коэффициенты Sij для всех свободных (не занятых клеток) по формуле Sij = cij − ui − v j . Получим:
S13 = 5 − 0 − 1 = 4; |
S14 |
= 3 − 0 + 2 = 5; |
S21 = 1 − 4 − 1 = −4; |
S31 = 6 − 6 − 1 = −1; S32 |
= 3 − 6 − 2 = −5; |
S33 = 7 − 6 −1 = 0. |
|
Среди коэффициентов |
Sij |
есть отрицательные числа, поэтому |
исходное решение не является оптимальным и его можно улучшить. Выбираем клетку x32 с наименьшим значением min Sij = S32 = −5 и
построим для этой клетки цикл пересчета (прямоугольник с вершинами в клетках x32 , x34 , x24 , x22 , которым приписаны знаки «+» и «-»
на рис. 2.2).
Рис. 2.2
Минимальный груз в отрицательных вершинах этого цикла находится в клетке (2,2) и равен x22 = 40. Осуществляем сдвиг по циклу
на величину λ = 40 . От значений количества груза в «отрицательных» клеток число 40 вычтем, а к количеству груза, записанного в «положительных» клетках число 40 добавим. При этом значение
получим x22 |
= 0 |
и эта |
переменная станет |
свободной, а |
x32 = 40 |
||||||
(переменная |
x32 |
станет базисной). |
Получили новое опорное решение |
||||||||
(табл.2.9) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 2.9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Поставщики |
|
|
|
|
|
Потребители |
|
|
|
|
|
|
|
|
В1 |
|
|
В2 |
|
В3 |
|
|
В4 |
А1 |
|
1 |
|
2 |
|
5 |
|
|
3 |
|
|
|
|
|
|
20 |
|
40 |
|
|
|
|
|
А2 |
|
1 |
|
6 |
|
5 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
40 |
|
60 |
А3 |
|
6 |
|
3 |
|
7 |
|
|
4 |
|
|
|
|
|
|
|
|
40 |
|
|
|
|
50 |
Вычислим стоимость перевозок: |
|
|
|
|
|
|
|||||
F1 = 20 1 + 40 2 + 40 5 + 60 2 + 40 3 + 50 4 = 740 |
(ден. ед.) |
|