E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

1

Wykład 2

PROGRAMOWANIE LINIOWE

OPTYMALIZACJA GRAFICZNA

1. Ogólna postać zadania optymalizacyjnego

Należy zoptymalizować funkcję z(x):

z(x) = f(x

1

, x

2

, ....x

i

.... x

n

)  max, min

gdzie:

x = (x

1

, x

2

, ....x

i

.... x

n

) – zmienne decyzyjne

przy ograniczeniach:

g

i

( x

1

, x

2

, x

j

,.... x

m

)



0

x

i



0; i = 1, 2, ....n

x

j



0; j = 1, 2, ....m

2. Elementy programowania liniowego

Z

matematycznym

liniowym

modelem

optymalizacyjnym

problemu

decyzyjnego mamy do czynienia wtedy, kiedy

równania i nierówności modelu

opisujące rozpatrywany problem mają charakter liniowy.
Zadaniem programowania liniowego

nazywa się problem decyzyjny polegający na

wyznaczeniu warunkowego ekstremum (minimum lub maksimum) funkcji celu
modelu liniowego, którego zmienne decyzyjne przyjmują nieujemne wartości.

Ogólna postać zadania programowania liniowego

Wyznaczyć wartość ekstremalną funkcji celu z ( x ):

x

c

x

z

T



)

(

przy warunkach (ograniczeniach):

b

Ax



0



x

gdzie:

z(x) - funkcja celu (kryterium),

x - wektor kolumnowy zmiennych decyzyjnych,

A -

macierz współczynników przy zmiennych decyzyjnych o wymiarach:

m x n; przy czym m < n,

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

2

c - n

wymiarowy wektor kolumnowy współczynników funkcji celu,

b - m

wymiarowy wektor kolumnowy wyrazów wolnych ograniczeń, zwany prawymi

stronami ograniczeń,

 -

oznacza relację typu:



,



lub =

Zagadnienie programowania liniowego posiada cztery postaci

w zależności od

występujących relacji:



(1) Postać standardowa I typu, jeżeli zależność jest opisana wzorem:

b

Ax





(2) Postać standardowa II typu dla przypadku, gdy:

b

Ax





(3) Postać kanoniczna dla:

b

Ax





(4) Postać mieszana dla zależności:

3

3

2

2

1

1

b

x

A

b

x

A

b

x

A







gdzie:



macierz A jest

macierzą blokową postaci:























3

2

1

A

A

A

A

a wektor b jest postaci:























3

2

1

b

b

b

b

Rozwiązaniem dopuszczalnym zadania programowania liniowego jest n –

wymiarowy wektor :

x = [ x

1

, x

2

,

…, x

n

]

spełniający warunki ograniczające i brzegowe.

Rozwiązanie dopuszczalne, przy którym funkcja celu osiąga wartość ekstremalną

nazywamy

rozwiązaniem optymalnym.

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

3

W przypadku poszukiwania maksimum funkcji celu, typowy zwrot nier

ówności

ograniczeń to



(nie większe) oraz



(nie mniejsze) dla zadań na minimum.

Jeśli ten warunek nie jest spełniony, mnożymy daną nierówność ograniczenia

przez wartość „–1” zmieniając tym samym zwrot tej nierówności.

W zadaniach programowania

liniowego stosuje się dwa rodzaje optymalizacji

(minimalizację i maksymalizację).

Zawsze jedno z kryterium optymalizacji można zastąpić kryterium przeciwnego

rodzaju poprzez zmianę wartości współczynników funkcji celu na przeciwne.

I tak zadanie programowania liniowego postaci:

0

4

2

18

6

3

2

1

2

1

2

1

2

1



















x

x

x

x

x

x

x

x

x

z

,

max,

)

(

jest

równoważne zadaniu postaci:

0

4

2

18

6

3

2

1

2

1

2

1

2

1

















x

x

x

x

x

x

x

x

x

z

,

min,

)

(

3. Optymalizacja – metoda graficzna

Rozwiązanie zadania programowania liniowego, które posiada dwie zmienne

decyzyjne x

1

i x

2

,

można przedstawić graficznie.

Zadanie przyjmuje postać:

0

2

1

2

2

1

1

2

2

22

1

21

1

2

12

1

11

2

2

1

1





















x

x

b

x

a

x

a

b

x

a

x

a

b

x

a

x

a

eks trem um

x

c

x

c

x

z

n

n

n

,

........

..........

..........

,

)

(

W układzie współrzędnych Ox

1

x

2

,

wyznacza się zbiór rozwiązań dopuszczalnych

X. Jest

to iloczyn wszystkich prostych i półpłaszczyzn odpowiadających równaniom

i nierównościom kolejnych ograniczeń zadania. Jeżeli ograniczenia są podane tylko w
postaci nierówności, obszarem rozwiązań dopuszczalnych będzie wielobok wypukły.

Rozwiązaniem dopuszczalnym będą współrzędne wierzchołka wieloboku, dla

których funkcja celu przyjmuje wartość ekstremalną – tzw. wierzchołka optymalnego.

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

4

W celu odnalezienia wierzchołka optymalnego wykreśla się w układzie

współrzędnych Ox

1

x

2

gradient



z(x)

funkcji celu z(x)

„ zaczepiając go” w początku

układu współrzędnych.

Kierunek wskazywany przez gradient jest niezależny od zmiennych decyzyjnych:

(x

1

, x

2

, …, x

n

).

Następnie rysujemy prostą prostopadłą do gradientu funkcji celu, przechodzącą

przez początek układu współrzędnych, czyli prostą o równaniu:

2

2

1

1

0

x

c

x

c

x

L







)

