Zadanie programowania liniowego część I
Wydział Elektroniki
Kier. Automatyka i Robotyka
Studia II st.
dr inż. Ewa Szlachcic
Zakład Sterowania i Optymalizacji
Instytut Informatyki, Automatyki i Robotyki
Politechnika Wrocławska
TEORIA I METODY
OPTYMALIZACJI
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
przy ograniczeniach
:
( )
x
c
x
T
X
x
f
=
∈
max
0
≥
≤
x
b
x
A
dim x=n, dim c=n, dim A =[m x n], dim b
1
=m
1
,
Postać kanoniczna zadania PL
x
c
T
X
x
x =
∈
0
max
{
}
0
,
:
≥
=
=
x
b
Ax
x
X
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Równoważność zadań programowania matematycznego
I Ograniczenie równościowe można
zastąpić dwoma ograniczeniami nierów-
ściowymi
0
)
(
=
±
+ j
n
i
x
x
g
II Ograniczenie nierównościowe można
zastąpić ograniczeniem równościowym ,
wprowadzając zmienną uzupełniającą
III Zmienną wolną można przedstawić
jako różnicę dwóch zmiennych nieujemnych
−
⇒
≥
≤
⇒
=
)
(
0
)
(
0
)
(
0
)
(
x
g
x
g
x
g
x
g
i
i
i
i
0
≥
+ j
n
x
R
x
i
∈
−
+
−
=
i
i
i
x
x
x
gdzie:
0
,
0
≥
≥
−
+
i
i
x
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przykład zadania programowania liniowego
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
Postać kanoniczna zadania PL – wprowadzenie zmiennych uzupełniających dla układu m równań
liniowych.
•Liczba zmiennych n=2,
•Liczba ograniczeń m=3.
=
+
+
+
+
=
+
+
+
+
−
=
+
+
+
+
=
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
Kolumny odpowiadające jednostkowej macierzy bazowej B
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Postać kanoniczna macierzowa zadania PL
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
{
}
0
,
:
≥
=
=
x
b
Ax
x
X
•Liczba zmiennych n=5,
•Liczba ograniczeń m=3.
Kolumny odpowiadające jednostkowej macierzy bazowej B – x
3
, x
4
, x
5
x
c
T
X
x
x =
∈
0
max
]
0
,
0
,
0
,
1
,
2
[
]
,
,
,
,
[
5
4
3
2
1
=
=
T
T
c
c
c
c
c
c
T
T
x
x
x
x
x
x
]
,
,
,
,
[
5
4
3
2
1
=
−
=
1
0
0
2
6
0
1
0
1
1
0
0
1
1
1
A
=
21
0
5
b
0
5
4
3
2
1
≥
=
x
x
x
x
x
x
5
4
3
2
1
x
x
x
x
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Podstawowe definicje
Jeśli dla układu równań liniowych Ax=b spełniony jest warunek rz[A
r
]=rz[A]
to mogą zaistnieć trzy następujące przypadki:
1.
rz[A] = m = n istnieje jedno rozwiązanie układu Ax=b.
2.
rz[A] = n < m istnieje jedno rozwiązanie układu równań, lecz przy tym
(m - n) równań jest zbędnych.
3. rz[A] = m < n istnieje nieskończenie wiele rozwiązań układu Ax=b , jest to
układ nieoznaczony.
Definicja 4.1 macierzy bazowej B
Macierzą bazową B układu równań Ax = b rz[A] = m, n>m nazywamy nieosobliwą
macierz kwadratową o wymiarach (m*m) utworzoną z liniowo-niezależnych kolumn a
j
macierzy A.
Definicja 4.2 rozwiązania bazowego
Rozwiązaniem bazowym układu równań Ax=b rz[A]=m, n>m nazywamy wektor
x
b
=B
-1
b utworzony ze zmiennych odpowiadających kolumnom a
j
macierzy bazowej B.
Składowe wektora bazowego x
b
są to zmienne bazowe.
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Rozwiązania bazowe
]
,
[
N
B
A =
m
B
B
=
≠
dim
,
0
det
]
,
[
N
B
x
x
x =
Definicja 4.3
Rozwiązanie bazowe jest rozwiązaniem bazowym dopuszczalnym zadania programowania
liniowego PL
jeśli wektor x
B
jest nieujemny tzn.
Wówczas rozwiązanie bazowe dopuszczalne posiada nie więcej niż m dodatnich x
i
.
Definicja 4.4
Niezdegenerowanym rozwiązaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe x
i
są większe od zera.
0
≥
B
x
B- macierz bazowa nieosobliwa
N- macierz niebazowa
- wektor zmiennych bazowych odpowiadających kolumnom macierz B
- wektor zmiennych niebazowych odpowiadających kolumnom macierz N
N
B
x
x
0
]
0
,
[
1
=
=
=
−
N
B
B
x
b
B
x
x
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Pierwsze rozwiązanie bazowe
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
Poszukiwanie rozwiązań bazowych
dopuszczalnych
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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ń
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
[
=
N
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 w postaci:
0
=
B
c
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Początkowa tablica simpleksowa
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 początkowe:
Wartość początkowa funkcji celu:
.
0
.
*
2
]
0
,
0
,
21
,
0
,
5
[
]
.
,
,
,
[
]
,
[
0
2
1
0
2
1
5
4
3
=
+
=
=
=
=
∧
∧
x
tzn
x
x
x
x
x
x
x
x
x
x
x
x
T
T
N
B
0
≠
X
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Pierwsza tablica simpleks-I rozwiązanie bazowe dopuszczalne
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
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
−
−
Wyszukiwarka
Podobne podstrony:
Biologia komórki, Laboratoria,' 10 2011 cz1
GN sem1 mgr luty 2011 cz1 id 1 Nieznany
Biologia komórki, Audytoria, 11 2011 cz1
01 2011 cz1 test klucz Adm
2w timo 2011
1w timo 2011
11w timo 2011
7w timo 2011
6w timo 2011
5w timo 2011 cz2
3w timo 2011
9w timo 2011
8w timo 2011
10w timo 2011
AKO 2011 2012 niestacjonarne przyklady cz1
AKO 2011 2012 niestacjonarne przyklady cz1
Cwalina Sopot 2011 12 cz1
więcej podobnych podstron