1
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – ekstremum funkcji liniowej przy liniowych
ograniczeniach
Opracowanie modelu programowania linowego:
●
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.
2
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
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 i jakich aby osiągnąć maksymalny zysk.
3
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
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=1…2
4
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda graficzna
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
2
1
1
2
3
4
5
6
7
8
0
1
3
2
4
5
6
7
8
9
10
3
2
1
3
x
2
x
1
obszar rozwiązań dopuszczalnych
Z=
0
Z=
12
00
Z=
16
00
Z=
18
00
5
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
- zmienne dopełniające
Programowanie liniowe – metoda algebraiczna
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=1…5
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ć kanoniczną.
Uwzględniamy zmienne dopełniające w funkcji celu:
6
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda algebraiczna
{
2 x
1
+
x
2
+
x
3
=
10
3 x
1
+
3 x
2
+
x
4
=
24
2 x
1
+
x
5
=
8
Z =300 x
1
+
200 x
2
+
0 x
3
+
0 x
4
+
0 x
5
Mamy 3 równania i 5 niewiadomych:
1
x
1
=
x
2
=
0
→
zmienne wolne
{
x
3
=
10
x
4
=
24
x
5
=
8
x
1
=
0, x
2
=
0, x
3
=
10, x
4
=
24, x
5
=
8 → rozw. bazowe dopuszczalne
Z =0 → wartość funkcji celu
x
3,
x
4,
x
5
→
zmienne bazowe
7
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda algebraiczna
2
x
1
=
x
3
=
0 → zmienne wolne
{
x
2
=
10
x
4
=−
6
x
5
=
8
x
1
=
0, x
2
=
10, x
3
=
0, x
4
=−
6, x
5
=
8 → rozw. bazowe niedopuszczalne
x
2,
x
4,
x
5
→
zmienne bazowe
3
x
1
=
x
4
=
0 → zmienne wolne
{
x
2
=
8
x
3
=
2
x
5
=
8
x
1
=
0, x
2
=
8, x
3
=
2, x
4
=
0, x
5
=
8 → rozw. bazowe dopuszczalne
Z =1600 → wartość funkcji celu
x
2,
x
3,
x
5
→
zmienne bazowe
8
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda algebraiczna
4
x
1
=
x
5
=
0 → zmienne wolne
{
x
2
+
x
3
=
10
3 x
2
+
x
4
=
24
0=8
→
układ sprzeczny
zmienne x
2,
x
3,
x
4
−
nie mogą być zmiennymi bazowymi
x
2,
x
3,
x
4
→
zmienne bazowe
5
x
2
=
x
3
=
0 → zmienne wolne
x
1
=
5, x
2
=
0, x
3
=
0, x
4
=
9, x
5
=−
2 → rozw. bazowe niedopuszczalne
x
1,
x
4,
x
5
→
zmienne bazowe
6
x
2
=
x
4
=
0 → zmienne wolne
x
1
=
8, x
2
=
0, x
3
=−
6, x
4
=
0, x
5
=−
8 → rozw. bazowe niedopuszczalne
x
1,
x
3,
x
5
→
zmienne bazowe
9
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda algebraiczna
7
x
2
=
x
5
=
0 → zmienne wolne
x
1
=
4, x
2
=
0, x
3
=
2, x
4
=
12, x
5
=
0 → rozw. bazowe dopuszczalne
Z =1200 → wartość funkcji celu
x
1,
x
3,
x
4
→
zmienne bazowe
8
x
3
=
x
4
=
0 → zmienne wolne
Z =1800 → wartość funkcji celu
x
1,
x
2,
x
5
→
zmienne bazowe
x
1
=
2, x
2
=
6, x
5
=
0 → rozw.bazowe dopuszczalne
9
x
3
=
x
5
=
0 → zmienne wolne
x
1
=
4, x
2
=
2, x
3
=
0, x
4
=
6, x
5
=
0 → rozw. bazowe dopuszczalne
Z =1600 → wartość funkcji celu
x
1,
x
2,
x
4
→
zmienne bazowe
10
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda algebraiczna
10
x
4
=
x
5
=
0 → zmienne wolne
x
1
=
4, x
2
=
4, x
3
=−
2, x
4
=
0, x
5
=
0 → rozw. bazowe niedopuszczalne
x
1,
x
2,
x
3
→
zmienne bazowe
C
n
m
=
n !
m !(n−m)!
C
5
3
=
5 !
3 !(5−3)!
=
10
Liczba możliwych rozwiązań jakie należy sprawdzić:
n – liczba zmiennych,
m – liczba ograniczeń
11
METODY OPTYMALIZACJI, Informatyka
Szczecin - 9.05.2013
Programowanie liniowe – metoda algebraiczna
NR
1
2
3
4
5
6
7
8
9
10
Zmienne wolne
x
1,
x
2
Zmienne bazowe Rozwiązanie bazowe
dopuszczalne
niedopuszczalne
dopuszczalne
układ sprzeczny
niedopuszczalne
niedopuszczalne
dopuszczalne
dopuszczalne
dopuszczalne
niedopuszczalne
Wartość funkcji celu
Z =0
Z =1600
Z =1200
Z =1800
Z =1600
x
1
=
2, x
2
=
6
x
1,
x
2,
x
3
x
3,
x
4,
x
5
x
2,
x
4,
x
5
x
2,
x
3,
x
5
x
2,
x
3,
x
4
x
1,
x
4,
x
5
x
1,
x
3,
x
5
x
1,
x
3,
x
4
x
1,
x
2,
x
5
x
1,
x
2,
x
4
x
1,
x
3
x
1,
x
4
x
1,
x
5
x
2,
x
3
x
2,
x
4
x
2,
x
5
x
3,
x
4
x
3,
x
5
x
4,
x
5