(

Nadając funkcji L(x) coraz większe wartości przesuwa się ona równolegle wzdłuż

kierunku wyznaczonego przez gradient, przecinając wielobok będący zbiorem
rozwiązań dopuszczalnych. Otrzymane proste równoległe dla różnych wartości funkcji
L(x)

są nazywane liniami izocelowymi.

Na rysunku 1

przedstawiono opisane postępowanie dla przykładowego zbioru

rozwiązań zadania programowania liniowego dla dwóch zmiennych x

1

i x

2

.

A

B

C

D

E

X

2

X

1

z(x)

L(x)

Rys. 1. Interpretacja graficzna zadania programowania liniowego

dwóch zmiennych

W momen

cie „zerwania kontaktu” prostej ze zbiorem rozwiązań, ostatni punkt

wspólny zbioru i prostej jest wierzchołkiem optymalnym. Rozwiązanie to będzie
maksymalizować funkcje celu z(x). W przypadku poszukiwania minimum, postępuje się

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

5

podobnie, przesuwając prostą prostopadłą do gradientu, w kierunku przeciwnym do tego
jaki wskazuje gradient.

Na rysunku 1

pole wieloboku ABCDE to zbiór rozwiązań zadania programowania

liniowego. Współrzędne wierzchołków wieloboku reprezentują dopuszczalne
rozwiązania bazowe. Współrzędne wierzchołka A stanowią rozwiązanie optymalne
minimalizujące funkcję celu z(x), natomiast współrzędne wierzchołka D maksymalizuję
funkcje celu. A i D są wierzchołkami optymalnymi.

W przypadku

kiedy jedna z prostych izocelowych będzie równoległa do jednego

z boków wieloboku wypukłego będzie to oznaczać, że rozwiązanie optymalne znajduje
się w dwóch punktach wierzchołkowych. Sytuację taką przedstawia rysunek 2.

Dla przypadku z rysunku 2

wierzchołkami optymalnymi maksymalizującymi

funkcję celu z(x) są wierzchołki C i D. Rozwiązaniami optymalnymi będą również
wszystkie punkty boku CD.

A

B

C

D

E

X

2

X

1

z(x)

L(x)

Rys.2.

Przypadek z nieskończenie wielką liczbą rozwiązań zadania liniowego

Dochodzenie do rozwiązania zadania programowania liniowego w metodzie
graficznej przebiega dwuetapowo:

1. W

ykreślenie zbioru rozwiązań dopuszczalnych.

2. W

yznaczenie w tym zbiorze rozwiązania optymalnego.

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

6

Przy wykreślaniu zbioru rozwiązań może wystąpić jeden z czterech przypadków:



rozwiązanie zadania posiada dokładnie jedno rozwiązanie optymalne,



rozwiązanie zadania posiada wiele rozwiązań optymalnych,



rozwiązanie zadania programowania liniowego jest sprzeczne,



rozwiązanie zadanie nie posiada skończonego rozwiązania

optymalnego.

Przypadek 1 -

rozwiązanie zadania posiada dokładnie jedno rozwiązanie optymalne

Maksymalizujemy funkcję celu postaci:

max

)

(









2

1

3

x

x

x

z

przy ograniczeniach:

0

2

2

2

2

2

2

1

2

1

2

1

2

1

















x

x

III

x

x

II

x

x

I

x

x

,

)

(

)

(

)

(

Rysunek 3

przedstawia geometryczną interpretację rozwiązania przypadku. Istnieje

prosta izocelowa

, która przecina zbiór rozwiązań dopuszczalnych dokładnie w

jednym punkcie

. Punkt ten jest wierzchołkiem optymalnym, a jego współrzędne

maksymalizują funkcję celu.

2

X

1

z(x)

L(x)

(II)

(III)

Rys.3. Interpretacja geometryczna

skończonego jednoznacznego rozwiązania

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

7

Przypadek 2 -

rozwiązanie zadania posiada wiele rozwiązań optymalnych

Rozwiązaniami optymalnymi są współrzędne skrajnych punktów boku oraz każde

współrzędne będące liniową wypukłą ich kombinacją. Sytuację tą przedstawia rys. 4.

Dotyczy ona minimalizacji funkcji celu postaci:

min

)

(







2

1

2

2

x

x

x

z

przy ograniczeniach:

0

2

2

2

2

2

2

1

2

1

2

1

2

1

















x

x

III

x

x

II

x

x

I

x

x

,

)

(

)

(

)

(

X

2

X

1

z(x)

L(x)

(I)

(II)

(III)

Rys.4. Interpretacja geometryczne niejednoznacznego rozwiązania

Przypadek 3 -

rozwiązanie zadania programowania liniowego jest sprzeczne

Maksymalizujemy funkcję celu postaci:

max

)

(







2

1

x

x

x

z

przy ograniczeniach:

0

2

2

2

2

2

2

1

2

1

2

1

2

1

















x

x

III

x

x

II

x

x

I

x

x

,

)

(

)

(

)

(

E. Michlowicz: Badania operacyjne – Programowanie liniowe (1)

8

Rysunek 5

przedstawia geometryczną interpretację rozwiązania przypadku. Zbiór

rozwiązań dopuszczalnych jest pusty (X=



).

Układ warunków ograniczających jest

sprzeczny.

X

2

X

1

z(x)

L(x)

(I)

(II)

(III)

Rys.5. Interpretacja geometryczne przypadku zadania sprzecznego

Geometrycznie można rozwiązać również zadanie programowania liniowego

posiadające trzy zmienne decyzyjne.

Obszarem rozwiązań dla takiego zadania będzie wielościan wypukły w

przestrzeni trójwymiarowej R

3

.

W przypadku wystąpienia trzech i więcej zmiennych

decyzyjnych, do rozwiązania zadania stosuje się różnego rodzaju algorytmy ułatwiające
poszukiwanie rozwiązań optymalnych.