E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

1

WYKŁAD 2_1

PROGRAMOWANIE LINIOWE

optymalizacja metodą graficzną

1.

Funkcja celu:

f(x) = f(x

1

, x

2

) = c

1

x

1

+c

2

x

2

 max

2.

Ograniczenia:

g

1

(x) = a

1

x

1

+ b

1

x

2

≤ A

g

2

(x) = g

2

(x

1

, x

2

)

g

3

(x) = g

3

(x

1

, x

2

)

g

4

(x) = x

1

≥ 0

g

5

(x) = x

2

≥ 0

Rozwiązanie graficzne w układzie współrzędnych

(x

1

, x

2

)

znaleźć: x

1

i x

2

 f(x) max

Przykład:

Funkcja celu:

f(x) = f(x

1

, x

2

) = 2x

1

+3x

2

 max

Ograniczenia:

g

1

(x) = 2x

1

+ 2x

2

≤ 14

(1)

g

2

(x) = 4x

1

≤ 16

(2)

g

3

(x) = x

1

+ 2x

2

≤ 8

(3)

g

4

(x) = x

1

≥ 0

(4)

g

5

(x) = x

2

≥ 0

(5)

Rozwiązanie: jednoznaczne (4, 2),

x

1

= 4;

x

2

= 2

wartość maksymalna funkcji celu:

z(x) = z(x

1

, x

2

) = 2*4 +3*2 = 14

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

2

ALGORYTM POSTĘPOWANIA

g

4

(x) = x

1

≥ 0

x

1

≥ 0

x

1

x

2

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

3

g

5

(x) = x

2

≥ 0

x

2

≥ 0

x

1

x

2

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

4

Część wspólna: g

4

(x) = x

1

≥ 0 i g

5

(x) = x

2

≥ 0

x

1

≥ 0

x

2

≥ 0

x

1

x

2

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

5

g

1

(x) = a

1

x

1

+ b

1

x

2

≤ A

ax

1

+ b x

2

≤ c

x

1

x

2

g

1

(x

1

, x

2

) ≤ 0

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

6

Część wspólna:

g

1

(x) = a

1

x

1

+ b

1

x

2

≤ A i

g

4

(x) = x

1

≥ 0 i g

5

(x) = x

2

≥ 0

ax

1

+ b x

2

≤ A

x

1

x

2

ax

1

+ b x

2

– A ≤ 0

^ x

1

≥ 0 ^ x

2

≥ 0

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

7

g

2

(x) = g

2

(x

1

, x

2

)

x

1

x

2

g

1

(x

1

, x

2

) ≤ 0

g

2

(x

1

, x

2

) ≤ 0

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

8

g

3

(x) = g

3

(x

1

, x

2

)

g

1

(x

1

, x

2

) ≤ 0

x

1

x

2

g

2

(x

1

, x

2

) ≤ 0

g

3

(x

1

, x

2

) ≤ 0

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

9

Obszar rozwiązań dopuszczalnych

g

1

(x

1

, x

2

) ≤ 0

x

1

x

2

g

2

(x

1

, x

2

) ≤ 0

g

3

(x

1

, x

2

) ≤ 0

OBSZAR

ROZWIĄZAŃ

DOPUSZCZALNYCH

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

10

Funkcja celu

g

1

(x

1

, x

2

) ≤ 0

x

1

x

2

g

2

(x

1

, x

2

) ≤ 0

g

3

(x

1

, x

2

) ≤ 0

OBSZAR

ROZWIĄZAŃ

DOPUSZCZALNYCH

z = f (x

1

, x

2

) = 0

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

11

Funkcja celu, izolinie

g

1

(x

1

, x

2

) ≤ 0

x

1

x

2

g

2

(x

1

, x

2

) ≤ 0

g

3

(x

1

, x

2

) ≤ 0

z = f (x

1

, x

2

) = 0

90

o

z = f (x

1

, x

2

)  max

E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna

12

Rozwiązanie optymalne – jedno, jednoznaczne

A (x

1opt

, x

2opt

)

g

1

(x

1

, x

2

) ≤ 0

x

1

x

2

g

2

(x

1

, x

2

) ≤ 0

g

3

(x

1

, x

2

) ≤ 0

A (x

1opt

, x

2opt

)

z = f (x

1

, x

2

)  max

z = f (x

1

, x

2

) = 0

x

2opt

X

1opt