Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
(d
0
T
, σ
T
) NF = (6, 7, 3, 4)
w = 0
x
6
, x
7
w
(d
0
T
, σ
T
) (c
0T
, π
T
)
NF = (6, 7, 3, 4)
1
◦
1
◦
. l = 3, s = 3, c
0
s
= −1/3.
2
◦
. a
0
s
= B
−1
a
s
=
1 −4/3 1/3
0 1 −1/2
0 −1/3 1/3
0
−1
0
=
4/3
−1
1/3
; b
0
=
2
3/2
1
B
−1
a
0
s
π
T
1
◦
min
µ
2
4/3
, ∞,
1
1/3
¶
⇒ k = 1, a
0
ks
= 4/3.
3
◦
.
NB
3
1
2
NF
6
7
5
4
b
+
3/2
3
1/2
z
+
= z − c
0
s
b
+
k
= −11/2 − (−1/3)(3/2) = −5
B
−1
3/4 −1 1/4
3/4 0 −1/4
−1/4 0 1/4
π
T
1/4 0 −3/4
:=
π
T
0 1/3 −5/6
−
β
T
k
3/4 −1 1/4
·
c
0
s
−1/3
= (3, 1/2, 3/2, 0, 0) = , z
min
= 5.
1
◦
.
c
0T
0 0 0 3/4
1 2 3 4
=
π
T
1/4 0 −3/4
5 6 7
G
2 2 0 0
2 3 −1 0
2 6 0 −1
+
c
T
1 4 0 0
NF = (6, 7, 5, 4)
(c
0T
, π
T
) (3/4, 1/4)
c
0T
π
T
(c
0T
, π
T
)
=
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≥ 6;
2x
1
+ 6x
2
≥ 9;
x
1
+ x
2
≤ 4;
2x
1
+ 2x
2
= 7;
x
1
+ 2x
2
= z → min .
≥
−1 ≤
−2 −3 1 0 0 0 −6
−2 −6 0 1 0 0 −9
1 1 0 0 1 0 4
2 2 0 0 0 1 7
1 2 0 0 0 0 0
0 0 0 0 0 1 0
x
6
w
x
6
x
6
w
−2 −3 1 0 0 0 −6
−2 −6 0 1 0 0 −9
1 1 0 0 1 0 4
2 2 0 0 0 1 7
1 2 0 0 0 0 0
−2 −2 0 0 0 0 −7
NB
3
4
5
6
NF
1 1
2 2
= (0, 0, −6, −9, 4, 7) 6= , 0 = z, 7 = w.
b ≥ 0, 6=
w
w
1
◦
. d
0T
= σ
T
G + d
T
; c
0T
= π
T
G + c
T
. σ
T
= 0 π
T
= 0
d
0T
= d
T
, c
0T
= c
T
, d
0T
= (−2, −2), c
0T
= (1, 2).
(d
0T
, σ
T
) = (−2, −2, 0, 0, 0, 0) ⇒ l = 1, s = 1, d
0
s
= −2, c
0
s
= 1.
2
◦
. a
0
s
= B
−1
a
s
= a
s
= (−2, −2, 1, 2)
T
, b
0
= (−6, −9, 4, 7)
T
min(∞, ∞, 4/1, 7/2) = 7/2 ⇒ k = 4, a
0
ks
= 2.
3
◦
.
NB
3
4
5
1
NF
6
2
b
+
1
−2
1/2
7/2
z
+
= z − c
0
s
b
+
k
= −7/2; b
0
:= b
+
w
+
= w − d
0
s
b
+
k
= 0
B
−1
1 0 0 1
0 1 0 1
0 0 1 −1/2
0 0 0 1/2
π
T
0 0 0 −1/2
:=
π
T
0 0 0 0
−
β
T
k
0 0 0 1/2
·
c
0
s
1
σ
T
0 0 0 1
:=
σ
T
0 0 0 0
−
β
T
k
0 0 0 1/2
·
d
0
s
−2
= (7/2, 0, 1, −2, 1/2, 0) 6= , z = 7/2, w = 0.
1
◦
.
d
0
T
0 0
=
σ
T
0 0 0 1
·
G
−2 −3
−2 −6
1 1
2 2
+
d
T
−2 −2
c
0T
0 1
=
π
T
0 0 0 −1/2
·
G
−2 −3
−2 −6
1 1
2 2
+
c
T
1 2
(d
0T
, σ
T
) NF = (6, 2)
w = 0
(c
0T
, π
T
)
x
6
,
l = 2, NF (l) = 2.
1
◦
1
◦
. b
0T
=
1 2 3 4
1 −2 1/2 7/2
⇒ k = 2.
2
◦
.
a
0T
k
0 −4
=
β
T
k
0 1 0 1
·
G
−2 −3
−2 −6
1 1
2 2
; a
0
k
[NF (2)] = −4 < 0
min
j=NF (2)
Ã
(c
0T
, π
T
)
| a
0
kj
|
!
= min
µ
1
| −4 |
¶
=
1
4
⇒ l = 2, s = 2, c
0
s
= 1.
3
◦
. a
0
s
=
1 0 0 1
0 1 0 1
0 0 1 −1/2
0 0 0 1/2
·
−3
−6
1
2
=
−1
−4
0
1
; a
0
ks
= −4.
4
◦
.
NB =
1 2 3 4
, NF =
1 2
.
b
0T
=
1 2 3 4
3/2 1/2 1/2 3
.
z
+
= −7/2 − 1 ∗ 1/2 = −4.
B
−1
=
1 −1/4 0 3/4
0 −1/4 0 −1/4
0 0 1 −1/2
0 1/4 0 3/4
.
π
T
0 1/4 0 −1/4
:=
π
T
0 0 0 −1/2
−
β
T
k
0 −1/4 0 −1/4
·
c
0
s
1
.
c
0T
0 0
1 2
:=
π
T
0 1/4 0 −1/4
3 4 5 (6)
·
G
−2 −3
−2 −6
1 1
2 2
+
c
T
1 2
.
1
◦
. b
0
⇒
z
min
= 4.
x
1
+ x
2
+ x
3
≤ 15.
G
1 2 5
2 3 3
1 1 2
1 2 3
B
−1
1 −1 1
0 1 −2
0 −1 3
b
0
12
6
21
NB
1 4
2 2
3 1
NF
1 6
2 5
3 3
c
0T
0 0 2
1 2 3
π
T
0 1 7
4 5 6
−z
249
A
1 2 5 1 0 0 45
2 3 3 0 1 0 60
1 1 2 0 0 1 27
−9 −10 −15 0 0 0 0
x
1
+x
2
+x
3
≤ 15
G
1 2 5
2 3 3
1 1 2
1 1 1
1 2 3
B
−1
1 −1 1 0
0 1 −2 0
0 −1 3 0
0 0 0 1
b
0
12
6
21
15
NB
1 4
2 2
3 1
4 (7)
NF
1 6
2 5
3 3
c
0T
0 0 2
1 2 3
π
T
0 1 7 0
4 5 6 7
−z
249
A
1 2 5 1 0 0 0 45
2 3 3 0 1 0 0 60
1 1 2 0 0 1 0 27
1 1 1 0 0 0 1 15
−9 −10 −15 0 0 0 0 0
x
7
x
1
+ x
2
+ x
3
+ x
7
= 15, x
7
≥ 0.
x
7
NB =
1 2 3 4
x
2
x
1
B
−1
b
0
x
7
NB
NB G
NB(i)
i = 1, 2, . . . , m
G NB(i) m
m = 3
B
−1
b
0
i = 1 NB(1) = 4 ⇒ 4
G ⇒
i = 2 N B(2) = 4 ⇒ G(m + 1, 2)
⇒ i B
−1
i
b
0
G(m + 1, N B(i)), B
−1
b
0
B
−1
1 −1 1 0
0 1 −2 0
0 −1 3 0
0 −1 2 1
b
0
12
6
21
9
i = 3 NB(3) = 1 ⇒ G(m + 1, 1)
⇒ i B
−1
b
0
G(4, NB(i))
B
−1
b
0
B
−1
1 −1 1 0
0 1 −2 0
0 −1 3 0
0 0 −1 1
b
0
12
6
21
−12
NB
1 4
2 2
3 1
4 7
NB
x
7
= (21, 6, 0, 12, 0, 0, −12) 6= , z = −249.
(c
0T
, π
T
)
b
0
−12
1
◦
. k = 4.
2
◦
.
a
0T
k
0 0 −1
1 2 3
=
β
T
k
0 0 −1 1
4 5 6 7
·
G
1 2 5
2 3 3
1 1 2
1 1 1
.
(c
0T
, π
T
) (a
0T
k
, β
T
k
) NF =
1 2 3
min
µ
7
| −1 |
, ∞,
2
| −1 |
¶
= 2 ⇒ l = 3, s = NF (l) = 3, c
0
s
= 2.
3
◦
.
a
0
s
4
−1
3
−1
=
B
−1
1 −1 1 0
0 1 −2 0
0 −1 3 0
0 0 −1 1
·
a
s
5
3
2
1
, a
0
ks
= −1.
4
◦
. NB =
1 2 3 4
, NF =
1 2 3
.
b
0T
=
1 2 3 4
−36 18 −15 12
.
−z = 225.
= (−15, 18, 12, −36, 0, 0, 0) 6=
B
−1
1 −1 −3 4
0 1 −1 −1
0 −1 0 3
0 0 1 −1
.
π
T
0 1 5 2
:=
π
T
0 1 7 0
−
β
T
k
0 0 1 −1
·
c
0
s
2
.
c
0T
0 0 0
1 2 3
:=
π
T
0 1 5 2
4 5 6 7
·
G
1 2 5
2 3 3
1 1 2
1 1 1
+
c
T
−9 −10 −15
.
1
◦
. k = 1.
2
◦
.
a
0T
k
0 0 0
1 2 3
=
β
T
k
0 −1 −3 4
4 5 6 7
·
G
1 2 5
2 3 3
1 1 2
1 1 1
.
(c
0T
, π
T
) (a
0T
k
, β
T
k
) NF =
1 2 3
min
µ
5
| −3 |
,
1
| −1 |
, ∞
¶
= 1 ⇒ l = 2, s = 5, c
0
s
= 1.
3
◦
.
a
0
s
−1
1
−1
0
=
B
−1
1 −1 −3 4
0 1 −1 −1
0 −1 0 3
0 0 1 −1
·
a
s
0
1
0
0
, a
0
ks
= −1
4
◦
. NB =
1 2 3 4
, NF =
1 2 3
.
b
0T
=
1 2 3 4
36 −18 21 12
.
−z = 189.
= (21, −18, 12, 0, 36, 0, 0) 6=
B
−1
−1 1 3 −4
1 0 −4 3
−1 0 3 −1
0 0 1 −1
.
π
T
1 0 2 6
:=
π
T
0 1 5 2
−
β
T
k
−1 1 3 −4
·
c
0
s
1
.
c
0T
0 0 0
1 2 3
:=
π
T
1 0 2 6
4 5 6 7
·
G
1 2 5
2 3 3
1 1 2
1 1 1
+
c
T
−9 −10 −15
.
1
◦
. k = 2.
2
◦
.
a
0T
k
0 1 0
1 2 3
=
β
T
k
1 0 −4 3
4 5 6 7
·
G
1 2 5
2 3 3
1 1 2
1 1 1
.
(c
0T
, π
T
) (a
0T
k
, β
T
k
) NF =
1 2 3
min
µ
2
| −4 |
, ∞, ∞
¶
=
1
2
⇒ l = 1, s = 6, c
0
s
= 2.
3
◦
.
a
0
s
3
−4
3
1
=
B
−1
−1 1 3 −4
1 0 −4 3
−1 0 3 −1
0 0 1 −1
·
a
s
0
0
1
0
, a
0
ks
= −4
4
◦
. NB =
1 2 3 4
, NF =
1 2 3
.
b
0T
=
1 2 3 4
45/2 9/2 15/2 15/2
.
−z = 180.
= (15/2, 0, 15/2, 0, 45/2, 9/2, 0) =
B
−1
−1/4 1 0 −7/4
−1/4 0 1 −3/4
−1/4 0 0 5/4
−1/4 0 0 −1/4
.
π
T
3/2 0 0 15/2
:=
π
T
1 0 2 6
−
β
T
k
−1/4 0 1 −3/4
·
c
0
s
2
.
c
0T
0 1/2 0
:=
π
T
3/2 0 0 15/2
·
G
1 2 5
2 3 3
1 1 2
1 1 1
+
c
T
−9 −10 −15
.
1
◦
. b
0
⇒
= (15/2, 0, 15/2, 0, 45/2, 9/2, 0) z
min
= −180.