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
−
−