Івченко І.Ю. Математичне програмування
Подождите немного. Документ загружается.
111
= ! -
$. % $ ">,
= p + q – 1, # = ’ -
. % $= <
«$ », # > $ -
, # ! = $
($=, -
= $ $ >).
1.
; $ .
+ 26
,!*,5 !
B
j
A
i
B
1
B
2
B
3
"
b
j
a
i
236
A
1
5
2
2
1
3
3a
1
' = 2
a
1
'' = 0
A
2
2
4 3 5
2
a
2
' = 0
A
3
4
3
0
6 4
4
a
3
' = 4
a
3
'' = 0
"
b
1
' = 0 b
2
' = 0
b
3
' = 2
b
3
'' = 0
,
31
= 0, # ,
12
= 2, !
B
1
A
1
cc
i
i
331
mi
n
, = $ $ ,
31
,
13
= 0. -
! .
4.
39F
? = > V min -
>. ; = $ = . ? -
> VV. ? >> ,
112
V. ; $-
, # ", >> -
. @ =
.
5.
:3 3 (
3C (
& $. 26 ($ -
).
C $ $ " -
,
24
= T > 0 ( #
24
= 1 " $
ij
). * "! $
4
7
2
. @ $ > T
,
14
= 2, "! $ 7
1
, -
,
12
= 2 T. K " $
2
T ,
32
= 3. @ $ 7
3
,
33
= 1 T. O , > T ,
23
= 2,
>! $
3
, " -
, A
2
, " " (. $.
25 ), , #$ ,
ij
( ) -
, T $ $", = ,
ij
,
T . ;! "
( =). % T $ :
T d
x
ij
min
.
;
min $>! .
,
24
= T, , #$ $-
p + q – 1, $ -
. A = $, #
T =
x
ij
min
.
. (12.6)
'!, # $ . )$ $
! T .
6.
23(3
? -
> '
j
, # <
$>!
113
ca
jk
m
k
ij
j
O
¦
'
1
, j= ,n1 , (12.7)
O
k
— ! :
Ca
sik
m
k
ksi
O
¦
*
1
, i= ,m1 . (12.8)
) (12.7) (12.8) = $
:
'
j
= / · A
j
– C
j
, j = ,n1 . (12.9)
/ A
si
=
si
, i= ,m1 .
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
©
§
a
a
a
A
mj
j
j
j
...
2
1
,
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
©
§
a
a
a
A
msi
si
si
si
...
2
1
, / = (O
1
, O
2
,..., O
m
).
A
j
— (9.15)—(9.17), !-
,
j
.
A
si
— - , # $ -
. * = $ -
A
ij
(12.1)—(12.4), ! ,
ij
$ %, >
¸
¸
¸
¸
¸
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
©
§
0
...
1
...
0
...
1
...
0
A
ij
P
+ j (12.10)
K I
x
(i, j), # >
$. 25, $ ,
ij
> 0.
114
I
x
= {(i, j), ,
ij
> 0} (12.11)
? W = /
W = (U
1
, U
2
, …, U
p
, – X
1
, – X
2
, …, –X
q
)... (12.12)
K '
ij
7
ij
( !> '
j
A
j
), (12.9) ! :
'
ij
= WA
ij
–
ij
= U
i
– X
j
–
ij
. (12.13)
=! $ U
i
X
j
— -
W
WA
ij
= U
i
– X
j
=
ij
, (i, j) I
x
(12.14)
) (12.14) p + q – 1 p + q
U
i
X
j
. ' A
ij
(12.14), -= $.
=, ! ! ’, #
(, U
1
= 0).
; U
i
–X
j
(12.13) = $
'
ij
$.
. %.
X % , # '
ij
d 0 (i = ,p1 ;
j =
,q1 ). ) (12.13) ! !,
> , << ’.
J $. 26. '"
, # > $ $. 26.
A: (1,1), (1,2), (2,2), (3,2), (3,3), (3.4).
) (12.14):
U
1
– X
1
=
11
= 3, U
3
– X
2
=
32
= 2,
U
1
– X
2
=
12
= 2, U
3
– X
3
=
33
= 3,
U
2
– X
2
=
22
= 4, U
3
– X
4
=
34
= 2.
" . @! U
1
= 0,
–X
1
= 3, –X
2
= 2, U
2
= 2, U
3
= 0, –X
3
= 3, –X
4
= 2.
@ $ U
i
-X
j
-
:
) >
C =
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
©
§
CCC
CCC
C%%
pqpp
q
q
...
.......................
...
...
21
22221
11211
;
115
$) > «U
i
» «-X
j
»
U
i
C =
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
©
§
CCC
CCC
C%%
pqpp
q
q
...
....................
...
...
21
22221
11211
0;
–
X
j
) % , # > -
;
) U
1
0 " U
i
;
) U
i
(U
1
= 0)
ij
(
1j
)
" $ –X
j
, #$
(12.14), –X
j
«–X
j
»;
) , !
ij
–
X
j
; $ U
i
(12.14);
=) > . .;
) ) U
i
–X
j
.
7. ( 23(3
1. $> %.
2. ;$ X, $ -
L(X).
3. ' > %, , # -
> .
4. $ U
i
–X
j
.
5. $ > %`.
6. ; . J# '
ij
d 0, -
. &’ . J# !
'
ij
t 0, ’ =.
7. ) '
ij
t 0 $ '
st
= max'
ij
.
8. @ '
st
$ T.
9. $ T, T =
X
ij
kr
min
,
,
! ,
ij
, # "> -
(. .) .
10. ;$ X`, #> T ,
$ L(X`)
L(X`) = L(X) – T'
st
.
116
% (%) ! => > -
< :;. % ! :
min o L(x) =
¦¦
q
j
p
i
ijij
xc
11
¦
q
j
iij
ax
1
, i = ,P1
¦
p
i
jij
bx
1
, j = ,q1
X
ij
t 0, i = ,P1 , j = ,q1 ,
¦¦
q
j
j
p
i
i
ba
11
.
; ’ %:
1. (! X.
2. $>! %`.
3. ;! .
4. J# '
ij
d0, . &’-
. J# ! '
ij
t0, ’ -
=.
1.
!$ !-%* #
; = ’
.12
¦¦
j
j
i
i
ba
117
+ 27
,!*,5 !
B
1
B
2
B
3
B
4
B
j
A
i
b
j
a
i
2532
"
A
1
4
3
2
2
2
21= 2
= 0
A
2
2
2
4
2
3 1
= 0
A
3
6
2
2
1
3
3
2
2
= 5
= 2
= 0
" b
1
' = 0
b
2
' = 3
b
2
'' = 1
b
2
''' = 0
b
3
' = 0 b
4
' = 0
L(X) = 33.
2.
!$ $' $
+ 28
,!*,5 !
B
1
B
2
B
3
B
4
B
j
A
i
b
j
a
i
2532
"
A
1
4
3
2
2
3
2
2
1
2
2
a
1
' = 2
a
1
'' = 0
A
2
2
2
2
4
3
2
6
1
T
1
a
2
' = 0
A
3
6
2
2
2
3
4
3
1
5
2
2
a
3
' = 3
a
3
'' = 1
a
3
''' = 0
" b
1
' = 0
b
2
' = 3
b
2
'' = 0
b
3
' = 2
b
3
'' = 0
b
4
' = 0
118
C ,
12
= 2 ( # b
2
=5> 2
'
1
a
). @, #
C
32
= ,32)2,4min(
322
min
xc
i
i
336
'
23
'
3
baa
. . '-
!, # , $ -
, = .
3.
!&, !
+ 29
,!*,5 !
B
1
B
2
B
3
B
4
B
j
A
b
j
a
i
2532
"
A
1
4
3 V 2 V 2
2
VV 1
22,0
A
2
2
24
1
3
1
V 1
1,0
A
3
6
VV 2
2
2
4
32
4,0
-
"
01,00 0
L(X) = 21
%.
X % , # '
ij
d 0 (i = ,p1 ;
j =
,q1 ).
4.
6$!
) " > % $. 25;
$)
ij
, # > $;
) " «U
i
» «–X
j
»;
U
i
% =
¸
¸
¸
¹
·
¨
¨
¨
©
§
2322
1342
1223
0
–X
j
119
) U
1
! (U
1
= 0);
) " :
11
= 3
12
= 2, (12.14):
U
1
– X
1
=3 o 0 – X
1
=3 o –X
1
= 3.
O" , U
1
$ $ –X
1
, #$
> $
11
–X
2
= 2;
U
i
% =
¸
¸
¸
¹
·
¨
¨
¨
©
§
2322
1342
1223
0
–
X
j
3 2;
) –X
2
–X
1
" ! -
ij
!
22
= 4,
32
= 2 –X
2
= 2, $ = ’
U
2
– X
2
=4 o U
2
=2,
U
3
– X
2
=2 o U
3
=0;
U
i
% =
0
2
0
2322
1342
1223
¸
¸
¸
¹
·
¨
¨
¨
©
§
–X
j
3 2;
=) U
2
= 2 U
3
= 0,
-X
3
–X
4
:
U
3
– X
3
=
33
= 3 o –X
3
= 3,
U
3
– X
4
= 2 o –X
4
= 2.
U
i
% =
0
2
0
2322
1342
1223
¸
¸
¸
¹
·
¨
¨
¨
©
§
–X
j
3 2 3 2.
%, U
i
–X
j
, = $ '
ij
(12.3). @ U
i
+ (–X
j
) $
ij
(i = ,p1 ) (j = ,q1 ) > C
`
.
C
`
=
¸
¸
¸
¹
·
¨
¨
¨
©
§
1100
'
11
= U
1
+ ( – X
1
) –
11
= 0 + 3 – 3 = 0,
120
'
12
= U
1
+ ( – X
2
) –
12
= 0 + 2 – 2 = 0,
'
13
= U
1
+ ( – X
3
) –
13
= 0 + 3 – 2 = 1,
'
14
= U
1
+ ( – X
4
) –
14
= 0 + 2 – 1 = 1.
;=> , = -
>
C` =
¸
¸
¸
¹
·
¨
¨
¨
©
§
0001
3203
1100
; , # > ($-
$ $ ), >> >.
%, , = -
. * # '
ij
t 0, %, $. 25,
. @ < :; ! -
"
L(X`) = L(X) – T'
k
, (12.15)
8 8` — «» . @
% (12.15) ! :
L(X`) = L(X) – T'
st
, (12.16)
T ! (12.6), '
st
(12.13). @ #$ ""
min(X), (s,t) $ , #$
T'
st
=
max
),( ji
T'
ij
. (12.17)
* # $ T'
st
’ <
$ T, (12.17) -
!
'
st
=
max
),( ji
'
ij
. (12.18)
? $ (12.18) ! $,
< ! $
. ; , # '
st
= '
21
= '
24
= 3
( '
st
= '
24
), T = min(X
22
, X
34
) = min(2,2)
= 2. % # T ! -
,
, <! ,
24
= T. ? $ $-
= (p + q – 1) – 1 -
, # $ («#») -
. % ,`
22
$ ,`
24
$