Metoda punktów wierzchołkowych

Rozważmy zagadnienie PL w postaci zwyczajnej

F  c x  c x  .....  c x  Max.( Min.) 1 1

2

2

n

n

Przy warunkach

n

 a x  r , gdzie i  , 1

,

2 ..., l (a)

ij

j

i

j 1

n

 a x  r , gdzie i  l  , 1 ..., k (b)

ij

j

i

j 1

n

 a x  r , gdzie i  k  , 1 ..., l (c)

ij

j

i

j 1

oraz

x  0 , gdzie j  , 1

,...,

2

n.

j

Wprowadzając zmienne uzupełniające

x

, x

,

x

n

...,

1

n 2

n k

przekształca się postać zwyczajną zagadnienia PL do

postaci standardowej

F  c x  c x  .....  c x  0 x

 ..... 0 x

1 1

2

2

n

n

n



1

n k

 Ma .(

x Min.)

Przy warunkach

n1

 a x  r , gdzie i  , 1 ..., m

ij

j

i

j 1

x  0 , gdzie j  , 1

,...,

2

n  k .

j

Współczynniki a stojące przy zmiennych

ij

uzupełniających są równe:

1 gdy nierówności są postaci (a)

-1 gdy nierówności są postaci (b) Często zmienne uzupełniające oznacza się

s , s , ..., s

1

2

k

nazywając je zmiennymi:

niedoboru dla warunków (a)

nadmiaru dla warunków (b)

Metoda punktów wierzchołkowych

Etapy metody punktów wierzchołkowych: 1) Utworzenie modelu matematycznego.

2) Przekształcenie modelu do postaci standardowej.

3) Określenie rzędu r macierzy współczynników a

ij

postaci standardowej.

 n  k 

4) Rozwiązanie 

 układów równań

 n  k  r 

utworzonych poprzez przyjęcie wartości zero dla

n  k  r zmiennych.

5) Obliczenie wartości funkcji celu w wyznaczonych punktach spełniających warunki nieujemności.

6) Wybór punktu realizującego żądane ekstremum funkcji celu.