Семушин И.В. Практикум по методам оптимизации
Подождите немного. Документ загружается.
= (21, 6, 0, 12, 0, 0); z
min
= −249.
·
G I
c
T
O
T
¸
x =
·
b
z
¸
, c ≥ 0.
c ≥ 0 b
>
<
0
b ≥ 0 c
>
<
0
t (t = 1, 2, . . . , N ) b
0
, π
T
, B
−1
, c
0
z. π
T
≥ 0, c
0
≥ 0 b
0
>
<
0
b
0
= b,
π
T
= 0
T
, B
−1
= I, c
0
= c, z = 0.
G
k a
0T
k
= β
T
k
G, β
T
k
k
B
−1
, c
0T
= π
T
G + c
T
,
c
T
; A = [ G | I ]
s a
0
s
= B
−1
a
s
, a
s
s
A.
1
◦
. b
0
,
k
2
◦
. a
0T
k
= β
T
k
G. k (a
0T
k
, β
T
k
)
NF (i), k
a
0
kj
< 0,
l s = NF (l)
min
j
Ã
(c
0T
, π
T
)
j
| a
0
kj
|
!
=
(c
0T
, π
T
)
s
| a
0
ks
|
,
c
0
s
= (c
0T
, π
T
)
s
.
(c
0T
, π
T
)
j
j
(c
0T
, π
T
)
3
◦
. a
0
s
= B
−1
a
s
a
0
ks
.
4
◦
.
NB(k)
←
→
NF (l).
b
+
k
= b
0
k
/a
0
ks
; b
+
i
= b
0
i
− a
0
is
b
+
k
(i 6= k).
z
+
= z − c
0
s
b
+
k
.
z z
+
β
+
kj
= β
kj
/a
0
ks
; β
+
ij
= β
ij
− a
0
is
β
+
kj
(i 6= k).
π
+T
= π
T
− β
T
k
c
0
s
; π := π
+
.
c
0T
= π
T
G + c
T
.
+
b
0
k
:= b
0
k
/a
0
ks
,
−z.
x
1
, x
2
≥ 0
2x
1
+ 3x
2
≥ 6;
2x
1
+ 6x
2
≥ 9;
2x
1
+ 2x
2
≤ 7;
x
1
+ 4x
2
= z → min .
A b
−2 −3 1 0 0 −6
−2 −6 0 1 0 −9
2 2 0 0 1 7
1 4 0 0 0 0
NB
1 3
2 4
3 5
NF
1 1
2 2
= (0, 0, −6, −9, 7) 6= , 0 = z.
1
◦
. b
0T
=
1 2 3
−6 −9 7
⇒ k = 2.
2
◦
.
a
0T
k
−2 −6
1 2
=
β
T
k
0 1 0
3 4 5
·
G
−2 −3
−2 −6
2 2
min
µ
1
| −2 |
,
4
| −6 |
¶
=
1
2
⇒ l = 1, s = 1, c
0
s
= 1.
3
◦
. a
0
s
= B
−1
a
s
= a
s
= (−2, −2, 2)
T
; a
0
ks
= −2.
a
s
B
−1
B
−1
= I.
4
◦
.
NB =
1 2 3
, NF =
1 2
.
b
0T
=
1 2 3
3 9/2 −2
.
−z = −9/2.
B
−1
=
1 −1 0
0 −1/2 0
0 1 1
.
π
T
=
0 1/2 0
=
0 0 0
−
0 −1/2 0
·
1
.
c
0T
0 1
1 2
=
π
T
0 1/2 0
3 4 5
·
G
−2 −3
−2 −6
2 2
+
c
T
1 4
.
1
◦
. b
0
⇒ k = 3.
2
◦
.
a
0T
k
0 −4
1 2
=
β
T
k
0 1 1
3 4 5
·
G
−2 −3
−2 −6
2 2
min
µ
1
| −4 |
¶
=
1
4
⇒ l = 2 , s = 2, c
0
s
= 1.
3
◦
. a
0
s
=
1 −1 0
0 −1/2 0
0 1 1
·
−3
−6
2
=
3
3
−4
; a
0
ks
= −4.
4
◦
.
NB =
1 2 3
, NF =
1 2
.
b
0T
=
1 2 3
3/2 3 1/2
.
−z = −5.
B
−1
=
1 −1/4 3/4
0 1/4 3/4
0 −1/4 −1/4
.
π
T
=
0 3/4 1/4
=
0 1/2 0
−
0 −1/4 −1/4
·
1
.
c
0T
0 0
1 2
=
π
T
0 3/4 1/4
3 4 5
·
G
−2 −3
−2 −6
2 2
+
c
T
1 4
.
1
◦
. b
0
⇒
= (3, 1/2 , 3/2 , 0, 0); z
min
= 5.
4
◦
(c) b
0
,
1
◦
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 .
A b
−2 −3 1 0 0 0 0 −6
−2 −6 0 1 0 0 0 −9
1 1 0 0 1 0 0 4
2 2 0 0 0 1 0 7
−2 −2 0 0 0 0 1 −7
1 2 0 0 0 0 0 0
NB
1 3
2 4
3 5
4 6
5 7
NF
1 1
2 2
= (0, 0, −6, −9, 4, 7, −7) 6= , 0 = z.
1
◦
. b
0T
=
1 2 3 4 5
−6 −9 4 7 −7
⇒ k = 2.
2
◦
.
a
0T
k
−2 −6
1 2
=
β
T
k
0 1 0 0 0
3 4 5 6 7
·
G
−2 −3
−2 −6
1 1
2 2
−2 −2
min
µ
1
| −2 |
,
2
| −6 |
¶
=
1
3
⇒ l = 2, s = 2 c
0
s
= 2.
3
◦
. a
0
s
= B
−1
a
s
= a
s
= (−3, −6, 1, 2, −2)
T
; a
0
ks
= −6
3
◦
4
◦
.
NB =
1 2 3 4 5
, NF =
1 2
.
b
0T
=
1 2 3 4 5
−3/2 3/2 5/2 4 −4
.
−z = −3.
B
−1
=
1 −1/2 0 0 0
0 −1/6 0 0 0
0 1/6 1 0 0
0 1/3 0 1 0
0 −1/3 0 0 1
.
π
T
=
0 1/3 0 0 0
=
0 0 0 0 0
−
0 −1/6 0 0 0
·
2
.
c
0T
1/3 0
1 2
=
π
T
0 1/3 0 0 0
3 4 5 6 7
·
G
−2 −3
−2 −6
1 1
2 2
−2 −2
+
c
T
1 2
.
1
◦
. b
0
⇒ k = 5.
2
◦
.
a
0T
k
−4/3 0
1 2
=
β
T
k
0 −1/3 0 0 1
3 4 5 6 7
·
G
−2 −3
−2 −6
1 1
2 2
−2 −2
min
µ
1/3
| −4/3 |
,
1/3
| −1/3 |
¶
=
1
4
⇒ l = 1, s = 1, c
0
s
= 1/3.
3
◦
. a
0
s
= B
−1
a
s
= (−1, 1/3, 2/3, 4/3, −4/3)
T
; a
0
ks
= −4/3.
4
◦
.
NB =
1 2 3 4 5
, NF =
1 2
.
b
0T
=
1 2 3 4 5
3/2 1/2 1/2 0 3
.
−z = −4.
⇒
= (3, 1/2, 3/2, 0, 1/2, 0, 0); z
min
= 4.
B
−1
B = I.
B
−1
= [ β
ij
]
B(i, j) = A[ i, NB(j) ].
1/4 −1/4 1/4
1/4 3/4 −7/4
−3/4 −1/4 9/4
·
5 2 1
3 3 2
2 1 1
=
1 0 0
0 1 0
0 0 1
,
B,
A
NB =
1 2 3
.
−1
G I
c
T
0
T
= π
T
d
T
0
T
= σ
T
x =
b
z
w
, b ≥ 0.
x = (x
F
, x
B
) = = (0, b)
b ≥ 0 = (0, b) 6=
z c
T
π
T
w d
T
σ
T
w
z
w
(c
T
, π
T
) (d
T
, σ
T
)
(d
T
, σ
T
)
w
(c
T
, π
T
)
z
x
1
, x
2
≥ 0
2x
1
+ 2x
2
≤ 7;
2x
1
+ 3x
2
≥ 6;
2x
1
+ 6x
2
≥ 9;
x
1
+ 4x
2
= z → min .
2 2 0 0 1 0 0 7
2 3 −1 0 0 1 0 6
2 6 0 −1 0 0 1 9
1 4 0 0 0 0 0 0
0 0 0 0 0 1 1 0
.
σ
T
= 0
T
σ
T
σ
T
= ,
w = x
6
+ x
7
σ
T
=
x
6
x
7
w
w
x
6
x
7
1 I
A
1 2 3 4 5 6 7
2 2 0 0 1 0 0 7
2 3 −1 0 0 1 0 6
2 6 0 −1 0 0 1 9
1 4 0 0 0 0 0 0
−4 −9 1 1 0 0 0 −15
NB
5
6
7
NF
1 1
2 2
3 3
4 4
= (0, 0, 0, 0, 7, 6, 9) = , 0 = −z, −15 = −w.
z w
z = 0, w = 15.
(d
T
, σ
T
) (c
T
, π
T
)
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
= , c
0T
=
(d
0T
, σ
T
) = (−4, −9, 1, 1, 0, 0, 0) ⇒ l = 2, s = 2, d
0
s
= −9, c
0
s
= 4.
2
◦
. a
0
s
= B
−1
a
s
= a
s
=
2
3
6
B = I
b
0
=
7
6
9
, min (7/2, 6/3, 9/6) = 9/6 ⇒ k = 3, a
0
ks
= 6.
3
◦
.
NB
5
6
2
NF
1
7
3
4
b
+
4
3/2
3/2
z
+
= z − c
0
s
b
+
k
= 0 − 4 · 3/2 = −6
w
+
= w − d
0
s
b
+
k
= −15 + 9 · 3/2 = −3/2
B
−1
1 0 −1/3
0 1 −1/2
0 0 1/6
π
+T
0 0 −2/3
=
π
T
0 0 0
−
β
T
k
0 0 1/6
·
c
0
s
4
σ
+T
0 0 3/2
=
σ
T
0 0 0
−
β
T
k
0 0 1/6
·
d
0
s
−9
= (0, 3/2, 0, 0, 4, 3/2, 0) = ; z = 6, w = 3/2.
z w z, z
+
, w w
+
,
3
◦
z w
1
◦
.
d
0T
−1 0 1 −1/2
1 2 3 4
=
σ
T
0 0 3/2
5 6 7
G
2 2 0 0
2 3 −1 0
2 6 0 −1
+
d
T
−4 −9 1 1
c
0T
−1/3 0 0 2/3
1 2 3 4
=
π
T
0 0 −2/3
5 6 7
G
2 2 0 0
2 3 −1 0
2 6 0 −1
+
c
T
1 4 0 0
(d
0T
, σ
T
) NF = (1, 7, 3, 4)
l = 1, s = 1, d
0
s
= −1. NF (c
0T
, π
T
) s = 1
c
0
s
= −1/3.
2
◦
. a
0
s
= B
−1
a
s
=
1 0 −1/3
0 1 −1/2
0 0 1/6
2
2
2
=
4/3
1
1/3
; b
0
=
4
3/2
3/2
,
min
µ
4
4/3
,
3/2
1
,
3/2
1/3
¶
⇒ k = 2, a
0
ks
= 1.
3
◦
.
NB
5
1
2
NF
6
7
3
4
b
+
2
3/2
1
z
+
= z − c
0
s
b
+
k
= −11/2
w
+
= w − d
0
s
b
+
k
= 0
w := w
+
= 0
= (3/2, 1, 0, 0, 2, 0, 0) = , z = 11/2.
B
−1
1 −4/3 1/3
0 1 −1/2
0 −1/3 1/3
π
+
T
0 1/3 −5/6
=
π
T
0 0 −2/3
−
β
T
k
0 1 −1/2
·
c
0
s
−1/3
σ
+T
0 1 1
=
σ
T
0 0 3/2
−
β
T
k
0 1 −1/2
·
d
0
s
−1
B
−1
1 −4/3 1/3
0 1 −1/2
0 −1/3 1/3
·
B
1 2 2
0 2 3
0 2 6
=
I
1 0 0
0 1 0
0 0 1
B
NB
NB = (5, 1, 2)
1
◦
.
d
0T
0 0 0 0
1 2 3 4
=
σ
T
0 1 1
5 6 7
G
2 2 0 0
2 3 −1 0
2 6 0 −1
+
d
T
−4 −9 1 1
c
0T
0 0 −1/3 5/6
1 2 3 4
=
π
T
0 1/3 −5/6
5 6 7
G
2 2 0 0
2 3 −1 0
2 6 0 −1
+
c
T
1 4 0 0