Zadanie programowania liniowego PL
max f (x)= cT x
przy ograniczeniach:
A1x d" b1
A2 x e" b2
x e"0
dim x=n, dim c=n
Macierze A1, A2 odpowiadają za współczynniki w m1 i m2
ograniczeniach
dim A1 =[m 1 x n], dim A2 =[m 2 x n]
Wektory b1, b2 odpowiadają za prawe strony ograniczeń
dim b1=m1, dim b2=m2
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Zadanie programowania liniowego - przykłady
x1 + x2 d" 5
Å„Å‚ üÅ‚
max x0 = 2x1 +1x2
ôÅ‚x
x"X
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚
òÅ‚ żł
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
Przykład I System produkcji  maksymalizacja zysku
Przykład II System cięcia dłu\
yc
min x = 0.3x + 0.6x + 0.2x
0 1 2 3
7x + 3 x + 0x e" 2100
1 2 3
przy ograniczeniach
0x + 1x + 2x e" 1200
1 2 3
x , x , x e" 0
1 2 3
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Przykład III
Maksymalizacja zysków w procesie produkcji w fabryce papieru.
Cel: Optymalny poziom produkcji papieru niskiej i wysokiej jakości
przy uwzględnieniu ograniczeń.
Zakład przemysłowy produkuje papier niskiej i wysokiej jakości. Do produkcji
wykorzystywane są następujące składniki:
pulpa drzewna
chemikalia
szmaty lniane
woda
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Ceny surowców kształtują się Surowiec Cena jednost.
następująco: [zł/jedn.]
Pulpa 3
Woda jest wolna od opłat.
Chemikalia 4
Jej zu\
ycie jest nielimitowane.
Szmaty lniane 9
Surowiec/jedn Jakość papieru
W zale\
ności od tego, czy
ostkÄ™
Niska Wysoka
produkowany
jest papier niskiej, czy wysokiej
Pulpa 1,10 1,50
jakości zu\
ywana jest ró\
na
Chemikalia 0,10 0,20
ilość surowców.
Szmaty 0,10 0,40
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Koszt wyprodukowania jednostki papieru:
niskiej jakości wynosi - 1,8 [zł], natomiast
wysokiej jakości - 1,5 [zł].
Cena sprzeda\
y jednostki produktu końcowego wynosi :
10 [zł] dla produktu niskiej jakości
16,5 [zł] dla produktu wysokiej jakości.
Efektem ubocznym przy produkcji papieru są ścieki. Podczas wytwarzania
jednostki papieru niskiej jakości powstają 3 jednostki ścieków, zaś w przypadku
papieru o wysokiej jakości powstaje 6 jednostek ścieków.
Część ścieków poddawana jest procesowi oczyszczania w wyniku czego ilość
zanieczyszczenia jest redukowana o 50%. Pozostała część ścieków jest
odprowadzana do kanałów. Koszt tych operacji przedstawia się następująco:
Oczyszczanie ścieków powstałych przy produkcji papieru niskiej jakości = 0,11
[zł] na jednostkę produkcyjną,
oczyszczanie ścieków powstałych przy produkcji papieru wysokiej jakości =0,12
[zł] na jednostkę produkcyjną,
Koszt odprowadzenia jednostki ścieków do kanałów = 0,3 [zł].
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Proces produkcyjny obarczony jest z góry nało\
onymi ograniczeniami:
Zakład mo\
e zakupić maksymalnie 50 jednostek pulpy drzewnej
Maksymalna przepustowość oczyszczalni ścieków wynosi 60 jednostek
Ze względu na kooperację zakład musi wytworzyć przynajmniej 12
jednostek papieru niskiej jakości
Cel: znalezienie optymalnego poziomu produkcji papieru niskiej i wysokiej
jakości, takiego aby zysk przedsiębiorstwa był maksymalny.
Uwzględnić nale\
y wszystkie koszty generowane przez proces
produkcyjny oraz ograniczenia tego\
procesu.
W celu znalezienia maksymalnego zysku , nale\
y zmaksymalizować
funkcję celu przedstawiającą zysk zakładu produkcji papieru.
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Definicja problemu programowania liniowego PL
T
Wektor zmiennych decyzyjnych:
x = [x , x , x , x ]
1 2 3 4
gdzie:
- wielkość produkcji papieru niskiej jakości
x1
x2
-wielkość produkcji papieru wysokiej jakości
x3
-ilość oczyszczanych ścieków przy produkcji papieru niskiej jakości
x4
- ilość oczyszczanych ścieków przy produkcji papieru wysokiej jakości.
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Pulpa drzewna Chemikalia Szmaty lniane
(koszt jednostki 3) (koszt jednostki 4) (koszt jednostki 9)
1,1x1 0,1x1 0,1x1 1,5x2 0,2x2 0,4x2
Koszt produkcji Koszt produkcji
jednostki papieru jednostki papieru
niskiej jakości 1,8 wysokiej jakości 1,5
3x1 6x2
3x1-x3 6x2-x4
x3 x4
x1 Koszt oczyszczania jednostki Koszt oczyszczania jednostki x2
ścieków przy produkcji papieru ścieków przy produkcji papieru
niskiej jakości 0,11 wysokiej jakości 0,12
0,5x3 0,5x4
Cena sprzeda\
y Koszt jednostki Cena sprzeda\
y
10 usuwanych ścieków 0,3 16,5
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Wyznaczenie funkcji celu i ograniczeń zadania produkcji papieru
dochód
10x1 +16,5x2
1,8x1 +1,5x2 koszty produkcji
koszty materiałów do produkcji papieru niskiej jakości
3Å"1,1x1 + 4 Å" 0,1x1 + 9 Å" 0,1x1
3Å"1,5x2 + 4 Å" 0,2x2 + 9 Å" 0,4x2 koszty materiałów do produkcji papieru wysokiej jakoÅ›ci
koszty oczyszczania ścieków
0,11x3 + 0,12x4
koszt odprowadzenia ścieków
0,3[(3x1 - x3 )+ 0,5x3 + (6 x2 - x4 )+ 0,5x4 ]
W celu znalezienia maksymalnego zysku, nale\
y maksymalizować funkcję celu w
postaci: dochód  koszty.
max F(X ) = 10x1 +16,5x2 -(1,8x1 +1,5x2)-(3Å"1,1x1 + 4Å"0,1x1 + 9Å"0,1x)+
X
-(3Å"1,5x2 + 4Å"0,2x2 + 9Å"0,4x)-(0,11x3 + 0,12x4)+
-(0,3[(3x1 - x3)+ 0,5x3 + (6x2 - x4)+ 0,5x4])=
= 2,7x1 + 4,4x2 + 0,04x3 + 0,03x4
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Zatem funkcja celu jest postaci:
max F(X ) = 2,7x1 + 4,4x2 + 0,04x3 + 0,03x4
X
Uwzględniając następujące ograniczenia :
maksymalna ilość pulpy
1,1x1 +1,5x2 d" 50
maksymalna przepustowość oczyszczalni
x3 + x4 d" 60
ścieków
3x1 - x3 d" 0
wymaganie nieujemnego przepływu
6x2 - x4 d" 0
wymaganie nieujemnego przepływu
wymaganie wyprodukowania określonej x1 e" 12
liczby papieru niskiej jakości
x e" 0
Wymaganie produkowania określonej liczby
2
papieru wysokiej jakości:
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Zadanie maksymalizacji zysku produkcji papieru
max x = 2.7x +1.5x + 0.04x + 0.03x
0 1 2 3 4
x"X
1.1x1 +1.5x2 d" 50
Å„Å‚ üÅ‚
ôÅ‚ ôÅ‚
x1 + x2 d" 60
ôÅ‚ ôÅ‚
ôÅ‚x
X = : 3x1 - x3 e" 0, x e" 0ôÅ‚
òÅ‚ żł
ôÅ‚ ôÅ‚
6x2 - x4 e" 0
ôÅ‚ ôÅ‚
ôÅ‚ x1 e" 12 ôÅ‚
ół þÅ‚
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Zadanie programowania nieliniowego PN
'"
ëÅ‚xöÅ‚
f (x)= f
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x"X
przy ograniczeniach:
X = x gi(x)d"0, i=1,...,m
{ }
Zadanie programowania nieliniowego polega na znalezieniu wektora zmiennych
'"
decyzyjnych , nale\
ącego do zbioru rozwiązań dopuszczalnych X w postaci:
x
takiego, \
e dla
"x"X
'"
ëÅ‚ öÅ‚
f x d" f (x )
ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Przykład zadania programowania nieliniowego
Przykład IV. Zadania sterowania siecią dystrybucji wody minimalizujące
zu\
ycie energii elektrycznej
Dana jest sieć dystrybucji wody w postaci:
m- węzłów,
s - odbiorców z odpowiednimi potrzebami, w których utrzymywane jest
à "Rs
odpowiednie ciśnienie oraz n łuków,
ka\
dy łuk  i charakteryzuje się przepływem yi:
y"Rn
Opis sieci:
spadek ciśnienia xi na łuku  i :
x"Rn xi =ri yi2 sgn yi + di
gdzie: ri- opór hydrauliczny łuku  i
di- ró\
nica wysokości geodezyjnych łuku  i
Ograniczenia wynikajÄ…ce ze struktury sieci: A y = Ã
I prawo Kirchhoff a:
A  macierz incydencji dla węzłów sieci wodociągowej,
II prawo Kirchhoff a:
B x = 0
B  macierz oczkowa dla węzłów sieci wodociągowej.
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Sterowanie sieciÄ… dystrybucji wody minimalizujÄ…ce zu\
ycie energii
elektrycznej
n
min f ( y) = fi(yi )
"
i=1
gdzie: fi(yi )= xi yi = ri yi3 sgn yi + di yi
przy ograniczeniach:
A y = Ã
B x = 0
xi =ri yi2 sgn yi + di
y"Rn
x"Rn
à "Rs
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Przykład V- Zadanie lokalizacji magazynu i ustalania tras dostaw
optymalizacji sieci tras dostaw z wyborem najlepszego poło\
enia dla
magazynu
Przykład VI Zadania klasy VRP
np..: Firma CorbitConnect - obsługa rynku dostaw
np.: - procedury logistyczne:
- Route scheduling, optimisation and disposition
- Fleet management and controlling
- Fleet controlling
- Mobile navigation with tour management
- Mobile tour management
np.: Program PLANTOUR - Firma CorbitConnect
Przykład VII  Zadanie doboru optymalnej topologii sieci
telekomunikacyjnej
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.