Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Zadanie programowania liniowego PL
przy ograniczeniach:
( )
x
c
x
T
f
=
max
0
2
2
1
1
≥
≥
≤
x
b
x
A
b
x
A
dim x=n, dim c=n
Macierze A
1
, A
2
odpowiadają za współczynniki w m
1
i m
2
ograniczeniach
dim A
1
=[m
1
x n], dim A
2
=[m
2
x n]
Wektory b
1
, b
2
odpowiadają za prawe strony ograniczeń
dim b
1
=m
1
, dim b
2
=m
2
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Zadanie programowania liniowego - przykłady
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
3
2
1
0
2
.
0
6
.
0
3
.
0
min
x
x
x
x
+
+
=
Przykład II System cięcia dłuŜyc
Przykład I System produkcji – maksymalizacja zysku
0
,
,
1200
2
1
0
2100
0
3
7
3
2
1
3
2
1
3
2
1
≥
≥
+
+
≥
+
+
x
x
x
x
x
x
x
x
x
przy ograniczeniach
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Przykład III
Maksymalizacja zysków w procesie produkcji w fabryce papieru.
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
Cel: Optymalny poziom produkcji papieru niskiej i wysokiej jakości
przy uwzględnieniu ograniczeń.
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Ceny surowców kształtują się
następująco:
9
Szmaty lniane
4
Chemikalia
3
Pulpa
Cena jednost.
[zł/jedn.]
Surowiec
Woda jest wolna od opłat.
Jej zuŜycie jest nielimitowane.
W zaleŜności od tego, czy
produkowany
jest papier niskiej, czy wysokiej
jakości zuŜywana jest róŜna
ilość surowców.
0,40
0,10
Szmaty
0,20
0,10
Chemikalia
1,50
1,10
Pulpa
Wysoka
Niska
Jakość papieru
Surowiec/jedn
ostkę
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
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ł].
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
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.
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Definicja problemu programowania liniowego PL
Wektor zmiennych decyzyjnych:
T
x
x
x
x
x
]
,
,
,
[
4
3
2
1
=
gdzie:
- wielkość produkcji papieru niskiej jakości
-wielkość produkcji papieru wysokiej jakości
-ilość oczyszczanych ścieków przy produkcji papieru niskiej jakości
- ilość oczyszczanych ścieków przy produkcji papieru wysokiej jakości.
4
3
2
1
x
x
x
x
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Pulpa drzewna
(koszt jednostki 3)
Chemikalia
(koszt jednostki 4)
Szmaty lniane
(koszt jednostki 9)
Koszt produkcji
jednostki papieru
niskiej jakości 1,8
Koszt produkcji
jednostki papieru
wysokiej jakości 1,5
Koszt oczyszczania jednostki
ścieków przy produkcji papieru
niskiej jakości 0,11
Koszt oczyszczania jednostki
ścieków przy produkcji papieru
wysokiej jakości 0,12
Cena sprzedaŜy
10
Cena sprzedaŜy
16,5
Koszt jednostki
usuwanych ścieków 0,3
1,1x
1
0,1x
1
0,1x
1
0,4x
2
0,2x
2
1,5x
2
x
1
x
2
3x
1
6x
2
x
3
x
4
3x
1-
x
3
6x
2-
x
4
0,5x
3
0,5x
4
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
dochód
koszty produkcji
koszty materiałów do produkcji papieru niskiej jakości
koszty materiałów do produkcji papieru wysokiej jakości
koszty oczyszczania ścieków
koszt odprowadzenia ścieków
W celu znalezienia maksymalnego zysku, naleŜy maksymalizować funkcję celu w
postaci: dochód – koszty.
Wyznaczenie funkcji celu i ograniczeń zadania produkcji papieru
2
1
5
,
16
10
x
x +
2
1
5
,
1
8
,
1
x
x +
1
1
1
1
,
0
9
1
,
0
4
1
,
1
3
x
x
x
⋅
+
⋅
+
⋅
2
2
2
4
,
0
9
2
,
0
4
5
,
1
3
x
x
x
⋅
+
⋅
+
⋅
4
3
12
,
0
11
,
0
x
x +
(
)
(
)
[
]
4
4
2
3
3
1
5
,
0
6
5
,
0
3
3
,
0
x
x
x
x
x
x
+
−
+
+
−
(
) (
)
(
) (
)
(
)
(
)
[
]
(
)
4
3
2
1
4
4
2
3
3
1
4
3
2
2
1
1
2
1
2
1
03
,
0
04
,
0
4
,
4
7
,
2
5
,
0
6
5
,
0
3
3
,
0
12
,
0
11
,
0
4
,
0
9
2
,
0
4
5
,
1
3
1
,
0
9
1
,
0
4
1
,
1
3
5
,
1
8
,
1
5
,
16
10
)
(
max
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
X
F
X
+
+
+
=
=
+
−
+
+
−
−
+
+
−
⋅
+
⋅
+
⋅
−
+
⋅
+
⋅
+
⋅
−
+
−
+
=
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Zatem funkcja celu jest postaci:
Uwzględniając następujące ograniczenia :
maksymalna ilość pulpy
maksymalna przepustowość oczyszczalni
ścieków
wymaganie nieujemnego przepływu
wymaganie nieujemnego przepływu
wymaganie wyprodukowania określonej
liczby papieru niskiej jakości
Wymaganie produkowania określonej liczby
papieru wysokiej jakości:
4
3
2
1
03
,
0
04
,
0
4
,
4
7
,
2
)
(
max
x
x
x
x
X
F
X
+
+
+
=
50
5
,
1
1
,
1
2
1
≤
+
x
x
60
4
3
≤
+ x
x
0
3
3
1
≤
− x
x
0
6
4
2
≤
− x
x
12
1
≥
x
0
2
≥
x
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Zadanie maksymalizacji zysku produkcji papieru
4
3
2
1
0
03
.
0
04
.
0
5
.
1
7
.
2
max
x
x
x
X
x
+
+
+
=
∈
x
x
≥
≥
−
≥
≥
−
≤
+
≤
+
=
12
0
6
0
,
0
3
:
60
50
5
.
1
1
.
1
1
4
2
3
1
2
1
2
1
x
x
x
x
x
x
x
x
x
x
x
X
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Zadanie programowania nieliniowego PN
przy ograniczeniach:
( )
=
∧
∈
x
x
x
f
f
X
min
{
}
m
i
g
x
X
i
,...,
1
,
0
)
(
=
≤
=
x
Zadanie programowania nieliniowego polega na znalezieniu wektora zmiennych
decyzyjnych
, naleŜącego do zbioru rozwiązań dopuszczalnych X w postaci:
takiego, Ŝe dla
X
∈
∀x
( )
x
x
f
f
≤
∧
∧
x
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
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
odpowiednie ciśnienie oraz n łuków,
kaŜdy łuk „i” charakteryzuje się przepływem y
i
:
Opis sieci:
spadek ciśnienia x
i
na łuku „i”:
gdzie: r
i
- opór hydrauliczny łuku „i”
d
i
- róŜnica wysokości geodezyjnych łuku „i”
Ograniczenia wynikające ze struktury sieci:
I prawo Kirchhoff’a:
A – macierz incydencji dla węzłów sieci wodociągowej,
II prawo Kirchhoff’a:
B – macierz oczkowa dla węzłów sieci wodociągowej.
i
i
i
i
i
d
y
y
r
x
+
=
sgn
2
n
R
y∈
n
R
x∈
s
R
∈
σ
σ
=
y
A
0
=
x
B
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Sterowanie siecią dystrybucji wody minimalizujące zuŜycie energii
elektrycznej
( )
i
n
i
i
y
f
y
f
∑
=
=
1
)
(
min
gdzie:
( )
i
i
i
i
i
i
i
i
i
y
d
y
y
r
y
x
y
f
+
=
=
sgn
3
przy ograniczeniach
:
σ
=
y
A
0
=
x
B
i
i
i
i
i
d
y
y
r
x
+
=
sgn
2
n
R
y∈
n
R
x∈
s
R
∈
σ
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika.
III r Potok: Elektronika.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
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