1
Poszukiwanie rozwiązań bazowych
dopuszczalnych
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Pierwsze rozwiązanie bazowe dopuszczalne
N
B
x
N
B
b
B
x
1
1
−
−
−
=
N
N
B
B
x
c
N
B
c
b
B
c
x
)
(
1
1
0
−
−
=
−
−
N
N
B
B
B
x
N
B
c
N
B
c
b
B
b
B
c
x
x
−
−
=
−
−
−
−
1
1
1
1
0
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Wprowadzone oznaczenia:
≡
≡
−
−
0
10
00
1
1
0
m
B
y
y
y
b
B
b
B
c
y
M
≡
−
≡
−
−
mj
j
j
j
j
j
B
j
y
y
y
a
B
c
a
B
c
y
M
1
0
1
1
N
j
R
j
a
∈
,
oraz
gdzie oznaczają kolumny macierzy N.
∑
∈
−
=
R
j
j
j
x
y
y
x
0
00
0
∑
∈
=
−
=
N
R
j
j
ij
i
Bi
m
i
dla
x
y
y
x
,...,
1
,
0
Funkcja celu x
0
m funkcji ograniczeń
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Postać początkowej tablicy simpleksowej
N
B
b
B
x
c
N
B
c
b
B
c
x
x
B
N
B
B
N
1
1
1
1
0
−
−
−
−
−
−
].
0
,...,
0
[
=
x
N
b
x
c
x
x
B
N
N
−
−
0
0
dla przypadku gdy c
B
=0 tzn. pierwsze rozwiązanie bazowe dopuszczalne odpowiada za
punkt wierzchołkowy x
0
=
B
c
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Postać początkowej tablicy simpleksowej dla omawianego
przykładu
2
6
21
x
5
1
-1
0
x
4
1
1
5
x
3
-1
-2
0
x
0
x
2
x
1
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
5
4
3
2
1
0
0
0
0
1
2
max
x
x
x
x
x
X
x
+
+
+
+
=
∈
x
=
+
+
+
+
=
+
+
+
+
−
=
+
+
+
+
=
21
0
0
2
6
0
0
0
5
0
0
:
5
2
1
4
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
X
0
2
1
5
4
3
≥
=
=
x
x
x
x
x
x
x
x
N
B
=
2
1
x
x
x
N
=
5
4
3
x
x
x
x
B
x
B
x
N
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Polepszanie rozwiązania bazowego dopuszczalnego
∑
∈
=
−
=
N
R
j
j
ij
i
Bi
m
i
dla
x
y
y
x
,...,
1
,
0
∑
∈
−
=
N
R
j
j
j
x
y
y
x
0
00
0
0
,
0
0
0
≤
↑
↑
≥
k
k
j
y
gdy
x
również
to
x
gdy
zatem
x
zawsze
2
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Polepszanie bazowego rozwiązania dopuszczalnego
0
,
0
0
>
∈
=
<
ik
N
j
y
oraz
R
k
k
j
pewnego
dla
y
).
0
,
/
(
min
0
,...,
1
>
=
=
ik
ik
i
m
i
rk
y
y
y
θ
{ }
Br
rk
j
k
R
j
rk
rj
rk
r
k
x
y
x
y
y
y
y
x
N
1
0
−
−
=
∑
−
∈
{ }
Br
rk
ik
j
k
R
j
rk
rj
ik
ij
rk
r
ik
i
B
x
y
y
x
y
y
y
y
y
y
y
y
x
N
i
+
−
−
−
=
∑
−
∈
0
0
Gdy mamy nie-zdegenerowane rozwiązanie bazowe dopuszczalne takie, że
dla przynajmniej jednego i wówczas można z niego otrzymać lepsze bazowe
rozwiązanie dopuszczalne przez wymianę jednej z kolumn macierzy B na kolumnę
macierzy N.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Optymalne rozwiązanie zadania programowania liniowego PL metodą
simpleks
Twierdzenie 4.5
Twierdzenie 4.5
Rozwiązanie bazowe dopuszczalne układu równań Ax=b
jest rozwiązaniem optymalnym zadania PL, jeśli są spełnione dwa warunki:
(i) Warunek prymalnej dopuszczalności:
{
}
m
i
dla
y
io
,...,
1
0
∈
≥
(ii) Warunek optymalności
N
j
R
j
dla
y
∈
∀
≥ 0
0
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Pierwsza tablica simpleks-I rozwiązanie bazowe dopuszczalne
{
}
m
i
dla
y
io
,...,
1
0
∈
≥
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
0
0
0
0
00
0
mk
mj
m
Bm
rk
rj
r
Br
ik
ij
Bi
k
j
k
j
y
y
y
x
y
y
y
x
y
y
y
x
y
y
y
x
x
x
iO
−
−
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
0
0
0
0
00
0
mk
mj
m
Bm
rk
rj
r
Br
ik
ij
Bi
k
j
k
j
y
y
y
x
y
y
y
x
y
y
y
x
y
y
y
x
x
x
iO
−
−
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
0
0
0
0
00
0
mk
mj
m
Bm
rk
rj
r
Br
ik
ij
Bi
k
j
k
j
y
y
y
x
y
y
y
x
y
y
y
x
y
y
y
x
x
x
iO
−
−
N
j
R
j
dla
y
∈
∀
≥0
0
Kryterium
dopuszczalności
Kryterium
optymalności
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Polepszona tablica simpleks odpowiada za następne rozwiązanie bazowe
dopuszczalne o większej wartości funkcji celu.
...
/
1
...
/
...
/
...
...
...
/
)
/
(
...
)
/
(
...
...
...
/
...
)
/
(
...
)
/
(
...
...
...
0
0
0
0
0
0
0
0
00
0
rk
rk
rj
rk
r
k
rk
ik
rk
rj
ik
ij
rk
r
ik
i
Bi
rk
k
rk
rj
k
j
rk
r
k
Br
j
y
y
y
y
y
x
y
y
y
y
y
y
y
y
y
y
x
y
y
y
y
y
y
y
y
y
y
x
x
x
−
−
−
−
−
−
−
−
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Algorytm simpleks dla ograniczeń mniejszościowych
Krok 1
. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiązania
bazowego dopuszczalnego. Należy sprawdzić dopuszczalność
rozwiązania: czy Tak - idź do kroku 2, Nie – STOP.
Krok 2.
(test optymalności). Czy
dla każdego
?
• Tak - to aktualne rozwiązanie jest optymalne.
•
Nie - idź do kroku 3.
Krok 3.
(Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną wchodzącą do
bazy taką zmienną
dla której
Typową regułą jest wybór zmiennej jest reguła dla której:
0
0
≥
j
y
N
R
j ∈
N
k
R
k
x
∈
,
.
0
0
<
k
y
{
}
0
,
0
0
0
min
≤
=
∈
j
j
R
j
k
y
y
y
N
k
x
Idż do kroku 4.
m
i
dla
y
i
,...,
1
0
0
=
≥
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Algorytm simpleks (prymalny) c.d.
Krok 5. (eliminacja Gauss’a). Wyznacz oraz
względem zmiennych
oraz zmiennej
zgodnie z wyprowadzonym wzorem.
Podstaw
aby otrzymać nowe rozwiązanie bazowe dopuszczalne.
Idź do kroku 2.
Krok ten czasami nazywa się wymianą zmiennej bazowej ( piwotyzacją).
k
x
,
,
N
Bi
R
i
x
≠
}
{
,
k
R
j
x
N
j
−
∈
0
i
}
{
,
0
=
−
∈
=
Br
N
j
x
k
R
j
x
Krok 4. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z bazy
taką zmienną
dla której
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.
Idż do kroku 5.
,
Br
x
).
0
,
/
(
min
0
,...,
1
>
=
=
ik
ik
i
m
i
rk
y
y
y
θ
r
B
x
3
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Schemat reguły przeliczenia współczynników w tablicy simpleks
wg metody eliminacji Gauss’a
p - element centralny (główny)
q – dowolny element w wierszu centralnym (głównym)
r – dowolny element w kolumnie centralnej (głównej)
s – dowolny pozostały element
−
−
⇒
p
p
r
p
p
p
rq
s
q
s
r
q
1
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
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:
1. Zbiór X rozwiązań dopuszczalnych
2. 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
]
0
,
4
1
,
0
,
4
9
,
4
11
[
]
.
,
,
,
[
0
5
4
3
2
1
=
=
=
∧
x
x
x
x
x
x
x
T
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
0
≠
X
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Przykład zadania programowania liniowego – metoda prymalna simpleks
- I rozw. bazowe dopuszczalne.
2
6
21
x
5
1
-1
0
x
4
1
1
5
x
3
-1
-2
0
x
0
x
2
x
1
Krok 1
. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiązania bazowego
dopuszczalnego. Należy sprawdzić dopuszczalność rozwiązania.
Tak - idź do kroku 2, Nie – STOP.
Krok 2.
(test optymalności).
Tak - to aktualne rozwiązanie jest optymalne. Nie - idź do Kroku 3.
Krok 3.
(Wybór zmiennej wchodzącej do bazy) - zmienna x
1
.
Krok 4. (wybór zmiennej usuwanej z bazy) -
- zmienna x
5
. Idż do kroku 5.
Rozwiązanie bazowe dopuszczalne:
Wartość optymalna funkcji celu:
0
]
0
,
0
,
21
,
0
,
5
[
]
.
,
,
,
[
0
2
1
5
4
3
=
=
=
∧
x
x
x
x
x
x
x
T
T
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Przykład zadania programowania liniowego – metoda prymalna simpleks cd.
- II rozw. bazowe dopuszczalne.
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
Krok 5. (eliminacja Gauss’a). Wyznacz nowa tablicę simpleksów. Idź do kroku 2.
Rozwiązanie bazowe dopuszczalne:
Wartość optymalna funkcji celu:
7
]
0
,
0
,
2
7
,
2
7
,
2
3
[
]
.
,
,
,
[
0
2
5
1
4
3
=
=
=
∧
x
x
x
x
x
x
x
T
T
Krok 2.
(test optymalności). Tak - to aktualne rozwiązanie jest optymalne.
Nie - idź do Kroku 3.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
-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
Rozwiązanie bazowe optymalne:
Wartość optymalna funkcji celu:
4
31
]
0
,
0
,
4
11
,
2
1
,
4
9
[
]
.
,
,
,
[
0
3
5
1
4
2
=
=
=
∧
∧
x
x
x
x
x
x
x
T
T
Przykład zadania programowania liniowego – metoda prymalna simpleks cd.
- III rozw. bazowe dopuszczalne = rozwiązanie optymalne.
Krok 2.
(test optymalności).
Tak - to aktualne rozwiązanie jest optymalne.
Wyszukiwarka
Podobne podstrony:
5w to przypadki 2011
1w to wprowadzenie 2011
6w to dpl 2011
6 sposobów na to, PITY 2011, Informacje o podatkach, dokumenty
4w to pl
7w to wlasnosci 2011
3w to proglin 2011
2w to przyklady 2011
CreateSpace SEO Made Simple 2011
David Damron Minimalism 7 Steps to a Simpler Life
więcej podobnych podstron