Ларин Р.М., Пяткин А.В., Плясунов А.В. Методы оптимизации примеры и задачи
Подождите немного. Документ загружается.
z
15
= 2.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
−ξ −1 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
1 −1 −1 −1 0 0 −1 1 0
x
4
0 2 −3 1 1 0 0 0 1
ξ
∗
= −z
00
= 1 > 0
−x
1
− 4x
2
− x
3
→ min,
x
1
+ x
2
+ x
3
= 2,
−2x
1
+ x
2
− x
3
= −1,
3x
1
+ 2x
3
= 3,
x
j
≥ 0 (j = 1, 2, 3).
−1
x
4
, x
5
x
6
x
4
+
x
5
+
x
6
→
min
,
x
1
+ x
2
+ x
3
+ x
4
= 2,
2x
1
− x
2
+ x
3
+ x
5
= 1,
3x
1
+ 2x
3
+ x
6
= 3,
x
j
≥ 0 (j = 1, 6)
x = (0, 0, 0, 2, 1, 3)
>
x
4
, x
5
x
6
ξ = (2 − x
1
− x
2
− x
3
) + (1 − 2x
1
+ x
2
− x
3
) + (3 − 3x
1
− 2x
3
) = 6 − 6x
1
− 4x
3
.
−ξ −6x
1
− 4x
3
= −6.
x
1
x
2
x
3
x
4
x
5
x
6
−ξ −6 −6 0 −4 0 0 0
x
4
2 1 1 1 1 0 0
x
5
1 2 −1 1 0 1 0
x
6
3 3 0 2 0 0 1
s s = 3
r = 2 z
23
= 1
x
1
x
2
x
3
x
4
x
5
x
6
−ξ −2 2 −4 0 0 4 0
x
4
1 −1 2 0 1 −1 0
x
3
1 2 −1 1 0 1 0
x
6
1 −1 2 0 0 −2 1
z
32
x
1
x
2
x
3
x
4
x
5
x
6
−ξ 0 0 0 0 0 0 2
x
4
0 0 0 0 1 1 −1
x
3
3/2 3/2 0 1 0 0 1/2
x
2
1/2 −1/2 1 0 0 −1 1/2
ξ
∗
= −z
00
= 0
x
1
x
2
x
3
x
4
0 0 0 0
x
3
3/2 3/2 0 1
x
2
1/2 −1/2 1 0
x
4
x
4
x
4
+ x
5
= x
6
w(x)
3/2x
1
+ x
3
= 3/2,
−1/2x
1
+ x
2
= 1/2,
w(x) = −x
1
− 4(1/2 + 1/2x
1
) − (3/2 − 3/2x
1
) = −7/2 − 3/2x
1
.
−w − 3/2x
1
= 7/2
x
1
x
2
x
3
−w 7/2 −3/2 0 0
x
3
3/2 3/2 0 1
x
2
1/2 −1/2 1 0
B =
(A
2
, A
3
) x = (0, 1/2, 3/2)
s = 1, r = 1 z
11
= 3/2
x
1
x
2
x
3
−w 5 0 0 1
x
1
1 1 0 2/3
x
2
1 0 1 1/3
x
∗
= (1, 1, 0), w(x
∗
) = −5
−x
1
+ 4x
2
− 3x
3
− 10x
4
−→ min
x
1
+ x
2
− x
3
+ x
4
= 0, x
1
+ 14x
2
+ 10x
3
− 10x
4
= 11,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
−x
1
+ 5x
2
+ x
3
− x
4
−→ min
x
1
+ 3x
2
+ 3x
3
+ x
4
≤ 3, 2x
1
+ 3x
3
− x
4
≤ 4,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
−x
1
− 10x
2
+ x
3
− 5x
4
−→ min
x
1
+ 2x
2
− x
3
− x
4
= 1, −x
1
+ 2x
2
+ 3x
3
+ x
4
= 2, x
1
+ 5x
2
+ x
3
− x
4
= 5
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
−x
1
− x
2
− x
3
− x
4
−→ min
4x
1
+ 2x
2
+ 5x
3
− x
4
= 5, 5x
1
+ 3x
2
+ 6x
3
− 2x
4
= 5, 3x
1
+ 2x
2
+ 4x
3
− x
4
= 4
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0
−x
1
− x
2
+ x
3
− x
4
+ 2x
5
−→ min
3x
1
+x
2
+x
3
+x
4
−2x
5
= 10, 6x
1
+x
2
+2x
3
+3x
4
−4x
5
= 20, 10x
1
+x
2
+3x
3
+6x
4
−7x
5
= 30
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
−x
1
− 2x
2
− 3x
3
− 4x
4
− 5x
5
−→ min
x
2
+ x
3
− 2x
4
+ 7x
5
= 2, x
1
+ x
3
− 2x
4
− 6x
5
= 2, x
1
+ x
2
− 2x
4
+ 7x
5
= 2
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0
X x
B = (A
1
, . . . , A
m
)
x
B
+ B
−1
Nx
N
= B
−1
b, x
N
= 0, (∗)
B
−1
b ≥ 0 m + (n −m) = n
X x = (B
−1
b, 0)
x
k
= 0 n − m x
x
s
= 0 s ∈ J \ {1, . . . , m} x
s
x
s
≥ 0
s
x
s
z
0s
< 0
x
s
w(x)
r(r ∈ {1, . . . , m})
(∗) x
s
= 0 x
r
= 0
x
s
x
r
x
r
z
r0
= 0 B
x
s
x
r
x
r
= 0 z
r0
/z
rs
x
1
, x
2
x
3
x = (x
1
, x
2
, x
3
)
>
x
4
, x
5
x
6
a
i
x = b
i
(i = 1, m),
x ∈ E
n
. i = 1, 2, 3, m = n = 3
(1, 1, 0)
>
(0, 1/2, 3/2)
>
X
x
n+i
= 0 (1 ≤ i ≤ m) a
i
x = b
i
x
1
= 0, x
2
= 0, x
3
= 0
X
x
4
= 2, x
5
= 1, x
6
= 3
(x
j
≥ 0 (j = 4, 5, 6))
X
x
1
, x
2
x
3
x
1
z
01
= −6 <
0 x
3
z
03
= −4 < 0 x
3
s = 3
r = 1 z
13
(0, 0, 2) x
5
= z
20
= −1
x
4
= 0, x
6
= z
30
= −1
z
i0
/z
is
z
is
> 0
x
σ(i)
= 0
r
z
r0
z
rs
= min
1≤i≤m
n
z
i0
z
is
| z
is
> 0
o
.
s = 3 r = 2
(0, 0, 1)
>
x
4
= 1, x
5
= 0, x
6
= 1 2x
1
− x
2
+ x
3
=
1(x
5
= 0)
x
1
, x
2
x
5
x
1
x
2
= 0, x
5
= 0, x
1
≥ 0
x
0
1
, x
0
2
x
0
5
x
0
2
x
6
= 0 x
4
= 0 z
10
/z
12
= z
30
/z
32
= 1/2
z
32
z
00
= 0 x = (0, 1/2, 3/2)
>
X
Ax = b
X
x
4
= 0 : x
1
+ x
2
+ x
3
= 1
x
2
x
3
x
1
X x
00
1
z
01
= −3/2 < 0
x
00
1
x
3
= 0 z
11
> 0
x = (1, 1, 0)
>
x
1
= (0, 1/2, 3/2)
>
x
2
= (1, 1, 0)
>
w(x) =
n
X
j=1
c
j
x
j
→ min (1)
a
i
x − b
i
≥ 0, i ∈ I
1
; (2)
a
i
x − b
i
= 0, i ∈ I
2
; (3)
x
j
≥ 0, j ∈ J
1
. (4)
I = I
1
∪ I
2
= {1, . . . , m}, I
1
∩ I
2
= ∅, J
1
⊂ J =
{1, . . . , n}, J
2
J \ J
1
x
j
, j ∈ J
2
y
i
(i ∈ I);
y = (y
1
, . . . , y
m
) b = (b
1
, . . . , b
m
)
>
y
i
≥ 0(i ∈ I
1
),
y
i
(i ∈ I
2
)
x
j
(j ∈ J
1
)
m
X
i=1
a
ij
y
i
≤ c
j
(j ∈ J
1
)
y j A
j
A
x
j
(j ∈ J
2
)
m
X
i=1
a
ij
y
i
= c
j
(j ∈ J
2
).
m
X
i=1
b
i
y
i
→ max, (1
0
)
m
X
i=1
a
ij
y
i
≤ c
j
, j ∈ J
1
; (2
0
)
m
X
i=1
a
ij
y
i
= c
j
, j ∈ J
2
; (3
0
)
y
i
≥ 0, i ∈ I
1
. (4
0
)
(1) (4) (1
0
) (4
0
)
w(x) =
n
X
j=1
c
j
x
j
→ min z(y) =
m
X
i=1
b
i
y
i
→ max
a
i
x ≥ b
i
i ∈ I
1
y
i
≥ 0
a
i
x = b
i
i ∈ I
2
y
i
−
x
j
≥ 0 j ∈ J
1
yA
j
≤ c
j
x
j
− j ∈ J
2
yA
j
= c
j
.
(1
0
) (4
0
)
w(x) = x
1
− 10x
2
+ 2x
3
− x
4
+ 7x
5
→ min,
2x
1
− x
2
≤ 1,
x
1
− x
2
+ 2x
3
− x
4
+ x
5
≥ 4,
x
2
+ x
3
− x
4
= 0,
x
1
− x
3
+ 2x
5
≥ 3,
x
1
, x
3
≥ 0.
w(x)
y
1
−2x
1
+ x
2
≥ −1,
y
2
x
1
− x
2
+ 2x
3
− x
4
+ x
5
≥ 4,
y
3
x
1
− x
3
+ 2x
5
≥ 3,
y
4
x
2
+ x
3
− x
4
= 0,
x
1
, x
3
≥ 0.
y
i
(i = 1, 2, 3, 4).
(1
0
) (4
0
)
z(y) = −y
1
+ 4y
2
+ 3y
3
→ max,
−2y
1
+ y
2
+ y
3
≤ 1, x
1
y
1
− y
2
+ y
4
= −10, x
2
2y
2
− y
3
+ y
4
≤ 2, x
3
−y
2
− y
4
= −1, x
4
y
2
+ 2y
3
= 7, x
5
y
1
, y
2
, y
3
≥ 0.
x
1
+ 10x
2
− x
3
→ max,
x
1
+ x
2
+ x
3
≥ 1,
x
1
− x
2
− x
3
≤ 2,
x
2
≤ 0.
−x
1
− 10x
2
+ x
3
→ min,
y
1
x
1
+ x
2
+ x
3
≥ 1,
y
2
−x
1
+ x
2
+ x
3
≥ −2,
y
3
−x
2
≥ 0.
(1
0
) (4
0
)
y
1
− 2y
2
→ max,
y
1
− y
2
= −1,
y
1
+ y
2
− y
3
= −10,
y
1
+ y
2
= 1,
y
1
≥ 0, y
2
≥ 0, y
3
≥ 0.
(1
0
) (4
0
)
x
1
+ 10x
2
− x
3
→ max,
u
1
−x
1
− x
2
− x
3
≤ −1,
u
2
x
1
− x
2
− x
3
≤ 2,
u
3
x
2
≤ 0,
−u
1
+ 2u
2
→ min,
−u
1
+ u
2
= 1,
−u
1
− u
2
+ u
3
= 10,
−u
1
− u
2
= −1,
u
1
≥ 0, u
2
≥ 0, u
3
≥ 0.
(1
0
) (4
0
)
x
0
2
= −x
2
−x
1
+ 10x
0
2
+ x
3
→ min,
y
1
x
1
− x
0
2
+ x
3
≥ 1,
y
2
−x
1
− x
0
2
+ x
3
≥ −2,
x
0
2
≥ 0.
y
1
− 2y
2
→ max,
y
1
− y
2
= −1,
−y
1
− y
2
≤ 10,
y
1
+ y
2
= 1,
y
1
≥ 0, y
2
≥ 0.
x
1
+ 2x
2
+ 3x
3
−→ min
x
1
+ x
2
− 4x
3
≥ 1, x
1
− x
2
= 2,
x
1
≥ 0
2x
1
+ x
2
− x
3
− x
4
−→ min
x
1
+ x
2
− x
3
+ x
4
= 1, x
1
− x
2
+ x
3
− x
4
≥ 2, x
1
− x
3
≤ 3,
x
1
≥ 0, x
2
≤ 0
x
1
+ 2x
2
+ 3x
3
+ 4x
4
+ 5x
5
−→ min
x
1
+ x
3
+ x
4
+ x
5
≥ 0, x
1
+ x
4
+ x
5
≤ 0, x
1
− x
5
= 1
x
1
≥ 0, x
2
≥ 0, x
5
≤ 0
x
1
+ 2x
2
− x
3
+ 4x
4
− x
5
+ 6x
6
−→ min
2x
1
− x
2
+ x
3
≤ 2, x
2
− x
3
− x
4
≤ 3, x
3
+ x
4
− x
5
≥ 4, x
5
+ x
6
= 7
x
1
≥ 0, x
2
≥ 0, x
4
≤ 0, x
5
≤ 0
m
P
i=1
n
P
j=1
c
ij
x
ij
−→ min
n
P
j=1
x
ij
= a
i
, i = 1, m,
m
P
i=1
x
ij
= b
j
, j = 1, n,
x
ij
≥ 0, i = 1, m, j = 1, n;