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
Wyszukiwarka
Podobne podstrony:
Optymalizacja w2 pdf id 338946 Nieznany
Optymalizacja w1 pdf id 338945 Nieznany
Optymalizacja w2 pdf id 338946 Nieznany
BOIE Cewka pdf id 91559 Nieznany
LINK pdf id 268780 Nieznany
PRZ OPI wyklad 3 v2 pdf id 4033 Nieznany
odpowiedzi pdf id 332621 Nieznany
BATczesc od Trawy pdf id 80765 Nieznany
cukrzyca miazdzyca pdf id 12087 Nieznany
fizyka cz 2 pdf id 176637 Nieznany
Prezentacja pdf id 391045 Nieznany
I KOLO INSTALACJE pdf id 208281 Nieznany
farm 3 PDF id 168032 Nieznany
PDF id 352778 Nieznany
Kieliszek tresc w pdf id 234535 Nieznany
PRZ OPI wyklad 2 v4 pdf id 4033 Nieznany
begg makro PDF id 82389 Nieznany (2)
GEOMETRIA PDF id 189573 Nieznany
ochrona pdf id 791052 Nieznany
więcej podobnych podstron