Metoda punktów wierzchołkowych

Rozważmy zagadnienie PL w postaci zwyczajnej

.)

.(

.....

2

2

1

1

Min

Max

x

c

x

c

x

c

F

n

n











Przy warunkach

i

n

j

j

ij

r

x

a







1

, gdzie

l

i

...,

,

2

,

1



(a)

i

n

j

j

ij

r

x

a







1

, gdzie

k

l

i

...,

,

1





(b)

i

n

j

j

ij

r

x

a







1

, gdzie

l

k

i

...,

,

1





(c)

oraz

0



j

x

, gdzie

n

j

,...,

2

,

1



.

Wprowadzając zmienne uzupełniające

k

n

n

n

x

x

x







...,

,

,

2

1

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

postaci standardowej

k

n

n

n

n

x

x

x

c

x

c

x

c

F



















0

.....

0

.....

1

2

2

1

1

.)

.(Min

Max



Przy warunkach

i

n

j

j

ij

r

x

a









1

1

, gdzie

m

i

...,

,

1



0



j

x

, gdzie

k

n

j





,...,

2

,

1

.

Współczynniki

ij

a stojące przy zmiennych

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ę

k

s

s

s

...,

,

,

2

1

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

ij

a

postaci standardowej.

4) Rozwiązanie



















r

k

n

k

n

układów równań

utworzonych poprzez przyjęcie wartości zero dla

r

k

n





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.