3w to proglin 2011

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Zadanie programowania liniowego PL dla ograniczeń mniejszościowych

przy ograniczeniach

:

( )

x

c

x

T

X

x

f

=

max

0

x

b

x

A

dim x=n, dim c=n, dim A =[m x n], dim b

1

=m

1

,

Postać kanoniczna zadania PL

x

c

T

X

x

x =

0

max

{

}

0

,

:

=

=

x

b

Ax

x

X

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Równoważność zadań programowania matematycznego

I Ograniczenie równościowe można
zastąpić dwoma ograniczeniami nierów-

ściowymi

0

)

(

=

±

+ j

n

i

x

x

g

II Ograniczenie nierównościowe można
zastąpić ograniczeniem równościowym ,
wprowadzając zmienną uzupełniającą

III Zmienną wolną można przedstawić
jako różnicę dwóch zmiennych nieujemnych

=

)

(

0

)

(

0

)

(

0

)

(

x

g

x

g

x

g

x

g

i

i

i

i

0

+ j

n

x

R

x

i

+

=

i

i

i

x

x

x

gdzie:

0

,

0

+

i

i

x

x

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Przykład zadania programowania liniowego

2

1

0

1

2

max

x

x

X

x

+

=

x

+

+

+

=

0

,

21

2

6

0

5

:

2

1

2

1

2

1

x

x

x

x

x

x

x

x

X

5

4

3

2

1

0

0

0

0

1

2

max

x

x

x

x

x

X

x

+

+

+

+

=

x

Postać kanoniczna zadania PL – wprowadzenie zmiennych uzupełniających dla układu m równań
liniowych.

•Liczba zmiennych n=2,

•Liczba ograniczeń m=3.

=

+

+

+

+

=

+

+

+

+

=

+

+

+

+

=

21

0

0

2

6

0

0

0

5

0

0

:

5

2

1

4

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

X

Kolumny odpowiadające jednostkowej macierzy bazowej B

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Postać kanoniczna macierzowa zadania PL

2

1

0

1

2

max

x

x

X

x

+

=

x

+

+

+

=

0

,

21

2

6

0

5

:

2

1

2

1

2

1

x

x

x

x

x

x

x

x

X

{

}

0

,

:

=

=

x

b

Ax

x

X

•Liczba zmiennych n=5,

•Liczba ograniczeń m=3.

Kolumny odpowiadające jednostkowej macierzy bazowej B x

3

, x

4

, x

5

x

c

T

X

x

x =

0

max

]

0

,

0

,

0

,

1

,

2

[

]

,

,

,

,

[

5

4

3

2

1

=

=

T

T

c

c

c

c

c

c

T

T

x

x

x

x

x

x

]

,

,

,

,

[

5

4

3

2

1

=

=

1

0

0

2

6

0

1

0

1

1

0

0

1

1

1

A

=

21

0

5

b

0

5

4

3

2

1

=

x

x

x

x

x

x

5

4

3

2

1

x

x

x

x

x

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Podstawowe definicje

Jeśli dla układu równań liniowych Ax=b spełniony jest warunek rz[A

r

]=rz[A]

to mogą zaistnieć trzy następujące przypadki:

1.

rz[A] = m = n istnieje jedno rozwiązanie układu Ax=b.

2.

rz[A] = n < m istnieje jedno rozwiązanie układu równań, lecz przy tym

(m - n) równań jest zbędnych.

3. rz[A] = m < n istnieje nieskończenie wiele rozwiązań układu Ax=b , jest to

układ nieoznaczony.

Definicja 4.1 macierzy bazowej B

Macierzą bazową B układu równań Ax = b rz[A] = m, n>m nazywamy nieosobliwą
macierz kwadratową o wymiarach (m*m) utworzoną z liniowo-niezależnych kolumn a

j

macierzy A.

Definicja 4.2 rozwiązania bazowego

Rozwiązaniem bazowym układu równań Ax=b rz[A]=m, n>m nazywamy wektor

x

b

=B

-1

b utworzony ze zmiennych odpowiadających kolumnom a

j

macierzy bazowej B.

Składowe wektora bazowego x

b

są to zmienne bazowe.

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Rozwiązania bazowe

]

,

[

N

B

A =

m

B

B

=

dim

,

0

det

]

,

[

N

B

x

x

x =

Definicja 4.3

Rozwiązanie bazowe jest rozwiązaniem bazowym dopuszczalnym zadania programowania
liniowego PL

jeśli wektor x

B

jest nieujemny tzn.

Wówczas rozwiązanie bazowe dopuszczalne posiada nie więcej niż m dodatnich x

i

.

Definicja 4.4

Niezdegenerowanym rozwiązaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe x

i

są większe od zera.

0

B

x

B- macierz bazowa nieosobliwa

N- macierz niebazowa

- wektor zmiennych bazowych odpowiadających kolumnom macierz B
- wektor zmiennych niebazowych odpowiadających kolumnom macierz N

N

B

x

x

0

]

0

,

[

1

=

=

=

N

B

B

x

b

B

x

x

x

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Extremum zadania programowania liniowego PL

Twierdzenie 4.1

Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.

Definicja 4.5

Punkt x należący do wypukłego zbioru jest punktem wierzchołkowym zbioru
X, jeśli nie może być wyrażony jako kombinacja liniowa innych punktów zbioru X.

n

R

X

Twierdzenie 4.2

Rozwiązanie dopuszczalne x zadania programowania liniowego PL jest punktem
wierzchołkowym zbioru rozwiązań dopuszczalnych X wtedy i tylko wtedy gdy
odpowiada mu bazowe rozwiązanie dopuszczalne tzn.:

T

B

x

x

]

0

,

[

=

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Extremum zadania programowania liniowego PL cd.

1

:

R

X

f

Twierdzenie 4.3

Jeżeli funkcja , określona na domkniętym i ograniczonym wypukłym
zbiorze , jest ciągła i wypukła, to globalne maximum funkcji f(x) występuje w
punkcie ekstremalnym (bądź punktach) zbioru X.

n

R

X

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Extremum zadania programowania liniowego PL

cd.

p

x

x

x

.....

,

2

1

Twierdzenie 4.4

1.

Funkcja celu zadania PL przyjmuje wartość maksymalną w punkcie
wierzchołkowym zbioru rozwiązań dopuszczalnych zadania PL.

2. Jeśli funkcja celu zadania PL przyjmuje wartość maksymalną w więcej niż jednym

punkcie wierzchołkowym, to ma tą samą wartość dla każdej kombinacji wypukłej
tych punktów.

Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.

Zbiór rozwiązań optymalnych przyjmuje postać:

1

,...,

1

,

0

,

1

1

=

=

=

=

=

p

i

i

i

p

i

i

i

p

i

x

X

λ

λ

λ


Wyszukiwarka

Podobne podstrony:
5w to przypadki 2011
1w to wprowadzenie 2011
6w to dpl 2011
3w to wlasnosci
6 sposobów na to, PITY 2011, Informacje o podatkach, dokumenty
7w to wlasnosci 2011
4w to simpleks 2011
2w to przyklady 2011
5w to przypadki 2011

więcej podobnych podstron