wyk OLB pr zal

ńł
�ł
1
�ł20x + 10x2 + 6x3 + 3x4 max
�ł
�ł
�ł
�ł
�ł
14x1 + 8x2 + 6x3 + 4x4 d" 20,
�ł
�ł0 d" x1, x2, x3, x4 d" 1,
�ł
�ł
�ł
�ł
ółx , x2, x3, x4 " Z,
1
xj = 1 j-
24 = 16
ńł
n
�ł
�ł
�ł cjxj max
�ł
�ł
�łj=1
�ł
�ł
�ł
�ł
�ł
�ł
n
�ł ajxj d" b,
�ł
�łj=1
�ł
�ł
�ł
�ł
�ł0 d" xj d" 1, j = 1, . . . , n,
�ł
�ł
�ł
ółx " Z, j = 1, . . . , n,
j
aj, cj > 0 j = 1, . . . , n b > 0
n
aj d" b
j=1
cj
n
aj > b.
j=1
x1, x2 . . . , xn
c1 c2 cn
e" e" . . . e" .
a1 a2 an
ńł
n
�ł
�ł
�ł
cjxj max
�ł
�ł
�łj=1
�ł
�ł
�ł
�ł
n
�ł
�ł
�ł
ajxj d" b
�ł
�ł
�łj=1
�ł
�ł
�ł
ół0 d" xj d" 1, j = 1, . . . , n,
zj := ajxj, j = 1, . . . , n
ńł
n
�ł
cj
�ł
�ł
zj max
�ł
�ł
aj
�łj=1
�ł
�ł
�ł
�ł
n
�ł
�ł
�ł
zj d" b
�ł
�ł
�łj=1
�ł
�ł
�ł
ół0 d" zj d" aj, j = 1, . . . , n.
z = (z1, . . . , zn) z1 = min{a1, b}
a1 e" b z1 = b z2 = . . . =
zn = 0 (b, 0, . . . , 0) " Rn
n cj
z f(z) > f(b, 0, . . . , 0) f(z) := zj
j=1
aj
n
cj c1 n c1
f(z) = zj d" zj d" b = f(b, 0, . . . , 0),
aj a1 j=1 a1
j=1
(1, 0, . . . , 0) " Rn
a1 < b z1 = a1 z1 = a1
n - 1 z2 =
min{a2, b - a1}.
j-1
j " {1, . . . , n - 1} aj > b - ak > 0
k=1
j-1 j-1
zj = b - ak zk = 0 k > j b > ak > b > ai
k=1 k=1
i = 1, . . . , j - 1
ńł
�ł
1
�ł20x + 10x2 + 6x3 + 3x4 max
�ł
�ł
�ł
�ł
�ł
14x1 + 8x2 + 6x3 + 4x4 d" 20
�ł
�ł0 d" x1, x2, x3, x4 d" 1
�ł
�ł
�ł
�ł
ółx , x2, x3, x4 " Z
1
4
20 10 6 3
32 = aj > b = 20 > > >
j=1
14 8 6 4
ńł
�ł
�ł20x1 + 10x2 + 6x3 + 3x4 max
�ł
�ł
�ł14x1 + 8x2 + 6x3 + 4x4 d" 20
�ł
�ł
ół
0 d" x1, x2, x3, x4 d" 1
z1 = min{a1, b} = min{14, 20} = 14 x 1 =
z1
= 1
a1
ńł
�ł
�ł20 + 10x2 + 6x3 + 3x4 max
�ł
�ł
�ł8x2 + 6x3 + 4x4 d" 6
�ł
�ł
ół
0 d" x2, x3, x4 d" 1
6 3
z2 = min{a2, b - a1} = min{8, 6} = 6 x 2 = = x 3 = x 4 = 0
8 4
3
[1, , 0, 0]
4
271
2
G
� �(G) = 271
2
G Q
xr = 0 xr = 1
G Q1 = {x " G : x2 = 0} Q2 = {x " G : x2 = 1}
�(Qi) i = 1, 2
ńł
�ł
�ł20x1 + 6x3 + 3x4 max
�ł
�ł
Q1 - lin
�ł14x1 + 6x3 + 4x4 d" 20
�ł
�ł
ół
0 d" x1, x3, x4 d" 1
z1 = min{14, 20} = 14 x 1 = 1 z3 = min{6, 6} = 6 x 3 = 1 x 4 = 0
�(Q1) = f(1, 0, 1, 0) = 26 f(x1, x2, x3, x4) = 20x1 + 10x2 + 6x3 + 3x4
Q2
ńł
�ł
�ł20x1 + 6x3 + 3x4 + 10 max
�ł
�ł
Q2 - lin
�ł14x1 + 6x3 + 4x4 d" 12
�ł
�ł
ół
0 d" x1, x3, x4 d" 1
12
z1 = min{14, 12} = 12 x 1 = z3 = z4 = 0 x 3 = 0 x 4 = 0
14
�(Q2) = f(6, 1, 0, 0) = 271
7 7
Q2 �(Q1) < �(Q2)
G Q1, Q3, Q4
Q2 - lin Q2
Q3 = {x " G : x2 = 1, x1 = 0} Q4 = {x " G : x2 = 1, x1 = 1}
�(Qi) i = 3, 4
ńł
�ł
�ł6x3 + 3x4 + 10 max
�ł
�ł
Q3 - lin
�ł6x3 + 4x4 d" 12
�ł
�ł
ół
0 d" x3, x4 d" 1
z3 = min{6, 12} = 6 x 3 = 1 z4 = min{4, 6} = 4 x 4 = 1
�(Q3) = f(0, 1, 1, 1) = 19 Q4
ńł
�ł
�ł6x3 + 3x4 + 30 max
�ł
�ł
Q4 - lin
�ł6x3 + 4x4 d" -2
�ł
�ł
ół
0 d" x3, x4 d" 1
Q4 - lin �(Q4) = -"
Q �(Q) = maxi"{1,3,4} �(Qi) = �(Q1) = f(1, 0, 1, 0) =
26 �(Q1) = f(1, 0, 1, 0) x = [1, 0, 1, 0]

Wyszukiwarka

Podobne podstrony:
wyk OLB pr kom
wyk OLB pr lok 1
wyk optym A G pr geom
wyk OLB PL zast 2012 13
wyk optym pr geom z ogr
wyk OLB opt wielokr
wyk OLB prog dys 1
RMZ zał 7 (pr szk ORP)
pr inst ue zal 10 dzienne2[1] (2)
wos pr
Wyk ad 02
PR0114 Sonderablauf RoboterauslastungMobilerFräser

więcej podobnych podstron