Programowanie liniowe
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
Metody:
metoda graficzna,
metoda algebraiczna,
metoda simpleks.
1
METODY OPTYMALIZACJI, Informatyka 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 i jakich aby osiągnąć maksymalny zysk.
2
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  przykład
Oznaczenia:
x1= płyty barwne ,
x2= płyty bezbarwne.
Ograniczenia:
2 x1ƒÄ…x2Ä…Ä…10
3 x1ƒÄ…3 x2Ä…Ä…24
{
2 x1Ä…Ä…8
xi‡Ä…0 i=1‹Ä…2
Funkcja celu:
Z =300 x1ƒÄ…200 x2 Śą max
3
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  metoda graficzna
Funkcja celu:
Z =300 x1ƒÄ…200 x2 Śą max
1
x2
Ograniczenia:
1
2 x1ƒÄ…x2Ä…Ä…10
10
2 2
3 x1ƒÄ…3 x2Ä…Ä…24
9
3
{
3
2 x1Ä…Ä…8
8
7
6
5
4
obszar rozwiązań dopuszczalnych
3
2
1
0
1 2 3 4 5 6 7 8 x1
4
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Z
=
1
8
0
0
Z
=
1
6
0
0
Z
=
1
2
0
0
Z
=
0
Programowanie liniowe  metoda algebraiczna
Funkcja celu:
Z =300 x1ƒÄ…200 x2 Śą max
Ograniczenia:
2 x1ƒÄ…x2Ä…Ä…10
3 x1ƒÄ…3 x2Ä…Ä…24
{
2 x1Ä…Ä…8
Przekształcamy ograniczenia, tak aby wszystkie wyrazy wolne były
nieujemne i zapisujemy postać kanoniczną.
Postać kanoniczna  zamieniamy nierówności na równości:
2 x1ƒÄ…x2ƒÄ…x3=10
- zmienne dopełniające
3 x1ƒÄ…3 x2ƒÄ…x4=24
{
2 x1ƒÄ…x5=8
xi‡Ä…0 i=1‹Ä…5
Uwzględniamy zmienne dopełniające w funkcji celu:
Z =300 x1ƒÄ…200 x2ƒÄ…0 x3ƒÄ…0 x4ƒÄ…0 x5
5
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  metoda algebraiczna
2 x1ƒÄ…x2ƒÄ…x3=10 Z =300 x1ƒÄ…200 x2ƒÄ…0 x3ƒÄ…0 x4ƒÄ…0 x5
3 x1ƒÄ…3 x2ƒÄ…x4=24
{
2 x1ƒÄ…x5=8
Mamy 3 równania i 5 niewiadomych:
x1=x2=0 Śą zmienne wolne
1
x3, x4, x5 Śą zmienne bazowe
x3=10
x4=24
{
x5=8
x1=0, x2=0, x3=10, x4=24, x5=8 Śą rozw. bazowe dopuszczalne
Z =0 Śą wartość funkcji celu
6
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  metoda algebraiczna
x1=x3=0 Śą zmienne wolne x2, x4, x5 Śą zmienne bazowe
2
x2=10
x4=-6
{
x5=8
x1=0, x2=10, x3=0, x4=-6, x5=8 Śą rozw.bazowe niedopuszczalne
x1=x4=0 Śą zmienne wolne x2, x3, x5 Śą zmienne bazowe
3
x2=8
x3=2
{
x5=8
x1=0, x2=8, x3=2, x4=0, x5=8 Śą rozw. bazowe dopuszczalne
Z =1600 Śą wartość funkcji celu
7
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  metoda algebraiczna
x1=x5=0 Śą zmienne wolne
4 x2, x3, x4 Śą zmienne bazowe
x2ƒÄ…x3=10
Śą układ sprzeczny
3 x2ƒÄ…x4=24
{
0=8
zmienne x2, x3, x4 -nie mogą być zmiennymi bazowymi
x1, x4, x5 Śą zmienne bazowe
x2=x3=0 Śą zmienne wolne
5
x1=5, x2=0, x3=0, x4=9, x5=-2 Śą rozw. bazowe niedopuszczalne
x1, x3, x5 Śą zmienne bazowe
x2=x4=0 Śą zmienne wolne
6
x1=8, x2=0, x3=-6, x4=0, x5=-8 Śą rozw. bazowe niedopuszczalne
8
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  metoda algebraiczna
x2=x5=0 Śą zmienne wolne x1, x3, x4 Śą zmienne bazowe
7
x1=4, x2=0, x3=2, x4=12, x5=0 Śą rozw. bazowe dopuszczalne
Z =1200 Śą wartość funkcji celu
x1, x2, x5 Śą zmienne bazowe
x3=x4=0 Śą zmienne wolne
8
x1=2, x2=6, x3=0, x4=0, x5=4 Śą rozw. bazowe dopuszczalne
Z =1800 Śą wartość funkcji celu
x3=x5=0 Śą zmienne wolne x1, x2, x4 Śą zmienne bazowe
9
x1=4, x2=2, x3=0, x4=6, x5=0 Śą rozw.bazowe dopuszczalne
Z =1600 Śą wartość funkcji celu
9
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16
Programowanie liniowe  metoda algebraiczna
x4=x5=0 Śą zmienne wolne x1, x2, x3 Śą zmienne bazowe
10
x1=4, x2=4, x3=-2, x4=0, x5=0 Śą rozw. bazowe niedopuszczalne
Ilość możliwych rozwiązań jakie należy sprawdzić:
n!
n  liczba zmiennych,
Cm=
n
m  liczba ograniczeń
m !śąn-mźą!
5!
C3= =10
5
3!śą5-3źą!
10
METODY OPTYMALIZACJI, Informatyka Szczecin - 2008-03-16