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