Ларин Р.М., Пяткин А.В., Плясунов А.В. Методы оптимизации примеры и задачи
Подождите немного. Документ загружается.
s = 6, r = 2 B
4
= (A
5
, A
6
, A
7
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 −1/5 −1/5 −2 2 0 0 0
x
5
0 1/5 −4/5 −3 2 1 0 0
x
6
0 2/5 −3/5 −2 1 0 1 0
x
7
1 −3/5 7/5 6 −2 0 0 1
s = 1, r = 1 B
5
= (A
1
, A
6
, A
7
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 0 −1 −5 4 1 0 0
x
1
0 1 −4 −15 10 5 0 0
x
6
0 0 1 4 −3 −2 1 0
x
7
1 0 −1 −3 4 3 0 1
s = 2, r = 2 B
6
= (A
1
, A
2
, A
7
) = B
0
w(x) = −7x
1
− x
3
+ x
4
− x
5
→ min,
x
1
− x
2
+ x
3
= 1,
2x
1
+ 2x
2
+ x
3
+ x
4
+ 2x
5
= 12,
2x
1
+ x
2
+ x
5
= 4,
x
j
≥ 0, j = 1, 2, . . . , 5,
B
0
= (A
3
, A
4
, A
5
).
x
3
x
5
−3x
1
+ x
2
+ x
4
= 3.
x
3
, x
4
x
5
w(x) = −7x
1
− (1 − x
1
+ x
2
) + (3 + 3x
1
− x
2
) − (4 − 2x
1
− x
2
) = −2 − x
1
− x
2
.
x
3
+ x
1
− x
2
= 1,
x
4
− 3x
1
+ x
2
= 3,
x
5
+ 2x
1
+ x
2
= 4,
−w − x
1
− x
2
= 2.
B
0
x = (0, 0, 1, 3, 4)
>
,
x
1
x
2
x
3
x
4
x
5
−w 2 −1 −1 0 0 0
x
3
1 1 −1 1 0 0
x
4
3 −3 1 0 1 0
x
5
4 2 1 0 0 1
z
01
= z
02
= −1
s s = 1
{i | z
i1
> 0}
z
10
z
11
= 1 = min
n
z
i0
z
i1
| z
i1
> 0
o
= min
n
1
1
,
4
2
o
.
r = 1 z
11
B
1
= (A
1
, A
4
, A
5
).
x
1
x
2
x
3
x
4
x
5
−w 3 0 −2 1 0 0
x
1
1 1 −1 1 0 0
x
4
6 0 −2 3 1 0
x
5
2 0 3 −2 0 1
s = 2 r = 3
B
2
= (A
1
, A
2
, A
4
)
x
1
x
2
x
3
x
4
x
5
−w 13/3 0 0 −1/3 0 2/3
x
1
5/3 1 0 1/3 0 1/3
x
4
22/3 0 0 5/3 1 2/3
x
2
2/3 0 1 −2/3 0 1/3
z
23
= 5/3 z
03
= −1/3 < 0
z
20
z
23
=
22
5
<
z
10
z
13
= 5.
B
3
= (A
1
, A
2
, A
3
)
x
1
x
2
x
3
x
4
x
5
−w 29/5 0 0 0 1/5 4/5
x
1
1/5 1 0 0
x
3
22/5 0 0 1
x
2
18/5 0 1 0
z
0j
, j = 1, n
z
i0
(i = 0, m)
x
σ(i)
= z
i0
, i = 1, m w(x) = −z
00
,
x = (1/5, 18/5, 22/5, 0, 0) w(x) = −29/5.
−x
1
− x
2
−→ min
x
1
− x
2
≤ 1, 5x
1
+ x
2
≤ 1,
x
1
≥ 0, x
2
≥ 0
−x
1
+ 2x
2
−→ min
x
1
+ x
2
≤ 12, x
1
− x
2
≤ 8,
x
1
≥ 0, x
2
≥ 0
x
−6x
1
− x
2
− 4x
3
+ 5x
4
−→ min
3x
1
+ x
2
− x
3
+ x
4
= 4, 5x
1
+ x
2
+ x
3
− x
4
= 4,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
x = (1, 0, 0, 1)
>
−x
1
− 2x
2
− 3x
3
+ x
4
−→ min
x
1
− 3x
2
− x
3
− 2x
4
= −4, x
1
− x
2
+ x
3
= 0,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
x = (0, 1, 1, 0)
>
−x
1
− x
2
− x
3
− x
4
−→ min
x
1
+ x
2
+ x
3
+ 3x
4
= 3, x
1
+ x
2
− x
3
+ x
4
= 1, x
1
− x
2
+ x
3
+ x
4
= 1
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
x = (0, 0, 0, 1)
>
−x
1
− 2x
2
− x
3
− 3x
4
− x
5
−→ min
x
1
+ x
2
+ 2x
4
+ x
5
= 5, x
1
+ x
2
+ x
3
+ 3x
4
+ 2x
5
= 9, x
2
+ x
3
+ 2x
4
+ x
5
= 6
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
x = (0, 0, 1, 2, 1)
>
−x
1
+ x
2
− 2x
3
+ x
4
− x
5
−→ min
x
1
+ x
2
+ 2x
3
+ 3x
4
− 2x
5
= 3, x
2
− x
3
− x
4
− x
5
= 0, x
1
+ x
4
− x
5
= 0
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
x = (0, 2, 0, 1, 1)
>
−x
1
− 2x
2
− 2x
3
− x
4
− 6x
5
−→ min
x
1
+ 3x
2
+ 3x
3
+ x
4
+ 9x
5
= 18, x
1
+ 5x
2
+ 2x
4
+ 8x
5
= 13, x
3
+ x
5
= 3
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
x = (0, 1, 2, 0, 1)
>
−x
1
− x
2
− x
3
− x
4
− x
5
−→ min
x
1
+ x
2
+ 2x
3
= 4, −2x
2
− 2x
3
+ x
4
− x
5
= −6, x
1
− x
2
+ 6x
3
+ x
4
+ x
5
= 12
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
x = (1, 1, 2, 0, 0)
>
α = (z
0
, z
1
, . . . , z
n
)
α Â 0 z
p
> 0 p = min{i |
z
i
6= 0}
α
0
, α
00
∈ E
n+1
α
0
α
00
α
0
 α
00
α
0
− α
00
 0
E
n+1
{α
i
}
{α
i
}
α
i
= (z
i0
,
z
i1
, . . . , z
in
), i = 1, m
0
0
)
3
0
) {i | z
is
> 0, i ≥ 1} 6= ∅ r
1
z
rs
α
r
= min
n
1
z
is
α
i
| z
is
> 0, i ≥ 1
o
,
α
0
= (z
00
, z
01
, . . . , z
0n
)
B
0
= (A
1
, A
2
, A
7
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 0 0 −1 1 −1 1 0
x
1
0 1 0 1 −2 −3 4 0
x
2
0 0 1 4 −3 −2 1 0
x
7
1 0 0 1 1 1 1 1
s = 3 α
1
= (0, 1, 0, 1, −2, −3, 4, 0) α
2
= (0, 0, 1, 4, −3, −2, 1, 0)
α
3
= (1, 0, 0, 1, 1, 1, 1, 1)
α
3
−α
1
= (1, −1, ...) Â 0 α
3
−α
2
/z
23
= (1, 0, ...) Â 0 α
3
 α
1
α
3
 1/z
23
α
2
α
1
(1/z
23
)α
2
α
1
−
1
4
α
2
= (0, 1, . . . ) Â 0.
min{α
i
/z
i3
| z
i3
> 0} = (1/z
23
)α
2
r = 2
B
1
= (A
1
, A
3
, A
7
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 0 1/4 0 1/4 −6/4 5/4 0
x
1
0 1 −1/4 0 −5/4 −10/4 15/4 0
x
3
0 0 1/4 1 −3/4 −2/4 1/4 0
x
7
1 0 −1/4 0 7/4 6/4 3/4 1
s = 5, r = 3 B
2
=
(A
1
, A
3
, A
5
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 1 0 0 0 2 0 2 1
x
1
5/3 1 0 0
x
3
1/3 0 1 0
x
5
2/3 0 0 1
x
∗
= (5/3, 0, 1/3, 0, 2/3, 0, 0)
>
, w(x
∗
) = −1
B
0
−x
1
− 2x
2
− x
3
− 2x
4
− 3x
5
−→ min
x
1
− x
2
− 2x
5
= 0, x
2
+ x
4
+ 4x
5
= 0, x
2
+ x
3
+ x
5
= 1
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
B
0
= (A
1
, A
2
, A
3
)
−4x
1
− x
2
− x
3
+ x
4
− x
5
− 2x
6
−→ min
3x
1
+ 2x
2
+ x
3
+ x
4
+ x
5
+ x
6
= 1, 2x
1
+ 2x
2
+ x
4
+ x
5
= 0, x
1
+ x
2
+ x
4
= 1
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0, x
6
≥ 0
B
0
= (A
4
, A
5
, A
6
)
−x
1
− 4x
2
− x
3
− x
4
+ 2x
5
− x
6
−→ min
x
1
+ x
2
+ x
4
= 0, x
1
+ x
2
+ x
3
+ x
5
= 1, x
2
+ x
3
+ x
6
= 1
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0, x
6
≥ 0
B
0
= (A
4
, A
5
, A
6
)
X = ∅
A m
Ax = b
b ≥ 0 −1
ξ =
m
X
i=1
x
n+i
→ min,
a
i
x + x
n+i
= b
i
, i = 1, m;
x
j
≥ 0, j = 1, n + m,
B = (A
n+i
, . . . , A
n+m
) a
i
i A
i = 1, m B
ξ x
n+i
(i = 1, m)
x
j
(j = 1, n),
ξ =
m
X
i=1
(b
i
− a
i
x).
z
00
= −
m
X
i=1
b
i
z
0j
=
m
X
i=1
a
ij
, j = 1, n.
x
j
= 0 (j = 1, n), x
n+i
= b
i
(i = 1, m)
ξ
∗
> 0
X = ∅
x
j
(j = n + 1, n + m)
x
j
(j ≤
n)
x
r
(r > n)
z
rs
6= 0 (1 ≤ s ≤ n)
z
rs
z
rj
= 0 j = 1, n r
w(x)
Ax = b
A
m
0
w(x)
x
1
− x
2
+ x
3
− x
4
+ 3x
5
→ min,
x
1
+ x
4
+ 2x
5
= 1,
−x
2
− x
3
+ x
4
+ 2x
5
= 1,
2x
1
− 3x
2
+ x
3
+ x
4
= 0,
x
j
≥ 0 (j = 1, . . . , 5).
x
6
, x
7
, x
8
x
6
+ x
7
+ x
8
→ min,
x
1
+ x
4
+ 2x
5
+ x
6
= 1,
−x
2
− x
3
+ x
4
+ 2x
5
+ x
7
= 1,
2x
1
− 3x
2
+ x
3
+ x
4
+ x
8
= 0,
x
j
≥ 0 (j = 1, . . . , 8),
x = (0, 0, 0, 0, 0, 1, 1, 0)
>
.
x
6
, x
7
x
8
ξ = (1−x
1
−x
4
−2x
5
)+(1+x
2
+x
3
−x
4
−2x
5
)+(−2x
1
+3x
2
−x
3
−x
4
) = 2−3x
1
+4x
2
−3x
4
−4x
5
.
−ξ −3x
1
+ 4x
2
− 3x
4
− 4x
5
= −2.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
−ξ −2 −3 4 0 −3 −4 0 0 0
x
6
1 1 0 0 1 2 1 0 0
x
7
1 0 −1 −1 1 2 0 1 0
x
8
0 2 −3 1 1 0 0 0 1
s
s = 4 r = 3
z
34
= 1
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
−ξ −2 3 −5 3 0 −4 0 0 3
x
6
1 −1 3 −1 0 2 1 0 −1
x
7
1 −2 2 −2 0 2 0 1 −1
x
4
0 2 −3 1 1 0 0 0 1
z
15
.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
−ξ 0 1 1 1 0 0 2 0 1
x
5
1/2 −1/2 3/2 −1/2 0 1 1/2 0 −1/2
x
7
0 −1 −1 −1 0 0 −1 1 0
x
4
0 2 −3 1 1 0 0 0 1
ξ
∗
= 0.
x
7
z
21
=
−1 6= 0,
z
21
x
1
x
2
x
3
x
4
x
5
x
5
1/2 0 2 0 0 1
x
1
0 1 1 1 0 0
x
4
0 0 −5 −1 1 0
x
2
x
3
2x
2
+ x
5
= 1/2,
x
1
+ x
2
+ x
3
= 0,
−5x
2
− x
3
+ x
4
= 0.
w(x) = (−x
2
− x
3
) − x
2
+ x
3
− (5x
2
+ x
3
) + 3(1/2 − 2x
2
) = 3/2 − 13x
2
− x
3
.
B = (A
1
, A
4
, A
5
)
x = (0, 0, 0, 0, 1/2) :
x
1
x
2
x
3
x
4
x
5
−w −3/2 0 −13 −1 0 0
x
5
1/2 0 2 0 0 1
x
1
0 1 1 1 0 0
x
4
0 0 −5 −1 1 0
s = 2, r = 2.
z
22
= 1
x
1
x
2
x
3
x
4
x
5
−w −3/2 13 0 12 0 0
x
5
1/2 −2 0 −2 0 1
x
2
0 1 1 1 0 0
x
4
0 5 0 4 1 0
x
∗
= (0, 0, 0, 0, 1/2), w(x
∗
) = 3/2.
−2x
1
− 7x
2
+ x
3
+ 4x
4
→ min,
x
1
+ x
2
− x
4
= 1,
2x
1
+ x
2
+ x
3
− 2x
4
= 3,
x
j
≥ 0 (j = 1, . . . , 4).
x
5
, x
6
x
5
+ x
6
→ min,
x
1
+ x
2
− x
4
+ x
5
= 1,
2x
1
+ x
2
+ x
3
− 2x
4
+ x
6
= 3,
x
j
≥ 0 (j = 1, . . . , 6)
x = (0, 0, 0, 0, 1, 3)
>
x
5
, x
6
x
1
x
2
x
3
x
4
x
5
x
6
−ξ −4 −3 −2 −1 3 0 0
x
5
1 1 1 0 −1 1 0
x
6
3 2 1 1 −2 0 1
z
11
.
x
1
x
2
x
3
x
4
x
5
x
6
−ξ −1 0 1 −1 0 3 0
x
1
1 1 1 0 −1 1 0
x
6
1 0 −1 1 0 −2 1
z
32
.
x
1
x
2
x
3
x
4
x
5
x
6
−ξ 0 0 0 0 0 1 1
x
1
1 1 1 0 −1 1 0
x
3
1 0 −1 1 0 −2 1
ξ
∗
= −z
00
= 0
w(x)
x
1
+ x
2
− x
4
= 1,
−x
2
+ x
3
= 1,
w(x) = −2(1 − x
2
+ x
4
) − 7x
2
+ (1 + x
2
) + 4x
4
= −1 − 4x
1
+ 2x
4
.
B = (A
1
, A
3
)
x = (1, 0, 1, 0)
x
1
x
2
x
3
x
4
−w −1 0 −4 0 2
x
1
1 1 1 0 −1
x
3
1 0 −1 1 0
s = 2, r = 1 z
12
= 1
x
1
x
2
x
3
x
4
−w 3 4 0 0 −2
x
2
1 1 1 0 −1
x
3
2 1 0 1 −1
x
1
− x
2
+ x
3
− x
4
+ 3x
5
→ min,
x
1
+ x
4
+ 2x
5
= 1,
−x
2
− x
3
+ x
4
+ 2x
5
= 2,
2x
1
− 3x
2
+ x
3
+ x
4
= 0,
x
j
≥ 0 (j = 1, . . . , 5).
x
6
, x
7
, x
8
x
6
+ x
7
+ x
8
→ min,
x
1
+ x
4
+ 2x
5
+ x
6
= 1,
−x
2
− x
3
+ x
4
+ 2x
5
+ x
7
= 2,
2x
1
− 3x
2
+ x
3
+ x
4
+ x
8
= 0,
x
j
≥ 0 (j = 1, . . . , 8),
x = (0, 0, 0, 0, 0, 1, 2, 0)
>
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
−ξ −3 −3 4 0 −3 −4 0 0 0
x
6
1 1 0 0 1 2 1 0 0
x
7
2 0 −1 −1 1 2 0 1 0
x
8
0 2 −3 1 1 0 0 0 1
z
34
=
1.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
−ξ −3 3 −5 3 0 −4 0 0 3
x
6
1 −1 3 −1 0 2 1 0 −1
x
7
2 −2 2 −2 0 2 0 1 −1
x
4
0 2 −3 1 1 0 0 0 1