Idea Transcript
. .
,
.
.
2017
1
519.8 22.18 14
: .
.
.
.
,
.,
.
.
, »
.
«
-
;
,
,
«
-
»
. .,
.
. :
14 . .
.–
:
/ . , 2017. – 64 .
.
,
, «
-
». . 519.8 22.18
© ©
. .,
. ., 2017 , 2017
2
................................................................................................... 4 1.
.................................................................... 5 1.1.
.................................................................. 5
1.2.
................... 6
1.3. ............................................................................ 10 2.
............................................................................... 12 2.1.
............................. 13
2.2.
................................ 15
3.
.......................................... 17 3.1.
........ 17
4.
................................................................... 22
5.
.............................. 28 ......................................................................... 63
3
, ,
.
,
, ,
,
,
,
. -
.
, . .
-
. – «
–
», . . -
. .
-
, ,
, ,
-
. .
,
-
( ). : (
. ,
) –
,
,
-
. .
, . . « ». , .
4
-
1. 1.1. : , . . , .
-
, ,
.; ,
-
,
.
.
,
,
: (
)
f ( x1 , x 2 ,..., xn )
Y
max(min),
(1.1.1)
,
G ( x1 , x2 ,..., xn ) 0.
(1.1.2) . ,
-
–
(1.1.2).
–
–
–
-
.
Y
f ( x1 , x 2 ..., x n )
-
, (
, ).
,
G
-
.
G ( x1 , x2 ,..., x n ) 0 (
-
)
x1
0, x 2
0,..., xn
0, ,
(
)
5
-
f ( x1 , x2 ,..., xn )
max(min)
(1.1.3)
,
-
g1 ( x1 , x 2 ,..., x n ) 0, (1.1.4)
............................ g m ( x1 , x 2 ,..., x n ) 0. f ( x1 , x2 ,..., xn ) (1.1.4) –
; (
) . –
-
, . – .
-
: ; ; , ;
,
, ,
, . .
.
1.2. , . ( k
m–k
n
6
)
a11 x1
a12 x 2
... a1n x n
b1 ,
a 21 x1
a 22 x 2
... a 2 n x n
b2 ,
a31 x1
a32 x 2
... a3 n x n
b3 ,
......................................... a k 1 x1
ak 2 x2
... a kn x n
a(k
1)1 1
x
a(k
1) 2
a(k
2 )1 1
x
a(k
2) 2
bk ,
x2
... a ( k
x2
... a ( k
1) n
xn
2)n
(1.2.1)
bk 1 ,
xn
bk 2 ,
.......................................... a m1 x1
... a mn x n
am2 x2
xj
0, j
bm
1,..., n
(1.2.2) (
F
c1 x1 c 2 x 2 c3 x3 ... c n x n X (1.2.2)
(1.2.1) (
F
)
max(min).
( x1 , x2 , x3 ,..., x n ) , )
(1.2.3) -
. , (1.2.1)
,
, ,
.
: n
F
ci x j
max(min),
(1.2.4)
j 1 n
aij x j
bi
(i 1,..., k ),
(1.2.5)
aij x j
bi
(i
(1.2.6)
j 1 n
k 1,..., m),
j 1
xj
0, j 1,..., n.
7
(1.2.7)
(
) *
X (1.2.5)–(1.2.7), ( – ,
F
( x1* , x2* ,..., xn* ),
). -
,
,
–
.
a11 x1 a12 x2
, ... a1n xn
:
b1 ,
a 21 x1 a 22 x 2 ... a2 n xn
b2 ,
a31 x1 a32 x2 ... a3 n x n
b3 ,
(1.2.8)
......................................... a m1 x1 a m 2 x2 ... a mn xn bm , x j 0, j 1,..., n,
F
c1 x1
c2 x2
c3 x3
...c n x n
max(min)
(1.2.9) .
, , « »
xj
« »,
0, j
1,..., n
, .
,
F
c1 x1 c 2 x 2
c3 x3 ...cn x n
max(min),
a11 x1 a12 x 2 ... a1n x n
b1 ,
a 21 x1 a 22 x 2 ... a 2 n x n
b2 ,
a 31 x1 a32 x 2 ... a3n x n
b3 ,
......................................... a m1 x1 a m 2 x 2 ... a mn x n xj
0, j
1,..., n
8
(1.2.10)
(1.2.11)
bm , (1.2.12)
xj –
, , -
.
)
. –
.
, . m
m
xn 1 , xn
2 ,..., xn m ,
:
a11 x1
a12 x2
... a1n xn
xn
a 21 x1
a 22 x2
... a 2 n x n
xn
2
b2 ,
a31 x1
a32 x2
... a3n xn
xn
3
b3 ,
......................................... a m1 x1 am 2 x2 ... a mn x n
xj ,
xn 1 , xn 2 ,..., xn 0, j 1,..., ( n m) .
m
b1 ,
1
xn
m
(1.2.13)
bm .
–
, .
, « », «–».
,
-
,
(–1),
F1
F
c1 x1
c2 x2
c3 x3
... cn xn
max .
,
.
X
( xn 1 , xn 2 ,..., xn
(1.2.14)
m),
9
(1.2.13)
(1.2.14)
-
.
2 x1
F
3 x2
max,
3 x 2 18,
x1 2 x1
x2 16, 5,
x2 3 x1
21,
x1 0; x 2
0. . ,
:
x1 3 x 2
x3
18,
2 x1
x4
16,
x2 3 x1
x2 x5
15, 21.
x6
«+»,
.
1.3. :
F
c1 x1 c 2 x 2 ... c n x n
max(min),
a11 x1 a12 x 2 ... a1n x n
b1 ,
a 21 x1 a 22 x 2 ... a 2 n x n
b2 ,
a 31 x1 a32 x 2 ... a3n x n
b3 ,
......................................... a m1 x1 a m 2 x 2 ... a mn x n
xj
0, j 1,..., n. .
10
(1.3.1)
(1.3.2)
bm , (1.3.3)
c (c1 , c2 ,..., cn )
1.
.
b (b1 , b2 ,..., bm ) . A {a ij }, i 1,..., m; j
2. 3. (
) x
4.
-
1,..., n .
( x1 ,..., x n )
-
.
.
x1 , x 2 , ..., x n ,
5.
,
(
).
6. (
).
7. . 8.
, ,
,
. ,
. (
)
m
n
,
(n–m)
. ,
-
C nm .
, ,
-
,
. 1.
-
, . ,
, . 2(
). , -
. ,
,
,
.
11
3(
). -
, ,
,
,
,
, . , ,
-
,
– – ). (
4(
),
. ,
,
,
-
. ,
, .
5(
).
, -
. ,
-
,
-
,
.
2. – (
)
(
-
). ,
. ,
.
12
-
2.1. m
A1 , A2 ,..., Am .
ai n B j ( j 1, n) .
bj
B1 , B2 ,..., Bn .
Ai (i 1, m) . -
Cij ,
-
Bj .
Ai
, (
) ,
.
xij
,
i
j
. . 2.1.1, . 2.1.1
B1 A1 …
Ai …
Am
Bj
…
c11
c1 j
…
x11 …
x1 j
…
ci1
…
xi1 …
x ij
…
cm1
…
cmj
…
x m1 b1
x mj bj
…
c1n
…
a1
x 1n
…
cij
…
Bn
…
…
…
cin
…
ai
x in
…
…
…
cmn
…
am
x mn bn
…
ai
bj -
m n
Z
cij xij
(2.1.1)
i 1j 1 n
xij
ai , i 1, m
(
);
j 1
13
(2.1.2)
n
xij
b j , j 1, n
(
);
(2.1.3)
j 1
xij
0 , i 1,..., m, j 1,..., n. ai
,
ai
,
bj ,
(2.1.4)
bj ,
-
.
-
. , m
n
ai
. i 1
bj . j 1 m
n
ai
bj ,
i 1
(n+1)-
j 1 m
bn
n
ai
1 i 1
m
ci , n
bj
1
0, i 1, m.
j 1
n
ai
bj ,
i 1
(m+1)-
j 1 n
am
m
bi
1
j 1
cm
ai
0,
1, j
j 1, n.
i 1
-
. (2.1.2)–(2.1.4) ;
, –
,
. -
. : 1.
( )–
2.
(
. ),
( ). ,
.
14
2.2. . ,
-
, ( ,
. m+n m+n–1 m+n–1
, m·n
) (
-
m+n–1),
,
. .
(
) .
xmn ,
x11 .
. .
,
,
,
,
cij . .
,
,
-
, . ,
cij .
,
,
cij ,
.
xij
(i,j).
ai
bj,
b 'j
bj
Ai
ai .
min(ai , b j ) . Bj
,
,
i
,
.
ai Ai
bj
j-
ai'
ai
bj . ,
, ,
– 15
.
,
-
(
),
,
,
,
,
,
,
-
,
,
.
,
-
.
(2.1.2)–(2.1.4). ,
,
-
ai , i 1, m ; b j , j 1, n .
i j
–
, m+n–1, m+n–1
m+n
-
.
, . ,
, ,
(
)–
.
, (2.1.2)–(2.1.4)
m+n–1 . ,
,
m+n–1. , ,
0, . ,
-
. ,
,
. .
, ,
-
, ,
.
,
.
,
-
. , .
,
,
, , , . 16
.
,
-
3. ) -
. : (
–
, (
); (
)
. .
-
, . : x ( x1 , ..., xn ) R n – n– Rn – p ( p1 , ..., pn ) – K– ( )
,
xi –
i;
; ; ,
pi –
i;
,
-
.
3.1.
.
pi
, , . . xi
K ,
-
,
.
x
. «
»
. u (x) u ( x1 , ..., xn ) . ,
u (x )
max
(3.1.1)
n
pi xi
K , x 0.
(3.1.2)
i 1
B(p, K) p
, K:
17
-
B (p, K )
Rn
x
n
pi xi
K
,
(3.1.3)
i 1
.
B(p, K )
x R
n
n
pi xi
K
B(p, K)
i 1
. (3.1.1), (3.1.2)
-
,
u (x* ) max u (x) .
(3.1.4)
x B (p , K )
x*
1.
(3.1), (3.2) .
. p1, ..., pn
,
-
K
x1* , ..., xn*
*
x
-
(3.1.1), (3.1.2).
. -
, . . .
, ,
, .
, ,
,
-
. n
L(x, ) u(x)
(
pi xi
K),
(3.1.5)
i 1
–
. . , :
18
-
L xi
u xi
0, i 1, n,
pi
0, i 1, n, (3.1.6)
n
L
pi xi
0,
K
0.
i 1
x
*
( x1* , ..., xn* )
*
.
, .
,
,
, .
-
, .
,
-
,
, x
( x1 , xn ) R 2 .
-
u x1
p1
0,
u x2
p2
0,
p1 x1
p 2 x2
K
0. ,
-
,
u * x x1
*
p1
u * x x2
u * x x1
p2
u * x x2
p1 . p2
(3.1.7)
x ( x1 , ..., xn ) R n
, , . 1.
-
u * x xi
pi , i 1, n .
,
-
( 2.
(3.1.8)
). ,
-
, 19
1 u * x p1 x1
1 u * x p 2 x2
1 u * x p n xn
...
3.
i 1, n .
,
(3.1.9)
, ,
, .
:
K
. ,
-
, .
(
-
) .
,
,–
0
.
, .
, ,
. . 3.1.1, . .
. 3.1.1.
20
-
K p2 K p1
tg
p1 . p2
u ( x1 , x2 ) const
du
0, . .
u dx1 x1
dx2 dx1
u dx2 x2
0
u x1 . u x2
(3.1.10)
p1 . p2
(3.1.11)
x* ,
dx2 dx1 ,
u x1 u x2
p1 , p2 ,
21
(3.1.12) (3.1.8).
4. 1 . 1 2-
:
.
. . I
II
III
IV
2
1
0
2
3
0
1
1
21
4
6
10
3 – 2
.
.
.
.
,
,
. 2 3 .
. -
, ,
. ,
-
,
. ,
I II III
2 4 6
3 1 7
16
12
180 240 426
,
-
,
. 22
3 . 19
, – 16
19
-
. 26
, –17
8
. 868 – 853 .
,
– 638
5 4
.
.
,
-
.,
. . 4 –
– :
,
«
,
».
– 21, 8, 12, 5 – 3
2
.
, .
.,
.
2, 1, 2, 1
,
– 3, 1, 1, 0 ,
.
.
.
. – -
.
.
I
3 . 2,
.
. 5 , 2
8, 6, 9. .
,–1
.
2
, 2
1
. 10
.
.
,
12
.
.
. 6 – : «
,
».
– 6, 5, 2, 2
.
.
23
– ,
, – 90, 164, 30, 50 . –3 . ., – 4 5, 4, 3, 2 . . . .
, . .
. ,
7 . ,
– 120, 35
70
. 10
,8–
5–
.
. 5
., 7
.
8
.
. .
10 –8
.
-
.,
. . 8
20 – 20
.
, 15 , 10 . 16 .
.
.
180
.
5 .
8 ,8 .
.
. .
. . 10
– 200
.
.
.,
.
–
. 9 . 14
, – 15
20
-
. 40
, – 27
4
. 1200 – 1097 .
, 5
13
.
– 993 .
,
-
.,
. . 10 , .
-
14
, – 15
20
.
,–
40 27
4 – 993
. 1200 , – 1097 .
,
5
13
.
.
., -
. 24
.
2
A1 , A2 , A3 . A1 , A2 , A3 . 1, 2 , 3 b1 , b2 , b3 , b4 , b5 -
B1 , B2 , B3 , B4 , B5 B1 , B2 , B3 , B4 , B5 . .
A1 A2 A3
B1
B2
B3
B4
B5
11
12
13
14
15
21
22
23
24
25
31
32
33
34
35
, .
1
a1
200,
b2
125,
a2
450,
b3
325,
a3
250,
b4
250,
b1
100,
b5
100;
5 8 7 10 3 4 2 2 5 6 . 7 3 5 9 2 2
a1
70,
b2
70,
a2
80,
b3
30,
a3
150,
b4
80,
b1
20,
b5
100;
3 5 8 6 3 2 5 4 7 3 . 7 5 6 4 8
25
-
3
a1
110,
b2
30,
a2
50,
b3
70,
a3
80,
b4
50,
b1
40,
b5
50;
5 2 3 8 3 3 4 7 2 6 . 6 5 3 4 2 4
a1
100,
b2
70,
a2
60,
b3
20,
a3
90,
b4
60,
b1
30,
b5
70;
7 3 8 4 5 2 5 7 3 8 . 4 6 3 8 4 5
a1
20,
b2
40,
a2
110,
b3
30,
a3
120,
b4
60,
b1
70,
b5
50;
2 6 9 1 6 7 5 3 4 5 . 7 3 5 9 2 6
a1
120,
b2
90,
a2
30,
b3
80,
a3
100,
b4
20,
b1
30,
b5
30;
2 8 4 6 3 3 2 5 2 6 . 6 5 8 7 4 7
a1
130,
b2
50,
a2
90,
b3
30,
a3
140,
b4
80,
b1
110,
b5
90;
2 3 6 8 2 10 8 1 2 3 . 5 6 7 4 4 8
a1
200,
b2
125,
a2
450,
b3
325,
a3
250,
b4
250,
b1
100,
b5
100;
1 4 8 2 8 5 1 3 6 6 . 8 2 3 5 2
26
9
a1
30,
b2
40,
a2
70,
b3
20,
a3
50,
b4
60,
b1
10,
b5
20;
2 7 3 6 2 9 4 5 7 3 . 5 7 6 2 4 10
a1
20,
b2
35,
a2
90,
b3
40,
a3
40,
b4
20,
b1
25,
b5
30;
9 8 2 5 4 7 2 7 8 3 . 5 9 6 6 3
3
u ( x1 , x 2 ) x1 x2 , p1 ,
x1
x2 –
.
p2 . K
x1
.
x2
? .
:
1) ; 2)
. 1
2
3
4
5
6
7
8
0,1 0,2 0,3 0,4 0,5 0,5 0,6 0,8
9
10
1
0,5
0,5 0,4 0,5 0,6 0,2 0,1 0,2 0,4 0,5 0,5
p1
1
2
2
6
2
3
3
6
6
2
p2
2
1
2
1
3
2
2
4
2
1
K
36
30
50
50
80
60
90
30
30
40
27
5.
)
,
,
-
. 1 4
.
,
-
. 2
.
.,
–3
.
. ,
-
.
11 2 3 4
22 1 4 0
2 2 0 4
12 8 16 12 n = 2, m = 4.
2
1
3
max.
2
1,
–
2
,
,
–
-
.
. . X1OX2
. X1OX2
2
1
( 2
2
, . 5.1.1) 12 ;
, .
1
2
2
8;
4
1
28
16 ;
4
2
12 ;
1
0;
2
0.
0;
1
,
0 < 12 – 2 1 2 .
2
2
, 12 ;
0. ,
OABCD –
-
.
. 5.1.1.
. . 5.1.2):
(
2
1
3
2
6;
2
1
3
2
13 .
(2; 3) , ,
(0;0).
,
-
, . : ,
1
4,
2
2. ,
,
.
2 4 3 2 14 .
29
. 5.1.2.
.
, 4
.
14 2
.
2 -
. . , .
, (
),
, . ) ( ) I II III (
.) 30
12 4 3
4 4 12
30
40
300 120 252
,
1
2
.
,
12
1
4
2
4
1
4
2
3
1 1
12 0,
300, 120,
2 2
252, 0.
1
30
-
2
40 2 .
1
,
: -
, . ,
-
.
.
12 4 3
1 1 1 1 2
4
2
300,
(I )
4 2 120, 12 2 252,
( II ) ( III ) ( IV )
0, 0.
(V ) . 5.1.3. . ,
–
.
, ,
, . , ,
, .
31
,
–
. 5.1.3.
12 1 4 5.1.3
, 300 .
2
,
,
12 ,
, I), ,
,
12
1
4
2
300 .
1
4
300 (
2
, (0; 0) . 12 0 4 0 300 . (0; 0) , . 5.1.3.
.
,
-
. . 5.1.3, OABCD. ,
OABCD,
, .
,
, .
32
(30; 40)
, h–
30 30 ,
,
30
1
40
2
. . 5.1.3).
480 (
40
1
2
1
40
h, -
2
h , h = 480
,
-
, , 480 480,
.
,
, .
h , , 480
,
. 30
40
1
2
-
480
,
. ,
. II
III.
,
4 1 4 3 1 12
120, 250.
2 2
, ,
12 , 2 18 . 18 , 30 12 40 18 1080
-
1
12 ,
max
.
3
F
2
4 1 1
4
1
3 0,
2
8, 9,
2
0.
2
.
33
x2
16,
2
2
1
x1
-
2
4
1
4
2
1
3
1
2
16,
(I )
8,
( II ) ( III ) ( IV )
2
9,
2
0, 0.
1 2
(V ) ,
-
( . 5.1.4). . 5.1.4, . . ,
,
F
,
x1
x2
.
x1
x2
4 (
4
(1; 1) .
)
. 5.1.4.
,
3
, .
, .
I
–
II,
34
F
2
4 3
1 1
16, 9.
2 2
,
1
Fmax
,
x1
2
1.
-
7.
x2 4 (1; 1) .
.
6,
, ,
,
. 5.1.4, -
F
.
3
1
0,
2
9,
0,
1
1
2
3.
-
Fmin
,
3.
1. A1, A2, A3
A4 B1, B2, B3, B4.
{a1, a2, a3, a4} b4}. Ai
,
{b1, b2, b3, -
cij Bj –
4×4. -
, . .
1 2 3 4
1 12 4 3 24 250
2 16 4 8 33 1000
3 21 9 14 36 700
35
4 19 5 10 34 1100
950 300 1350 450
4
ai = 950 + 300 + 1350 + 450 = 3050, i 1 4
b j = 250 + 1000 + 700 + 1100 = 3050. j 1
.
.
,
-
. . 1 12 4 3 24 250
1 2 3 4
2 16 4 8 33 1000
3 21 9 14 36 700
1.
4 19 5 10 34 1100
950 300 1350 450
,
-
.
3.
1350, 250,
– 250. .
× × 3 × 0
16 4 8 33 1000
21 9 14 36 700
19 5 10 34 1100
950 300 1100 450 0
4.
300,
– 1000. × × 3 × 0
300, 16 4 8 33 700
21 × 14 36 700
36
19 × 10 34 1100
950 0 1100 450 0
.
8.
1100,
– 700.
700,
. × × 3 × 0
× 4 8 × 0
21 × 14 36 700
19 × 10 34 1100
950 0 400 450 0
10.
400,
– 1100.
400,
. × × 3 × 0
× 4 8 × 0
21 × x 36 700
19 × 10 34 700
950 0 0 450 0
19.
950,
– 700.
700,
. × × 3 × 0
× 4 8 × 0
21 × × 36 700
19 × 10 × 0
250 0 0 450 0
21.
250,
– 700.
250,
. × × 3 × 0
× 4 8 × 0
21 × × 36 450
37
19 × 10 × 0
0 0 0 450 0
36.
450,
450.
450,
. × × 3 × 0
× 4 8 × 0
21 × × 36 0
19 × 10 × 0
0 0 0 0 0 ,
, ,
.
,
1
2
3
12
1
4 21
16
19
[250] 4
2
950
[700]
4
9
5
8
14
10
300
[300] 3
3
[250]
[700] 24
4
1350
[400] 36
33
34
450
[450] 250
1000
700
1100
2.
,
7,
m + n – 1 = 7. ,
.
3. ui + vj = cij,
. ui , v j u1 = 0.
,
, -
: u1 + v3 = 21; u4 + v3 = 36; u1 + v4 = 19; u3 + v4 = 10; u3 + v1 = 3; u3 + v2 = 8; u2 + v2 = 4;
0 + v3 = 21; 21 + u4 = 36; 0 + v4 = 19; 19 + u3 = 10; –9 + v1 = 3; –9 + v2 = 8; 17 + u2 = 4; 38
v3 = 21; u4 = 15; v4 = 19; u3 = –9; v1 = 12; v2 = 17; u2 = –13.
.
u1=0
v1=12 12
v2=17 16
v3=21 21 [250]
v4=19 19 [700]
4
4
9
5
8
14
10
u2= –13
[300] 3
u3= –9
[250] 24
u4=15
[400]
[700] 36
33
34
[450] ,
,
ui + vj > cij, . .
(1,2): 0 + 17 > 16; (2,4): –13 + 19 > 5; (4,1): 15 + 12 > 24;
= 0 + 17 – 16 = 1; 24 = –13 + 19 – 5 = 1; 41 = 15 + 12 – 24 = 3; 12
max(4,1) = 3. (4,1): 24. «+», «–», «+», «–».
(4,1) – . 1 1 2
2
3 21
19
12
16
4
4
9
5
8
14
10
[250] [+]
[700] [–]
950 300
[300] 3 [700]
[250] [–]
3
24
[400] [+] 33
36
(+) 250
1000
ij,
= min (3,1) = 250. ,
1350 34
[450] [–] 700
4
. .
4
450 1100 ,
250 250
ij,
39
, , .
. 1
2
3
12
1
4 21
16
19
[500] 4
2
950
[450]
4
9
5
8
14
10
300
[300] 3
3
[700] 24
4
36
33
[250] 250
34
450
[200] 1000
700
4. vj
1350
[650]
1100
. ui + vj = cij,
, u1 + v3 = 21; u4 + v3 = 36; u4 + v1 = 24; u1 + v4 = 19; u3 + v4 = 10; u3 + v2 = 8; u2 + v2 = 4;
0 + v3 = 21; 21 + u4 = 36; 15 + v1 = 24; 0 + v4 = 19; 19 + u3 = 10; –9 + v2 = 8; 17 + u2 = 4;
, :
ui, u1= 0.
v3 = 21; u4 = 15; v1 = 9; v4 = 19; u3 = –9; v2 = 17; u2 = –13. .
v1=9 u1=0 u2= –13
v4=19 19 [450]
4
4
9
5
8
14
10
3 [700] 24
0 + 17 > 16; –13 + 19 > 5;
[650] 33
[250]
, (1,2): (2,4):
v3=21 21 [500]
[300]
u3= –9 u4=15
12
v2=17 16
36
34
[200] , ui + vj > cij, . . = 0 + 17 – 16 = 1, 24 = –13 + 19 – 5 = 1, 12
40
max(1,2) = 1.
(1,2): 16. «+», «–», «+», «–».
(1,2) – . 1
2
3 16
12
4 19
21 [450] [–]
[500]
1 (+)
5
9
4
4
300
[300]
2
8
3
10
14 [650] [+]
[700] [–]
3 24
33
36
[250]
4
1350 34
[200]
250
1000
450
700
1100
ij,
. .
950
,
= min (1, 4) = 450. ,
,
450 ij,
450
, . .
1
3
12
1
16
4
19
4
9
5
8
14
10 [1100]
33
36
34
950
[500]
300
[300] 3
3
[250] 24 [250]
1350 450
[200]
250
1000
5. vj
4 21
[450]
2
4
2
700
1100
. ui + vj = cij,
,
, :
41
ui , u1 = 0.
u1 + v2 = 16; u2 + v2 = 4; u3 + v2 = 8; u3 + v4 = 10; u1 + v3 = 21; u4 + v3 = 36; u4 + v1 = 24;
0 + v2 = 16; 16 + u2 = 4; 16 + u3 = 8; –8 + v4 = 10; 0 + v3 = 21; 21 + u4 = 36; 15 + v1 = 24;
v2 = 16; u2 = –12; u3 = –8; v4 = 18; v3 = 21; u4 = 15; v1 = 9. .
v1=9 u1=0 u2= –12
v3=21 21 [500]
v4=18 19
4
4
9
5
8
14
10 [1100]
33
36
34
[300]
3
u3= –8 u4=15
12
v2=16 16 [450]
[250] 24 [250]
[200] ,
,
ui + vj > cij, . .
(2,4): –12 + 18 > 5;
24
= –12 + 18 – 5 = 1. (2,4): 5. «+», «–», «+», «–».
(2,4) – . 1
2
3
12
1
16 [450]
21
19
9
5
[500] 4
4 [300] [–]
2
300 8
14
[250] [+]
3 24
33
[250] 250
950
(+)
3
4
4
10 [1100] [–]
36
34
[200] 1000 42
700
1100
1350 450
-
ij,
. .
,
= min (2, 2) = 300. ,
,
300 ij,
300
, . .
1
2
3
12
1
16 [450]
4
2
4 21
19
9
5
950
[500] 4
300
[300] 3
3
8
14
[550] 24
4
33
36
34
450
[200] 1000
700
6. vj
1350
[800]
[250] 250
10
1100
. ui + vj = cij,
,
, :
u1 + v2 = 16; u3 + v2 = 8; u3 + v4 = 10; u2 + v4 = 5; u1 + v3 = 21; u4 + v3 = 36; u4 + v1 = 24;
0 + v2 = 16; 16 + u3 = 8; –8 + v4 = 10; 18 + u2 = 5; 0 + v3 = 21; 21 + u4 = 36; 15 + v1 = 24;
v2 = 16; u3 = –8; v4 = 18; u2 = –13; v3 = 21; u4 = 15; v1 = 9. .
v1=9 u1=0 u2= –13
v3=21 21 [500]
v4=18 19
4
4
9
5 [300]
3
u3= –8 u4=15
12
v2=16 16 [450]
8 [550]
24
[800] 33
[250]
36 [200]
43
10
14
34
ui , u1 = 0.
, ui + vj
cij.
F(x)= 16·450 + 21·500 + 5·300 + 8·550 + 10·800 + 24·250 + 36·200 = 44800, F(x) = 44800
.
.
2.
.
(
)
. ,
–
. .
, -
. . .
. 1 1 4 2 4
1 2 3
2 2 3 7 6
3 4 8 6 8
4 3 5 3 8
6 8 10
3
ai = 6 + 8 + 10 = 24, i 1 4
b j = 4 + 6 + 8 + 8 = 26. j 1
, .
, .
(
)
, ,
44
,
2 (26–24). .
, -
. 1 1 4 2 0 4
1 2 3 4
2 2 3 7 0 6
3 4 8 6 0 8
4 3 5 3 0 8
6 8 10 2
.
:
,
,
= (cij), .
1.
,
-
. 1 1[4] 4 2 0 4
1 2 3 4
2 2[2] 3[4] 7 0 6
3 4 8[4] 6[2] 0[2] 8
4 3 5 3[8] 0 8
6 8 10 2
, , ,
-
, .
2. m + n – 1 = 7.
,
7,
,
.
F(x) = 1·4 + 2·2 + 3·4 + 8·4 + 6·2 + 3·8 + 0·2 = 88. 3.
. ,
45
, ,
. -
, , . . . .
ij,
(
), ij =1
i
j.
, . (
ij
-
). , ,
ij
,
. -
. (
,
,
,
. .). ( .
(
)
-
)
,
,
. ,
,
ij.
–
, . .
.
, , ,
,
, , . , ,
, ij
, . .,
. :
–
, .
, -
. . ij,
– .
46
,
4.
. (1,3)
«+», «–», «+», «–».
– 1 1[4] 4 2 0 4
1 2 3 4
2 2[2] [–] 3[4] [+] 7 0 6
3 4 (+) 8[4] [–] 6[2] 0[2] 8
(1,3; 1,2; 2,2; 2,3)
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3 5 3[8] 0 8
. 13 = (4) – (2) + (3) – (8) = –3.
(1,4)
1 1[4] 4 2 0 4
-
2 3 4 2[2] [–] 4 3 (+) 5 3[4] [+] 8[4] [–] 7 6[2] [+] 3[8] [–] 0 0[2] 0 6 8 8
-
6 8 10 2
(1,4; 1,2; 2,2; 2,3; 3,3; 3,4)
. 14 = (3) – (2) + (3) – (8) + (6) – (3) = –1.
(2,1)
«+», «–», «+», «–».
–
1 2 3 4
1 1[4] [–] 4 (+) 2 0 4
2 2[2] [+] 3[4] [–] 7 0 6
(2,1; 2,2; 1,2; 1,1)
3 4 8[4] 6[2] 0[2] 8
4 3 5 3[8] 0
. 21 = (4) – (3) + (2) – (1) = 2.
47
-
6 8 10 2
(2,4)
«+», «–», «+», «–».
–
1
1 1[4]
2 2[2]
3 4
2
4
3[4]
8[4] [–]
5
(+)
8
3
2 0
7 0
6[2] [+] 0[2]
3[8] [–] 0
10 2
4
6
8
8
4
(2,4; 2,3; 3,3; 3,4)
4 3
-
6
. 24 = (5) – (8) + (6) – (3) = 0.
(3,1)
«+», «–», «+», «–».
–
-
1
1 1[4] [–]
2 2[2] [+]
3 4
4 3
6
2
4
3[4] [–]
8[4] [+]
5
8
0
7 0
6[2] [–] 0[2]
3[8] 0
10 2
4
6
8
8
3
2
(+)
4
(3,1; 3,3; 2,3; 2,2; 1,2; 1,1)
(3,2)
. 31 = (2) – (6) + (8) – (3) + (2) – (1) = 2. «+», «–», «+», «–».
–
-
1
1 1[4]
2 2[2]
3 4
4 3
6
2
4
3[4] [–]
8[4] [+]
5
8
3
2
7
6[2] [–]
3[8]
10
4
0
0
0[2]
0
2
4
6
8
8
(+)
(3,2; 3,3; 2,3; 2,2)
. 32 = (7) – (6) + (8) – (3) = 6.
48
(4,1)
«+», «–», «+», «–».
–
1 2 3 4
1 1[4] [–] 4 2 0 (+) 4
2 2[2] [+] 3[4] [–] 7 0 6
3 4 8[4] [+] 6[2] 0[2] [–] 8
4 3 5 3[8] 0 8
-
6 8 10 2
(4,1; 4,3; 2,3; 2,2; 1,2; 1,1)
. 41 = (0) – (0) + (8) – (3) + (2) – (1) = 6.
(4,2)
«+», «–», «+», «–».
–
1 2 3 4
1 1[4] 4 2 0 4
2 2[2] 3[4] [–] 7 (+) 0 6
(4,2; 4,3; 2,3; 2,2)
(4,4; 4,3; 3,3; 3,4)
(1,3),
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3 5 3[8] 0 8
. 42 = (0) – (0) + (8) – (3) = 5.
(4,4)
1 1[4] 4 2 0 4
3 4 8[4] [+] 6[2] 0[2] [–] 8
-
2 2[2] 3[4] 7 0 6
3 4 8[4] 6[2] [+] 0[2] [–] 8
4 3 5 3[8] [–] 0 (+) 8
. 44 = (0) – (0) + (6) – (3) = 3. , (–3).
49
-
6 8 10 2
-
5.
. (1,3) ,
, ,
. .
, ij, = min (1, 2) = 2. , 2
. , 2 ij
, -
,
,
. ,
F(x) = 1·4 + 4·2 + 3·6 + 8·2 + 6·2 + 3·8 + 0·2 = 82 1 1[4] 4 2 0 4
1 2 3 4
2 2 3[6] 7 0 6
3 4[2] 8[2] 6[2] 0[2] 8
.
.
4 3 5 3[8] 0 8
6 8 10 2
. (1,2)
1 2 3 4
«+», «–», «+», «–». 1 1[4] 4 2 0 4
–
2 2 (+) 3[6] [–] 7 0 6
(1,2; 1,3; 2,3; 2,2)
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3 5 3[8] 0 8
. 12 = (2) – (4) + (8) – (3) = 3.
(1,4)
1 1[4] 4 2 0 4
3 4[2] [–] 8[2] [+] 6[2] 0[2] 8
2 2 3[6] 7 0 6
3 4[2] [–] 8[2] 6[2] [+] 0[2] 8 50
-
4 3
(+)
5 3[8] [–] 0 8
6 8 10 2
(1,4; 1,3; 3,3; 3,4)
. 14 = (3) – (4) + (6) – (3) = 2. «+», «–», «+», «–».
(2,1) –
1 2 3 4
1 1[4] [–] (+) 4 2 0 4
2 2 3[6] 7 0 6
3 4[2] [+] 8[2] [–] 6[2] 0[2] 8
(2,1; 2,3; 1,3; 1,1)
1 1[4] 4 2 0 4
2 2 3[6] 7 0 6
3 4[2] 8[2] [–] 6[2] [+] 0[2] 8
(2,4; 2,3; 3,3; 3,4)
-
4 3
6 8 10 2
5 (+) 3[8] [–] 0 8
. 24 = (5) – (8) + (6) – (3) = 0.
(3,1)
«+», «–», «+», «–».
–
1 2 3 4
6 8 10 2
«+», «–», «+», «–».
–
1 1[4] [–] 4 (+) 2 0 4
4 3 5 3[8] 0 8
. 21 = (4) – (8) + (4) – (1) = –1.
(2,4)
1 2 3 4
-
2 2 3[6] 7 0 6
3 4[2] [+] 8[2] 6[2] [–] 0[2] 8
(3,1; 3,3; 1,3; 1,1)
4 3 5 3[8] 0 8
-
6 8 10 2
. 31 = (2) – (6) + (4) – (1) = –1.
51
(3,2)
«+», «–», «+», «–».
–
1 2 3 4
1 1[4] 4 2 0 4
2 2 3[6] [–] 7 (+) 0 6
(3,2; 3,3; 2,3; 2,2)
2 2 3[6] 7 0 6
3 4[2] [+] 8[2] 6[2] 0[2] [–] 8
(4,1; 4,3; 1,3; 1,1)
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3 5 3[8] 0 8
-
. 41 = (0) – (0) + (4) – (1) = 3.
(4,2)
1 1[4] 4 2 0 4
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3 5 3[8] 0 8
. 32 = (7) – (6) + (8) – (3) = 6.
(4,1)
1 1[4] [–] 4 2 0 (+) 4
3 4[2] 8[2] [+] 6[2] [–] 0[2] 8
-
2 2 3[6] [–] 7 0 (+) 6
(4,2; 4,3; 2,3; 2,2)
3 4[2] 8[2] [+] 6[2] 0[2] [–] 8
4 3 5 3[8] 0 8
. 42 = (0) – (0) + (8) – (3) = 5.
52
-
6 8 10 2
(4,4)
«+», «–», «+», «–».
– 1 1[4] 4 2 0 4
1 2 3 4
2 2 3[6] 7 0 6
3 4[2] 8[2] 6[2] [+] 0[2] [–] 8
(4,4; 4,3; 3,3; 3,4)
-
4 3 5 3[8] [–] 0 (+) 8
6 8 10 2
. 44 = (0) – (0) + (6) – (3) = 3. , (–1). ,
(2,1; 3,1),
-
. ,
-
, . 6.
.
(2,1)
,
-
,
-
, , . ij,
. .
,
= min (2, 3) = 2. , 2
2 ij
, -
,
,
. -
, F(x) = 1·2 + 4·4 + 4·2 + 3·6 + 6·2 + 3·8 + 0·2 = 80 1 1[2] 4[2] 2 0 4
1 2 3 4
2 2 3[6] 7 0 6
3 4[4] 8 6[2] 0[2] 8
(3,1)
4 3 5 3[8] 0 8
. 6 8 10 2 ,
, , 53
.
, . ij,
. .
,
= min (3, 3) = 2. , 2
2
, -
,
ij,
. -
, F(x) = 1·2 + 4·4 + 3·6 + 8·2 + 2·2 + 3·8 + 0·2 = 80 1 1[2] 4 2[2] 0 4
1 2 3 4
2 2 3[6] 7 0 6
3 4[4] 8[2] 6 0[2] 8
.
.
4 3 5 3[8] 0 8
6 8 10 2
(2,1;3,1)
,
F(x) = 80. . (1,2)
1 2 3 4
«+», «–», «+», «–». 1 1[2] [–] 4[2] [+] 2 0 4
–
2 2 (+) 3[6] [–] 7 0 6
(1,2; 1,1; 2,1; 2,2)
–
1 2 3 4
4 3 5 3[8] 0 8
6 8 10 2
. 12 = (2) – (1) + (4) – (3) = 2. «+», «–», «+», «–».
(1,4)
1 1[2] 4[2] 2 0 4
3 4[4] 8 6[2] 0[2] 8
2 2 3[6] 7 0 6
3 4[4] [–] 8 6[2] [+] 0[2] 8
(1,4; 1,3; 3,3; 3,4)
4 3
(+)
5 3[8] [–] 0 8 .
54
-
6 8 10 2
14
(2,3) –
1 2 3 4
1 1[2] [+] 4[2] [–] 2 0 4
2 2 3[6] 7 0 6
3 4[4] [–] 8 (+) 6[2] 0[2] 8
(2,3; 2,1; 1,1; 1,3)
2 2 3[6] 7 0 6
3 4[4] [–] 8 6[2] [+] 0[2] 8
(2,4; 2,1; 1,1; 1,3; 3,3; 3,4)
(3,1)
1 2 3 4
-
4 3
6 8 10 2
5 (+) 3[8] [–] 0 8
. 24 = (5) – (4) + (1) – (4) + (6) – (3) = 1. «+», «–», «+», «–».
– 1 1[2] [–] 4[2] 2 (+) 0 4
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3 5 3[8] 0 8
-
. 23 = (8) – (4) + (1) – (4) = 1.
(2,4)
1 1[2] [+] 4[2] [–] 2 0 4
= (3) – (4) + (6) – (3) = 2. «+», «–», «+», «–».
2 2 3[6] 7 0 6
3 4[4] [+] 8 6[2] [–] 0[2] 8
(3,1; 3,3; 1,3; 1,1)
4 3 5 3[8] 0 8
-
6 8 10 2
. 31 = (2) – (6) + (4) – (1) = –1.
55
(3,2)
«+», «–», «+», «–».
–
1 2 3 4
1 1[2] [–] 4[2] [+] 2 0 4
2 2 3[6] [–] 7 (+) 0 6
(3,2; 3,3; 1,3; 1,1; 2,1; 2,2)
(4,1)
1 2 3 4
2 2 3[6] 7 0 6
4 3 5 3[8] 0 8
-
6 8 10 2
. 41 = (0) – (0) + (4) – (1) = 3.
(4,2)
«+», «–», «+», «–».
–
1 2 3 4
6 8 10 2
. 32 = (7) – (6) + (4) – (1) + (4) – (3) = 5.
3 4[4] [+] 8 6[2] 0[2] [–] 8
(4,1; 4,3; 1,3; 1,1)
1 1[2] [–] 4[2] [+] 2 0 4
4 3 5 3[8] 0 8
«+», «–», «+», «–».
– 1 1[2] [–] 4[2] 2 0 (+) 4
3 4[4] [+] 8 6[2] [–] 0[2] 8
-
2 2 3[6] [–] 7 0 (+) 6
(4,2; 4,3; 1,3; 1,1; 2,1; 2,2)
(4,4)
3 4[4] [+] 8 6[2] 0[2] [–] 8
4 3 5 3[8] 0 8
56
6 8 10 2
. 42 = (0) – (0) + (4) – (1) + (4) – (3) = 4. «+», «–», «+», «–».
–
-
-
1 1[2] 4[2] 2 0 4
1 2 3 4
2 2 3[6] 7 0 6
(4,4; 4,3; 3,3; 3,4)
3 4[4] 8 6[2] [+] 0[2] [–] 8
4 3 5 3[8] [–] 0 (+) 8
6 8 10 2
. 44 = (0) – (0) + (6) – (3) = 3. , (–1).
(3,1), 7.
-
.
(3,1)
,
-
,
-
, , . ij,
. .
,
= min (1, 1) = 2. , 2
2 ij
, -
,
,
. -
, F(x) = 4·6 + 4·2 + 3·6 + 2·2 + 3·8 + 0·2 = 78 1 1 4[2] 2[2] 0 4
1 2 3 4
2 2 3[6] 7 0 6
3 4[6] 8 6[0] 0[2] 8
.
4 3 5 3[8] 0 8
. 6 8 10 2
. (1,1)
«+», «–», «+», «–». 1
1 2 3 4
1
(+) 4[2] 2[2] [–] 0 4
–
2 2 3[6] 7 0 6
3 4[6] [–] 8 6[0] [+] 0[2] 8 57
4 3 5 3[8] 0 8
6 8 10 2
(1,1; 1,3; 3,3; 3,1)
. 11 = (1) – (4) + (6) – (2) = 1.
(1,2) – 1 2 3 4
1 1 4[2] [+] 2[2] [–] 0 4
2 2 (+) 3[6] [–] 7 0 6
(1,2; 1,3; 3,3; 3,1; 2,1; 2,2)
(1,4)
1 2 3 4
2 2 3[6] 7 0 6
-
4 3
(+)
5 3[8] [–] 0 8
6 8 10 2
. 14 = (3) – (4) + (6) – (3) = 2.
(2,3)
«+», «–», «+», «–».
–
1 2 3 4
6 8 10 2
. 12 = (2) – (4) + (6) – (2) + (4) – (3) = 3.
3 4[6] [–] 8 6[0] [+] 0[2] 8
(1,4; 1,3; 3,3; 3,4)
1 1 4[2] [–] 2[2] [+] 0 4
-
«+», «–», «+», «–».
– 1 1 4[2] 2[2] 0 4
«+», «–», «+», «–». 3 4 4[6] [–] 3 8 5 6[0] [+] 3[8] 0[2] 0 8 8
2 2 3[6] 7 0 6
3 4[6] 8 (+) 6[0] [–] 0[2] 8
(2,3; 2,1; 3,1; 3,3)
4 3 5 3[8] 0 8 .
58
-
6 8 10 2
23
(2,4)
«+», «–», «+», «–».
–
1 2 3 4
1 1 4[2] [–] 2[2] [+] 0 4
2 2 3[6] 7 0 6
3 4[6] 8 6[0] 0[2] 8
(2,4; 2,1; 3,1; 3,4)
2 2 3[6] [–] 7 (+) 0 6
(3,2; 3,1; 2,1; 2,2)
4 3 5 3[8] 0 8
6 8 10 2
«+», «–», «+», «–».
– 1 2 3 4
3 4[6] 8 6[0] 0[2] 8
-
. 32 = (7) – (2) + (4) – (3) = 6.
(4,1) 1 1 4[2] 2[2] [–] 0 (+) 4
5 (+) 3[8] [–] 0 8
6 8 10 2
«+», «–», «+», «–».
–
1 2 3 4
4 3
-
. 24 = (5) – (4) + (2) – (3) = 0.
(3,2)
1 1 4[2] [+] 2[2] [–] 0 4
= (8) – (4) + (2) – (6) = 0.
2 2 3[6] 7 0 6
3 4[6] 8 6[0] [+] 0[2] [–] 8
(4,1; 4,3; 3,3; 3,1)
4 3 5 3[8] 0 8
. 41 = (0) – (0) + (6) – (2) = 4.
59
-
6 8 10 2
(4,2)
«+», «–», «+», «–».
– 1 1 4[2] [+] 2[2] [–] 0 4
1 2 3 4
2 2 3[6] [–] 7 0 (+) 6
(4,2; 4,3; 3,3; 3,1; 2,1; 2,2)
3 4[6] 8 6[0] [+] 0[2] [–] 8
6 8 10 2
«+», «–», «+», «–».
– 1 2 3 4
4 3 5 3[8] 0 8
. 42 = (0) – (0) + (6) – (2) + (4) – (3) = 5.
(4,4) 1 1 4[2] 2[2] 0 4
-
2 2 3[6] 7 0 6
3 4[6] 8 6[0] [+] 0[2] [–] 8
(4,4; 4,3; 3,3; 3,4)
-
4 3 5 3[8] [–] 0 (+) 8
6 8 10 2
. 44 = (0) – (0) + (6) – (3) = 3. , ,
F(x)
,
-
,
. ,
.
F(x) = 4·6 + 4·2 + 3·6 + 2·2 + 3·8 + 0·2 = 78
.
. -
,
, , ,
–
.
.
60
1.
3
u( x1 , x 2 )
).
x10,25 x 20,75 , p1 1,
x1
x2 –
.
p2 6
x1
.
2.
.
x2
?
x10,25 x 20,75 x1
2 x2
6, x1
max, 0, x2
0. -
.
dx 2 dx1
0,25 x1 0,75 x 20,75 0,75 x10,25 x 2 0,25
u u : x1 x 2
x2 . 3 x1 -
. ,
x1
2 x2
x2
6
3
1 x1 2 .
,
x2 3x1
1 2
x2
3 x1 . 2
,
3 * x1 2
3
1 * x2 2
x1*
61
3 * , x2 2
9 . 4
u
3 2
*
0, 25
9 4
0, 75
x10, 25 x 20,75
L( x1 , x 2 , )
1, 75
3 2
2,033 .
( x1
2 x2
.
-
2,033. . .
-
6) .
:
L x1
0,
L x2
0,
L
0,25 x1 0,75 x 20,75 0,75 x 10,25 x 2 0,25 x1
2 x2
0, 2
0,
6 0.
0, 2,
,
0,5 x1 0,75 x 20,75 x1
2 x2
0,75 x10,25 x 2 0,25 ,
. .
6 0,
3 0,25 2
3 x1 , 2
x1 2 x2 6 0,
3 , x 2* 2
x1*
*
x2
3/ 4
9 4
9 , 4
3/ 4
3 2
0,25
3/ 4
0,339 .
, 1,5
.
2,25
.
. 1
0,339.
62
1.
.
.
: «
)/ . . , . . 2. . . .– : 3. . . . . , . . view.php?id=374.
.–
: :
.
. »( , 2012. – 91 . / . .
-
, 2007. – 75 . « » / . – URL: http://sdo2.irgups.ru/course/
63
. . : . .
,
. .
03.05.2017. 60×84/16. . . . 4,0. 2017 . , .
. .-
. . 4,27. 100. ,
64
.
,15