Ларин Р.М., Пяткин А.В., Плясунов А.В. Методы оптимизации примеры и задачи
Подождите немного. Документ загружается.
x
1
− x
2
+ x
3
− x
4
= 1,
x
j
≥ 0, j = 1, 2, 3, 4.
{A
1
, A
2
} m = 2
B =
³
1 1
1 − 1
´
{A
1
, A
3
}
{A
1
, A
4
} {A
2
, A
3
} {A
3
, A
4
} {A
2
, A
4
}
C
2
4
= 6
{A
1
, A
2
} {A
1
, A
4
} {A
2
, A
3
} {A
3
, A
4
}
B
Bx
B
+ Nx
N
= b.
B
−1
x
B
= B
−1
b − B
−1
Nx
N
.
x
N
x
B
=
B
−1
b x
N
= 0
³
x
B
x
N
´
x
N
= 0
x
B
B = (A
1
, A
2
) x
B
=
³
1
0
´
x = (1, 0, 0, 0)
>
x = (1, 0, 0, 0)
>
{A
1
, A
4
}
x = (0, 0, 1, 0)
>
{A
2
, A
3
} {A
3
, A
4
}
x ≥ 0
x
1
+ x
2
+ x
3
+ x
4
= 3,
x
1
− x
2
+ x
3
+ 2x
4
= 1,
x
j
≥ 0 j = 1, 2, 3, 4.
B
1
= (A
1
, A
2
) B
2
= (A
1
, A
4
)
B
3
= (A
2
, A
3
) B
4
= (A
2
, A
4
) B
5
= (A
3
, A
4
) x
1
=
(2, 1, 0, 0)
>
x
2
= (5, 0, 0, −2)
>
x
3
= (0, 1, 2, 0)
>
x
4
= (0, 5/3, 0, 4/3)
>
x
5
= (0, 0, 5, −2)
>
x
1
, x
3
, x
4
x = (a, b, 0)
>
x
1
+ x
2
+ x
3
= a + b,
x
1
− 2x
2
= a − 2b,
x
j
≥ 0, j ∈ J = {1, 2, 3}, (a ≥ 0, b ≥ 0)?
a > 0, b > 0 B =
³
1 1
1 − 2
´
a > 0, b = 0, {A
j
| x
j
> 0} = {A
1
}
x = (a, 0, 0)
>
a > 0 :
B
1
= (A
1
, A
2
) B
2
= (A
1
, A
3
).
A a = 0, b > 0
x = (0, b, 0)
>
b > 0,
B
1
= (A
1
, A
2
) B
2
= (A
2
, A
3
).
a = b = 0, x = (0, 0, 0)
>
B
1
= (A
1
, A
2
), B
2
= (A
1
, A
3
) B
3
= (A
2
, A
3
).
−3x
1
− 2x
2
− x
3
→ min,
x
1
+ x
2
+ x
3
= 1,
x
1
− x
2
+ x
3
= 1,
x
j
≥ 0 (j = 1, 2, 3).
{x | x
1
+ x
2
+ x
3
= 1, x
j
≥ 0, j = 1, 2, 3}
A
B
1
= (A
1
, A
2
) B
2
= (A
2
, A
3
)
x
1
= (1, 0, 0)
>
x
2
= (0, 0, 1)
>
w(x
1
) = −3 w(x
2
) = −1
x
∗
= x
1
x
x
1
+ x
2
+ x
3
= 0, x
1
− x
2
+ x
3
= 0, x
1
≥ 0, x
2
≥ 0, x
3
≥ 0,
x = (0, 0, 0)
>
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 = (1, 0, 0, 0)
>
x
x
1
+ x
2
+ 2x
3
= 3, −2x
1
+ 3x
2
+ x
3
= 4,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0,
x = (1, 2, 0)
>
4x
1
− x
2
+ 2x
3
= 1, 10x
1
+ x
2
− 4x
3
= −3,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0,
x = (0, 1, 1)
>
x
1
− x
2
− 2x
4
= 1, 2x
1
− x
2
+ x
3
− x
4
= 2,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0,
x = (1, 0, 0, 0)
>
x
1
+ x
2
+ x
3
+ 6x
4
= 3, x
2
− x
3
− 2x
4
= 0, x
1
+ 2x
4
= 1,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0,
x = (1, 1, 1, 0)
>
B = (A
σ(1)
, . . . , A
σ(m)
)
x
B
+ B
−1
Nx
N
= B
−1
b.
c c = (c
B
, c
N
) c
B
= (c
σ(1)
, . . . , c
σ(m)
)
c
N
w = c
B
B
−1
b + (c
N
− c
B
B
−1
N)x
N
.
−w +
X
j∈S
0
z
0j
x
j
= z
00
,
x
σ(i)
+
X
j∈S
0
z
ij
x
j
= z
i0
, i = 1, . . . , m,
S
0
= J \ {σ(1), . . . , σ(m)}, z
00
= −c
B
B
−1
b,
(z
10
, . . . , z
m0
)
>
= B
−1
b,
z
0j
= c
j
− c
B
B
−1
A
j
, j = 1, . . . , n,
(z
1j
, . . . , z
mj
)
>
= B
−1
A
j
, j = 1, . . . , n.
z
ij
(i = 0, m, j = 0, n)
x
1
. . . x
j
. . . x
n
−w z
00
z
01
. . . z
0j
. . . z
0n
x
σ(1)
z
10
z
11
. . . z
1j
. . . z
1n
. . . . . . . . . . . . . . . . . .
x
σ(i)
z
i0
z
i1
. . . z
ij
. . . z
in
. . . . . . . . . . . . . . . . . .
x
σ(m)
z
m0
z
m1
. . . z
mj
. . . z
mn
i = 1, . . . , m
σ(i) i
z
0σ(i)
= 0 (i = 1, m)
x
1
. . . x
i
. . . x
m
x
m+1
. . . x
n
−w z
00
. . . . . . z
0m+1
. . . z
0n
x
1
z
10
. . . . . . z
1m+1
. . . z
1n
x
i
z
i0
. . . . . . z
im+1
. . . z
in
x
m
z
m0
. . . . . . z
mm+1
. . . z
mn
σ(i) = i (i = 1, m) B x
B
=
(z
10
, z
20
, . . . , z
m0
)
>
x
N
= 0 w
w(x) = −z
00
z
i0
≥ 0, i =
1, . . . , m, B
z
0j
≥
0, j = 1, . . . , n B
x
A
B = [A
σ(1)
, . . . , A
σ(m)
] A
σ(r)
A
s
, s ∈
J \ {σ (1), . . . , σ(m)} z
rs
0 r ≥ 1
[A
σ(1)
, . . . , A
σ(r−1)
, A
s
, A
σ(r+1)
, . . . , A
σ(m)
]
α
i
= (z
i0
, z
i1
, . . . , z
in
) (i = 0, m)
α
0
i
= (z
0
i0
, z
0
i1
, . . . , z
0
in
) (i = 0, m)
α
0
i
= α
i
−
z
is
z
rs
α
r
, i 6= r,
α
0
r
=
1
z
rs
α
r
.
r s z
rs
z
0
ij
= z
ij
−
z
is
z
rj
z
rs
, i 6= r,
z
0
rj
=
z
rj
z
rs
.
j = s s ∈ J
z
0s
< 0 z
is
≤ 0 i = 1, m w(x)
X
B x
i ∈ I z
i0
= 0
x z
0s
< 0 s ∈ J
r ∈ I z
rs
> 0 x
0
w(x
0
) < w(x)
x = (0, 0, 1, 1)
>
w(x) = x
1
+ x
2
− 2x
3
− 3x
4
→ min,
2x
1
− x
2
+ x
3
= 1,
−x
1
+ 2x
2
+ x
4
= 1,
x
j
≥ 0, j = 1, 2, 3, 4.
{A
j
| x
j
> 0} = {A
3
, A
4
} =
©
³
1
0
´
,
³
0
1
´
ª
A
B
x
3
x
4
w = x
1
+ x
2
− 2(1 − 2x
1
+ x
2
) − 3(1 + x
1
− 2x
2
) = −5 + 2x
1
+ 5x
2
.
−w + 2x
1
+ 5x
2
= 5,
x
3
+ 2x
1
− x
2
= 1,
x
4
− x
1
+ 2x
2
= 1.
x
1
x
2
x
3
x
4
−w 5 2 5 0 0
x
3
1 2 −1 1 0
x
4
1 −1 2 0 1
z
10
= 1, z
20
= 1 z
01
= 2, z
02
= 5, z
03
=
0, z
04
= 0 x
σ(1) = 3 σ(2) = 4
x = (0, 1, 0, 2, 1)
>
w(x) = −x
1
− x
2
→ min,
−x
1
+ x
2
+ x
3
= 1,
x
1
− 2x
2
+ x
4
= 0,
−x
1
+ 2x
2
+ x
5
= 3,
x
j
≥ 0, j = 1, 2, 3, 4, 5.
(A
2
, A
4
, A
5
) = ((1, −2, 2)
>
, (0, 1, 0)
>
, (0, 0, 1)
>
)
x
x
2
= 1, x
4
= 2, x
5
= 1 x
x
1
x
3
x
2
= 1 + x
1
− x
3
.
x
2
−x
1
+ x
3
+ x
2
= 1,
−x
1
+ 2x
3
+ x
4
= 2,
x
1
− 2x
3
+ x
5
= 1.
w(x) = −x
1
− x
2
= −x
1
− (1 + x
1
− x
3
) = −1 − 2x
1
+ x
3
.
−w − 2x
1
+ x
3
= 1.
x
1
x
2
x
3
x
4
x
5
−w 1 −2 0 1 0 0
x
2
1 −1 1 1 0 0
x
4
2 −1 0 2 1 0
x
5
1 1 0 −2 0 1
(z
10
, z
20
, z
30
)
>
= (1, 2, 1)
>
z
01
= −2 < 0 z
31
= 1 > 0
w(x) = −z
00
=
−1 z
31
6= 0
A
5
A
1
(A
1
, A
2
, A
4
)
x
1
x
2
x
3
x
4
x
5
−w 3 0 0 −3 0 2
x
2
2 0 1 −1 0 1
x
4
3 0 0 0 1 1
x
1
1 1 0 −2 0 1
w(x
0
) = −z
0
00
= −3 x
0
= (1, 2, 0, 3, 0)
>
z
0
03
= −3 < 0 j = 3
w(x)
x
x
1
− 2x
2
− 2x
3
−→ min
x
1
− x
2
+ 2x
3
= 0, x
1
+ x
2
+ 5x
3
= 2,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0
x = (1, 1, 0)
>
x
1
− 2x
2
− 4x
3
−→ min
x
1
− x
2
− x
3
= 1, x
1
+ x
2
+ x
3
= 3,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0
x = (2, 1, 0)
>
x
−x
1
− x
2
− 2x
4
−→ min
x
1
+ x
3
+ x
4
= 4, −x
1
− 2x
2
− 3x
3
+ x
4
= 0,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
x = (2, 0, 0, 2)
>
−x
1
+ x
2
− x
3
− 2x
4
−→ min
x
1
+ x
2
+ x
3
+ 2x
4
= 7, x
2
+ x
3
+ x
4
= 5, x
3
− x
4
= 3
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
x = (2, 2, 3, 0)
>
−x
1
− x
2
− x
3
− 5x
4
−→ min
x
1
+ x
2
− x
4
= 3, x
1
− x
2
+ 3x
4
= −1, 2x
1
+ x
2
+ x
3
− x
4
= 5
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
x = (1, 2, 1, 0)
>
x
B B
x
z
i0
≥ 0, i = 1, m
z
0j
≥ 0, j = 1, n
s : z
os
< 0, s ≥ 1
{i | z
is
> 0, i ≥ 1} 6= ∅ r
z
r0
z
rs
= min{
z
i0
z
is
| z
is
> 0, i ≥ 1},
σ(r) := s
x x
|{j | x
j
6= 0}| < m
w(x) = −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
j
≥ 0, j = 1, 2, 3, 4,
x = (0, 1, 1, 0)
>
.
{A
2
, A
3
} =
©
³
−3
−1
´
,
³
−1
1
´
ª
B
0
= (A
2
, A
3
) x
2
x
3
x
1
x
4
x
2
− 1/2x
1
+ 1/2x
4
= 1,
x
3
+ 1/2x
1
+ 1/2x
4
= 1.
w(x) = −x
1
− 2(1/2x
1
− 1/2x
4
+ 1) − 3(−1/2x
1
− 1/2x
4
+ 1) + x
4
= −5 − 1/2x
1
+ 7/2x
4
.
−w − 1/2x
1
+ 7/2x
4
= 5.
x
1
x
2
x
3
x
4
−w 5 −1/2 0 0 7/2
x
2
1 −1/2 1 0 1/2
x
3
1 1/2 0 1 1/2
z
01
= −1/2
(z
10
= 1, z
20
= 1)
(s = 1)
r = 2 z
21
= 1/2 > 0
z
21
B
1
= (A
1
, A
2
)
x
1
x
2
x
3
x
4
−w 6 0 0 1 4
x
2
2 0 1 1 1
x
1
2 1 0 2 1
B
1
x
∗
= (2, 2, 0, 0)
>
w(x
∗
) = −6 x
∗
= (z
20
, z
10
, 0, 0)
>
,
w(x
∗
) = −z
00
w(x) = −x
1
− 2x
2
+ x
3
− x
4
→ min,
x
1
+ x
2
− 2x
3
+ 3x
4
= 1,
2x
1
− x
2
− x
3
+ 3x
4
= 2,
x
j
≥ 0, j = 1, 2, 3, 4,
x = (0, 0, 1, 1)
>
.
A
3
=
³
−2
−1
´
, A
4
=
³
3
3
´
B
0
= (A
3
, A
4
) x
x
3
+ x
1
− 2x
2
= 1,
x
4
+ x
1
− x
2
= 1,
−w − x
1
− x
2
= 0,
x
1
x
2
x
3
x
4
−w 0 −1 −1 0 0
x
3
1 1 −2 1 0
x
4
1 1 −1 0 1
z
01
= −1 < 0
s = 1 r = 1
r = 2
z
10
z
11
=
z
20
z
21
= 1 = min
©
z
i0
z
is
| z
is
> 0
ª
.
r = 1 z
11
= 1 B
0
B
1
= (A
1
, A
4
)
x
1
x
2
x
3
x
4
−w 1 0 −3 1 0
x
1
1 1 −2 1 0
x
4
0 0 1 −1 1
z
22
= 1
B
1
B
2
= (A
1
, A
2
)
x
1
x
2
x
3
x
4
−w 1 0 0 −2 3
x
1
1 1 0 −1 2
x
2
0 0 1 −1 1
x =
(1, 0, 0, 0)
>
. z
02
= 0
z
03
= −2 < 0 z
13
= z
23
= −1 < 0 w(x)
z
02
=
−1 < 0
w(x) = −x
3
+ x
4
− x
5
+ x
6
→ min,
x
1
+ x
3
− 2x
4
− 3x
5
+ 4x
6
= 0,
x
2
+ 4x
3
− 3x
4
− 2x
5
+ x
6
= 0,
x
3
+ x
4
+ x
5
+ x
6
+ x
7
= 1,
x
j
≥ 0, j = 1, 2, . . . , 7.
B
0
=
(A
1
, A
2
, A
7
) x = (0, 0, 0, 0, 0, 0, 1)
>
.
x
1
, x
2
x
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, r = 1 B
1
= (A
2
, A
3
, A
7
)
z
01
= 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 1 0 0 −1 −4 5 0
x
3
0 1 0 1 −2 −3 4 0
x
2
0 −4 1 0 5 10 −15 0
x
7
1 −1 0 0 3 4 −3 1
s = 4, r = 2 B
2
= (A
3
, A
4
, A
7
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 1/5 1/5 0 0 −2 2 0
x
3
0 −3/5 2/5 1 0 1 −2 0
x
4
0 −4/5 1/5 0 1 2 −3 0
x
7
1 7/5 −3/5 0 0 −2 6 1
s = 5, r = 1 B
3
= (A
4
, A
5
, A
7
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
−w 0 −1 1 2 0 0 −2 0
x
5
0 −3/5 2/5 1 0 1 −2 0
x
4
0 2/5 −3/5 −2 1 0 1 0
x
7
1 1/5 1/5 2 0 0 2 1