Івченко І.Ю. Математичне програмування
Подождите немного. Документ загружается.
31
$
.
, +- :
»
»
»
¼
º
«
«
«
¬
ª
nmnn
m
m
ccc
ccc
ccc
C
!
####
!
!
21
22221
11211
»
»
»
¼
º
«
«
«
¬
ª
n
i
a
a
a
A
#
1
' = (b
1
,…, b
j
,…, b
m
)
@ <
0tij
x
, i = 1,…, n, j = 1,…, m, > =,
i- $ j- =.
’:
;$ $ ,
ij
> = 0, > -
>
min)(
11
o
¦¦
n
i
ij
m
j
ij
xcxL (3.5)
O > :
i
m
j
ij
ax
¦
1
(i = 1,…, n), (3.6)
j
n
i
ij
bx
¦
1
(j = 1,…, n), (3.7)
0tij
x
(i = 1, …,m; j = 1, …, n), (3.8)
%- ! $> :; m · n -
$=- m + n.
C$ ,
ij
, # > (3.6)—(3.8), -
>
»
»
»
¼
º
«
«
«
¬
ª
mnmm
n
n
xxx
xxx
xxx
x
!
####
!
!
21
22221
11211
,
> F > %-,
,
ij
— . ; 8
, < -
< , ! . % = [
ij
],
32
i = 1, …, n, j = 1, …, m ! ! , -
.
? (3.6) !
$, (3.7) ! .
C > , ! =
$ ( $)
¦¦
n
i
m
j
ji
ba
11
(3.9)
, :
¦¦
z
n
i
m
j
ji
ba
11
. (3.10)
3.
8 38 (3 4:
(3.5)—(3.8) (3.9) ! ! -
!, (3.10) — ! !. & (3.9) !
$> > >
(3.6) (3.7) ’, , =, =
’ . J# ! $> ,
$ < < .
;
¦¦
!
n
i
m
j
ji
ba
11
$ =-
, $
b
n + 1
= 6a
i
– 6b
j
, (3.11)
#
¦¦
n
i
m
j
ji
ba
11
, $. ;-
= ’ >4@.
O> " ’ +-. @ -
, . @
" — , .
&’ +- > !
:
Q ;
Q ;
Q , # " -
!< $ .
33
@ :;
= « < $ =-
», < (1.1)—(1.3)
= $ < >4@.
< :;:
Y &
min)(
11
o
¦¦
n
i
m
j
ijij
xcxL .
; $=:
i
m
j
ij
Axa
¦
d
1
(i = 1, …, n);
i
n
i
ij
bx
¦
1
(j = 1, …, m);
x
ij
t 0 (i = 1, …, n; j = 1, …, m).
@ ( )
= « -
’», «% -
», « < = $ =».
1. P « & -
, ', ’», «+ », «
, '»? K-
; , .
2. [ ! -
, ?
3. ' ()) .
34
4
3 (5 3(
B3: 443
1.
3(53 3
! -
= , .
:
n ! -
, # >
1
,
2
,…,
n
, m
$ b
1
, b
2
,…, b
m
c
ij
O
ij
,
ij
— i- j-
$ O
ij
— j- $, # >
> i- .
’:
? ,
ij
— i- , -
j- $.
! k = mn ,
ij
, # -
> $=
0tij
x
(i = 1, …, n; j = 1, …, m); (4.1)
i
m
j
ij
ax d
¦
1
(i =1, …, n); (4.2)
j
n
i
ijij
bx tO
¦
1
(j = 1, …, m) (4.3)
> (>) >
¦¦
n
i
m
j
ijij
xcZ
11
. (4.4)
= = >
, a
i
, b
j
,
c
ij
, O
ij
, #, > < < .
%, , O
ij
= = i- ,
> j- $.
% $= (4.2), (4.3)
¦
d
m
j
i
ij
ax
1
¦
t
O
n
i
j
ij
ij
b
x
1
.
J#
ij
> j- $
35
/"., < <
¦¦
O
n
i
ij
ij
ij
m
j
x
c
11
. .
I Z = , #
ij
> $-
, . ., , # >>
, $ . .
I = $ x
ij
. ;-
=> (4.1)—
(4.4), ! $ <.
$= = O
ij
(
# «O-»), -
. & =>
> $> , # >
$> > ’ .
; O
ij
>
, # = -
. %
!:
— ( O
ij
= const $- i j);
— ( O
ij
-
, $ O
ij
= O
1j
;
— i);
(O
ij
D
i
O
ij
i).
2.
3(53 3 3 44
&
1
, …,
, …, a
n
— !,
$ b
1
, …, b
j
, …, b
m
— (> -
). K O
ij
= O
j
(j = 1, …, m) > k-
$, # = $ > $- -
. K c
ij
, =, > i-
j- $.
C x
ij
, # > i- -
, # > j- $.
$= (4.1)—(4.4), -
" $= (4.3), # > -
¦
tO
n
i
j
ijij
bx
1
(j = 1, …, m).
36
@ $ = ,
! , $. ? -
> O
i
, # >
$, = $ > i- -
.
3.
3(53 3 239 44
&
1
, …,
i
,…, a
n
$ b
1
, …, b
j
, …, b
m
— -
, O
ij
, < >> ’ =
$, , $ O
ij
= D
i
O
ij
(j = 1, …, m), D
i
> i- . K c
ij
" > i- -
j- $, x
ij
— , # >
i- , # >
j- $.
; " <
ij
O
ij
,
(4.1)—(4.3).
(4.1)—(4.4), (O->), -
O.
@ ’ ! $ , #
! $> , $
(, ). '
$ >5@.
6 —
!-
.
I = $ x
ij
(
i- , j- $).
= = >
, a
i
, b
j
,
c
ij
, O
ij
.
; O
ij
>
, # =
. % !:
— ;
— ;
— .
37
1. O ! ?
2. $ ! ,
ij
, ,
a
i
, b
j
, c
ij
, O
ij
, ,.
3. & O-?
4. ' :
Q ;
Q ;
Q ' .
' .
1.
+ , 7, , % 1, 2, 3.
6 , (
3
/):
869
468
983
* , (/):
244
426
537
6 :
540, 430, 150 (.).
A. , H
* '
: : = 1 : 2 : 3.
B. ' , -
, ,
= 60, = 50, =
= 80
3
.
2.
),' , , ' 1, 2,
3 * , & .
38
'
+
1
, +
2
, +
3
. K ' -
:
1 :
495
883
—7 5
2 :
25—
943
7—3
3 :
4——
58—
36—
6 200, 400, 300.
22, 18, 30 .
A. % ' , -
' .
B. !, H ! ', H
!,
* ; 1 : 2 : 1, -
, H *
.
3.
), 7, , % 1, 2, 3.
* , (/):
12 24 34
63 32 56
35 53 67
K ,
(
3
/):
55 66 77
45 36 89
39 68 53
6 : 640, 330, 128 ().
A. , -
, .
B. , H
* '
: : = 1 : 2 : 3.
39
4.
+ , 1, 2, 3 -
7, , %. 6 , -
(
3
/):
30 20 40
31 30 50
32 40 20
* , (/.):
243
325
536
6 : 400, 300, 280 ().
A. , -
, .
B. , H
* '
: : = 1 : 2 : 3.
C.
' , -
! , , = 6000, = 50 000,
= 8000
3
.
40
5
343 (339F (E
1.
8, 23, 8
? n ),...,,(
21 n
aaa
A
-
! n- — . K a
i
( ni ,1 ) -
> .
).,...,,(
),,...,,(
21
21
n
n
xxx
aaaA
&
(5.1)
@ A B , # < -
: a
i
= b
i
, ni ,1 .
)> (>) * ' ! -
),
i
>> () -
* ':
iii
bac , ni ,1
@$ D * ! D
A
= (D
a1
, D
a2
, …, D
an
).
:> $!>
),...,,(
),,...,,(
),,...,,(
21
222212
112111
knkkk
n
n
xxx#
xxx#
xxx#
"""""""""
(5.2)
!
kk
#]#]#]^ !
2211
, (5.3)
k
,...,],]]
21
— .
' ! -
).0,...,0,0(0
) (5.2) ! — =>, #
!
,#]#]#]
kk
0
2211
! (5.4)
D
i
>> > ( 0 ! -).