Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Podsumowanie
Każde bazowe rozwiązanie dopuszczalne jest
punktem wierzchołkowym zbioru X.
Istnieje punkt wierzchołkowy zbioru X w którym
funkcja celu zadania PL przyjmuje maksimum
Każdemu punktowi wierzchołkowemu zbioru X
odpowiada m wektorów liniowo niezależnych z
danego zbioru n wektorów związanych z tym
punktem.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Rozwiązania optymalne
Twierdzenie 6.1
Twierdzenie 6.1
Je
Je
ś
ś
li zadanie programowania liniowego PL posiada rozwi
li zadanie programowania liniowego PL posiada rozwi
ą
ą
zanie optymalne i
zanie optymalne i
wszystkie rozwi
wszystkie rozwi
ą
ą
zania bazowe s
zania bazowe s
ą
ą
niezdegenerowane to za pomoc
niezdegenerowane to za pomoc
ą
ą
algorytmu
algorytmu
simpleks uzyskuje si
simpleks uzyskuje si
ę
ę
rozwi
rozwi
ą
ą
zanie optymalne po co najwy
zanie optymalne po co najwy
ż
ż
ej
ej
m
n
iteracjach.
iteracjach.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Zadanie programowania liniowego - przypadki szczególne
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
2
6
21
x
5
1
-1
0
x
4
1
1
5
x
3
-1
-2
0
x
0
x
2
x
1
Przykład:
Założenia:
algorytm simpleks startuje z bazowego dopuszczalnego rozwiązania oraz w
trakcie jego realizacji nie występuje degeneracja
I. Zadanie programowania liniowego PL posiada jedno rozwiązanie
Rozwiązanie bazowe optymalne:
Wartość optymalna funkcji celu:
4
31
]
4
9
,
4
11
[
0
1
=
=
∧
x
x
T
1/3
1/6
7/2
x
1
4/3
1/6
7/2
x
4
2/3
-1/6
3/2
x
3
-1/3
1/3
7
x
0
x
2
x
5
-1/2
1/4
11/4
x
1
-2
1/2
1/2
x
4
3/2
-1/4
9/4
x
2
1/2
1/4
31/4
x
0
x
3
x
5
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Przypadki szczególne cd.
Twierdzenie 6.2
Jeśli zadanie PL jest nieograniczone, to istnieją rozwiązania
bazowe dopuszczalne
oraz wektor
taki, że:
Wówczas zbiór rozwiązań jest pusty.
B
x
K
y
,
min
2
1
0
x
x
x
−
−
=
0
,
1
2
2
1
2
1
2
1
≥
−
≥
−
≤
−
−
x
x
x
x
x
x
m
i
dla
y
i
y
ik
k
,...,
1
0
0
0
=
≤
<
Przykład:
II. Zadanie programowania liniowego - nieograniczone
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Przypadki szczególne cd.
III. Zadanie programowania liniowego – posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze ograniczonym
Ten przypadek wystąpi wtedy, gdy można znaleźć tablicę simpleksową, której
odpowiada optymalne rozwiązanie bazowe, takie że:
i istnieje para
dla której:
Dla przestrzeni o wymiarze n rozwiązanie optymalne jest kombinacją wypukłą
wierzchołków należących do zbioru optymalnego.
i
x
[ ]
p
i
gdy
x
x
i
p
i
i
p
i
i
i
,...,
1
,
1
,
0
,
1
1
1
=
∈
=
=
∑
∑
=
∧
=
∧
∧
λ
λ
λ
n
j
dla
y
oraz
m
i
dla
y
j
i
,...,
1
0
,...,
1
0
0
0
=
≥
=
≥
(
)
{
}
{
}
n
j
m
i
j
i
,...,
1
,
,...,
1
,
,
0
0
0
0
∈
∈
0
0
,
0
0
0
0
0
0
0
>
>
=
j
i
i
j
y
i
y
y
!!
Dla rozwiązania zdegenerowanego, przypadek ten może zaistnieć również
pod innymi warunkami.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Przypadki szczególne cd.
III. Przykład gdy jest wiele rozwiązań optymalnych na zbiorze ograniczonym
x
1
x
2
x
0
0
-4
-2
x
3
4
-1
1
x
4
6
2
1
x
4
x
2
x
0
12
2
0
x
3
7
0.5
1.5
x
1
3
0.5
0.5
x
4
x
3
x
0
12
2
0
x
2
4.66 0.33 0.66
x
1
0.66 0.33
0.5
•1 rozwiązanie bazowe optymalne:
•2 rozwiązanie bazowe optymalne:
T
T
x
x
]
3
14
,
3
2
[
]
0
,
3
[
2
1
=
=
∧
∧
Zadanie posiada dwa dopuszczalne bazowe rozwiązania optymalne. Odpowiadają one dwóm
wierzchołkom w zbiorze rozwiązań optymalnych.
Zbiór rozwiązań optymalnych
[ ]
{
}
[ ]
.
)
3
14
3
14
(
),
3
7
3
2
(
:
1
,
0
)),
1
(
3
14
0
(
)),
1
(
3
2
3
(
:
1
,
0
,
)
1
(
:
2
1
−
+
=
=
∈
−
+
−
+
=
=
∈
−
+
=
=
∧
λ
λ
λ
λ
λ
λ
λ
λ
λ
x
x
x
x
x
x
x
x
X
2
1
0
2
4
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
=
0
,
6
2
4
:
2
1
2
1
x
x
x
x
x
x
X
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Przypadki szczególne cd.
IV. Zadanie programowania liniowego – posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze nieograniczonym
Ten przypadek wystąpi wtedy, gdy można znaleźć tablicę simpleksową,
której odpowiada optymalne rozwiązanie bazowe, takie że:
dla której, że istnieje j
0
takie, że i dla wszystkich „i” zachodzi
y
i0
=0 (degeneracja) bądź
0
0
0
=
j
y
n
j
dla
y
oraz
m
dlai
y
j
i
,...,
1
0
,...,
1
0
0
0
=
≥
=
≥
0
0
0
≤
j
y
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
Rozwiązanie optymalne zadania PL przyjmuje postać parametryczną:
Dla n=2 równanie parametryczne prostej,
Dla n=3 równanie parametryczne płaszczyzny itd.
T
x
)
3
7
,
3
2
(
1
=
∧
Przykład:
Bazowe rozwiązanie optymalne:
Zbiór rozwiązań optymalnych jest półprostą:
≥
+
=
∈
=
∧
∧
∧
0
,
)
3
1
,
3
2
(
:
1
2
t
t
x
x
R
x
X
T
2
1
0
4
2
max
x
x
X
x
+
−
=
∈
x
≥
≤
+
−
≤
+
−
=
0
,
4
2
1
1
2
:
2
1
2
1
x
x
x
x
x
x
X
x
1
x
2
x
0
0
2
-4
x
3
1
-2
1
x
4
4
-1
2
x
1
x
3
x
0
4
-6
4
x
2
1
-2
1
x
4
2
3
-2
x
4
x
3
x
0
8
2
0
x
2
2.33 0.66 -0,33
x
1
0.66 0.33 -0,66
IV. Zadanie programowania liniowego – posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze nieograniczonym
cd
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wykład 5
Wydział Elektroniki PWr
EiT III r. subkier. EKA
V. Zadanie programowania liniowego – zbiór rozwiązań dopuszczalnych
jest zbiorem pustym - brak rozwiązania
φ
=
X
2
1
0
4
max
x
x
X
x
+
=
∈
x
≥
−
≤
−
≤
+
=
0
,
2
4
:
2
1
2
1
x
x
x
x
x
x
X
W tej wersji metody prymalnej simpleks algorytm nie potrafi stworzyć pierwszego
rozwiązania bazowego dopuszczalnego z powodu wektora b, który posiada składowe
ujemne.
Przykład:
x
1
x
2
x
0
0
-1
-4
x
3
4
1
1
x
4
-2
1
-1
−
+
=
=
2
4
2
1
b
b
b
m
i
dla
y
i
,...,
1
0
0
=
≥
Nie jest spełniony warunek dopuszczalności pierwszej tablicy simpleks
Krok 1.
(start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiązania bazowego
dopuszczalnego. Należy sprawdzić dopuszczalność
rozwiązania:
Wyszukiwarka
Podobne podstrony:
5w to przypadki 2011
5w to przypadki 2011
4w to pl
TO NIE PRZYPADEK
druk dyik, Mimośrodowe rozciąganie lub ściskanie jest to taki przypadek obciążenia przyłożonego do ś
A2 bezokolicznik bez to PL
D1 used to PL
E be going to PL
C would like to PL
spl to pl
C1 have to PL
D2 be used to PL
Cel II To nie przypadek Goldratt EM
to poprawka opr www.przeklej.pl, Polibuda, studia, S12, TO
Poznanie to uzyskiwanie [ www potrzebujegotowki pl ]
więcej podobnych podstron