1
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Metody optymalizacji
dr inż. Anna Barcz
Zakład Metod Matematycznych
kontakt: pokój 28
abarcz@wi.ps.pl
1
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Metody optymalizacji
dr inż. Anna Barcz
Zakład Metod Matematycznych
kontakt: pokój 28
abarcz@wi.ps.pl
2
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Niech dany będzie układ m liniowo niezależnych równań z n niewiadomymi
x
1
,x
2
,...,x
n
, który będziemy nazywali układem ograniczeń zadania
programowania liniowego
Programowanie liniowe
{
a
11
x
1
a
12
x
2
a
1n
x
n
=b
1
a
21
x
1
a
22
x
2
a
2n
x
n
=b
2
a
m1
x
1
a
m2
x
2
a
mn
x
n
=b
m
gdzie, nie zmniejszając ogólności, można założyć, że b
i
≥
0.
Należy znaleźć nieujemne wartości zmiennych x
j
≥
0, (j=1,...,n), które
minimalizują (maksymalizują) funkcję celu
Z
=c
1
x
1
c
2
x
2
c
n
x
n
3
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Każdy zbiór zmiennych x
j
(j=1,...,n) spełniający układ równań będziemy
nazywali rozwiązaniem.
Jednak na x
j
nałożono dodatkowy warunek x
j
≥
0 (j=1,...,n).
Rozwiązania, które spełniają ten warunek będziemy nazywali
rozwiązaniami dopuszczalnymi.
Sens zadania programowania liniowego polega na tym, aby ze zbioru
rozwiązań dopuszczalnych wybrać to, które minimalizuje (maksymalizuje)
funkcję celu.
Programowanie liniowe
4
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Bazą nazywamy dowolny zbiór m zmiennych takich, że wyznacznik
składający się ze współczynników przy tych zmiennych jest różny od zera.
m zmiennych x
1
, x
2
, ..., x
m
nazywa się zmiennymi bazowymi.
pozostałe (n-m) zmiennych x
m+1
,x
m+2
,...,x
n
nazywa się zmiennymi
niebazowymi.
dla układu równań można zadać kilka różnych baz o różnych zmiennych
bazowych.
rozwiązanie bazowe nazywa się dopuszczalnym rozwiązaniem
bazowym, jeżeli wartości należących do niego zmiennych bazowych są
nieujemne.
Programowanie liniowe
5
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – ekstremum funkcji liniowej przy liniowych
ograniczeniach
Opracowanie modelu programowania liniowego:
●
określenie zmiennych zadania,
●
określenie ograniczeń w postaci liniowych równań lub nierówności,
●
wyznaczenie linowej funkcji celu podlegającej minimalizacji lub
maksymalizacji
Programowanie liniowe
Metody:
metoda graficzna,
metoda algebraiczna,
metoda simpleks.
6
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Metoda simpleks – iteracyjna procedura rozwiązywania zadania
programowania liniowego, zapisanego w postaci znormalizowanej.
Algorytm metody simpleks:
Wybór początkowego dopuszczalnego rozwiązania bazowego.
Przejście od początkowego rozwiązania do innego dopuszczalnego
rozwiązania bazowego o lepszej wartości funkcji celu.
Kontynuacja
poszukiwań
kolejnych
dopuszczalnych
rozwiązań
bazowych, polepszających wartości funkcji celu. Sąsiednie dopuszczalne
rozwiązanie bazowe różni się od poprzedniego tylko o jedną zmienną
bazową.
Jeśli nie ma możliwości polepszenia uzyskanego dopuszczalnego
rozwiązania bazowego, to można wywnioskować, że jest ono optymalne.
Programowanie liniowe – metoda simpleks
7
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – przykład
Zadanie: Pewien zakład produkuje dwa typy płytek chodnikowych.
Oba typy wymagają zużycia jednakowej ilości surowców (piasek,
woda, żwir, cement). Jeden typ jest barwny i do jego produkcji
potrzebna jest farba. Wyprodukowanie 1 tony płytek barwnych
wymaga 2h pracy maszyn, 3h pracy ludzkiej i 2l barwnika. Produkcja
tony płyt bezbarwnych wymaga 1h pracy maszyn, 3h pracy ludzkiej.
Zysk: płyty barwne 300 zł/t, płyty bezbarwne 200 zł/t. Dysponujemy
10h pracy urządzeń, 24h pracy ludzkiej i 8l barwnika. Ile
wyprodukować płyt (jakich) aby osiągnąć maksymalny zysk.
8
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – przykład
Oznaczenia:
x
1
= płyty barwne ,
x
2
= płyty bezbarwne.
Funkcja celu:
Z
=300 x
1
200 x
2
max
Ograniczenia:
{
2 x
1
x
2
10
3 x
1
3 x
2
24
2 x
1
8
x
i
0 i=12
9
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
- zmienne dopełniające
Programowanie liniowe – metoda simpleks
Funkcja celu:
Z
=300 x
1
200 x
2
max
Ograniczenia:
{
2 x
1
x
2
10
3 x
1
3 x
2
24
2 x
1
8
Postać kanoniczna – zamieniamy nierówności na równości:
{
2 x
1
x
2
x
3
=10
3 x
1
3 x
2
x
4
=24
2 x
1
x
5
=8
x
i
0 i=15
Z
=300 x
1
200 x
2
0 x
3
0 x
4
0 x
5
Przekształcamy ograniczenia, tak aby wszystkie wyrazy wolne były
nieujemne i zapisujemy postać znormalizowaną (kanoniczną).
Uwzględniamy zmienne dopełniające w funkcji celu:
10
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Postać kanoniczna:
{
2 x
1
x
2
x
3
=10
3 x
1
3 x
2
x
4
=24
2 x
1
x
5
=8
x
i
0 i=15
Z
=300 x
1
200 x
2
0 x
3
0 x
4
0 x
5
Funkcja celu:
Ograniczenia:
{
2 x
1
1 x
2
1 x
3
0 x
4
0 x
5
=10
3 x
1
3 x
2
0 x
3
1 x
4
0 x
5
=24
2 x
1
0 x
2
0 x
3
0 x
4
1 x
5
=8
Ograniczenia w postaci macierzowej:
2 1 1 0 0
3 3 0 1 0
2 0 0 0 1
A
⋅
x
1
x
2
x
3
x
4
x
5
X
=
10
24
8
b
A
⋅X =b
11
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
a
1
a
2
a
3
a
4
a
5
2 1 1 0 0
3 3 0 1 0
2 0 0 0 1
A
⋅
x
1
x
2
x
3
x
4
x
5
X
=
10
24
8
b
Programowanie liniowe – metoda simpleks
Ograniczenia w postaci macierzowej:
Z
=300 x
1
200 x
2
0 x
3
0 x
4
0 x
5
Funkcja celu:
Wektory bazowe
c
b
0
0
0
a
3
a
4
a
5
wiersz wskaźnikowy
c
j
b
10
24
8
300
a
1
2
3
2
200
a
2
1
3
0
0
a
3
1
0
0
0
a
4
0
1
0
0
a
5
0
0
1
Pierwsza tablica simpleksów
12
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
-200
F
j
−c
j
=c
b
T
⋅a
j
−c
j
-300
0
0
0
2
0
F
0
=c
b
T
⋅b
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
0
0
0
a
3
a
4
a
5
wiersz wskaźnikowy
c
j
b
10
24
8
300
a
1
2
3
200
a
2
1
3
0
0
a
3
1
0
0
0
a
4
0
1
0
0
a
5
0
0
1
b
a
1
10
/2=5
24
/3=8
8
/2=4
Pierwsza tablica simpleksów
kolumna kluczowa (KK)
wiersz kluczowy (WK)
2
element rozwiązujący (ER)
13
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
0
0
300
a
3
a
4
a
1
wiersz wskaźnikowy
c
j
b
300
a
1
200
a
2
0
a
3
0
a
4
0
a
5
Druga tablica simpleksów
2
Wektory bazowe
c
b
0
0
0
a
3
a
4
a
5
wiersz wskaźnikowy
c
j
b
10
24
8
300
a
1
2
3
200
a
2
1
3
0
0
a
3
1
0
0
0
a
4
0
1
0
0
a
5
0
0
1
Pierwsza tablica simpleksów
W1
W2
WK
0
1200
-200
0
0
150
1
4
0
0
0
1/2
WK / ER
NW3
12
0
3
0
1
-3/2
W2 - 3*NW3
2
0
1
1
0
-1
W1 - 2*NW3
-300
0
-200
0
0
0
b
a
2
2
/1=2
12
/3=4
1
14
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
200
0
300
a
2
a
4
a
1
wiersz wskaźnikowy
c
j
b
300
a
1
200
a
2
0
a
3
0
a
4
0
a
5
Trzecia tablica simpleksów
1
Wektory bazowe
c
b
0
0
300
a
3
a
4
a
1
wiersz wskaźnikowy
c
j
b
2
12
4
300
a
1
0
0
200
a
2
1
3
0
0
a
3
1
0
0
0
a
4
0
1
0
0
a
5
-1
-3/2
1/2
Druga tablica simpleksów
WK
W2
W3
0
1600
0
200
0
-50
1
4
0
0
0
1/2
6
0
0
-3
1
3/2
W2 - 3*NW1
0
1200
-200
0
0
150
b
a
5
6: 3
/2=4
4 :1
/2=8
2
0
1
1
0
-1
NW1
3/2
15
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
200
0
300
a
2
a
5
a
1
wiersz wskaźnikowy
c
j
b
300
a
1
200
a
2
0
a
3
0
a
4
0
a
5
Czwarta tablica simpleksów
0
1800
0
100
33.3
0
0
4
0
-2
2/3
1
0
6
1
-1
3/2
0
1
2
0
1
-1/3
0
Wektory bazowe
c
b
200
0
300
a
2
a
4
a
1
wiersz wskaźnikowy
c
j
b
300
a
1
200
a
2
0
a
3
0
a
4
0
a
5
Trzecia tablica simpleksów
0
1600
0
200
0
-50
1
4
0
0
0
1/2
6
0
0
-3
1
3/2
2
0
1
1
0
-1
ROZWIĄZANIE:
x
1
=2
x
2
=6
Z
=1800
16
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – postać kanoniczna
Przy realizacji metody simpleks mogą powstać pewne problemy
obliczeniowe, związane z tak zwanym zwyrodnieniem zadania.
Zwyrodniałym dopuszczalnym rozwiązaniem bazowym nazywa się
dopuszczalne rozwiązanie bazowe, w którym jedna lub kilka
zmiennych bazowych przybierają wartość zerową.
W tym przypadku może się okazać, że zmiana bazy nie zmienia
wartości funkcji celu.
17
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
- zmienne dopełniające
Programowanie liniowe – postać kanoniczna
Funkcja celu:
Z
=300 x
1
200 x
2
max
Ograniczenia:
{
−2 x
1
−x
2
−10
3 x
1
3 x
2
24
2 x
1
=8
Postać kanoniczna – zamieniamy nierówności na równości:
{
2 x
1
x
2
−x
3
=10
3 x
1
3 x
2
x
4
=24
2 x
1
=8
x
i
0 i=14
Z
=300 x
1
200 x
2
0 x
3
0 x
4
Przekształcamy ograniczenia, tak aby wszystkie wyrazy wolne były
nieujemne i zapisujemy postać kanoniczną.
Uwzględniamy zmienne dopełniające w funkcji celu:
{
2 x
1
x
2
10
3 x
1
3 x
2
24
2 x
1
=8
18
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Postać kanoniczna:
x
i
0 i=14
Z
=300 x
1
200 x
2
0 x
3
0 x
4
max
Funkcja celu:
Ograniczenia:
Ograniczenia w postaci macierzowej:
2 1
−1 0
3 3 0 1
2 0 0 0
A
⋅
x
1
x
2
x
3
x
4
X
=
10
24
8
b
A
⋅X =b
{
2 x
1
x
2
−x
3
=10
3 x
1
3 x
2
x
4
=24
2 x
1
=8
Brak bazy startowej !
19
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Dodajemy zmienne sztuczne:
x
i
0 i=16
Z
=300 x
1
200 x
2
0 x
3
0 x
4
−M x
5
−M x
6
Funkcja celu:
Ograniczenia:
Ograniczenia w postaci macierzowej:
2 1
−1 0 1 0
3 3 0 1 0 0
2 0 0 0 0 1
A
⋅
x
1
x
2
x
3
x
4
x
5
x
6
X
=
10
24
8
b
A
⋅X =b
{
2 x
1
x
2
−x
3
x
5
=10
3 x
1
3 x
2
x
4
=24
2 x
1
x
6
=8
Zmienne sztuczne
M – liczba dużo większa od pozostałych
współczynników funkcji celu
20
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – metoda simpleks
Ograniczenia w postaci macierzowej:
Funkcja celu:
Wektory bazowe
c
b
-1000
0
-1000
a
5
a
4
a
6
wiersz wskaźnikowy
c
j
b
10
24
8
300
a
1
2
3
2
200
a
2
1
3
0
0
a
3
-1
0
0
0
a
4
0
1
0
-1000
a
5
1
0
0
Pierwsza tablica simpleksów
2 1
−1 0 1 0
3 3 0 1 0 0
2 0 0 0 0 1
A
⋅
x
1
x
2
x
3
x
4
x
5
x
6
X
=
10
24
8
b
Z
=300 x
1
200 x
2
0 x
3
0 x
4
−M x
5
−M x
6
Z
=300 x
1
200 x
2
0 x
3
0 x
4
−1000 x
5
−1000 x
6
-1000
a
6
0
0
1
21
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – przykład 2
Funkcja celu:
Z
=5 x
1
3 x
2
max
Ograniczenia:
{
3 x
1
5 x
2
15
−5 x
1
−2 x
2
−10
x
i
0 i=12
22
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
Programowanie liniowe – przykład 2
Funkcja celu:
Ograniczenia (postać znormalizowana):
{
3 x
1
5 x
2
x
3
=15
5 x
1
2 x
2
x
4
=10
x
i
0 i=14
Z
=5 x
1
3 x
2
0 x
3
0 x
4
23
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
-3
F
j
−c
j
=c
b
T
⋅a
j
−c
j
-5
0
0
0
F
0
=c
b
T
⋅b
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
0
0
a
3
a
4
wiersz wskaźnikowy
c
j
b
15
10
5
a
1
3
5
3
a
2
5
2
0
a
3
1
0
0
a
4
0
1
b
a
1
15
/3=5
10
/5=2
Pierwsza tablica simpleksów
kolumna kluczowa (KK)
wiersz kluczowy (WK)
element rozwiązujący (ER)
24
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
-1
F
j
−c
j
=c
b
T
⋅a
j
−c
j
0
0
1
10
F
0
=c
b
T
⋅b
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
0
5
a
3
a
1
wiersz wskaźnikowy
c
j
b
9
2
5
a
1
0
1
3
a
2
3.8
2/5
0
a
3
1
0
0
a
4
-3/5
1/5
b
a
2
2.638
5
Druga tablica simpleksów
kolumna kluczowa (KK)
wiersz kluczowy (WK)
element rozwiązujący (ER)
25
METODY OPTYMALIZACJI
Szczecin - 2008-03-16
0
0
0.263 0.842
12.368
Programowanie liniowe – metoda simpleks
Wektory bazowe
c
b
3
5
a
2
a
1
wiersz wskaźnikowy
c
j
b
2.368
1.053
5
a
1
0
1
3
a
2
1
0
0
a
3
0.263
-0.105
0
a
4
-0.158
0.263
Trzecia tablica simpleksów
ROZWIĄZANIE:
x
1
=1.053 ,
x
2
=2.368
Z
=12.368